acceptodds
Under review as a conference paper at ICLR 2027

Optimal Stochastic Optimization with Bounded Gradient Noise

Abstract

Lower bounds for stochastic optimization usually rely on oracles that occasionally return very large gradient errors, so it is unclear whether they remain valid when the noise is uniformly bounded, a setting arjevani2023 left open. We show that bounding the noise does not make optimization easier. For smooth nonconvex, Polyak–Lojasiewicz (PL), strongly convex, and convex objectives, we prove matching upper and lower bounds under almost-surely bounded gradient noise. In particular, finding an -stationary point requires stochastic gradients in the noise-dominated regime, and when the centered noise is -Lipschitz, so stochastic gradient descent and variance reduction remain optimal. We also find a separation between PL and strongly convex objectives: in the noise-dominated regime, PL objectives require samples rather than . Further results cover additive noise, finite sums, relative noise, higher-order smoothness, and limits on sample reuse. Our lower bounds hold for arbitrary randomized algorithms that may re-evaluate samples adaptively and observe exact function values. They rest on bounded observations drawn from the Poisson kernel on the sphere, together with an information argument that controls all responses from reused samples.

Primary area:
optimization
Keywords:
Optimization Complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_mpjXOpenReview ↗
Rating
3(+1)
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic optimization when the gradient noise is bounded almost surely, rather than only having bounded variance. The main question is whether this stronger assumption leads to better complexity bounds. The answer given by the paper is mostly no. For smooth nonconvex problems, the usual ΔLσ2/ϵ4\Delta L\sigma^2/\epsilon^4 stochastic term remains necessary. The paper also studies PL, strongly convex, and convex objectives, as well as finite sums, additive and relative noise, smoother noise, higher-order smoothness, and different forms of sample reuse. The main technical idea in the lower bounds is to encode hidden directions using bounded observations from a Poisson kernel. This is used to handle algorithms that can query the same sample more than once. I think the paper is technically strong. My main reservation is more about the motivation: I am not yet convinced that the bounded-noise model studied here is important enough for current ML applications to justify the scope of the paper.

Critical strengths
  • The paper gives a fairly complete theoretical treatment of bounded gradient noise across several standard optimization classes.

  • The lower bounds are stronger than standard fresh-sample lower bounds. They allow randomized algorithms and, in several results, repeated adaptive queries to the same sample and additional value information.

Critical weaknesses
  • The ML motivation is still not very convincing to me. The paper gives bounded-feature logistic regression as an example where the noise is uniformly bounded, but I am not sure how common this assumption is in modern ML training. A lot of recent empirical work instead reports heavy-tailed or strongly nonuniform stochastic gradients. I would like to better understand which important learning problems are actually captured by the model studied here.

  • There is no empirical evidence for the main modeling assumption. I would not normally ask for experiments in a lower-bound paper just for the sake of having experiments. Here, however, the practical importance of the assumption itself is one of my main uncertainties. Even a simple study of gradient-noise distributions on a few standard datasets/models would help.

  • Some of the oracle models are rather abstract. In particular, the retained-sample oracle treats a sample as an opaque object that can be queried at different points without revealing the sample itself. This is mathematically useful, but in supervised learning the data point is usually directly available. It is not obvious to me what practical setting this model is intended to represent.

  • The headline nonconvex result now overlaps with concurrent work. Jin (2026) also proves the tight bounded-noise lower bound in the smooth nonconvex fresh-sample setting. The present paper clearly does much more than that, but the overlap should be discussed explicitly. As written, the introduction gives the impression that the basic nonconvex question is resolved here for the first time.

  • The lower bounds are high-dimensional minimax results. The dimension of the hard instance can depend on the query budget and on the fixed batch width KK. This is standard for oracle lower bounds, but it makes the connection to fixed-dimensional learning problems less direct.

  • Not all of the complexity picture is actually closed. For example, the higher-order result is matching only in a stated parameter regime, and some finite-sum PL/strongly convex cases remain open. This is fine, but given the broad title “Optimal Stochastic Optimization,” I think these limitations should be made more prominent.

  • The PL/strongly-convex separation is theoretically interesting, but I am not sure yet what it tells us about practice. The difference between κS\kappa S and SS is clean, but the paper does not give an example of a realistic learning problem where this distinction would change how one should optimize it.

Questions for authors
  1. Can the authors give more examples of ML problems where sup⁡x∣g(x;ξ)−∇F(x)∣≤σ\sup_x|g(x;\xi)-\nabla F(x)|\leq\sigma holds naturally? Is there any empirical evidence that this is a reasonable model for modern training problems?

  2. How do the authors view the relation to Jin (2026), “A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise”? What exactly is new in the present paper once the fresh-sample nonconvex result is separated out?

  3. How essential is the opaque retained-sample model? Would the lower bounds still hold if the algorithm could inspect the underlying data sample directly?

  4. The round lower bounds assume fixed finite KK, while the hard dimension may depend on KK. What changes if KK is allowed to grow with the target accuracy or total budget?

  5. Is the condition Q≤(1+m)(1+Cp)Q\leq(1+m)(1+C_p) in the higher-order result mainly a proof limitation, or do the authors expect a genuinely different rate outside this regime?

  6. Do the authors expect the finite-sum PL and strongly convex results to extend to n<Sn<S?

  7. Have the authors considered adding a small empirical study of the bounded-noise assumption itself? I think this would help much more than an experiment simply comparing optimization algorithms.

4 comments

Thank you for the thoughtful review and questions.

Q1: More examples of ML problems where sup⁡x∥g(x;ξ)−∇F(x)∥≤σ\sup_x \|g(x;\xi) - \nabla F(x)\| \le \sigma holds naturally, and practical motivation.

