Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

arXiv:2610.13871 · cs.LG · Submitted 2026-10-09 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking".

Jane: As a fastidious and diligent researcher,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at this paper called Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking. Basically, it tackles those optimization problems where you can only get part of the gradient and have to guess the rest from function evaluations.

Jane: Right, so when someone asks that, they mean we don't have the whole gradient vector grad F(x), and we only know some of it directly from sampling.

Lu: The core idea here is to split that true gradient into two parts, g K(x) which you can sample directly, and g U(x) which is the unknown part you have to infer.

Meng: So what's the big claim? Is it just a new way to estimate grad F(x) ?

Tom: It's more than that. they introduce tracking a residual vector, defined as v(x) which is grad F(x) minus some scaled version of the known gradient component, g K(x).

Jane: And they use those available gradient components to center each of their zeroth-order observations around an estimate of this residual vector.

Lu: That centering strategy is what turns the whole process into something called an error feedback contraction, which means the noise from random probing depends on how well you're tracking that residual instead of just how big the unknown part g U(x) is.

Meng: So it's making the probing less noisy if we track this residual correctly? What does that mean for deployment?

Tom: It leads to a randomized fixed-point iteration with an explicit contraction mechanism, which gives a principled way to look at momentum in this context.

Jane: The convergence analysis they present is pretty strong, even under pretty general assumptions for smooth nonconvex objectives.

Lu: They don't need any uniform bound on the unavailable gradient component g U(x), and they don't require things like bounded gradients or convexity or Polyhedral Lipschitz conditions.

Meng: That sounds powerful because those conditions are usually a headache to satisfy in real-world setups, right?

Tom: Exactly. And the convergence rates they achieve match established benchmarks, reaching O(d two epsilon-six) under Lipschitz gradients and O(d two epsilon-five) under an additional Lipschitz-Hessian assumption.

Jane: That's a solid number for function evaluation complexity, but it also shows how efficient they are in terms of the probes needed.

Lu: They show these strong rates can be reached using minimal probes: one probe direction, two function samples, and one known-component sample per update.

Paper summary: Meng: So if I'm running a model on real traffic data, that means I only need a few evaluations per step instead of needing lots of probing directions?

Tom: And they give you a prescription for the hyperparameters too. They assign specific roles to momentum rho, second momentum rho K, and the control variate weight gamma.

Jane: The parameter gamma is interesting because it's what interpolates between treating things as black-box and white-box treatment.

Lu: They show PISO performs best when the ratio of L v over L is greater than the sum of the variances from both gradient components, which suggests it works best when that opaque component varies slowly along the trajectory.

Meng: Okay, so if I'm dealing with a system where some parts are very stable and others jump around wildly, this parameter gamma helps me tune how I treat the unknown part.

Tom: And they give you a formula for the total function evaluation cost N, which looks like O(v L two sigma 2F two chi one epsilon-six + n F n K times gamma cubed L K sigma two K F epsilon-four + R lo).

Jane: That formula is a bit dense, but the important part for me is that the leading terms are independent of n F, which is the number of function evaluations.

Meng: So if I increase my function evaluations, n F, does it actually help reduce my total cost?

Tom: No, the leading terms don't depend on n F or n K, carrying no sigma K. That's a key trade-off they detail.

Jane: And they also talk about deployment cost based on batch sizes. Enlarging batches up to a threshold beta one is free in terms of function evaluations but reduces the deployment count by epsilon-four.

Lu: And further batch enlargement, beyond that threshold beta two removes another factor of d from the deployment count, but you have to do one more observation for that <ref:2610.13871#pg1>.

Tom: So it’s a trade-off between how much you probe and how many times you send data to the actual system.

Jane: They tested this framework across five different settings: multiproduct pricing, performative prediction, an eight times eight gridworld for reinforcement learning, and bilevel games.

Lu: The results show PISO variants are generally better than baselines with comparable oracle access in three of those settings.

Paper summary: Meng: And in the bilevel games specifically, it matches the strongest baseline at convergence on a routing game while reaching it earlier.

Tom: In performative reinforcement learning, PISO performs best among methods that query the environment rather than just differentiating a model of it.

Jane: So what does this mean for someone who only listens to the show? It means if you're doing complex optimization problems where you can't get the full gradient, this method gives you a concrete way to manage that uncertainty with minimal probing.

