acceptodds
Under review as a conference paper at ICLR 2027

Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

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^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.

Primary area:
optimization
Keywords:
Performative prediction, RL, zeroth-order optimization, momentum

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_KqbmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers stochastic nonconvex optimization of F:Rd→RF:\mathbb R^d\to\mathbb R whose gradient splits as ∇F=gK+gU\nabla F=g_K+g_U, where gKg_K can be sampled directly and gUg_U is accessible only through noisy function values; performative prediction, performative reinforcement learning and bilevel problems with a black-box lower level are the motivating examples. The proposed method, PISO, keeps a state mkm_k that tracks the residual v(x)=∇F(x)−γgK(x)v(x)=\nabla F(x)-\gamma g_K(x) and centers each two-point zeroth-order observation on this state, so that the probing variance scales with the tracking error ∥mk−v(xk)∥\|m_k-v(x_k)\| rather than with ∥v(xk)∥\|v(x_k)\|. A second state averages the noisy known component, and γ\gamma acts as a control-variate weight. With exact oracles and a fixed iterate, the tracking error follows the randomized sketch recursion Ek+1=(I−βPk)EkE_{k+1}=(I-\beta P_k)E_k, which contracts in mean square for 0<β<2/cd0<\beta<2/c_d.

Critical strengths
  1. One algorithm and one analysis for three application areas. The decomposition ∇F=gK+gU\nabla F=g_K+g_U covers performative prediction, performative reinforcement learning and bilevel problems with an opaque lower level. The analysis avoids bounded-gradient, bounded-domain, convexity and PL assumptions, uses one probe and one sample of each oracle per update, and separates the cost of deploying a decision from that of observing its outcome, which matters in performative settings.

  2. Broad experiments with code. The paper evaluates five settings from the three motivating areas, with ablations for each design choice and an anonymized code repository. The momentum sweep confirms the window predicted by the sketch interpretation: the best momentum is near 1−1/cd1-1/c_d, and the method diverges below 1−2/cd1-2/c_d.

Critical weaknesses
  1. The central mechanism is known, and the gain over prior work is conditional. SEGA (Hanzely, Mishchenko and Richtárik, NeurIPS 2018) builds a gradient estimate from random sketches with the same two ingredients as PISO: a memory updated by sketch-and-project and an unbiased readout. With spherical probes and the value β=1/cd=1/d\beta=1/c_d=1/d that the paper identifies as optimal (Lemma 5), the noiseless PISO update mk+1=mk+βPk(v−mk)m_{k+1}=m_k+\beta P_k(v-m_k) is exactly SEGA's sketch-and-project step applied to the residual, and the readout mk+Pk(v−mk)m_k+P_k(v-m_k) is SEGA's unbiased estimate. In the zeroth-order setting, JAGUAR (Veprikov, Bogdanov, Minashkin and Beznosikov, 2024) keeps the same memory with coordinate probes, refreshing one coordinate per iteration by a central finite difference, and its stochastic version evaluates the two points with independent samples; this is PISO with coordinate probes and β=1/d\beta=1/d in the independent-noise regime. Neither work is cited. What remains new is the application to the residual ∇F−γgK\nabla F-\gamma g_K, the analysis of the relaxation β\beta under independent noise and the accounting of deployments.

The advertised rates match those of Hikima & Takeda (2025a), with LL replaced by LvL_v and one probe per update instead of Ω(d)\Omega(d). However, LvL_v is defined along the method's own trajectory (Assumption 1), the step size needs an a-priori bound on it, and the default bound L+γLKL+\gamma L_K exceeds LL; the improvement in the constant is therefore realized only when a small bound on LvL_v is known in advance. Finally, Corollary 3 assumes ε2≤7γ2σK2/(dnK)\varepsilon^2\le7\gamma^2\sigma_K^2/(dn_K), and a similar condition under a Lipschitz Hessian; neither can hold when σK=0\sigma_K=0, that is, when the known component is exact, as in the Stackelberg problems of the bilevel experiments.

  1. The main results are not presented readably, and the appendices contradict each other.** The abstract states complexities O(d2ε−6)O(d^2\varepsilon^{-6}) and O(d2ε−5)O(d^2\varepsilon^{-5}) without saying what dd and ε\varepsilon are or which stationarity measure is meant. Theorem 2, labeled "Main", is a master inequality that breaks over four display lines, with about twenty symbols, three momentum parameters (β\beta, β~\tilde\beta, βK\beta_K) together with θ=θ(β~)\theta=\theta(\tilde\beta), a three-way minimum for the step size and more than a dozen numerical coefficients. Several of its quantities (ς\varsigma, σD,k\sigma_{D,k}, Σb,k\Sigma_{b,k}, bˉk\bar b_k, Bˉk\bar B_k) are defined elsewhere, and it states no rate. The rates appear only in Corollary 3, whose parameter choice involves the constants C1=102000 L2σF2ς2χ12C_1=102000\,L^2\sigma_F^2\varsigma^2\chi_1^2 and C2=1220 ς2σF2Qχ2C_2=1220\,\varsigma^2\sigma_F^2Q\chi_2 and two side conditions. The main theorem should be the complexity bound in the main regime, stated in O(⋅)O(\cdot) form with its parameter choice, with the master inequality moved to the appendix.
Questions for authors
  1. How does PISO differ from SEGA and JAGUAR applied to the residual, and which parts of the analysis are new relative to theirs?

  2. In the security game, PISO uses a residual norm cap (Appendix L.2.5) that is not part of Algorithm 1 and is not given to the baselines, and outside performative RL the baselines use the hyperparameters reported in their source papers, while PISO is tuned by a two-stage grid search. Can the authors report the analyzed variant (i.i.d. Gaussian probes, λ=0\lambda=0, no cap) on every task, with the same tuning budget for all methods?

  3. Does Corollary 3 extend to σK=0\sigma_K=0, the case of the bilevel experiments?