Uniformly bounded gradient noise arises whenever the per-sample loss is GG-Lipschitz with respect to the parameters on bounded or normalized inputs, which guarantees ∥g(x;ξ)−∇F(x)∥≤2G\|g(x;\xi) - \nabla F(x)\| \le 2G for every xx. This holds even when the objective includes an unbounded regularizer such as λ2∥x∥2\frac{\lambda}{2}\|x\|^2, which cancels in g(x;ξ)−∇F(x)g(x;\xi) - \nabla F(x). Natural examples include training a linear classifier or a Bradley-Terry preference model on normalized feature embeddings, logistic and multiclass softmax classification with bounded features, and robust regression on bounded covariates using Huber or Cauchy losses. While recent work on heavy tails asks whether outlier gradients make optimization harder than bounded variance, our results answer the complementary question of Arjevani et al. (2023) by showing that the classical ε−4\varepsilon^{-4} and σ2/(μη)\sigma^2/(\mu\eta) barriers come from ordinary bounded fluctuations rather than rare outlier spikes.

Q2: Relation to Jin (2026) and what is new beyond the fresh-sample nonconvex result?

Jin (2026) proves the Ω(Q+Qm)\Omega(Q + Qm) lower bound for smooth nonconvex objectives in the fresh-sample model where each sample is queried once for its gradient, using biased random sign vectors. Beyond that single-query nonconvex result, our paper uses observations drawn from the Poisson kernel, scalar sample losses, and the information bound in Lemma 13 to handle adaptive sample reuse, KK-point rounds, and exact function values, and establishes matching bounds for centered-noise and sample smoothness, finite sums, relative noise, higher-order smoothness, and the global PL, strongly convex, and convex function classes.

Q3: How essential is the opaque retained-sample model? Would lower bounds hold under direct sample inspection?

For the terms that come from estimating a single mean (such as Ω(m)\Omega(m) and Ω(S)\Omega(S)), the lower bounds still hold if the algorithm inspects the sample directly, because each sample loss is a fixed quadratic minus an inner product with the sample vector VV and contains no hidden population parameters. By contrast, bounds that depend on the number of optimization steps require access only through function and gradient evaluations, which models variance-reduced methods that evaluate a stored sample at xtx_t and xt−1x_{t-1} via backpropagation, since an algorithm with unlimited computation that could read the full formula of f(⋅;ξ)f(\cdot;\xi) could minimize the empirical risk without taking gradient steps.

Q4: What changes if KK is allowed to grow with the target accuracy or total budget?

When the ambient dimension dd is chosen after KK and the round budget RR, Lemma 13 holds with the same constants for any finite KK: all KK points in a round share one sample, so a round still advances progress along the chain by at most one stage and KK only increases the block dimension D=Θ(RK+log⁡T)D = \Theta(RK + \log T). When dd is fixed in advance and RK≳dRK \gtrsim d, the spherical concentration argument no longer applies because KK simultaneous points can span Ω(min⁡{K,d})\Omega(\min\{K, d\}) directions in a single round.

Q5: Is Q≤(1+m)(1+Cp)Q \le (1 + m)(1 + C_p) in Theorem 7 a proof limitation or a genuinely different regime?

We expect a genuinely different rate outside this regime (when mm is small and Ap≪QA_p \ll Q). In the noiseless case σ=0\sigma = 0 with p=2p = 2, deterministic first-order methods under Lipschitz Hessians achieve O(ε−7/4)O(\varepsilon^{-7/4}) against a lower bound of Ω(ε−12/7)\Omega(\varepsilon^{-12/7}) (Carmon et al., 2021), which sits strictly between our lower bound Ω(ε−3/2)\Omega(\varepsilon^{-3/2}) and upper bound O(ε−2)O(\varepsilon^{-2}). When Q≤(1+m)(1+Cp)Q \le (1 + m)(1 + C_p), the stochastic term mCpmC_p dominates and closes this gap.

Q6: Do the finite-sum PL and strongly convex results extend to n<Sn < S?

Not with the online formulas unchanged: when n<Sn < S (for instance, as η→0\eta \to 0 at fixed nn), evaluating all nn components gives the exact gradient ∇F(x)\nabla F(x) in nn calls, yielding upper bounds O(nDκ)O(nD_\kappa) and O(nEκ)O(nE_\kappa) that grow as log⁡(Δ/η)\log(\Delta/\eta) rather than linearly like S=σ2/(μη)S = \sigma^2/(\mu\eta).

Q7: Adding a small empirical study of the bounded-noise assumption.

Yes, we ran 300 steps of minibatch stochastic gradient descent on normalized UCI datasets with ℓ2\ell_2 regularization (λ=10−2\lambda = 10^{-2}), comparing the maximum per-sample gradient error max⁡i∥ζi(xt)∥\max_i \|\zeta_i(x_t)\| to the root-mean-square error. Across the trajectory, max⁡i∥ζi∥\max_i \|\zeta_i\| stayed in [1.01,1.11][1.01, 1.11] (ratio in [6.77,7.32][6.77, 7.32]) for 10-class softmax on Digits, and in [0.52,0.74][0.52, 0.74] (ratio in [2.15,2.98][2.15, 2.98]) for Cauchy regression on Diabetes; we will add this study to the appendix.

Thank you for the detailed responses. I appreciate the theoretical contributions and clarifications, but I am maintaining my score of 2.

My main concern remains the practical relevance of the assumptions and oracle model. While the authors provide valid examples of bounded gradient noise, these mostly concern relatively simple models with bounded features. The proposed experiments only demonstrate bounded noise along finite trajectories, rather than establishing its relevance to broader ML settings. Moreover, the strongest lower bounds rely on an opaque-sample oracle, whereas standard supervised learning typically allows direct access to the data. As the authors acknowledge, these bounds do not necessarily extend to such settings.

These limitations, together with the fact that the promised revisions are not yet reflected in the paper, prevent me from raising my score.

Q1: Where are the promised revisions now reflected in the updated paper?

Thank you for your follow-up. All revisions are now incorporated into the paper:

  • Section 1 (Page 1) and Appendix G.1 (Pages 62-63) expand the ML motivation and prove global all-xx bounded-noise bounds for normalized heads, bounded-derivative multilayer networks, and robust nonconvex M-estimators;
  • Section 1 (Page 2) and Section 6 (Page 9) state the three open boundary regimes;
  • Section 2 (Page 2) and Appendix G.1 (Page 63) clarify the practical scope of the fresh-sample, retained-sample, and KK-point oracles in supervised learning;
  • Section 3.2 (Page 5) discusses nonconvex PL applications in overparameterized networks and policy-gradient reinforcement learning;
  • Appendices G.2-G.3 (Pages 63-64, Tables 2-3) report the global parameter-space sweep across R=∥x∥∈[0.1,1000]R = \|x\| \in [0.1, 1000] and 300-step SGD trajectory diagnostics.

