# Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

arXiv: https://arxiv.org/abs/2610.13871 · HTML: https://mlsanity.com/paper/2610.13871/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 9 Oct 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 33)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [Performative Prediction with Neural Networks](https://mlsanity.com/paper/2304.06879/) (2023)
- [Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments](https://mlsanity.com/paper/2204.08281/) (2022)
- [How to Learn when Data Gradually Reacts to Your Model](https://mlsanity.com/paper/2112.07042/) (2021)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Plug-in Performative Optimization](https://mlsanity.com/paper/2305.18728/) (2023)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [Optimization with Access to Auxiliary Information](https://mlsanity.com/paper/2206.00395/) (2022)
- [Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss](https://mlsanity.com/paper/2405.17922/) (2024)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data](https://mlsanity.com/paper/2310.05792/) (2023)
- [Optimal Classification under Performative Distribution Shift](https://mlsanity.com/paper/2411.02023/) (2024)
- [Performative Reinforcement Learning with Linear Markov Decision Process](https://mlsanity.com/paper/2411.05234/) (2024)
- [Performative Policy Gradient: Optimality in Performative Reinforcement Learning](https://mlsanity.com/paper/2512.20576/) (2025)
- [Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions](https://mlsanity.com/paper/2412.20330/) (2024)
- [Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs](https://mlsanity.com/paper/2104.08406/) (2021)
- [Zeroth-order gradient estimators for stochastic problems with decision-dependent distributions](https://mlsanity.com/paper/2510.24929/) (2025)
- [On the computation of equilibria in monotone and potential stochastic hierarchical games](https://mlsanity.com/paper/2104.07860/) (2021)

## Abstract (arXiv)

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(d2varepsilon-6)) under Lipschitz gradients and (O(d2varepsilon-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.