5 comments

We thank the reviewer for their time and for a detailed and careful review, including the references to SEGA and JAGUAR and the gap in Corollary 3 for σK=0\sigma_K=0. We address each point below.

SEGA and JAGUAR. We will cite and discuss both papers. We disagree, however, with the conclusion that what remains is an application of a known mechanism: the setting of our paper is different from that of these works, and the differences are what the analysis has to handle.

The setting.

  1. The gradient is split. We minimize FF with ∇F=gK+gU\nabla F=g_K+g_U, where gKg_K is sampled directly and gUg_U is accessible only through function values. SEGA, JAGUAR and its follow-up (Petrov et al., 2025, arXiv) estimate the full gradient of a single objective. The split is what introduces the tracked object v=∇F−γgKv=\nabla F-\gamma g_K, the weight γ\gamma, the second state hh for the sampled component, the term (βKI−β~Pk)δk(\beta_KI-\tilde\beta P_k)\delta_k in the direction error, and the dependence on the smoothness of gUg_U rather than of FF. None of these has an analogue in those papers.
  2. The data distribution depends on the decision. In performative prediction and performative RL, querying FF at xk±μkukx_k\pm\mu_ku_k means deploying two different decisions, whose outcomes are drawn from two different distributions D(xk+μkuk)\mathcal D(x_k+\mu_ku_k) and D(xk−μkuk)\mathcal D(x_k-\mu_ku_k). The two queries therefore cannot share a sample, and the noise of the difference quotient grows as σD2≤σF2/(2μ2nF)\sigma_D^2\le\sigma_F^2/(2\mu^2n_F) when μ→0\mu\to0. This is the regime of our main result (Corollary 3), and it is what forces the balance between bias and variance in the radius. SEGA has no noise. JAGUAR and Petrov et al. draw the randomness from a fixed distribution that does not depend on xx; Petrov et al. evaluate both points at the same sample, which is unavailable in our setting, and JAGUAR's independent-sample case is analysed only for Frank-Wolfe with convex ff on a compact set.
  3. Nonconvex, unconstrained objectives and general probes. SEGA analyses strongly convex composite objectives (Theorem 3.3, with a relaxation of strong convexity for coordinate sketches, Remark 4.4); JAGUAR's nonconvex result (Theorem 3) assumes a deterministic, bounded oracle error. Both JAGUAR papers use coordinate probes only.

The mechanism. As stated in the submission (Section 2, and Related Work: "a sketch-and-project iteration"), the tracking step is an instance of sketch-and-project. With exact oracles it reads mk+1=mk+βPk(v(xk)−mk),Pk=skuk⊤,m_{k+1}=m_k+\beta P_k\big(v(x_k)-m_k\big),\qquad P_k=s_ku_k^\top , a relaxed sketch-and-project step towards v(xk)v(x_k). For sphere probes uk=sk=d wku_k=s_k=\sqrt d\,w_k, βPk=βd wkwk⊤\beta P_k=\beta d\,w_kw_k^\top, which at β=1/d\beta=1/d is the projection wkwk⊤w_kw_k^\top; this is SEGA's update (their eq. (4), B=IB=I, Sk=wkS_k=w_k), and coordinate probes give JAGUAR's. We do not claim the update rule as a contribution, and we will make the connection to SEGA and JAGUAR explicit. Our contribution is what the update is applied to and what we prove about it, in a setting that these works do not cover:

  • What is tracked. Sketch-and-project, SEGA and JAGUAR track the gradient of the objective. PISO tracks the residual v=∇F−γgKv=\nabla F-\gamma g_K of a split gradient, while the sampled component is handled by a separate average hh. This is what makes the method use the known component at all, and it is why the complexity depends on the smoothness of the opaque part rather than of FF.
  • What the tracker observes. In sketch-and-project the sketch ⟨v,uk⟩\langle v,u_k\rangle is exact; in SEGA it is an exact sketch of the gradient. Here it is a finite-difference quotient with a bias and, in the main regime, with noise from two independent samples drawn from two different distributions, of variance σF2/(2μ2nF)\sigma_F^2/(2\mu^2n_F).
  • What the relaxation does. In sketch-and-project for linear systems, the relaxation ω∈(0,2)\omega\in(0,2) is a convergence-speed parameter for a fixed target. Here the target v(xk)v(x_k) moves with the iterate and is observed with noise, so β\beta becomes the parameter that trades contraction against noise damping, and it must decrease with ε\varepsilon. Our stability range β∈(0,2/cd)\beta\in(0,2/c_d) is the classical range ω∈(0,2)\omega\in(0,2), and we will say so; the role of β\beta in the rate is what our theory establishes. The same holds for JAGUAR: it applies SEGA's update to zeroth-order estimates (its stochastic method "use[s] SEGA and momentum parts", Section 2.4 of Veprikov et al.), and its contribution is the analysis of that setting. Ours is the analysis of a different one.