Q2: Does uniform bounded gradient noise hold globally beyond simple linear models and finite trajectories?

Yes, it holds both analytically across all of Rd\mathbb{R}^d (Page 62) and empirically across four orders of magnitude of parameter norm (Table 2). When a representation h(xback;ξ)∈Rph(x_{\mathrm{back}};\xi) \in \mathbb{R}^p passes through LayerNorm or RMSNorm before an output layer W∈Rp×CW \in \mathbb{R}^{p \times C}, the normalized vector z(xback;ξ)=LN(h(xback;ξ))z(x_{\mathrm{back}};\xi) = \mathrm{LN}(h(x_{\mathrm{back}};\xi)) satisfies ∥z(xback;ξ)∥<p\|z(x_{\mathrm{back}};\xi)\| < \sqrt{p} for every input ξ\xi and every backbone parameter xbackx_{\mathrm{back}}. Under softmax, cosine-similarity contrastive, or Bradley-Terry preference losses, the logit derivative has norm at most 2\sqrt{2}, so the head noise satisfies sup⁡x∈Rd∥ζW(x;ξ)∥F≤22p\sup_{x \in \mathbb{R}^d} \|\zeta_W(x;\xi)\|_F \le 2\sqrt{2p} globally on Rd\mathbb{R}^d.

Likewise, for a two-layer nonlinear network f(W1,w2;ai,yi)=ℓ(yi∑j=1ptanh⁡(w2,j)tanh⁡(W1,j⊤ai))+λ2(∥W1∥F2+∥w2∥2)f(W_1,w_2;a_i,y_i) = \ell(y_i \sum_{j=1}^p \tanh(w_{2,j})\tanh(W_{1,j}^\top a_i)) + \frac{\lambda}{2}(\|W_1\|_F^2 + \|w_2\|^2) with 11-Lipschitz loss ℓ\ell and ∥ai∥≤B\|a_i\| \le B, the bounds ∣tanh⁡(u)∣≤1|\tanh(u)| \le 1 and sech2(u)≤1\mathrm{sech}^2(u) \le 1 and cancellation of the ℓ2\ell_2 penalty yield sup⁡(W1,w2)∈Rd0p+p∥ζi(W1,w2)∥≤2p(1+B2).\sup_{(W_1,w_2) \in \mathbb{R}^{d_0 p + p}} \|\zeta_i(W_1,w_2)\| \le 2\sqrt{p(1+B^2)}.

Q3: How do the oracle lower bounds apply to standard supervised learning where the data are directly accessible?

First, all of our baseline lower bounds (Θ(Q+Qm)\Theta(Q+Qm) for nonconvex, Θ(Dκ+κS)\Theta(D_\kappa+\kappa S) for PL, Θ(Eκ+S)\Theta(E_\kappa+S) for strongly convex, Θ(LR2/η+σ2R2/η2)\Theta(\sqrt{LR^2/\eta}+\sigma^2 R^2/\eta^2) for convex, relative noise, and higher-order smoothness) hold under the standard single-query fresh-sample first-order oracle (K=1K=1) without any retained-sample handle.

Second, although supervised learning examples ξi=(ai,yi)\xi_i = (a_i,y_i) are stored in memory, every general-purpose first-order and variance-reduced optimizer used in practice (SGD, momentum, Adam, SVRG, SARAH, SPIDER, PAGE) accesses samples solely by evaluating sample losses and gradients (f(x;ξi),∇f(x;ξi))(f(x;\xi_i), \nabla f(x;\xi_i)) at chosen iterates via backpropagation. Our fresh-sample and retained-sample lower bounds therefore apply unconditionally to every such algorithm; the retained-sample oracle captures variance-reduced methods that cache examples to re-evaluate their gradients at multiple adaptively chosen iterates. Only problem-specific algebraic solvers (such as closed-form matrix inversion in linear least squares) bypass gradient evaluations. Finally, the statistical lower bounds Ω(m)\Omega(m), Ω(S)\Omega(S), and Ω(σ2R2/η2)\Omega(\sigma^2 R^2/\eta^2) (Lemma 21) reduce to minimax mean estimation from the raw observations S1,…,SnS_1,\dots,S_n and hold even under unrestricted white-box inspection of the raw data.

Dear Authors,

Thank you for the revised manuscript. The new analytical examples and empirical results in Appendix G substantially address my main concerns regarding the relevance of bounded gradient noise. I appreciate these additions and am raising my score from 2 to 3.

However, some clarifications remain necessary. In particular, Eq. (233) establishes bounded noise for the output head, not necessarily for the full gradient when the backbone is trained. Moreover, the lower bounds for black-box first-order oracles should not be claimed to apply unconditionally to unrestricted raw-data access. Finally, Jin (2026) should be explicitly cited and distinguished from the present contributions.

These issues do not diminish the value of the main theoretical results, but addressing them would improve the paper's precision and positioning.

Best regards,

Reviewer mpjX

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

The paper addresses an open question that was posed by Arjevani et al. [1]: Does almost-surely bounded gradient noise allow better worst-case rates for smooth nonconvex stochastic optimization than bounded-variance noise? The authors answer this question negatively. They assume:

A1) The objective function F:Rd→RF:\mathbb{R}^d\to\mathbb{R} has an LL-Lipschitz gradient.

A2) F⋆:=inf⁡xF(x)>−∞F_\star:=\inf_x F(x)>-\infty and F(x0)−F⋆≤ΔF(x_0)-F_\star\le\Delta.

A3) Sample gradients g(x;ξ)=∇f(x;ξ)g(x;\xi)=\nabla f(x;\xi) satisfy Eξ[g(x;ξ)]=∇F(x)\mathbb{E}_\xi[g(x;\xi)]=\nabla F(x) for every xx, and for a fixed constant σ≥0\sigma\ge0, almost surely, ∥∣g(x;ξ)−∇F(x)∥∣≤σ\||g(x;\xi)-\nabla F(x)\|| \le\sigma simultaneously for all xx.

Under these assumptions, the authors prove a worst-case lower bound on the number of gradient evaluations [see Theorem 1] of Ω(ΔLε2+ΔLσ2ε4)\Omega\left(\frac{\Delta L}{\varepsilon^2}+\frac{\Delta L\sigma^2}{\varepsilon^4}\right) for achieving E∥∣∇F(x^)∥∣≤ε\mathbb{E}\||\nabla F(\widehat{x})\||\le\varepsilon, when 0<ε≤cΔL0<\varepsilon\le c\sqrt{\Delta L} for a universal constant c>0c>0. This matches the known upper bound for SGD under the bounded-variance assumption, showing that strengthening this assumption to almost-surely bounded noise does not improve the minimax complexity over this class.

The authors also establish lower bounds matching upper bounds for PL, strongly convex, and convex objectives, with the target E[F(x^)−F⋆]≤η\mathbb{E}[F(\widehat{x})-F_\star]\le\eta.

PL objectives [Theorem 4]. Under A1, A2, A3, and the PL condition: ∥∣∇F(x)∥∣2≥2μ(F(x)−F⋆)\||\nabla F(x)\||^2\ge2\mu(F(x)-F_\star) for every xx, the optimal gradient-evaluation complexity is Θ(Dκ+κσ2μη)\Theta\left(D_\kappa+\frac{\kappa\sigma^2}{\mu\eta}\right).

Strongly convex objectives [Theorem 5]. Under A1, A2, A3, and μ\mu-strong convexity of FF, the optimal gradient-evaluation complexity is Θ(Eκ+σ2μη)\Theta\left(E_\kappa+\frac{\sigma^2}{\mu\eta}\right).

Both results hold for 0<η≤Δ/1280<\eta\le\Delta/128, with κ=L/μ\kappa=L/\mu. For κ>1\kappa>1, Dκ:=1+log⁡(Δ/η)log⁡(κ/(κ−1))D_\kappa:=1+\frac{\log(\Delta/\eta)}{\log(\kappa/(\kappa-1))} and Eκ:=1+log⁡(Δ/η)log⁡((κ+1)/(κ−1))E_\kappa:=1+\frac{\log(\Delta/\eta)}{\log((\sqrt{\kappa}+1)/(\sqrt{\kappa}-1))}. At κ=1\kappa=1, both equal 11. Thus, when the stochastic terms dominate, the minimax complexity for general PL objectives is a factor κ\kappa larger than for strongly convex objectives, up to universal constants. For large κ\kappa, the strongly convex lower bound also matches the classical optimal upper bound under bounded-variance noise, since Eκ=1+log⁡(Δ/η)log⁡(κ+1κ−1)=Θ(κlog⁡Δη).E_\kappa=1+\frac{\log(\Delta/\eta)}{\log\left(\frac{\sqrt{\kappa}+1}{\sqrt{\kappa}-1}\right)}=\Theta\left(\sqrt{\kappa}\log\frac{\Delta}{\eta}\right). Hence, the complexity is Θ(κlog⁡(Δ/η)+σ2/(μη))\Theta\left(\sqrt{\kappa}\log(\Delta/\eta)+\sigma^2/(\mu\eta)\right), matching the classical accelerated stochastic rate.

Convex objectives [Theorem 6]. The authors retain A1 and A3, assume convexity, and replace A2 with the existence of a minimizer x⋆x_\star satisfying ∥∣x0−x⋆∥∣≤R\||x_0-x_\star\||\le R. They establish the optimal gradient-evaluation complexity Θ(LR2η+σ2R2η2)\Theta\left(\sqrt{\frac{LR^2}{\eta}}+\frac{\sigma^2R^2}{\eta^2}\right) for 0<η≤cLR20<\eta\le cLR^2, where c>0c>0 is a universal constant. This matches the known optimal rate under bounded-variance noise. Thus, as in the nonconvex and strongly convex (big κ\kappa) cases, almost-surely bounded noise does not improve the minimax rate for smooth convex objectives.

The upper bounds hold in every dimension, while the matching lower bounds are proved in sufficiently large dimensions. Thus, the results establish optimality in the worst case over all finite dimensions, not necessarily in each fixed dimension..

The paper contains additional results; I have summarized the main ones above.

[1] Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., & Woodworth, B. (2023). Lower bounds for non-convex stochastic optimization. Mathematical Programming.

Critical strengths

1) The authors show that replacing the bounded-variance assumption with almost-surely bounded gradient noise does not improve worst-case rates. For smooth nonconvex, convex, and strongly convex (big κ\kappa) objectives, they establish lower bounds that match the known optimal rates under bounded-variance noise.

2) The lower bounds hold even for arbitrary randomized algorithms that query the same sample ξ\xi at adaptively chosen points and observe g(x;ξ):=∇f(x;ξ)g(x;\xi):=\nabla f(x;\xi), f(x;ξ)f(x;\xi), and F(x)F(x) at each counted query.

3) An interesting result is that PL and strongly convex objectives have different worst-case complexities. In the noise-dominated regime, Theorems 4 and 5 give Θ(κσ2/(μη))\Theta(\kappa\sigma^2/(\mu\eta)) for PL objectives and Θ(σ2/(μη))\Theta(\sigma^2/(\mu\eta)) for strongly convex objectives, where η\eta is the expected objective-gap tolerance and κ=L/μ\kappa=L/\mu.

Critical weaknesses

1) Section 4 explains the main proof ideas, and the paper credits Arjevani et al. for posing the bounded-noise question. However, a more direct comparison with earlier lower-bound proofs would make the contribution clearer. In particular, which arguments are new in the bounded Poisson-kernel observations, the treatment of adaptive sample reuse, and the construction of scalar sample losses? Which parts adapt existing techniques?

2) The appendix is hard to follow because some symbols have different meanings and the proofs use lemmas from several sections. For example, QQ means ΔL/ε2\Delta L/\varepsilon^2 in Section 2 but a weight parameter in Appendix C.2. Similarly, SS means both a random observation in Section 4.1 and σ2/(μη)\sigma^2/(\mu\eta) in Section 2. Using different symbols and adding a short guide showing which lemmas support each main theorem would make the proofs easier to read and check.

