- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper studies stochastic nonconvex optimization under a generalized Blum--Gladyshev (BG-) noise model, where the variance of the stochastic gradient can grow polynomially with the distance from initialization: \begin{align*} \mathbb{E}_{\xi}\left[ \Vert \nabla f(x;\xi)-\nabla f(x)\Vert^2 \right] \le B^2\Vert x-x_0\Vert^a+G^2. \end{align*} The paper first empirically investigates stochastic gradient noise in large language model pretraining and observes subquadratic growth of the noise variance with respect to the distance from initialization. Motivated by this observation, the authors introduce the BG- model, which interpolates between bounded-variance noise and the classical BG-0 setting. The main theoretical contribution is an information-theoretic stochastic first-order oracle lower bound under the BG- model. For , the paper derives a lower bound with -dependence , and develops dynamically batched SGD and SGDM algorithms achieving an upper bound with the same -dependence. The proposed batch-size rules adapt to the distance of the current iterate from initialization in order to control the distance-dependent noise. The paper also proposes a practical adaptive batch-size scheduler and evaluates it on OLMo2 pretraining on C4. The experiments show that the proposed scheduler can improve validation loss over fixed small- and large-batch baselines while using substantially fewer optimization iterations.
Critical strengths
-
The BG- noise model is practically motivated and provides a useful generalization of existing assumptions. The empirical investigation of stochastic gradient noise in large language model pretraining provides a meaningful motivation for considering variance that grows with the distance from initialization. The proposed BG- model offers a continuous interpolation between bounded variance and quadratic growth, making the theoretical framework potentially useful for understanding a broader range of stochastic optimization regimes.
-
The paper combines lower-bound analysis, algorithm design, and large-scale empirical validation. The paper does not merely propose a heuristic batch-size scheduler. It provides an information-theoretic lower bound, matching upper bounds for dynamically batched SGD/SGDM, and experiments on language-model pretraining. This combination gives the work a coherent theoretical-to-practical narrative, and the empirical results suggest that the proposed scheduling principle can be useful in realistic large-scale training.
Critical weaknesses
-
The claimed matching between the upper and lower bounds is not fully justified at the level of the displacement analysis. A central claim of the paper is that the upper and lower bounds match in their -dependence. However, the connection between the displacement behavior used in the upper-bound analysis and that underlying the lower-bound construction is not sufficiently clear. In the upper-bound proof, Eq. (54) gives \begin{align*} \mathbb{E}\Vert x_t-x_0\Vert^2 \le 4\eta T\Delta + 2L\eta^3T^2\sigma^2 + 2\eta^2T\sigma^2, \end{align*} and hence an bound on the squared displacement. This estimate is then used, via Jensen's inequality, to control the distance-dependent noise and the required batch size. In contrast, the lower-bound construction relies on instances for which finding an -stationary point requires reaching a distance of order from initialization. Thus, the lower bound exploits a specific large-displacement mechanism to generate the distance-dependent noise. It is not clear that the displacement estimate used in the upper-bound proof is tight enough to capture the same mechanism. Consequently, while the final exponents coincide, the paper does not yet establish that the upper bound is tight with respect to the underlying displacement-dependent difficulty. Clarifying this point is important for the paper's claim of a matching characterization.
-
There is a gap between the theoretical guarantees and the optimizer used in the main practical experiments. The main theoretical results concern dynamically batched SGD and SGDM, whereas the large-scale language-model experiments use AdamW. Although the paper proposes a batch-size and learning-rate scaling rule for AdamW, the theoretical analysis does not directly cover AdamW or its adaptive moment estimates. Thus, the experiments demonstrate the practical usefulness of the proposed scheduling principle for AdamW, but they do not directly validate the theoretical mechanism established for SGD/SGDM. The paper should more clearly distinguish the theoretically established results from the empirical extension to AdamW.
Questions for authors
-
Tightness of the displacement analysis. The main theoretical claim is that the upper and lower bounds match in their -dependence. Could the authors clarify the relationship between the displacement bound used in the upper-bound proof and the displacement required by the lower-bound construction? In particular, Eq. (54) gives \begin{align*} \mathbb{E}\Vert x_t-x_0\Vert^2=O(T+T^2), \end{align*} which is then used to control the distance-dependent noise, whereas the lower-bound construction relies on reaching a distance of order from initialization. Is the displacement bound in Eq. (54) tight in the regime relevant to the final complexity bound? If not, in what precise sense should the resulting upper bound be viewed as matching the lower bound?
-
Meaning of the matching complexity. The lower bound applies to arbitrary algorithms accessing the BG- stochastic first-order oracle, whereas the upper bound is established for particular dynamically batched SGD/SGDM algorithms. Could the authors clarify whether the result should be interpreted as a minimax-optimal characterization of the oracle complexity, or primarily as a matching rate within the considered algorithmic framework?
-
Connection to AdamW. The main practical experiments use AdamW, while the theoretical guarantees are established for SGD and SGDM. Could the authors clarify which aspects of the BG- analysis are expected to extend to AdamW? In particular, is there a theoretical reason to expect the proposed distance-dependent batch-size rule and the learning-rate scaling used for AdamW to preserve the benefits established for SGD/SGDM?
-
Sensitivity to the BG- parameters. The practical scheduler depends on estimates of , , , and the target variance level. How sensitive is the performance to errors in these estimates? In particular, would the proposed scheduler remain effective if were estimated only approximately from an early stage of training?
-
Choice of the target variance. The theoretical batch-size rule depends on a target variance parameter , while the practical implementation estimates this quantity from a small-batch baseline. How should be selected when such a baseline is unavailable or too expensive to obtain? How sensitive are the empirical results to this choice?
6 comments
Response to Reviewer Dauf (2/3)
W2 and Q3: Connection to AdamW: Gap between the theoretical guarantees and the optimizer used in the main practical experiments.
We thank the reviewer for this point. To reduce the gap between theory and practice, in Theorem 4 of the revised manuscript (Appendix F), we analyze SignSGD with momentum (Bernstein et al. 2018) as a proxy for Adam, as they share multiple key features, such as nonlinear updates, coordinate-wise map of the momentum estimate, and the fact that the size of each coordinate does not depend on the gradient magnitude. We also show that the per-coordinate update of Adam is bounded by a constant multiple of its step size whenever , which is satisfied in practice and in our experiments .
Learning rate scaling: We adopt the rule from existing practice for Adam (Malladi et al., 2022; Merrill et al., 2026). We evaluate the effect of using the sqrt learning rate scaling rule, directly in the ablation below, where we report the validation loss averaged over seeds. (Due to the limited time available during the rebuttal period, we excluded the 1B model.)
| Model | Optimizer | Learning rate scaling | Validation loss |
|---|---|---|---|
| OLMo2-100M | AdamW | 3.4522 | |
| OLMo2-100M | AdamW | 3.4347 | |
| OLMo2-100M | AdamW | 3.6509 | |
| OLMo2-600M | AdamW | 2.8840 | |
| OLMo2-600M | AdamW | 2.8482 | |
| OLMo2-600M | AdamW | 3.1088 |
The best performance is obtained when the learning rate is scaled by while the batch size grows by a factor of , which is the rule used in our experiments. Without scaling (), BG- still attains a lower validation loss than the small batch baseline. Hence, the gains of BG- do not rely solely on the learning rate scaling, although the rule improves them further.
Merrill et al. use the same rule and argue that linear () scaling is suboptimal for Adam-based optimizers, consistent with the SDE analysis of Malladi et al. Intuitively, the learning rate must grow with the batch size for small and large-batch training to be comparable, since otherwise their per-step updates differ a lot in magnitude. However, a very large learning rate can cause unstable gradient updates for large batches resulting in suboptimal performance, which we observe in our experiments.
Q2: Meaning of the matching complexity.
We thank the reviewer for this question. Our results should be interpreted as a minimax-optimal characterization of the oracle complexity over the BG- class for , and not only as a matching rate within the dynamically batched SGD and SGDM.
To be precise, let denote all pairs where is -smooth with and is an unbiased BG- oracle. In this setting, the minimax optimal complexity is where the infimum is over all adaptive randomized algorithms that guarantee on every instance in , and is the number of oracle calls.
Under this setting:
Lower bound: Theorem 1 bounds from below in sufficiently large dimensions, for arbitrary algorithms, including unbounded queries, arbitrary output points, and random stopping times.
Upper bound: Dynamically batched SGD(M) with a uniformly sampled output iterate is one algorithm in this infimum, where the analysis only relies on unbiasedness and the proposed BG- variance bound (see our assumptions for formal definitions). Theorems 2 and 3 therefore bound from above over the same class.
Thus, the proofs of SGD(M) with dynamic batching show that the proposed lower bound is indeed achievable. Together, the two bounds (lower and upper) results generate .
The proposed match also extends beyond the dependence on , e.g., as Theorem 2 only requires , we may choose . Since , this returns which matches all three terms of the lower bound in Theorem 1 up to absolute constants for (the same holds for SGDM with fixed ).
We added this discussion to Appendix B.4 of the revised manuscript.
Response to Reviewer Dauf (3/3)
Q4: Sensitivity to the BG- parameters.
We thank the reviewer for this question. We added an ablation study to Appendix G.3 of the revised manuscript. Using the distance logged throughout the BG- runs in Table 1, we recompute the variance ratio in Eq. (12) after perturbing one of , , and by , while keeping the other two at their fitted values. The results are summarized below.
| Peak variance ratio | OLMo2-100M | OLMo2-600M | OLMo2-1B |
|---|---|---|---|
| Fitted | 9.3 | 13.5 | 21.7 |
| or perturbed by | 8.5 to 10.2 | 12.2 to 14.8 | 19.7 to 23.9 |
| increased by | 13.1 () | 22.5 () | 39.3 () |
| decreased by | 6.7 () | 8.2 () | 12.1 () |
Perturbing or changes the peak variance ratio by at most for all three models. Since the multiplier depends on and only through , a error in either parameter has nearly the same effect. Hence, the scheduler tolerates small errors in and . However, the exponent has a much larger effect, which grows with model size. A change in changes the peak variance ratio by up to , , and for the three models, and changes the largest batch size by up to one doubling. This is because the ratio depends on through , and both the displacement and the fitted exponent are larger for larger models. Hence, is the parameter that requires the most care, especially for larger models.
These results also show that fixing the exponent in advance is restrictive, e.g., the BG-0 noise model corresponds to , which differs from the fitted exponents of , , and by , , and , respectively. These differences are far larger than the perturbations that already change the largest batch size by up to one doubling. As shown in Section 2, the fitted also describes the measured variance growth better than BG-0.
Q5: Choice of the target variance.
We thank the reviewer for this question. Dependence on a variance level is standard in the analysis of stochastic methods. Under bounded variance, the step size of Ghadimi & Lan (2013) is tuned using the noise level , and the mini-batch analysis of Ghadimi, Lan & Zhang (2016) also sets the batch size using . The resulting term cannot be improved in general (Arjevani et al., 2023). In our setting, the corresponding unavoidable noise dependence is the and terms in Theorem 1.
Note that the target in Theorems 2 and 3 is different from these oracle constants, since we use it as the noise level that the algorithm chooses to maintain. It still plays the role of the batch size as in classical mini-batch SGD, where an oracle variance and a batch size correspond to a mini-batch variance of .
Theorem 2 holds for every , with cost Note that the distance-dependent term does not depend on . For every , we also have , so the bound is unchanged up to a factor of two across this range. As in our answer above, a canonical choice that requires no additional tuning is , which attains all three terms of the lower bound. When , we have , which is the exact practical ratio that we use in our proposed scheduler.
We would also like to clarify that our implementation does not estimate from a small-batch baseline. The multiplier in Eq. (12) depends on , and cancels in it. The only remaining role of is through the initial batch size, where selecting corresponds to the target . Hence, a baseline run is not required. Choosing the target corresponds to choosing , which is the initial batch size hyperparameter that any training run must set. In our experiments, we set equal to the small-batch baseline so that both methods start from the same batch size and learning rate (Appendix H). Without such a baseline, can be set according to the available compute budget.
Response to Reviewer Dauf (1/3)
W1 and Q1: The claimed matching between the upper and lower bounds is not fully justified at the level of the displacement analysis / Tightness of the displacement analysis.
We thank the reviewer for raising this point. In Appendix E of the revised manuscript, we show that the displacement estimate is tight up to constants when we directly utilize the Stage 1 hard instance from Appendix B. Under this setting, we show that dynamically batched SGD(M) reaches a distance of at least D=Δ/(4ϵ) within the first T/16 iterations and remains at least that far from initialization for the rest of its prescribed iteration budget. This yields a direct connection between the displacement used in the upper-bound analysis and the geometry of the lower-bound construction.
We would also like to clarify that Eq. (54) is stated without substituting the algorithm's parameters. In Theorem 2, η=ϵ2/(2Lσ2) and T=⌈4Δ/(ηϵ2)⌉, so 4Δ/ϵ2≤ηT≤5Δ/ϵ2. Substitution into Eq. (54) and using ϵ2≤LΔ:
\le 4\eta T\Delta+2L\eta^3T^2\sigma^2+2\eta^2T\sigma^2 \le (20+25+5)\frac{\Delta^2}{\epsilon^2} =\frac{50\Delta^2}{\epsilon^2}.$$ The revised SGDM analysis gives the same bound (Eq. (96)). Thus, the apparent $O(T+T^2)$ expression corresponds to a root-mean-square displacement of at most $\sqrt{50}\Delta/\epsilon$ under the prescribed parameters. In Appendix E (Proposition 2), we apply SGD and SGDM to $f(u,y)=f_0(u)+\phi(u)f_{\mathrm{scaled}}(y)$. Denoting $V(r):=B^2r^a+G^2$, the proof consists of three steps: 1. **The travel coordinate never decreases.** The oracle's travel-coordinate component is exact, with $\partial_u f\le -2\epsilon$ for $u\le D$ and $\partial_u f\le 0$ everywhere. Hence the travel-coordinate component of momentum is nonpositive, and $u_t$ is nondecreasing on every realization. 2. **The iterates reach $D$ early.** Before reaching $D$, unrolling momentum produces $u_t\ge 2\epsilon\eta(t-\beta/(1-\beta))$. Therefore, our algorithms reach $D$ no later than $$\bar t:=\left\lceil\frac{D}{2\epsilon\eta}+\frac{\beta}{1-\beta}\right\rceil \le\frac{T}{16},$$ where the last inequality follows from the accuracy conditions in Proposition 2. Consequently, $\\|x_t-x_0\\|\ge D$ for every $\bar t\le t<T$, almost surely. 3. **The batch rule forces the sample cost.** Both algorithms satisfy $\eta T\ge4\Delta/\epsilon^2$ and $b_t\ge(2L\eta/\epsilon^2)V(\\|x_t-x_0\\|)$. Since at least $15T/16$ iterations have displacement at least $D$, $$\sum_{t=0}^{T-1}b_t \ge\frac{15T}{16}\frac{2L\eta}{\epsilon^2}V(D) \ge\frac{15}{2}L\Delta\,\epsilon^{-4} \left[G^2+B^2\left(\frac{\Delta}{4\epsilon}\right)^a\right].$$ Combining the pathwise displacement lower bound with the upper bounds results in, for every $\bar t\le t<T$, $$\frac{\Delta^2}{16\epsilon^2} \le\mathbb{E}\\|x_t-x_0\\|^2 \le\frac{50\Delta^2}{\epsilon^2},$$ and, for $0\le a\le2$, $$\left(\frac{\Delta}{4\epsilon}\right)^a \le\mathbb{E}\\|x_t-x_0\\|^a \le\left(\mathbb{E}\\|x_t-x_0\\|^2\right)^{a/2} \le50^{a/2}\left(\frac{\Delta}{\epsilon}\right)^a.$$ Thus, both the second-moment displacement estimate and its conversion to the $a$-th moment through Jensen's inequality are tight up to constants on at least $15/16$ of the iterations. The distance-dependent contribution to the prescribed batch cost is therefore $\Theta(B^2L\Delta^{a+1}\epsilon^{-(4+a)})$, in the worst case under the prescribed iteration budgets. The same scale explains the noise-dependent term in the lower bound, a chain of length $\Theta(L\Delta/\epsilon^2)$ is multiplied by the reveal factor $1/p=1+\Theta_a(V(\Delta/\epsilon)/\epsilon^2)$. Both analyses therefore correspond to a noise-dependent cost of order $L\Delta\,V(\Delta/\epsilon)\,\epsilon^{-4}$ for fixed $a$. Note that Theorems 1–3 already establish the minimax match for $a\in [0,2]$, as SGD(M) with dynamic batching attains the matching rate with our lower bounds in Theorem 1. We strengthen this relation in Appendix E by showing explicitly that the intermediate displacement and moment estimates are also tight on the Stage 1 hard instance.