Where the guarantees can be compared, ours are sharper in dd. With independent samples, JAGUAR's guarantee (convex ff, compact set, function value) has a noise term of O(d9/2σf3L3D6ε−6)\mathcal O(d^{9/2}\sigma_f^3L^3D^6\varepsilon^{-6}) iterations (Corollary 4); we obtain O(ΔvL2σF2d2ε−6)\mathcal O(\Delta_vL^2\sigma_F^2d^2\varepsilon^{-6}) function evaluations for nonconvex FF on Rd\mathbb R^d. The criteria differ, but at the same order ε−6\varepsilon^{-6} JAGUAR's dimension dependence is worse by a factor d5/2d^{5/2}, under assumptions we do not need. With a shared sample, the only nonconvex guarantee in this line of work (Petrov et al., for sign-based updates, O(Lδ0d2σ2ε−4)\mathcal O(L\delta_0d^2\sigma^2\varepsilon^{-4}) in the Euclidean criterion) is a factor dd above our O(Δvdσg2ε−4)\mathcal O(\Delta_vd\sigma_g^2\varepsilon^{-4}) (Regime A), where σg2=tr⁡Cov⁡∇f(x;ζ)\sigma_g^2=\operatorname{tr}\operatorname{Cov}\nabla f(x;\zeta) is the same quantity as their σ2\sigma^2.

The gap in the independent-sample regime comes from the treatment of the finite-difference bias. Both JAGUAR papers bound the finite-difference error only through its second moment (Lemma 4 of Veprikov et al.: dL2τ2+8dσf2/τ2+2dσ∇2+2dΔ2/τ2dL^2\tau^2+8d\sigma_f^2/\tau^2+2d\sigma_\nabla^2+2d\Delta^2/\tau^2, reused in the proof of Lemma 1 of Petrov et al.). We separate its mean, which is undamped, from its fluctuation, which is damped by β\beta (Part 2), and this separation is what gives d2d^2.

Finally, the identification of PISO at β=1/d\beta=1/d with JAGUAR's stochastic method does not hold. Our tracking lemma reads Ek∥Ek+1∥2≤(1−β2)∥Ek∥2+54β2(Σmz2+Σb2)+10β∥bˉk∥2+10β3∥Bˉk∥2+5Lv2η2β Ek∥Gk∥2,\mathbb E_k\|E_{k+1}\|^2\le\Big(1-\frac\beta2\Big)\|E_k\|^2+\frac54\beta^2\big(\Sigma_{\rm mz}^2+\Sigma_b^2\big)+10\beta\|\bar b_k\|^2+10\beta^3\|\bar B_k\|^2+\frac{5L_v^2\eta^2}{\beta}\,\mathbb E_k\|G_k\|^2, with Ek=mk−v(xk)E_k=m_k-v(x_k) and Σmz2=cdγ2σK2+ς2σD2\Sigma_{\rm mz}^2=c_d\gamma^2\sigma_K^2+\varsigma^2\sigma_D^2. The noise enters at order β2\beta^2 against a contraction of β/2\beta/2, so its steady-state contribution is 52β(Σmz2+Σb2)\frac52\beta(\Sigma_{\rm mz}^2+\Sigma_b^2), which is not damped at β=1/cd\beta=1/c_d. JAGUAR's tracking lemma (Lemma 5) has exactly this undamped floor, of order d(σf2/τ2+σ∇2)d(\sigma_f^2/\tau^2+\sigma_\nabla^2), and removes it with a second momentum layer, gk+1=(1−ηk)gk+ηkρkg_{k+1}=(1-\eta_k)g_k+\eta_k\rho_k. Our corollaries instead take β=nFε4/C1≪1/cd\beta=n_F\varepsilon^4/C_1\ll1/c_d.

What the analysis adds. Viewing PISO as sketch-and-project applied to the residual, the new elements are the following. (i) A nonconvex, unconstrained analysis for a split gradient with a decision-dependent distribution, so that the two queries use independent samples from different distributions; none of SEGA, JAGUAR or its follow-up treats this setting, and in the shared-sample regime our rate is better by a factor dd than the only nonconvex guarantee in this line of work. (ii) General probe families satisfying (D1)–(D3), covering Gaussian, sphere and coordinate probes in one argument, where all three papers use either exact sketches or coordinate probes. (iii) A separation of the finite-difference bias inside the tracking recursion. The cross term is computed exactly, Ek⟨(I−βPk)Ek,  bksk⟩=⟨Ek,bˉk⟩−β⟨Ek,Bˉk⟩,bˉk=Ek[bksk],Bˉk=Ek[bk∥sk∥2uk],\mathbb E_k\big\langle(I-\beta P_k)E_k,\;b_ks_k\big\rangle=\langle E_k,\bar b_k\rangle-\beta\langle E_k,\bar B_k\rangle,\qquad \bar b_k=\mathbb E_k[b_ks_k],\quad \bar B_k=\mathbb E_k\big[b_k\|s_k\|^2u_k\big], so the mean bˉk\bar b_k enters at order β\beta (undamped after dividing by the contraction β/2\beta/2), while the second moment Σb2=Ek[bk2∥sk∥2]\Sigma_b^2=\mathbb E_k[b_k^2\|s_k\|^2] enters at order β2\beta^2 and is damped like any other noise. With ∥bˉk∥≤Lμd\|\bar b_k\|\le L\mu\sqrt d and Σb2≤94L2μ2d3\Sigma_b^2\le\frac94L^2\mu^2d^3 for Gaussian probes, the radius balance gives ς2χ12=d2\varsigma^2\chi_1^2=d^2; bounding the bias through its second moment alone, as both JAGUAR papers do, would give d4ε−6d^4\varepsilon^{-6} in our analysis. (iv) The known component, for which the direction error is Δk=(1−βK)ζk+(I−β~Pk)Ek+(βKI−β~Pk)δk+β~(bk+ξk)sk,E∥(βKI−β~Pk)δk∥2=(βK2−2βKβ~+cdβ~2) E∥δk∥2,\Delta_k=(1-\beta_K)\zeta_k+(I-\tilde\beta P_k)E_k+(\beta_KI-\tilde\beta P_k)\delta_k+\tilde\beta(b_k+\xi_k)s_k,\qquad \mathbb E\big\|(\beta_KI-\tilde\beta P_k)\delta_k\big\|^2=(\beta_K^2-2\beta_K\tilde\beta+c_d\tilde\beta^2)\,\mathbb E\|\delta_k\|^2, so that, with the average hh (βK<1\beta_K<1), one known-component sample per iteration suffices. (v) The applications: to our knowledge, this is the first use of sketch-and-project tracking in performative prediction, performative RL and bilevel games, and the deployment accounting of Section 3.2 is specific to these settings.

