- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper considers stochastic nonconvex optimization of whose gradient splits as , where can be sampled directly and 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 that tracks the residual and centers each two-point zeroth-order observation on this state, so that the probing variance scales with the tracking error rather than with . A second state averages the noisy known component, and acts as a control-variate weight. With exact oracles and a fixed iterate, the tracking error follows the randomized sketch recursion , which contracts in mean square for .
Critical strengths
-
One algorithm and one analysis for three application areas. The decomposition 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.
-
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 , and the method diverges below .
Critical weaknesses
- 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 that the paper identifies as optimal (Lemma 5), the noiseless PISO update is exactly SEGA's sketch-and-project step applied to the residual, and the readout 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 in the independent-noise regime. Neither work is cited. What remains new is the application to the residual , the analysis of the relaxation under independent noise and the accounting of deployments.
The advertised rates match those of Hikima & Takeda (2025a), with replaced by and one probe per update instead of . However, is defined along the method's own trajectory (Assumption 1), the step size needs an a-priori bound on it, and the default bound exceeds ; the improvement in the constant is therefore realized only when a small bound on is known in advance. Finally, Corollary 3 assumes , and a similar condition under a Lipschitz Hessian; neither can hold when , that is, when the known component is exact, as in the Stackelberg problems of the bilevel experiments.
- The main results are not presented readably, and the appendices contradict each other.** The abstract states complexities and without saying what and 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 (, , ) together with , a three-way minimum for the step size and more than a dozen numerical coefficients. Several of its quantities (, , , , ) are defined elsewhere, and it states no rate. The rates appear only in Corollary 3, whose parameter choice involves the constants and and two side conditions. The main theorem should be the complexity bound in the main regime, stated in form with its parameter choice, with the master inequality moved to the appendix.
Questions for authors
-
How does PISO differ from SEGA and JAGUAR applied to the residual, and which parts of the analysis are new relative to theirs?
-
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, , no cap) on every task, with the same tuning budget for all methods?
-
Does Corollary 3 extend to , the case of the bilevel experiments?
5 comments
part 2
Where the guarantees can be compared, ours are sharper in . With independent samples, JAGUAR's guarantee (convex , compact set, function value) has a noise term of iterations (Corollary 4); we obtain function evaluations for nonconvex on . The criteria differ, but at the same order JAGUAR's dimension dependence is worse by a factor , 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, in the Euclidean criterion) is a factor above our (Regime A), where is the same quantity as their .
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.: , 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 (Part 2), and this separation is what gives .
Finally, the identification of PISO at with JAGUAR's stochastic method does not hold. Our tracking lemma reads with and . The noise enters at order against a contraction of , so its steady-state contribution is , which is not damped at . JAGUAR's tracking lemma (Lemma 5) has exactly this undamped floor, of order , and removes it with a second momentum layer, . Our corollaries instead take .
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 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, so the mean enters at order (undamped after dividing by the contraction ), while the second moment enters at order and is damped like any other noise. With and for Gaussian probes, the radius balance gives ; bounding the bias through its second moment alone, as both JAGUAR papers do, would give in our analysis. (iv) The known component, for which the direction error is so that, with the average (), 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.
part 3
One probe per update versus . 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 directions per update, that is directions, or deployed decisions, before a single step at and ; and even with batching, absorbing the term of their bound requires at . Their own experiments, with a budget of samples, use . Our guarantee holds for one direction per update.
and the step size. We agree that the step size is set with an a priori bound ,
\eta=\min\Big�0�,
and that the leading term then carries . 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 ; what changes is that the constant that matters is the smoothness of the opaque part rather than that of . Since , any Lipschitz constant of gives , which at is . Without such information, and the leading term is that of a black-box method up to the factor . The one-probe-per-update property does not depend on any of this. We will state this in the main text.
. Thank you for catching this; it is a statement-level gap, and the rate is unchanged. In Corollary 3, is subject to three constraints: the radius balance , the known-oracle constraint , and the moment condition , which is for Gaussian probes. The condition only ensures that the second implies the third at . When the second constraint is void, is admissible, and the third is imposed directly through . Then and , 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, and the parameter choice of Corollary 3, PISO reaches after function evaluations, and under a -Lipschitz Hessian, plus lower-order terms, with . The master inequality, the lower-order terms and the numerical constants move to the appendix, and the abstract will define , and the stationarity measure.
Questions. Q1 is answered above, and Q3 under .
part 1
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. 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.
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⊤, a relaxed sketch-and-project step towards v(xk). For sphere probes uk=sk=dwk, βPk=βdwkwk⊤, which at β=1/d is the projection wkwk⊤; this is SEGA's update (their eq. (4), B=I, Sk=wk), 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: