- 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 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 . 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 and 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
-
Can the authors give more examples of ML problems where holds naturally? Is there any empirical evidence that this is a reasonable model for modern training problems?
-
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?
-
How essential is the opaque retained-sample model? Would the lower bounds still hold if the algorithm could inspect the underlying data sample directly?
-
The round lower bounds assume fixed finite , while the hard dimension may depend on . What changes if is allowed to grow with the target accuracy or total budget?
-
Is the condition in the higher-order result mainly a proof limitation, or do the authors expect a genuinely different rate outside this regime?
-
Do the authors expect the finite-sum PL and strongly convex results to extend to ?
-
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 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- 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 -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 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 (Page 62) and empirically across four orders of magnitude of parameter norm (Table 2). When a representation passes through LayerNorm or RMSNorm before an output layer , the normalized vector satisfies for every input and every backbone parameter . Under softmax, cosine-similarity contrastive, or Bradley-Terry preference losses, the logit derivative has norm at most , so the head noise satisfies globally on .
Likewise, for a two-layer nonlinear network with -Lipschitz loss and , the bounds and and cancellation of the penalty yield
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 ( for nonconvex, for PL, for strongly convex, for convex, relative noise, and higher-order smoothness) hold under the standard single-query fresh-sample first-order oracle () without any retained-sample handle.
Second, although supervised learning examples 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 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 , , and (Lemma 21) reduce to minimax mean estimation from the raw observations 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
Thank you for the thoughtful review and questions.
Q1: More examples of ML problems where supx∥g(x;ξ)−∇F(x)∥≤σ holds naturally, and practical motivation.
Uniformly bounded gradient noise arises whenever the per-sample loss is G-Lipschitz with respect to the parameters on bounded or normalized inputs, which guarantees ∥g(x;ξ)−∇F(x)∥≤2G for every x. This holds even when the objective includes an unbounded regularizer such as 2λ∥x∥2, which cancels in g(x;ξ)−∇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 and σ2/(μη) 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) 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, K-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) and Ω(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 V 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 xt and xt−1 via backpropagation, since an algorithm with unlimited computation that could read the full formula of f(⋅;ξ) could minimize the empirical risk without taking gradient steps.
Q4: What changes if K is allowed to grow with the target accuracy or total budget?
When the ambient dimension d is chosen after K and the round budget R, Lemma 13 holds with the same constants for any finite K: all K points in a round share one sample, so a round still advances progress along the chain by at most one stage and K only increases the block dimension D=Θ(RK+logT). When d is fixed in advance and RK≳d, the spherical concentration argument no longer applies because K simultaneous points can span Ω(min{K,d}) directions in a single round.
Q5: Is Q≤(1+m)(1+Cp) in Theorem 7 a proof limitation or a genuinely different regime?
We expect a genuinely different rate outside this regime (when m is small and Ap≪Q). In the noiseless case σ=0 with p=2, deterministic first-order methods under Lipschitz Hessians achieve O(ε−7/4) against a lower bound of Ω(ε−12/7) (Carmon et al., 2021), which sits strictly between our lower bound Ω(ε−3/2) and upper bound O(ε−2). When Q≤(1+m)(1+Cp), the stochastic term mCp dominates and closes this gap.
Q6: Do the finite-sum PL and strongly convex results extend to n<S?
Not with the online formulas unchanged: when n<S (for instance, as η→0 at fixed n), evaluating all n components gives the exact gradient ∇F(x) in n calls, yielding upper bounds O(nDκ) and O(nEκ) that grow as log(Δ/η) rather than linearly like S=σ2/(μη).
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 regularization (λ=10−2), comparing the maximum per-sample gradient error maxi∥ζi(xt)∥ to the root-mean-square error. Across the trajectory, maxi∥ζi∥ stayed in [1.01,1.11] (ratio in [6.77,7.32]) for 10-class softmax on Digits, and in [0.52,0.74] (ratio in [2.15,2.98]) for Cauchy regression on Diabetes; we will add this study to the appendix.