One probe per update versus Ω(d)\Omega(d). The review lists this among the remaining differences with Hikima & Takeda; we would like to stress that it is the difference between a guarantee for the method that is run and a guarantee for a method that cannot be run. Their Theorem 9 prescribes N=d2ε−4N=d^2\varepsilon^{-4} directions per update, that is 9⋅1069\cdot10^6 directions, or 1.8⋅1071.8\cdot10^7 deployed decisions, before a single step at d=30d=30 and ε=0.1\varepsilon=0.1; and even with batching, absorbing the term 54d2N(d+2)E∥∇F∥2\frac{54d^2}{N(d+2)}\mathbb E\|\nabla F\|^2 of their bound requires N>1.5⋅103N>1.5\cdot10^3 at d=30d=30. Their own experiments, with a budget of 50005000 samples, use N∈{1,10,102}N\in\{1,10,10^2\}. Our guarantee holds for one direction per update.

LvL_v and the step size. We agree that the step size is set with an a priori bound Lˉv\bar L_v,

\eta=\min\Big�0�,

and that the leading term then carries LˉvΔF\bar L_v\Delta_F. This is the same requirement as for any first-order or black-box method, whose step size is set with an a priori bound on LL; what changes is that the constant that matters is the smoothness of the opaque part rather than that of FF. Since v=gU+(1−γ)gKv=g_U+(1-\gamma)g_K, any Lipschitz constant LUL_U of gUg_U gives Lˉv≤LU+∣1−γ∣LK\bar L_v\le L_U+|1-\gamma|L_K, which at γ=1\gamma=1 is LUL_U. Without such information, Lˉv=L+γLK\bar L_v=L+\gamma L_K and the leading term is that of a black-box method up to the factor (L+γLK)/L(L+\gamma L_K)/L. The one-probe-per-update property does not depend on any of this. We will state this in the main text.

σK=0\sigma_K=0. Thank you for catching this; it is a statement-level gap, and the rate is unchanged. In Corollary 3, β\beta is subject to three constraints: the radius balance β=nFε4/C1\beta=n_F\varepsilon^4/C_1, the known-oracle constraint 11βcdγ2σK2/nK≤ε2/611\beta c_d\gamma^2\sigma_K^2/n_K\le\varepsilon^2/6, and the moment condition βς62≤χ12\beta\varsigma_6^2\le\chi_1^2, which is β≤1/(9d2)\beta\le1/(9d^2) for Gaussian probes. The condition ε2≤7γ2σK2/(dnK)\varepsilon^2\le7\gamma^2\sigma_K^2/(dn_K) only ensures that the second implies the third at nF=nFmax⁡n_F=n_F^{\max}. When σK=0\sigma_K=0 the second constraint is void, βK=1\beta_K=1 is admissible, and the third is imposed directly through nF≤C1/(9d2ε4)n_F\le C_1/(9d^2\varepsilon^4). Then T=Θ(Δv/(βε2))=Θ(C1Δv/(nFε6))T=\Theta(\Delta_v/(\beta\varepsilon^2))=\Theta(C_1\Delta_v/(n_F\varepsilon^6)) and N=2nFT=Θ(C1Δvε−6)\mathsf N=2n_FT=\Theta(C_1\Delta_v\varepsilon^{-6}), so Corollary 3 covers the bilevel experiments. We will state both cases.

Presentation. We agree. The main theorem will read: under Assumptions 1–3, with Gaussian or sphere probes, nF=nK=1n_F=n_K=1 and the parameter choice of Corollary 3, PISO reaches 1T∑k<TE∥∇F(xk)∥2≤ε2\frac1T\sum_{k<T}\mathbb E\|\nabla F(x_k)\|^2\le\varepsilon^2 after N=O(ΔvL2σF2d2ε−6)\mathsf N=\mathcal O(\Delta_v L^2\sigma_F^2d^2\varepsilon^{-6}) function evaluations, and O(ΔvσF2Qd2ε−5)\mathcal O(\Delta_v\sigma_F^2Qd^2\varepsilon^{-5}) under a QQ-Lipschitz Hessian, plus lower-order terms, with Δv=LˉvΔF+∥v(x0)∥2\Delta_v=\bar L_v\Delta_F+\|v(x_0)\|^2. The master inequality, the lower-order terms and the numerical constants move to the appendix, and the abstract will define dd, ε\varepsilon and the stationarity measure.

Questions. Q1 is answered above, and Q3 under σK=0\sigma_K=0.

Reviewer_zXFnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

PISO studies optimization when part of the gradient is available and the rest must be estimated from function evaluations. It keeps a running estimate of the missing part and updates it using random probes. The paper provides convergence results and experiments in performative prediction, reinforcement learning, and bilevel games.

Critical strengths

Tracking the missing part of the gradient is a useful idea. The paper explains clearly why centering each observation on the current estimate can reduce probing error. Moreover, the analysis avoids requiring a uniform bound on the missing gradient. This makes the results more relevant to problems where that component can be large.

