Optimization problems in machine learning often expose only a portion of the gradient directly, requiring the remaining component to be inferred from function evaluations. This structure appears across performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. When the unavailable gradient component is large or poorly bounded, methods that assume full gradient knowledge can stall or produce unreliable iterates.
Limitations of Gradient-Full Assumptions in Stochastic Optimization
Many existing stochastic methods require a uniform bound on the unavailable gradient component or rely on response-model derivatives that may not exist. These assumptions limit applicability in settings where only partial gradient information is accessible, or where function evaluations are cheaper than gradient queries. Prior work has addressed partial gradients in specific contexts, but a unified treatment that works across performative, reinforcement, and bilevel settings has been lacking.
Partially Informed Stochastic Optimization (PISO)
PISO combines the available gradient component with a running estimate of the residual. Each zeroth-order observation is centred on this residual estimate, which causes the variance due to random probing to depend on the tracking error rather than the residual's magnitude. This design choice yields a randomized sketch iteration with an explicit contraction mechanism and provides a principled interpretation of momentum without adding overhead from extra gradient queries.
Convergence Without Uniform Gradient Bounds
For smooth nonconvex objectives, PISO establishes convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. This relaxation means the method can operate effectively even when the unobserved gradient component grows or shifts over the course of optimization, as long as its variation remains controlled.
Function-Evaluation Complexity Under Lipschitz Assumptions
With independently sampled function evaluations and Gaussian or spherical probes, PISO achieves O(d²ε⁻⁶) function-evaluation complexity under Lipschitz gradients. Under an additional Lipschitz-Hessian assumption, the complexity improves to O(d²ε⁻⁵). These rates require only one probe direction, two function samples, and one known-component sample per update, making the per-iteration cost minimal compared to methods that require multiple gradient or Hessian queries.
Batching Trade-Offs for Deployment Efficiency
The analysis quantifies how batching observations trades function evaluations for fewer deployments. In settings where function evaluations are expensive or subject to rate limits, batching can reduce the number of environment interactions while modestly increasing the number of iterations needed to reach a target accuracy. This trade-off lets practitioners tailor the method to the cost structure of their specific problem.
Empirical Performance Across Optimization Settings
Across five representative settings, PISO variants improve on tested baselines with comparable oracle access in three cases, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning. The methods without response-model derivatives typically rely on finite-difference or sample-based approximations, which can be high-variance; PISO's centred residual tracking provides a more stable alternative.
Practical Integration and Design Considerations
PISO can be incorporated into existing optimization loops with three ingredients: the available gradient component, the ability to sample function values, and a probe direction (Gaussian or spherical). The running residual estimate can be maintained as a simple exponential moving average of past tracking errors. Because the method does not require Hessian information or uniform gradient bounds, it is suitable for high-dimensional problems where second-order methods are infeasible and for applications where only function evaluations are readily available.
As optimization problems grow more complex and involve only partial gradient access, methods that can operate reliably without full gradient information become increasingly valuable. PISO demonstrates that a simple centred-residual mechanism can yield principled convergence guarantees and improved empirical performance across a range of settings. Future work might explore adaptive probe scheduling, variance-reduced extensions, or integration with second-order information when available. Read the paper on arXiv