Lu: The paper’s main contributions are formalizing the problem as residual identification, which proved that centering zeroth-order observations on a running estimate turns gradient estimation into an error feedback contraction.

Meng: And the second thing is unifying the convergence analysis, giving you those strong rates without needing bounds on g U(x).

Tom: And third, they gave you a prescription for tuning the momentum rho, second momentum rho K, and that control variate weight gamma.

Jane: So to sum up, this paper presents PISO as a theoretically sound technique that uses the structure of gradient decomposition to get state-of-the-art performance in complex black-box environments.

Lu: It’s a framework for when you're dealing with systems where you can only see partial gradient information.

Meng: It seems like it moves this from a theoretical concept into something that actually has some knobs you can tune for deployment.

Tom: Yeah, it's definitely more than just theory now. and the next thing is what we take away from the title of Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking.

Jane: That title tells us exactly how they are doing it: they are tracking that residual vector using zeroth-order information to optimize partially informed stochastic problems.

Lu: It highlights that the key mechanism is this specific residual tracking, which is what makes the whole method work in these difficult scenarios.

Meng: So for someone who only listens, it’s about taking what you can sample and intelligently combining it with a running estimate to estimate the missing pieces of information needed for optimization.

Tom: It’s about managing uncertainty by making the error in your estimation depend on how well you track that specific residual vector.

Jane: So, this paper gives us a concrete tool for tackling optimization problems where direct gradient access is missing by focusing on tracking that residual vector using function evaluations.

Conclusion: Tom: So we’ve been walking through how this paper works, and now we gotta wrap up what this actually means for optimization problems where you don't have the whole gradient.

Jane: Right, so we’re talking about "Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking," and the authors are doing something pretty clever with how they look at missing information.

Tom: It sounds technical, but basically, they found a way to use what you *can* sample—those function evaluations—to estimate the parts of the gradient you *can't* see.

Jane: Exactly. The core idea is tracking this residual vector, which they call v(x), using that known part of the gradient component, g K(x). It turns estimating that missing piece into something called an error feedback contraction.

Tom: That means the noise from your random probing doesn't just depend on how big the unknown part is; it depends on how well you're tracking this residual vector.

Jane: And they show that this setup leads to some really strong convergence guarantees, even for smooth non-convex objectives, without needing those super strict assumptions we usually have to satisfy.

Tom: The numbers are what stick with me—they match state-of-the-art rates like O(d two epsilon-six) under Lipschitz gradients. That’s a lot of performance compared to what you see in some of the older black-box methods.

Jane: And they show that these strong rates can be achieved with minimal probes—just one probe direction and two function samples per update, which is way better than needing many more directions.

Tom: So for someone who just listens, this means when you're stuck on a hard optimization problem where you only get partial gradient info, there’s a structured way to manage that uncertainty without drowning in thousands of probes.

Jane: It’s about taking what you can sample and intelligently combining it with a running estimate to fill in the gaps, specifically through that residual tracking mechanism.

Tom: The authors give you a prescription for tuning things like momentum rho and that control variate weight gamma, which helps you decide when to treat the system more like a black box versus something more white box.

Jane: That's a big deal because it moves it from just being an idea to being something you can actually tune for deployment.

Tom: It’s about managing uncertainty by making the error in your estimation depend on how well you track that specific residual vector, which is a very principled way to do it.

Jane: So this paper gives us a concrete tool for tackling optimization problems where direct gradient access is missing by focusing on tracking that residual vector using function evaluations.

Tom: But they’re not claiming it solves every single problem; the complexity analysis shows how the total number of function evaluations scales, and there are still trade-offs involving batch sizes.

Jane: And that’s a fair point—it’s about understanding the cost to run this method in the real world versus how much performance you get.

Tom: We’ve covered the mechanics and the numbers; next we gotta look at what this actually changes for AI applications when you can't see inside a model.

El Mahdi Chayti, Alireza Mirrokni, Martin Jaggi

Machine Learning and Optimization Laboratory (MLO) at EPFL

cs.LG

Submitted: 2026-10-09

Updated: 2026-10-09

Code: https://github.com/alirezamirrokni/PISO

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: As a fastidious and diligent researcher, I have meticulously cross-referenced the provided text excerpts from both documents (A and B) concerning "Partially Informed Stochastic Optimization (PISO)"

Key concepts