Critical weaknesses
  1. The deployment comparison overstates the advantage. The cited multi-direction method also allows repeated observations at fixed probe points, so its deployment count need not equal its observation count. Both methods should be compared with batching allowed. Using one probe per update remains useful, but does not establish the claimed deployment savings.
  2. The security-game comparison mixes residual tracking with other changes. PISO receives separate tuning and additional caps on its residual and momentum, while the guided baselines use published settings with clipping disabled. Without matched controls, it is difficult to tell how much of the improvement comes from residual tracking.
Questions for authors
  1. How does the deployment comparison change when batching is allowed for both methods?
  2. Does the security-game advantage remain with matched tuning and clipping controls?
3 comments

We thank the reviewer for their time and for the review, and in particular for the point on deployments, which is correct and which we address first.

Deployments. The reviewer is correct on the total counts. In the multi-direction estimator each probe point can be averaged over mm samples, and the error bound in Hikima & Takeda's proof (Theorem 9 and Lemma 7) reads

E∥∇F(xt)−gt∥2≤9σ2d2μ2Nm+9M2μ2+9M2μ2d22N+54d2N(d+2)E∥∇F(xt)∥2,\mathbb E\|\nabla F(x_t)-g_t\|^2\le\frac{9\sigma^2d^2}{\mu^2Nm}+9M^2\mu^2+\frac{9M^2\mu^2d^2}{2N}+\frac{54d^2}{N(d+2)}\mathbb E \|\nabla F(x_t)\|^2,

with T=Θ(ε−2)T=\Theta(\varepsilon^{-2}) iterations, 2N2N deployed decisions per iteration and 2Nm2Nm samples. The last term must be absorbed into the descent step, which requires 54d2N(d+2)<1\frac{54d^2}{N(d+2)}<1, that is N=Ω(d)N=\Omega(d); the others are at most ε2\varepsilon^2 under the following two choices.

  • μ=Θ(ε)\mu=\Theta(\varepsilon), N=Θ(d2)N=\Theta(d^2), m=Θ(ε−4)m=\Theta(\varepsilon^{-4}): deployments 2NT=Θ(d2ε−2)2NT=\Theta(d^2\varepsilon^{-2}), samples 2NmT=Θ(d2ε−6)2NmT=\Theta(d^2\varepsilon^{-6}).
  • μ=Θ(ε/d)\mu=\Theta(\varepsilon/\sqrt d), N=Θ(d)N=\Theta(d), m=Θ(d2ε−4)m=\Theta(d^2\varepsilon^{-4}): deployments Θ(dε−2)\Theta(d \varepsilon^{-2}), samples Θ(d3ε−6)\Theta(d^3\varepsilon^{-6}).

These are exactly the two operating points of PISO in Section 3.2, so with batching allowed for both methods the total deployment–observation trade-off is the same. We will rewrite Section 3.2 to say so, and around the two differences that remain, which we regard as the substantive ones.

First, and most importantly, the multi-direction guarantee requires Ω(d)\Omega(d) directions before every single update, and this is not usable in practice. Each direction is a pair of deployed decisions, so the method must deploy Θ(d)\Theta(d) decisions, observe their outcomes, and only then take one step. As stated, Theorem 9 of Hikima & Takeda prescribes N=d2ε−4N=d^2\varepsilon^{-4} directions per update: at d=30d=30 and ε=0.1\varepsilon=0.1 this is 9⋅1069\cdot10^6 directions, that is 1.8⋅1071.8\cdot10^7 deployed decisions per step. Even with batching, the absorption condition alone requires N>54d2/(d+2)≈1.5⋅103N>54d^2/(d+2)\approx1.5\cdot10^3 at d=30d=30, so more than 3⋅1033\cdot10^3 of the 50005000 samples of their pricing experiment would be spent before the first step. Their experiments accordingly use N∈{1,10,102}N\in\{1,10,10^2\}, outside the range covered by the analysis, so the guarantee does not describe the method that is run. In our security game (dd up to 300300) the same condition gives N>1.6⋅104N>1.6\cdot10^4 directions per step. PISO's guarantee holds with one direction per update, as in our experiments: it updates after three deployed decisions (xkx_k and xk±μkukx_k\pm\mu_ku_k), and its rate applies to that configuration.

Second, the multi-direction counts carry the smoothness MM of FF through η≤1/(4M)\eta\le1/(4M), whereas PISO's carry Lˉv\bar L_v; with Lˉv=L+γLK\bar L_v=L+\gamma L_K the two are of the same order, and PISO's counts are smaller when a bound on the smoothness of the opaque component is available.

Residual cap and tuning. We agree that the comparison should isolate residual tracking. The residual norm cap was used only in the security game; the other four settings, including the routing game, ran Algorithm 1 without it. We investigated why it was needed there: we had used ρ=0.98\rho=0.98 for every security instance, and for d≥98d\ge98 this places β=1−ρ\beta=1-\rho outside the window 0<β<2/cd0<\beta<2/c_d of Eq. (9), where the analysis predicts that the residual iteration expands; every security instance (d∈[100,300]d\in[100,300]) is in this regime. We reran both games with the prescribed ρ=1−1/cd\rho=1-1/c_d and no cap (new figures in the appendix of the revised PDF). In the security game the residual stays bounded without any safeguard, and the uncapped runs are at least as good as the capped ones, below PZOS throughout and across the whole dimension range; in the routing game, where β\beta was at most marginally outside the window, the results are unchanged. In the revision the cap is removed, so PISO runs as analysed in all five settings and the comparison involves no safeguard on either side.