3) The proofs use very large constants. For example, the condition ε≤cΔL\varepsilon \le c\sqrt{\Delta L}, with c=2−20c = 2^{-20}, gives Q≥240Q \ge 2^{40}. The proofs also use R0=260R_0 = 2^{60} and CPL=256⋅106C_{\mathrm{PL}} = 256 \cdot 10^6. These constants do not affect the stated minimax rates up to universal factors, but they limit the numerical information provided by the bounds. A short discussion of where the largest constants arise, and whether they can be reduced, would be useful.

Justification of the score: I lean toward weak acceptance because the paper addresses an explicit open question and establishes matching bounds under a broad oracle model. I find the main results important. My main concerns are the explanation of the new proof ideas and the readability of the appendix. Clearer comparisons with earlier proofs and a short guide to the main lemmas would make the results easier to understand and check.

I want to stress that I have not checked all the proofs in detail. I mainly followed the logic and the main steps of the arguments, and I did not find any major issue in what I checked.

Questions for authors

1) Could the authors give a more intuitive explanation of why general PL objectives are a factor of κ\kappa harder than strongly convex objectives in the noise-dominated regime (from a statistical point of view)?

2) Which parts of the lower-bound proof are new, and which adapt earlier techniques? Please clarify the roles of the Poisson-kernel observations, the argument for adaptive sample reuse, and the construction of scalar sample losses.

3) Can the large constants, such as R0=260R_0=2^{60} and CPL=256⋅106C_{\mathrm{PL}}=256\cdot10^6, be substantially reduced? Which proof steps cause the largest losses?

4 comments

Thank you for the thorough summary and constructive feedback.

Q1: Why are general PL objectives a factor of κ\kappa harder than strongly convex objectives in the noise-dominated regime?

From a statistical viewpoint, the factor of κ\kappa comes from whether noisy gradients queried at different iterates estimate a single shared direction or Θ(κ)\Theta(\kappa) unrelated directions. Under μ\mu-strong convexity, ⟨∇F(x),x−x⋆⟩≥F(x)−F⋆\langle \nabla F(x), x - x_\star \rangle \ge F(x) - F_\star holds globally and an objective gap of η\eta confines x⋆x_\star to a ball of radius 2η/μ\sqrt{2\eta/\mu}, so averaging noisy gradients along the trajectory pools information toward the same minimizer x⋆x_\star and locating it under noise σ\sigma costs Θ(σ2/(μη))=Θ(S)\Theta(\sigma^2/(\mu\eta)) = \Theta(S) samples regardless of LL.

Without convexity, the PL inequality ∥∇F(x)∥2≥2μ(F(x)−F⋆)\|\nabla F(x)\|^2 \ge 2\mu(F(x) - F_\star) only links the local gradient norm to the remaining gap, allowing the optimization path to bend through T≍L/μ=κT \asymp L/\mu = \kappa orthogonal stages, each with active gradient norm Θ(μη)\Theta(\sqrt{\mu\eta}). Because unvisited stages are gated off to zero, noisy gradients from stage jj contain no information about the hidden direction of stage j+1j + 1. Any algorithm is forced to solve Θ(κ)\Theta(\kappa) statistically independent estimation problems of sample cost Θ(S)\Theta(S) one after another, requiring Θ(κS)\Theta(\kappa S) samples in total.

Q2: Which parts of the lower-bound proof are new, and which adapt earlier techniques?

Our deterministic nonconvex construction adapts the chain and radial quadratic term of Carmon et al. (2020, 2021) and Arjevani et al. (2023), while the three parts you asked about are new:

  1. Poisson-kernel observations: Arjevani et al. (2023) hide the next direction using a rare Bernoulli variable that reveals θp+1/q\theta_{p+1}/q with small probability q≍ε2/σ2q \asymp \varepsilon^2/\sigma^2, which creates unbounded gradient errors of size Θ(σ2/ε)\Theta(\sigma^2/\varepsilon). We replace rare amplification with a continuous vector V∼pβθV \sim p_{\beta\theta} drawn from the Poisson kernel on SD−1\mathbb{S}^{D-1}, which satisfies E[V/β∣θ]=θ,∥V/β−θ∥≤2/β,KL(Pβθ∥μD)≤2Dβ2.\mathbb{E}[V/\beta \mid \theta] = \theta, \quad \|V/\beta - \theta\| \le 2/\beta, \quad \mathrm{KL}(P_{\beta\theta} \| \mu_D) \le 2D\beta^2.
  2. Adaptive sample reuse: Oracles based on discrete thresholds fail when a sample is queried more than once, because two queries can bracket the threshold and reveal θ\theta. Because our Poisson observation is continuous, every response of a sample at stage pp is a deterministic function of the earlier directions and the stored vectors Vh,≤p+1V_{h,\le p+1}. Lemma 13 bounds the information revealed by the entire stored vector Vh,iV_{h,i} the first time sample hh is used at stage ii, so all later adaptive re-evaluations, gradient differences, and exact function values reveal no further information.
  3. Scalar sample losses: Rather than specifying a vector oracle directly, we construct bounded-below scalar sample losses f=F+Nf = F + N by making the objective affine on the region where a stage coordinate is still small and multiplying the noise by smooth cutoff functions Θj(q)\Theta_j(q) so that at most one stage's noise term is active at any point xx. This keeps ∥∇N∥≤σ\|\nabla N\| \le \sigma and Lip(∇N)≤H\mathrm{Lip}(\nabla N) \le H independent of the chain length TT even after differentiating the gates. We will make this comparison explicit in Section 4.

Q3: Can the large constants, such as R0=260R_0 = 2^{60} and CPL=256⋅106C_{\mathrm{PL}} = 256 \cdot 10^6, be substantially reduced?