Residual Identification: The core idea is to split the true gradient into two parts: one that can be calculated directly from samples and another that is unknown. PISO focuses on identifying this unknown part, which is represented by a 'residual' vector. By tracking this residual, the method learns how to correct its estimates iteratively.
Error-Feedback Contraction: This describes the mechanism where function evaluations are used not just to estimate the gradient directly, but specifically to reduce the error in tracking that residual vector. Instead of relying solely on random probing, PISO uses this feedback loop to make each update more accurate, leading to faster convergence.

Summary

As a fastidious and diligent researcher, I have meticulously cross-referenced the provided text excerpts from both documents (A and B) concerning Partially Informed Stochastic Optimization (PISO) to construct a comprehensive, detailed summary of the paper's methodology, contributions, complexity analysis, and experimental setup.

Here is the detailed synthesis:

Comprehensive Research Summary: Partially Informed Stochastic Optimization (PISO)

This research introduces Partially Informed Stochastic Optimization (PISO) as a novel framework designed to tackle optimization problems where direct access to the full gradient grad F(x) is unavailable, necessitating inference from function evaluations. This structure is prevalent in challenging domains such as performative prediction, performative reinforcement learning, and bilevel optimization involving a black-box lower level.

Core Methodology: Residual Identification and Error Feedback Contraction

The fundamental insight of PISO lies in decomposing the true gradient into two components:

grad F(x) = g K(x) + g U(x)

where g K(x) is the component estimable through direct sampling (the known component), and g U(x) is the intractable, unknown component.

PISO addresses this by tracking a residual vector, defined as:

v(x):= grad F(x) - gamma g K(x)

where gamma is a control parameter interpolating between black-box and white-box treatment. The method's core mechanism is to use the available gradient component (g K) to center each zeroth-order observation around an estimate of this residual, v(x). This centering strategy transforms the gradient estimation process into an error-feedback contraction, where the variance introduced by random probing depends on the tracking error of the residual rather than solely on the magnitude of the intractable component (g U).

The update mechanism is formulated as a randomized fixed-point iteration that exhibits an explicit contraction mechanism, providing a principled interpretation of momentum.

Theoretical Guarantees and Convergence Analysis

The theoretical analysis establishes strong convergence guarantees under remarkably general assumptions, significantly relaxing constraints typically required for gradient-based methods:

Generality of Assumptions: The analysis is robust for smooth nonconvex objectives. Crucially, it does not require a uniform bound on the unavailable gradient component (|g U|), nor does it mandate assumptions like bounded gradients, bounded domains, convexity, or Polyhedral Lipschitz (PL) conditions.
Convergence Dependence: The convergence guarantees are governed by the smoothness constant L v of the residual v(x) and the initial magnitude of the residual |v(x 0)|.
Matching State-of-the-Art Rates: PISO achieves leading function-evaluation complexities that match established benchmarks, specifically reaching ** O(d 2 epsilon-6) ** under Lipschitz gradients and ** O(d 2 epsilon-5) ** under an additional Lipschitz-Hessian assumption. These rates are comparable to those achieved by methods like Hikima & Takeda (2025a).
Efficiency in Probes: The analysis demonstrates that these strong rates can be attained using minimal probes: one probe direction, two function samples, and one known-component sample per update.

Parameter Prescription and Momentum Interpretation

The paper provides a detailed prescription for the method's hyperparameters, assigning a specific role to each parameter:

Momentum (rho): This acts as the step size of the sketch iteration and has a stability window width of 2/cd. The analysis shows rho must scale with the dimension d, implying rho=0 is not a special case but corresponds to an expanding map.
Second Momentum (rho K): This momentum component, applied to the known component (g K), is what makes the use of only one sample per iteration admissible.
Control Variate Weight (gamma): This parameter interpolates between black-box and white-box treatment. The analysis shows PISO performs best when the ratio L v/L < sigma 2 g sigma 2 g + gamma 2 sigma 2 K, indicating superior performance over standard black-box methods when the opaque component varies slowly along the trajectory.

Complexity and Deployment Trade-offs

The complexity analysis meticulously details the trade-off between observation cost and deployment cost:

Function Evaluation Cost (N): The total number of function evaluations N is derived based on probe distribution and oracle regime, given by:

N = O(v L 2 sigma 2F 2 chi 1 epsilon-6 + n F n K times gamma cubed L K sigma 2 K F epsilon-4 + R lo)