Tuning. For the baselines we use the hyperparameters reported as optimal in their own papers, and we believe this is the fairest protocol available. In each benchmark the strongest competitors are the methods designed for it, and they run with the settings their authors selected on the same problems: ZOS and PZOS on the routing and security instances of Fischer & Paccagnan, and GZO-NS, GZO-HS, ZO-OGVR and ZO-TG on the pricing and strategic-classification benchmarks of Hikima & Takeda. Each competitor is therefore evaluated at the configuration its authors chose for this very benchmark, and no result depends on how carefully we would re-tune a method we did not design. In the bilevel games the guided baselines also use the radius and step schedules published for PZOS. On the PISO side, the selection is a small two-stage grid, three values each of the initial radius, the initial step size and ρ\rho, followed by the known-component fraction and, where relevant, λ\lambda or the cycle length (Appendix L). In the two games ρ\rho is now set by the prescription 1−1/cd1-1/c_d rather than by the grid, and in pricing the selected ρ=0.92\rho=0.92 is the grid value closest to the prediction 1−1/cd=0.9171-1/c_d=0.917. Performative RL is the one benchmark that none of the zeroth-order baselines was designed for; there, their step schedules were tuned separately.

Dear Reviewer zXFn, as the discussion period closes in a few hours, we would like to check whether our response and the revised PDF address your two concerns. Section 3.2 is rewritten following your point on deployments: with batching allowed for both methods, the total trade-off is the same, and the remaining difference is per update (Appendix K gives the derivation). In the security game, PISO now runs with the prescribed momentum and no cap, so the comparison involves no safeguard on either side, and its advantage over PZOS remains across the whole dimension range (Figures 2, 5 and 9). If these changes resolve your concerns, we would be grateful if you would consider updating your assessment; if not, we would be glad to clarify any remaining point.

Reviewer_REYcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper develops a novel algorithm, PISO, for solving problems with partial access to part of the gradient and with function access for the remaining component. Experiments across five settings show the utility of the proposed approach.

Critical strengths
  • The paper develops two algorithms, PISO and PISO$^2$, for solving problems with partial access to part of the gradient and function access to the remaining component. This problem naturally occurs in multiple settings, including performative prediction, RL, and bilevel optimization.

  • The paper presents numerical results on all three problem classes discussed in the introduction.

  • The paper presents finite-time theoretical convergence guarantees for the presented algorithms

  • The presented analysis is general in the sense that the target quantity to be estimated varies from a full gradient estimate to a fully zeroth-order estimate.

Critical weaknesses
  • My major concern with the paper is that, to me, it seems that the paper presents a complicated solution to solve an easy problem.

    Here is my reasoning: the overall goal is to obtain an estimate of the gradient ∇F\nabla F by estimating gKg_K and gUg_U separately. Now we already have access to an unbiased estimate of gKg_K, and a zeroth-order estimate of gUg_U is obtained from classical perturbation-based techniques. Now this zeroth-order estimate is biased, and this bias depends on the radius of the perturbation, which is under our control. At a high level, overall, we are basically solving an optimization problem where we have access to a biased stochastic gradient estimate of ∇F\nabla F, and importantly, this bias is under our control (i.e., we can make it as small as possible). So the problem can be analyzed using standard descent-based approaches.

    However, the paper presents an error feedback-based approach to control the bias, which is already under our control. This is not fully clear to my why the presented analysis is necessary. To me, it seems that it may be useful for the setting with γ>0\gamma > 0, but for γ>0\gamma > 0, we are not really aiming to solve the actual problem since we ignore part of the gradient under this setting.

  • The residual is generally defined to capture the gradient error; however, in the paper, the residual is defined to be the target quantity (gradient) we want to estimate. I do not understand the reasoning behind this choice. This makes the reading difficult, especially the initial part of the paper where the authors refer to the residual multiple times. Similarly, the usage of work probe for the random perturbations is non-standard and is not clear in the initial reading of the paper.

  • The presented guarantees match exactly those of Hikima & Takeda (2025a); why is that?

  • The experiments are conducted on fairly small-scale problems.

Questions for authors

Can the authors please address my first concern?

2 comments

We thank the reviewer for their time and for the review. The main concern is addressed first, as requested.

Why the problem is not solved by plugging a zeroth-order estimate into a standard descent method. The obstacle is the variance of the estimate, not its bias, and it is not controlled by the radius. Write v=∇F−γgKv=\nabla F-\gamma g_K for the part estimated from function values (v=gUv=g_U at γ=1\gamma=1). A single-direction estimate R=⟨v,u⟩sR=\langle v,u\rangle s, with E[su⊤]=I\mathbb E[su^\top]=I, satisfies, for Gaussian and sphere probes,

E∥R−v∥2=E∥(su⊤−I)v∥2=(cd−1)∥v∥2,cd=d+2 (Gaussian), cd=d (sphere).\mathbb E\|R-v\|^2=\mathbb E\|(su^\top-I)v\|^2=(c_d-1)\|v\|^2,\qquad c_d=d+2\ \text{(Gaussian)},\ c_d=d\ \text{(sphere)}.

This term does not depend on μ\mu, so it does not vanish as μ→0\mu\to0, and it does not vanish as the method converges, since gUg_U need not be zero at a stationary point of FF. Plugging G=γg^K+RG=\gamma\hat g_K+R into SGD, the descent lemma gives

1T∑k<TE∥∇F(xk)∥2≤2ΔFηT+Lη (cd−1) sup⁡x∥v(x)∥2+(bias and oracle-noise terms),\frac1T\sum_{k<T}\mathbb E\|\nabla F(x_k)\|^2\le\frac{2\Delta_F}{\eta T}+L\eta\,(c_d-1)\,\sup_x\|v(x)\|^2+(\text{bias and oracle-noise terms}),

so reaching ε2\varepsilon^2 requires η≲ε2/(LdGU2)\eta\lesssim\varepsilon^2/(L d G_U^2) with GU=sup⁡∥v∥G_U=\sup\|v\|, and T≳LΔFdGU2ε−4T\gtrsim L\Delta_F d G_U^2\varepsilon^{-4}: the complexity depends on a uniform bound on the opaque component, which can be arbitrarily large.