Yes, they can be reduced by several orders of magnitude. They do not come from the Poisson-kernel argument itself, but from squaring conservative derivative bounds on the cutoff functions and rounding to powers of two:

  1. In R0=260R_0 = 2^{60}, differentiating the steep quintic cutoff Θj\Theta_j in Lemma 17 inflates the gradient of the noise potential, which requires scaling down β=B0ε/σ\beta = B_0\varepsilon/\sigma by B0=216B_0 = 2^{16} and contributes B02=232B_0^2 = 2^{32} to m=B02β−2m = B_0^2\beta^{-2}, while the remaining 2282^{28} factor comes from the projection threshold a=1/16a = 1/16 in Lemma 9 and rounding to powers of two. Widening the projection threshold aa to 1/41/4, using wider cubic cutoffs, and avoiding power-of-two rounding reduces R0R_0 by roughly 77 to 88 orders of magnitude.
  2. In CPL=256⋅106C_{\mathrm{PL}} = 256 \cdot 10^6, Lemma 24 squares both the lower bound on the partial derivative (1/641/64) and the smallest eigenvalue of the radial map's Jacobian (1/31/3) in the PL inequality, producing a factor near 10610^6 before multiplying by the smoothness constant 256256. Choosing a steeper linear slope on the small-coordinate region and moving the transition threshold closer to 11 reduces CPLC_{\mathrm{PL}} to roughly 10410^4-10510^5. We will add a short discussion of these constants in Appendices B and C, resolve the symbol collisions for QQ and SS, and add a guide linking each main theorem to its supporting lemmas.
Reviewer_1W1xOpenReview ↗

Follow-up

Thank you for your response.

For the first point: What I understand from what you wrote, is that in the strongly convex case, observations at different iterates provide information about a common minimizer, while your hard PL construction requires learning successive hidden directions.

What do you mean by: a single shared direction? For a fresh unbiased gradient sample, E[gt∣xt]=∇F(xt)\mathbb E[g_t\mid x_t]=\nabla F(x_t) varies across iterates. I assume that you mean a shared minimizer rather than a fixed gradient direction.

Could you relate your intuition to the proof in Appendix F.6 and explain how using strong convexity can lead to the statistical term O(σ2/(μη))O(\sigma^2/(\mu\eta)) without the factor of κ\kappa?

For the second point: Thank you for the explanation. I now better understand the role of the Poisson kernel observations. But, I have some reservations about saying that all three parts are new. Arjevani et al. [1] already construct scalar sample losses in Section 5.1 and consider active oracles allowing sample reuse in Section 5.2.

My understanding is that the new contribution is constructing sample losses with almost surely bounded gradient noise and proving that the lower bound still holds when samples are reused adaptively. This should be mentioned in the revised version.

For the third point: This is not a major concern for me. But I cannot check these smaller constants based on the explanation alone. It would help to include the supporting calculations in the revised version.

[1] Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., & Woodworth, B. (2023). Lower bounds for non-convex stochastic optimization. Mathematical Programming.

Thank you for your thoughtful follow-up comments.

Q1: Clarifying "a single shared direction" and relating the intuition to Appendix F.6. You are completely right: "a single shared direction" was imprecise phrasing on our part. Because E[gt∣xt]=∇F(xt)\mathbb{E}[g_t | x_t] = \nabla F(x_t) varies across iterates, what is shared across iterates in the strongly convex case is a common global minimizer x⋆x^\star (so the population gradient at each iterate has a positive inner product with the displacement xt−x⋆x_t - x^\star toward that same point), whereas our PL lower-bound construction requires learning a sequence of Θ(κ)\Theta(\kappa) independent hidden unit vectors θ1,…,θT\theta_1, \dots, \theta_T.

In Appendix F.5 and F.6, this role of a shared minimizer x⋆x^\star appears directly in the proof of Lemma 39. The accelerated algorithm (217)-(218) accumulates the noisy gradients Gt=∇F(xt)+ξtG_t = \nabla F(x_t) + \xi_t into a single auxiliary sequence zt=zt−1−(at/β)Gtz_t = z_{t-1} - (a_t/\beta)G_t (with at=ta_t = t and At=t(t+1)/2A_t = t(t + 1)/2) and tracks the potential At(F(yt)−F(x⋆))+β2∥zt−x⋆∥2A_t(F(y_t) - F(x^\star)) + \frac{\beta}{2}\|z_t - x^\star\|^2 relative to x⋆x^\star:

  1. Convexity relative to the common minimizer x⋆x^\star at every query point, F(xt)−F(x⋆)≤⟨∇F(xt),xt−x⋆⟩F(x_t) - F(x^\star) \le \langle \nabla F(x_t), x_t - x^\star \rangle, allows the linear gradient terms across all TT steps to telescope against β2∥zt−x⋆∥2\frac{\beta}{2}\|z_t - x^\star\|^2 in Eq. (221). The smoothness constant LL is only needed so that the negative quadratic term −12(β−Lat2/At)∥zt−zt−1∥2-\frac{1}{2}(\beta - La_t^2/A_t)\|z_t - z_{t-1}\|^2 in Eq. (221) absorbs the noise term β4∥zt−zt−1∥2\frac{\beta}{4}\|z_t - z_{t-1}\|^2 from Young's inequality on −at⟨ξt,zt−zt−1⟩-a_t\langle \xi_t, z_t - z_{t-1}\rangle, which requires only β≥4L\beta \ge 4L.
  2. Summing Eq. (221) from t=1t = 1 to TT gives Eq. (220), E[F(yT)−F(x⋆)]≤βR02T(T+1)+σ2(2T+1)3β\mathbb{E}[F(y_T) - F(x^\star)] \le \frac{\beta R_0^2}{T(T + 1)} + \frac{\sigma^2(2T + 1)}{3\beta} for E∥X−x⋆∥2≤R02\mathbb{E}\|X - x^\star\|^2 \le R_0^2, and choosing β=max⁡{4L,σT3/2/R0}\beta = \max\{4L, \sigma T^{3/2}/R_0\} in Eq. (222) yields Eq. (223): E[F(yT)−F(x⋆)]≤4LR02T2+2σR0T.\mathbb{E}[F(y_T) - F(x^\star)] \le \frac{4LR_0^2}{T^2} + \frac{2\sigma R_0}{\sqrt{T}}. Because β\beta is free to grow with σT3/2/R0\sigma T^{3/2}/R_0 independently of LL once β≥4L\beta \ge 4L, LL drops out of the stochastic error term 2σR0/T2\sigma R_0/\sqrt{T} completely.
  3. In Appendix F.6, μ\mu-strong convexity enters at the start of each restart stage jj (where E[F(X)−F(x⋆)]≤δj\mathbb{E}[F(X) - F(x^\star)] \le \delta_j) to convert the objective gap into the squared distance bound R02=2δj/μR_0^2 = 2\delta_j/\mu to x∗x^* in Eq. (225). Substituting R0=2δj/μR_0 = \sqrt{2\delta_j/\mu} into Eq. (223) gives Eq. (226): E[F(yT)−F(x⋆)]≤8κδjT2+2σ2δj/μT.\mathbb{E}[F(y_T) - F(x^\star)] \le \frac{8\kappa\delta_j}{T^2} + \frac{2\sigma\sqrt{2\delta_j/\mu}}{\sqrt{T}}. Making each term at most δj/4\delta_j/4 in Eq. (227) takes Tδj=max⁡{⌈32κ⌉,⌈128σ2/(μδj)⌉}T_{\delta_j} = \max\{\lceil\sqrt{32\kappa}\rceil, \lceil 128\sigma^2/(\mu\delta_j)\rceil\} calls. Because LL disappeared from the stochastic term of Eq. (223), the second term 128σ2/(μδj)128\sigma^2/(\mu\delta_j) depends on μ\mu but not LL, avoiding any factor of κ=L/μ\kappa = L/\mu; summing over δj=2−jΔ\delta_j = 2^{-j}\Delta down to η\eta in Eq. (228) gives O(κlog⁡(Δ/η)+σ2/(μη))O(\sqrt{\kappa}\log(\Delta/\eta) + \sigma^2/(\mu\eta)).