Crucially, the leading terms are independent of n F (number of function evaluations) and n K (number of known samples), carrying no sigma K.

Deployment Cost: The analysis quantifies deployment cost based on batch sizes. Enlarging batches up to a threshold (beta 1) is free in terms of function evaluations but reduces the deployment count by epsilon-4 (from (d 2 epsilon-6) to (d 2 epsilon-2)). Further batch enlargement (beta 2) removes another factor of d from the deployment count at the cost of one additional observation.

Experimental Validation and Superiority

PISO was rigorously evaluated across five distinct settings: multiproduct pricing, strategic classification (performative prediction), an 8x8 gridworld (performative RL), and bilevel games. The results consistently demonstrate PISO's efficacy:

Performance: PISO variants are generally superior to baselines with comparable oracle access in three of the tested settings.
Bilevel Games: It matches the strongest bilevel baseline at convergence on a routing game while reaching it earlier.
Performative RL: PISO performs best among methods that query the environment rather than differentiating a model of it.

Summary of Key Contributions

The paper's primary contributions are threefold:

Formal Formulation: They successfully formulated the optimization problem under the condition (1) as residual identification, leading to the derivation of PISO and PISO2, proving that centering zeroth-order observations on a running estimate turns gradient estimation into an error-feedback contraction.
Unified Convergence Analysis: They provided a single, powerful convergence analysis whose complexity is governed by L v and |v(x 0)|, entirely independent of requiring uniform bounds on the unavailable gradient component (|g U|). This analysis matches leading rates while requiring only one probe per update instead of (d).
Parameter Guidance: They provided a prescriptive roadmap for tuning the method, assigning specific roles to momentum (rho), second momentum (rho K), and the control variate weight (gamma).

In conclusion, PISO is a highly efficient, theoretically sound optimization technique that leverages structural properties of gradient decomposition to achieve state-of-the-art performance in complex, black-box environments by intelligently managing the uncertainty inherent in partially informed data.

Improvements for AI systems

A Partially Informed Stochastic Optimization (PISO) algorithm can be implemented to optimize functions where only a part of the gradient is directly accessible, such as in performative prediction or reinforcement learning, by combining the available gradient component with a running estimate of the residual. This allows for convergence guarantees without requiring a uniform bound on the unavailable gradient component.
The PISO framework enables an explicit contraction mechanism and provides a principled interpretation of momentum, allowing optimization methods to be structured as a randomized sketch iteration with an explicit contraction mechanism. This yields convergence rates of O(d squared ε-6) under Lipschitz gradients and O(d squared ε-5) under an additional Lipschitz-Hessian assumption.
The system can adapt its optimization strategy based on the oracle access regime (Regime A, B, or C), with specific prescriptions for momentum parameters like the mixing weight λ and the known-component momentum ρK. For instance, in Regime B (independent randomization), choosing a single known-component sample per iteration suffices, which is admissible under certain conditions.
The optimization can dynamically balance the trade-off between observation cost and deployment count by adjusting batch sizes (nF and nK). Specifically, increasing the batches up to a cap β1 allows for a reduction in the deployment count from Θ(d squared ε-6) to Θ(d squared ε-2) at no cost in total observations.
The system can leverage per-step drift-minimizing weight selection (γ⋆k = 1 + B/C), where γ is a control-variate coefficient built from uncentred second moments, to minimize the per-step drift Ek∥vk+1 − vk∥ squared. This allows the optimization to adapt its focus between tracking the full gradient and tracking only the opaque component.
The system can utilize different probe distributions (Gaussian, Sphere, or Coordinate probes) depending on the problem structure. For example, coordinate probes are noted for their direct bias bounds, while Gaussian and Sphere families satisfy a smoothing identity that yields favorable complexity constants like χ1 = √d and χ2 = d.
The system can manage the trade-off between deployment cost and observation count based on the chosen operating point (β1 or β2). For instance, at β1, deployments are Θ(d squared ε-2) while observations are Θ(d squared ε-6), representing a balance where deployments are 3T = Θ(∆v/(βε2)).
The system can employ a warm-start strategy for the known-component state (h0), such as the single-sample warm start, h0 = gbK(x0), which reduces the required iteration count by addressing initialization terms that otherwise cost resources like nK samples.

Abstract

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