The standard remedy is to average NN directions per step, which divides (cd−1)(c_d-1) by NN, and this is what makes it impractical: the analysis of Hikima & Takeda requires N=Ω(d)N=\Omega(d) directions, each a pair of deployed decisions, before every update, and their theorem prescribes N=d2ε−4N=d^2\varepsilon^{-4}, that is 9⋅1069\cdot10^6 directions per step at d=30d=30 and ε=0.1\varepsilon=0.1. In their own pricing experiment (d=30d=30, 50005000 samples in total) even the minimal requirement exceeds 1.5⋅1031.5\cdot10^3 directions per step, and their experiments use at most 10210^2, so the guarantee does not cover the configurations that are run. The bias is also not free to shrink when the two queries use independent samples: the noise of the difference quotient is σD2≤σF2/(2μ2nF)\sigma_D^2\le\sigma_F^2/(2\mu^2n_F), so decreasing μ\mu to reduce the bias ∥bˉ∥≤Lμd\|\bar b\|\le L\mu\sqrt d increases the variance, and this balance is what leads to the exponent ε−6\varepsilon^{-6}, for PISO as for Hikima & Takeda.

PISO centres each observation on a running estimate mkm_k, Rk=mk+(Dk−⟨γg^K(xk)+mk,uk⟩)sk,R_k=m_k+\big(D_k-\langle\gamma\hat g_K(x_k)+m_k,u_k\rangle\big)s_k, which has the same target but an error proportional to ∥mk−v(xk)∥\|m_k-v(x_k)\| rather than to ∥v(xk)∥\|v(x_k)\|. With exact oracles the tracking error follows Ek+1=(I−βPk)EkE_{k+1}=(I-\beta P_k)E_k and contracts in mean square for 0<β<2/cd0<\beta<2/c_d. This removes GUG_U from the complexity and gives the best known rates for this setting with one direction per update. The error-feedback structure is therefore not a way to control the bias; it is what makes a single direction per update sufficient.

On γ\gamma. The weight γ\gamma does not remove any part of the gradient. With λ=0\lambda=0 the step is Gk=γhk+1+mk+1G_k=\gamma h_{k+1}+m_{k+1}, where hh tracks gKg_K and mm tracks v=∇F−γgKv=\nabla F-\gamma g_K, so Gk≈γgK(xk)+(∇F(xk)−γgK(xk))=∇F(xk)G_k\approx\gamma g_K(x_k)+\big(\nabla F(x_k)-\gamma g_K(x_k)\big)=\nabla F(x_k) for every γ\gamma. The weight only decides how ∇F\nabla F is split between the sampled part and the tracked part; γ=0\gamma=0 is the fully zeroth-order method, in which mm tracks ∇F\nabla F itself.

Terminology. We use "residual" for what remains of ∇F\nabla F after removing γgK\gamma g_K, and agree that it can be confused with an error. We will define it at its first occurrence in the introduction and refer to it as the tracked component where ambiguity arises. A "probe" is the random direction uku_k along which the two function values F(xk±μkuk)F(x_k\pm\mu_ku_k) are taken; we will define the term where it first appears.