By contrast, for a general PL objective without convexity (Appendix F.4, Eq. (212)), there is no comparison inequality against a fixed x⋆x^\star that lets a distance potential telescope with β≫L\beta \gg L; each step uses the local LL-smooth descent bound at step size 1/L1/L, contracting the gap by 1−1/κ1 - 1/\kappa while adding variance σ2/(2LBt)\sigma^2/(2LB_t), which multiplies the statistical cost by κ\kappa in Eq. (213).

Q2: Crediting Sections 5.1 and 5.2 of Arjevani et al. (2023) for scalar sample losses and active sample reuse.

We agree with your point and thank you for pointing out. Arjevani et al. (2023) already construct scalar sample losses in Section 5.1 and consider active oracles allowing sample reuse in Section 5.2. In the revised version, we will explicitly credit Sections 5.1 and 5.2 of Arjevani et al. (2023) for both of these ideas, and state clearly in Sections 4 and 5 that our new contribution is constructing scalar sample losses with almost surely bounded gradient noise and proving that the lower bounds continue to hold when samples are reused adaptively (along with our extensions to global PL, strongly convex, convex, and finite-sum problems).

Q3: Including supporting calculations for the smaller constants in the revised version.

We agree that a verbal summary alone is not enough to verify the smaller constants, since checking them requires tracing the first- and second-derivative bounds of the modified gate and cutoff functions through Lemmas 15-18 and Lemma 24. We will include the explicit supporting calculations for these reduced constants in Appendices B and C of the revised manuscript.

Thank you for your response. Equation 226 addresses my point about the factor κ\kappa. The observation about convex PL objectives is clean: Even if there are multiple minimizers, we can use the closest one at the start of each stage. We use the same minimizer for every step in that stage. Then quadratic growth gives the same distance bound as in the strongly convex case, and the statistical rate remains O(σ2/(μη))O(\sigma^2/(\mu\eta)).

Small remark: xt−x⋆x_t-x^\star points from the minimizer to the current iterate so “toward the minimizer” describes the opposite direction. The inequality is correct.

I will keep my score. For me, the paper’s main contribution is theoretical. Do the classical worst case rates in stochastic optimization require rare, arbitrarily large gradient errors? The authors show that the same rates can occur even when gradient errors are uniformly bounded by σ\sigma. As a consequence, in this setting, any noise class between bounded noise and bounded variance has the same worst case rate in expectation at the same noise scale. I consider this result significant because it gives the community a clearer understanding of the role of noise in worst case behavior, regardless of how common bounded noise is in ML applications.

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

This paper studies minimax stochastic first-order complexity under uniformly almost-surely bounded gradient noise. It establishes matching upper and lower bounds for smooth nonconvex, globally PL, strongly convex, and convex objectives, with additional results for centered-noise regularity, finite sums, relative noise, higher-order population smoothness, and restricted sample reuse. The main technical contribution is a bounded continuous encoding of hidden directions, combined with an information argument that accommodates adaptive sample reuse and exact function values at charged query points.

Critical strengths

An almost-sure uniform bound on gradient error is substantially stronger than a variance bound. Standard lower-bound constructions based on rare, amplified responses do not automatically satisfy this restriction. Establishing that the familiar nonconvex statistical barrier persists in this smaller oracle class is therefore meaningful;

The Poisson-kernel encoding provides bounded observations with the required mean and controlled relative entropy. Importantly, the analysis controls the information carried by an entire stored code rather than treating repeated evaluations of the same sample as independent observations. The framework also accounts for adaptive queries, exact population and sample values at charged points, and outputs that were never queried.

Critical weaknesses

The lower bounds take a worst case over all finite dimensions and allow the hard dimension to grow with the announced budget and KK. Thus, the absence of a KK improvement in the stated minimax rates does not establish an absence of parallel-query gains at fixed dimension. For example, the block dimension in Eq. (73) grows at least linearly with the number of charged query points, while the total dimension also includes the chain length. An explicit dimension bound in the main results would make this distinction easier to assess.

Gradient evaluations, shared-sample KK-point rounds, and distinct samples are different resources. In particular, a round in the paper uses one shared sample at several preselected points, which differs from parallel minibatch with independent samples. Although the definitions are given, a single model-comparison table would help readers avoid interpreting results from one access model as conclusions about another.

Questions for authors

For Theorems 1 and 4, what total ambient dimension suffices as a function of the target accuracy, noise level, condition number, query budget, and KK?

Beyond the scaling calculation T≍κT\asymp\kappa, what is the geometric reason that a general PL objective can force a separate statistical cost at successive stages, whereas strong convexity permits the statistical term to avoid the additional κ\kappa factor?

