Track trials, findings, and clinical evidence as it lands.
Search papers, labs, and topics across Lattice.
We introduce Partially Informed Stochastic Optimization (PISO), a novel algorithm for optimization problems where only a partial gradient is directly accessible and the remainder must be estimated via function evaluations. PISO combines the known gradient with a running estimate of the residual, centering zeroth-order observations on this estimate to reduce variance. This approach yields improved function-evaluation complexities of \(O(d^{2}\varepsilon^{-6})\) and \(O(d^{2}\varepsilon^{-5})\) under Lipschitz and Lipschitz-Hessian assumptions, respectively, and demonstrates empirical gains across several optimization tasks.
A new optimization framework, PISO, achieves state-of-the-art function-evaluation complexities for partially informed gradients by cleverly tracking and centering on the unknown residual.
Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of \(O(d^{2}\varepsilon^{-6})\) under Lipschitz gradients and \(O(d^{2}\varepsilon^{-5})\) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.