Matching Hikima & Takeda. Matching their rates is the point. Their best rates, d2ε−6d^2\varepsilon^{-6} and d2ε−5d^2\varepsilon^{-5}, are established only for N=Ω(d)N=\Omega(d) directions per update (and stated with N=d2ε−4N=d^2\varepsilon^{-4} and N=d2ε−3N=d^2\varepsilon^{-3}), which, as above, cannot be used even at d=30d=30. We obtain the same rates with one direction per update, with Lˉv\bar L_v in place of LL, and while using the known component. The dimension dependence coincides because both analyses rest on the same bound on the mean of the finite-difference bias, ∥bˉ∥≤Lμχ1\|\bar b\|\le L\mu\chi_1 with ς2χ12=d2\varsigma^2\chi_1^2=d^2; we do not claim an improved dependence on dd relative to their result. (Although we still can't prove it, we suspect the dependence on dd and ε\varepsilon is already optimal for the performative prediction setting; a proof of this is an open problem to the best of our knowledge).

Scale. The benchmarks are those of the papers we compare against, chosen so that the comparisons are direct; the security instances go up to d=300d=300.

Dear Reviewer REYc, as the discussion period closes in a few hours, we would like to check whether our response addresses your main concern. In short, the difficulty is not the bias, which the radius controls, but the variance of a single-direction estimate, of order d∥gU∥2d\|g_U\|^2, which does not decrease with the radius or as the method converges; reducing it by averaging requires Ω(d)\Omega(d) directions per update, whereas residual tracking makes this variance proportional to the tracking error and needs one direction (Section 2, "A first estimator, and its cost"). The revised PDF also defines "residual" and "probe" at their first occurrence, as you suggested. If this resolves your concern, we would be grateful if you would consider updating your assessment; if not, we would be glad to clarify any remaining point.

Comments on the paper

2 comments

We thank all reviewers for their time and their reviews. We have uploaded a revised PDF in which every change is in blue. The changes and the new results are summarized below; the responses to each reviewer give the details.

  1. Prior work (Sections 2 and 4). We cite and discuss SEGA (Hanzely et al., 2018), JAGUAR (Veprikov et al., 2024) and its follow-up (Petrov et al., 2025). Section 2 now states the connection explicitly: for sphere probes, βd\beta d plays the role of the relaxation parameter of sketch-and-project, β=1/d\beta=1/d gives the SEGA update applied to the residual, and coordinate probes give the JAGUAR update. Section 4 explains what differs: these methods estimate the gradient of a single objective whose randomness does not depend on the decision, whereas in our setting the gradient splits into a sampled part and a part accessible only through function values, and the distribution depends on the decision, so that the two queries cannot share a sample. Where the guarantees can be compared, our dimension dependence is better: d2d^2 against d9/2d^{9/2} for JAGUAR with independent samples (which also requires convexity and a compact domain), and a factor dd below the follow-up with a shared sample.

  2. Deployments (Section 3.2 and Appendix K). Reviewer zXFn is correct that, once batching at fixed probe points is allowed, multi-direction estimators reach the same total deployment–observation trade-off as PISO; Section 3.2 is rewritten accordingly, and Appendix K derives the two operating points from the bound of Hikima & Takeda. The difference that remains is per update: their guarantee requires Ω(d)\Omega(d) probe directions, each a pair of deployed decisions, before every step, whereas PISO updates after three deployed decisions.

  3. Corollary 3. The case σK=0\sigma_K=0, an exact known component as in the bilevel games, is now stated; the rates are unchanged.

  4. Step size and definitions. After Assumption 1 we state that a Lipschitz constant LUL_U of gUg_U gives the a priori bound Lˉv=LU+∣1−γ∣LK\bar L_v=L_U+|1-\gamma|L_K used to set the step size, and that the leading constant improves on the black-box one when such a bound smaller than LL is known. "Residual" and "probe" are defined at their first occurrence, and the abstract states the stationarity criterion and the dimension.

  5. Bilevel experiments (Figures 2, 5 and 9; Appendix L.2). The residual norm cap was used only in the security game. It was needed because ρ=0.98\rho=0.98 places the momentum outside the stability window of Eq. (9) for every security instance (d≥98d\ge98), where the analysis predicts that the residual iteration expands. Both games now use the prescribed ρ=1−1/cd\rho=1-1/c_d and no safeguard. In the security game the residual state stays bounded (new Figure 9) and the results are at least as good as before, below PZOS throughout and across d∈[100,300]d\in[100,300]; in the routing game they are unchanged. The analysed algorithm is therefore the one run in all five settings, and in the two games its momentum is set by the prescription rather than by a grid search.

  6. Tuning protocol. The baselines use the hyperparameters reported as optimal in their own papers, except in performative RL, which none of the zeroth-order baselines was designed for and where they were tuned separately. In each of the other benchmarks the strongest competitors are the methods designed for it (ZOS and PZOS on the bilevel games, the methods of Hikima & Takeda on pricing and classification), and they run with the settings their authors selected on the same problems.

  7. Presentation of the main theorem. Reviewer Kqbm asked for the main theorem to state the complexity directly. We will restate Theorem 2 in this form, with the master inequality moved to the appendix, in the final version.


Edit: point 7 is now done in the latest revision.

AuthorsOpenReview ↗

Summary of the discussion

We thank the reviewers for their reviews and the Area Chair for handling the paper. The reviewers did not respond to our rebuttal or to the revised PDF during the discussion period, so we summarize here the concerns raised and how the revision addresses them (all changes are in blue).

Concerns and changes.

  • Relation to SEGA and JAGUAR (Reviewer Kqbm). Sections 2 and 4 now discuss both works. The tracking step is an instance of sketch-and-project, as the submission already stated; the contribution is the analysis of a setting these works do not cover, a gradient split into a sampled and an opaque part with a decision-dependent distribution, so that the two queries cannot share a sample. Where guarantees can be compared, ours are sharper: d2d^2 against d9/2d^{9/2} for JAGUAR with independent samples, which also requires convexity and a compact domain.
  • Presentation of the main result (Reviewer Kqbm). Theorem 2 now states the complexity directly, with the master inequality in Appendix F, and the case of an exact known component (σK=0\sigma_K=0) is covered with unchanged rates.
  • Deployments (Reviewer zXFn). Section 3.2 is corrected: with batching allowed for both methods, the total trade-off between deployments and observations is the same. The difference that remains is per update: the multi-direction guarantee requires Ω(d)\Omega(d) probe directions before every step, whereas ours holds with one.
  • Residual cap and tuning (Reviewers Kqbm and zXFn). The cap, used only in the security game, was needed because a fixed momentum placed the method outside the stability window derived in the analysis. With the prescribed momentum ρ=1−1/cd\rho=1-1/c_d, both bilevel games now run without any cap, and the results are unchanged in routing and at least as good in security (Figures 2, 5 and 9). The analysed algorithm therefore runs in all five settings, and the baselines use the hyperparameters reported by their authors.
  • Why residual tracking is needed (Reviewer REYc). The obstacle is not the bias of the zeroth-order estimate, which the probe radius controls, but a variance of order d∥gU∥2d\|g_U\|^2 that does not decrease with the radius or as the method converges. Residual tracking makes this variance proportional to the tracking error, so one probe direction per update suffices. The revision also defines "residual" and "probe" at their first occurrence.

Contribution. One algorithm and one analysis cover performative prediction, performative reinforcement learning, and bilevel problems with an opaque lower level. PISO attains the best known rates for this setting, O(d2ε−6)\mathcal O(d^2\varepsilon^{-6}) and O(d2ε−5)\mathcal O(d^2\varepsilon^{-5}) under a Lipschitz Hessian, with one probe direction per update and without a uniform bound on the opaque component. The analysis identifies the momentum as the step size of a randomized sketch and predicts both its optimum and its stability limit; the experiments confirm both, with the momentum sweep peaking at the predicted 1−1/cd1-1/c_d and the residual growing outside the window where the analysis predicts it.

Since the current scores were given before the revision and without discussion, we believe they do not reflect the paper in its revised form, and we ask the Area Chair to take the revision and our responses into account.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.