The paper establishes a statistical complexity separation between general PL objectives and strongly convex objectives. What happens for the intermediate class of objectives that are convex and satisfy the global PL condition, but are not necessarily strongly convex?

1 comment

Thank you for the careful review and constructive feedback.

Q1: What total ambient dimension suffices in Theorems 1 and 4? Each construction places TT stages in orthogonal coordinate blocks of dimension DD, so the ambient dimension is d=TDd = TD. Let MM be the number of queried points plus one for the final output: M=N+1M = N + 1 for an evaluation budget NN, or M=RK+1M = RK + 1 for RR rounds of KK points. Across our constructions, Eq. (73) and Eq. (116) set the block dimension to D=Θ(M+log⁡T)D = \Theta(M + \log T).

In Theorem 1, with Q=ΔL/ε2Q = \Delta L/\varepsilon^2 and m=σ2/ε2m = \sigma^2/\varepsilon^2, the chain uses T=Θ(Q)T = \Theta(Q) stages, so d=Θ(Q(M+log⁡Q))d = \Theta(Q(M + \log Q)) suffices for any announced budget MM. At the minimax round budget R≍Q(1+m)R \asymp Q(1 + m) for (5) (setting K=1K = 1 for single-point evaluations), this becomes d=O(KQ2(1+m))=O(KΔ2L2ε4(1+σ2ε2)).d = O(KQ^2(1 + m)) = O\left(K\frac{\Delta^2 L^2}{\varepsilon^4}\left(1 + \frac{\sigma^2}{\varepsilon^2}\right)\right).

In Theorem 4, with κ=L/μ\kappa = L/\mu, S=σ2/(μη)S = \sigma^2/(\mu\eta), and Dκ=1+log⁡(Δ/η)/log⁡(κ/(κ−1))D_\kappa = 1 + \log(\Delta/\eta)/\log(\kappa/(\kappa - 1)), the chain for PL objectives uses T=Θ(κ)T = \Theta(\kappa) stages in (11), which requires d=O(Kκ2S)d = O(K\kappa^2 S) at the minimax round budget R≍κSR \asymp \kappa S. For the deterministic term, the chain with geometrically decreasing weights for large κ\kappa uses T=Θ(Dκ)T = \Theta(D_\kappa) stages and needs d=Θ(Dκ(M+log⁡Dκ))=O(KDκ2)d = \Theta(D_\kappa(M + \log D_\kappa)) = O(KD_\kappa^2) at R≍DκR \asymp D_\kappa, while for bounded κ>1\kappa > 1 the smaller projection threshold in Lemma 26 multiplies DD by an additional factor of order (Δ/η)(κ−1)−2(\Delta/\eta)(\kappa - 1)^{-2}.

We agree that because DD grows linearly with RKRK, our minimax bounds apply when the ambient dimension can exceed RKRK, and do not rule out speedups from KK parallel queries when the dimension dd is fixed in advance. We will state these dimension bounds explicitly in the main theorems, clarify this distinction in Section 2, and add a summary table comparing the access models.

Q2: What is the geometric reason that a general PL objective forces a separate statistical cost at successive stages, whereas strong convexity avoids the κ\kappa factor? Under μ\mu-strong convexity, any point with objective gap δ=F(x)−F⋆\delta = F(x) - F_\star lies within distance 2δ/μ\sqrt{2\delta/\mu} of the minimizer x⋆x_\star, and the population gradient at every point has a positive inner product with the displacement x−x⋆x - x_\star. Because noisy gradients queried anywhere along the path point on average toward the same global minimizer x⋆x_\star, an algorithm can average out noise across the entire trajectory. The statistical cost is therefore set solely by the radius η/μ\sqrt{\eta/\mu} of the η\eta-sublevel set near the solution, which requires Θ(σ2/(μη))=Θ(S)\Theta(\sigma^2/(\mu\eta)) = \Theta(S) samples regardless of LL.

A general PL objective only requires the local gradient norm to dominate the remaining gap, ∥∇F(x)∥2≥2μ(F(x)−F⋆)\|\nabla F(x)\|^2 \ge 2\mu(F(x) - F_\star), without forcing the gradient to point toward the global minimizer. Geometrically, this allows the objective to form a curved valley that makes T≍κT \asymp \kappa orthogonal turns. Because later turns remain completely flat until the current turn is crossed, noisy gradients collected before reaching stage jj carry no information about the hidden direction of stage jj. Unlike in the strongly convex case, the algorithm cannot pool noisy gradients from earlier parts of the trajectory to estimate the final target location; instead, each turn presents a fresh, statistically independent directional estimation problem of cost SS, so traversing all Θ(κ)\Theta(\kappa) turns costs Θ(κS)\Theta(\kappa S).

Q3: What happens for the intermediate class of objectives that are convex and satisfy the global PL condition?

For objectives that are convex, LL-smooth, and globally μ\mu-PL, the extra κ\kappa factor in the statistical term disappears, and the optimal complexity matches the strongly convex rate Θ(Eκ+S)\Theta(E_\kappa + S) for all κ≥1\kappa \ge 1. The lower bound Ω(Eκ+S)\Omega(E_\kappa + S) follows from Theorem 5 because every μ\mu-strongly convex, LL-smooth function is both convex and globally μ\mu-PL. For the upper bound, any smooth bounded-below convex function satisfying the global μ\mu-PL inequality has a nonempty, closed, and convex set of minimizers X⋆X_\star, and satisfies the quadratic growth bound ∥x−ΠX⋆(x)∥2≤2μ(F(x)−F⋆)\|x - \Pi_{X_\star}(x)\|^2 \le \frac{2}{\mu}(F(x) - F_\star), where ΠX⋆\Pi_{X_\star} denotes Euclidean projection onto X⋆X_\star (Karimi et al., 2016). In Appendix F.6, the restarted accelerated proof in Lemma 39 uses strong convexity only to bound the squared distance from each stage's starting point to its closest minimizer by 2δj/μ2\delta_j/\mu, so quadratic growth together with convexity and LL-smoothness yields the same O(Eκ+S)O(E_\kappa + S) upper bound. We will add this result in Section 3.2.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.