acceptodds
Under review as a conference paper at ICLR 2027

Why Does Adaptive Batching Help LLM Pretraining? A Perspective from Unbounded Variance

Abstract

Increasing the batch size during training is a common practice in large language model (LLM) pretraining, yet the theoretical justification behind its success is not well understood. Analyses of stochastic optimization often assume uniformly bounded stochastic gradient variance, yet recent evidence suggests that this assumption fails in many practical nonconvex problems. The Blum–Gladyshev (BG-) noise model relaxes this assumption by allowing the variance to grow quadratically with the distance from initialization, suggesting that batch size schedulers can help by controlling the variance growth during training. However, this growth can be overly conservative in practice. We empirically investigate variance growth in LLM pretraining and observe that a generalized BG model with a tunable growth exponent provides a tighter description of practical noise behavior. Motivated by this observation, we introduce the generalized BG- noise model, which interpolates between bounded variance () and BG- noise (). Under -smoothness, we derive an information-theoretic lower bound with growth-dependent oracle complexity and establish a matching upper bound in -dependence by increasing the batch size as the iterates move away from initialization. Finally, we propose an adaptive batch scheduler that controls variance growth through dynamic batch size adjustments during training. In pretraining OLMo2 models of up to 1B parameters on C4, our scheduler achieves a lower validation loss than both small and large batch training under matched token budgets, while using less than 10% of the iterations of small batch training.

Primary area:
optimization
Keywords:
LLM Pretraining, Nonconvex Stochastic Optimization, Blum-Gladyshev Noise, Unbounded Variance, Adaptive Batch Size

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DaufOpenReview ↗
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-aa) 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-aa 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-aa model. For 0≤a≤20\le a\le 2, the paper derives a lower bound with ϵ\epsilon-dependence Ω(ϵ−(4+a))\Omega(\epsilon^{-(4+a)}), and develops dynamically batched SGD and SGDM algorithms achieving an upper bound with the same ϵ\epsilon-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
  1. The BG-aa 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-aa 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.

  2. 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
  1. 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 ϵ\epsilon-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 O(T+T2)O(T+T^2) 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 ϵ\epsilon-stationary point requires reaching a distance of order Δ/ϵ\Delta/\epsilon 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 ϵ−(4+a)\epsilon^{-(4+a)} 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.

  2. 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
  1. Tightness of the displacement analysis. The main theoretical claim is that the upper and lower bounds match in their ϵ\epsilon-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 Δ/ϵ\Delta/\epsilon 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 ϵ−(4+a)\epsilon^{-(4+a)} upper bound be viewed as matching the lower bound?

  2. Meaning of the matching complexity. The lower bound applies to arbitrary algorithms accessing the BG-aa 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?

  3. 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-aa 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 k\sqrt{k} learning-rate scaling used for AdamW to preserve the benefits established for SGD/SGDM?

  4. Sensitivity to the BG-aa parameters. The practical scheduler depends on estimates of aa, BB, GG, and the target variance level. How sensitive is the performance to errors in these estimates? In particular, would the proposed scheduler remain effective if aa were estimated only approximately from an early stage of training?

  5. Choice of the target variance. The theoretical batch-size rule depends on a target variance parameter σ2\sigma^2, while the practical implementation estimates this quantity from a small-batch baseline. How should σ2\sigma^2 be selected when such a baseline is unavailable or too expensive to obtain? How sensitive are the empirical results to this choice?

6 comments
AuthorsOpenReview ↗

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ϵ)D=\Delta/(4\epsilon) within the first T/16T/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)\eta=\epsilon^2/(2L\sigma^2) and T=⌈4Δ/(ηϵ2)⌉T=\lceil4\Delta/(\eta\epsilon^2)\rceil, so 4Δ/ϵ2≤ηT≤5Δ/ϵ24\Delta/\epsilon^2\le\eta T\le5\Delta/\epsilon^2. Substitution into Eq. (54) and using ϵ2≤LΔ\epsilon^2\le L\Delta:

\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.
AuthorsOpenReview ↗

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 β12<β2\beta_1^2<\beta_2, which is satisfied in practice and in our experiments (0.9,0.95)(0.9,0.95).

Learning rate scaling: We adopt the k\sqrt{k} 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 33 seeds. (Due to the limited time available during the rebuttal period, we excluded the 1B model.)

ModelOptimizerLearning rate scalingValidation loss
OLMo2-100MAdamW113.4522
OLMo2-100MAdamWk\sqrt{k}3.4347
OLMo2-100MAdamWkk3.6509
OLMo2-600MAdamW112.8840
OLMo2-600MAdamWk\sqrt{k}2.8482
OLMo2-600MAdamWkk3.1088

The best performance is obtained when the learning rate is scaled by k\sqrt{k} while the batch size grows by a factor of kk, which is the rule used in our experiments. Without scaling (f(k)=1f(k)=1), BG-aa still attains a lower validation loss than the small batch baseline. Hence, the gains of BG-aa do not rely solely on the learning rate scaling, although the k\sqrt{k} rule improves them further.

Merrill et al. use the same rule and argue that linear (kk) 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-aa class for a∈[0,2]a\in[0,2], and not only as a matching rate within the dynamically batched SGD and SGDM.

To be precise, let P\mathcal{P} denote all pairs (f,g)(f,g) where ff is LL-smooth with f(x0)−finf⁡≤Δf(x_0)-f^{\inf}\le\Delta and gg is an unbiased BG-aa oracle. In this setting, the minimax optimal complexity is C(ϵ)=inf⁡A sup⁡(f,g)∈P E[τ],\mathcal{C}(\epsilon)=\inf_{\mathcal{A}}\ \sup_{(f,g)\in\mathcal{P}}\ \mathbb{E}[\tau], where the infimum is over all adaptive randomized algorithms that guarantee E∣∇f(x^)∣2≤ϵ2\mathbb{E}\\|\nabla f(\hat{x})\\|^2\le\epsilon^2 on every instance in P\mathcal{P}, and τ\tau is the number of oracle calls.

Under this setting:

Lower bound: Theorem 1 bounds C(ϵ)\mathcal{C}(\epsilon) 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-aa variance bound (see our assumptions for formal definitions). Theorems 2 and 3 therefore bound C(ϵ)\mathcal{C}(\epsilon) 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 C(ϵ)=Θ(ϵ−(4+a))\mathcal{C}(\epsilon)=\Theta(\epsilon^{-(4+a)}).

The proposed match also extends beyond the dependence on ϵ\epsilon, e.g., as Theorem 2 only requires ϵ2≤min⁡{2σ2,LΔ}\epsilon^2\le\min\{2\sigma^2,L\Delta\}, we may choose σ2=max⁡{G2,ϵ2/2}\sigma^2=\max\{G^2,\epsilon^2/2\}. Since σ2+G2≤2G2+ϵ2/2\sigma^2+G^2\le 2G^2+\epsilon^2/2, this returns E[SFO] ≤ 5LΔϵ2+20 G2LΔϵ4+10⋅50a/2 B2LΔa+1ϵ4+a,\mathbb{E}[\mathrm{SFO}]\ \le\ \frac{5L\Delta}{\epsilon^{2}}+\frac{20\,G^2L\Delta}{\epsilon^{4}}+\frac{10\cdot 50^{a/2}\,B^2L\Delta^{a+1}}{\epsilon^{4+a}}, which matches all three terms of the lower bound in Theorem 1 up to absolute constants for a∈[0,2]a\in[0,2] (the same holds for SGDM with fixed β\beta).

We added this discussion to Appendix B.4 of the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer Dauf (3/3)

Q4: Sensitivity to the BG-aa parameters.

We thank the reviewer for this question. We added an ablation study to Appendix G.3 of the revised manuscript. Using the distance ∣xt−x0∣\\|x_t-x_0\\| logged throughout the BG-aa runs in Table 1, we recompute the variance ratio 1+(B2/G2)∣xt−x0∣a1+(B^2/G^2)\\|x_t-x_0\\|^a in Eq. (12) after perturbing one of BB, GG, and aa by ±5%\pm5\%, while keeping the other two at their fitted values. The results are summarized below.

Peak variance ratioOLMo2-100MOLMo2-600MOLMo2-1B
Fitted (B,G,a)(B,G,a)9.313.521.7
BB or GG perturbed by ±5%\pm5\%8.5 to 10.212.2 to 14.819.7 to 23.9
aa increased by 5%5\%13.1 (+40%+40\%)22.5 (+67%+67\%)39.3 (+82%+82\%)
aa decreased by 5%5\%6.7 (−28%-28\%)8.2 (−39%-39\%)12.1 (−44%-44\%)

Perturbing BB or GG changes the peak variance ratio by at most 10%10\% for all three models. Since the multiplier depends on BB and GG only through B/GB/G, a 5%5\% error in either parameter has nearly the same effect. Hence, the scheduler tolerates small errors in BB and GG. However, the exponent has a much larger effect, which grows with model size. A 5%5\% change in aa changes the peak variance ratio by up to 40%40\%, 67%67\%, and 82%82\% for the three models, and changes the largest batch size by up to one doubling. This is because the ratio depends on aa through ∣xt−x0∣a\\|x_t-x_0\\|^a, and both the displacement and the fitted exponent are larger for larger models. Hence, aa 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 a=2a=2, which differs from the fitted exponents of 0.980.98, 1.381.38, and 1.491.49 by 104%104\%, 45%45\%, and 34%34\%, respectively. These differences are far larger than the 5%5\% perturbations that already change the largest batch size by up to one doubling. As shown in Section 2, the fitted a<2a<2 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 σ\sigma, and the mini-batch analysis of Ghadimi, Lan & Zhang (2016) also sets the batch size using σ\sigma. The resulting LΔσ2ϵ−4L\Delta\sigma^2\epsilon^{-4} term cannot be improved in general (Arjevani et al., 2023). In our setting, the corresponding unavoidable noise dependence is the G2G^2 and B2B^2 terms in Theorem 1.

Note that the target σ2\sigma^2 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 σ2\sigma^2 and a batch size bb correspond to a mini-batch variance of σ2/b\sigma^2/b.

Theorem 2 holds for every σ2≥ϵ2/2\sigma^2\ge\epsilon^2/2, with cost O(LΔ(σ2+G2)ϵ−4+B2LΔa+1ϵ−(4+a)).\mathcal{O}\left(L\Delta(\sigma^2+G^2)\epsilon^{-4}+B^2L\Delta^{a+1}\epsilon^{-(4+a)}\right). Note that the distance-dependent term does not depend on σ2\sigma^2. For every σ2∈[ϵ2/2, G2]\sigma^2\in[\epsilon^2/2,\,G^2], we also have σ2+G2≤2G2\sigma^2+G^2\le 2G^2, 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 σ2=max⁡{G2,ϵ2/2}\sigma^2=\max\{G^2,\epsilon^2/2\}, which attains all three terms of the lower bound. When G2≥ϵ2/2G^2\ge\epsilon^2/2, we have bt=⌈1+(B2/G2)∣xt−x0∣a⌉b_t=\lceil 1+(B^2/G^2)\\|x_t-x_0\\|^a\rceil, 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 σ2\sigma^2 from a small-batch baseline. The multiplier ktk_t in Eq. (12) depends on (xt,x0,B,G,a)(x_t,x_0,B,G,a), and σ2\sigma^2 cancels in it. The only remaining role of σ2\sigma^2 is through the initial batch size, where selecting b0b_0 corresponds to the target σ2=cβG2/b0\sigma^2=c_\beta G^2/b_0. Hence, a baseline run is not required. Choosing the target σ2\sigma^2 corresponds to choosing b0b_0, which is the initial batch size hyperparameter that any training run must set. In our experiments, we set b0b_0 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, b0b_0 can be set according to the available compute budget.

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

The paper studies adaptive batching through stochastic-gradient variance that grows with distance from initialization. It introduces a BG-a variance model and gives lower and upper expected oracle-complexity bounds with matching accuracy exponents for 0≤α≤20\leq \alpha\leq2, including dynamically batched SGD and SGDM. Measurements at randomly perturbed parameter states motivate subquadratic growth and a displacement-based batch scheduler. Experiments with AdamW on OLMo2 pretraining report lower mean validation loss than small and large fixed batches at matched token budgets, alongside fewer updates and shorter training time than small-batch training.

Critical strengths
  • Theorems 1, 2, 3 provide a coherent characterization of how the distance-growth exponent changes expected oracle complexity. The upper-bound proofs cap conditional noise before controlling displacement and expected batch cost, and Proposition 1 explains why second-moment assumptions alone do not extend that cost argument beyond a=2.

  • The scheduler gives a concrete application of the model, with lower reported mean validation loss at all three tested pretraining sizes and substantially fewer updates than the small-batch runs under equal token budgets (Table 1). The explicit optimizer, batch, and timing comparisons make the practical evidence useful, even though the explanation remains incomplete.

Critical weaknesses
  • The evidence connecting the measured variance law to the claimed training mechanism is incomplete. Section 2 fits random perturbations around initialization with a constrained exponent, rather than checking the fitted law along training trajectories; Figure 3(b) shows a modeled ratio. Moreover, the tested AdamW algorithm and learning-rate scaling are outside the fixed-step SGD/SGDM guarantees, as Appendix G acknowledges. The results support a promising perspective, but this gap limits how strongly they explain the practical gains.

  • Could the intended momentum contribution be clarified against a matched-target-variance SGD comparison? In the common feasible accuracy regime, Theorem 2 with target variance σ2/cβ\sigma^2/c\beta gives the same batch rule as Theorem 3, an eight-times larger step size, and a 32-times smaller expression before rounding the iteration budget. Appendix D correctly qualifies its comparison within the SGDM parameterization. What additional mechanism is established beyond that parameterization?

Questions for authors
  • What fitting objective, weighting, and reference-gradient procedure produced (B,G,a), and what evidence supports the fitted relationship along the actual training trajectory? Please also define the ratio in Figure 3(b) and state whether warmup/cosine progress is indexed by tokens or updates.
  • What conclusion about momentum remains when SGD uses σ2/cβ\sigma^2/c\beta in the common accuracy regime of Theorems 2 and 3?
  • Theorem 1's construction requires the dimension condition in Lemma 5, equation (33). Is the intended statement existential over a sufficiently large dimension?
4 comments
AuthorsOpenReview ↗

Response to Reviewer cNGo (1/2)

Weakness 1A & Question 1B: Measured variance law to the claimed training mechanism

We thank the reviewer for their comments. We would like to state that Assumption 2 is a property of the oracle, not of the optimizer. For a fixed query point xx, let V(x):=Eξ∣∇f(x;ξ)−∇f(x)∣2V(x):=\mathbb{E}_\xi\\|\nabla f(x;\xi)-\nabla f(x)\\|^2. The expectation is taken over the sample ξ\xi only, with xx held fixed, and it is not a conditional expectation along an optimizer's trajectory. Hence, VV is a deterministic function determined by the model and the data distribution, and Assumption 2 requires

V(x)≤B2∣x−x0∣a+G2for every x∈Rd,i.e.,sup⁡∣x−x0∣=rV(x)≤B2ra+G2for every r≥0.V(x)\le B^2\\|x-x_0\\|^a+G^2\quad\text{for every }x\in\mathbb{R}^d,\qquad\text{i.e.,}\qquad \sup_{\\|x-x_0\\|=r}V(x)\le B^2r^a+G^2\quad\text{for every } r\ge0.

In our proofs, the bound is applied at the iterates. Since xtx_t is Ft\mathcal{F}_t-measurable and the samples ξt,1,…,ξt,bt\xi_{t,1},\dots,\xi_{t,b_t} are independent of Ft\mathcal{F}_t, the unbiased minibatch estimator satisfies Et∣gt−∇f(xt)∣2=V(xt)bt≤B2∣xt−x0∣a+G2bt.\mathbb{E}_t\\|g_t-\nabla f(x_t)\\|^2=\frac{V(x_t)}{b_t}\le\frac{B^2\\|x_t-x_0\\|^a+G^2}{b_t}. The iterates themselves are random and depend on the optimizer, its hyperparameters, and the realized samples. For instance, for SGD we have Et[xt+1−xt]=−η∇f(xt)\mathbb{E}_t[x_{t+1}-x_t]=-\eta\nabla f(x_t), so the displacement xt−x0x_t-x_0 is biased toward descent directions of ff rather than spread over the sphere {x:∣x−x0∣=r}\{x:\\|x-x_0\\|=r\}. Since our guarantees must hold for every trajectory the algorithm can produce, Assumption 2 is stated uniformly over xx.

A training checkpoint reveals VV at a single optimizer-selected point per radius, which only satisfies V(xt)≤sup⁡∣x−x0∣=∣xt−x0∣V(x)V(x_t)\le\sup_{\\|x-x_0\\|=\\|x_t-x_0\\|}V(x). Thus, checkpoints can show that the bound is loose along a given path, but they cannot estimate the right-hand side of Assumption 2. To estimate it without the optimizer bias, in Section 2, we query x=x0+rux=x_0+ru with directions uu drawn independently of the data and of any optimizer, estimate V(x)V(x) with the unbiased minibatch estimator, and fit B2∣x−x0∣a+G2B^2\\|x-x_0\\|^a+G^2. Hence, the fitted BG-aa curve is an empirical upper bound on VV over each sphere, and the variance along a particular trajectory can lie well below it, depending on the optimizer. Because our this bound does not depend on a specific path, it also covers iterates that leave a given training path, e.g., when the optimizer, its hyperparameters, or the data distribution change.

Weakness 1B: Relation to AdamW and learning-rate scaling

We thank the reviewer for this point. We agree that the tested AdamW algorithm and the learning rate scaling are outside the fixed-step SGD/SGDM guarantees, and that the language model experiments should be read as an empirical extension of the theory. To narrow this gap, we added a theoretical result for an Adam-like update and an ablation of the learning rate scaling.

Guarantee for a bounded-step proxy of Adam: In Theorem 4 of the revised manuscript (Appendix F), we analyze SignSGD with momentum (Bernstein et al., 2018) under the same distance-dependent batch rule, as a proxy for Adam. The two share several key features, such as nonlinear updates, a coordinate-wise map of the momentum estimate, and a per-coordinate update size that does not depend on the gradient magnitude. Theorem 4 shows that the batch rule retains the ϵ−(4+a)\epsilon^{-(4+a)} dependence for this biased update, for every finite a≥0a\ge0. We also show that the per-coordinate update of Adam is bounded, similar to SignSGDM, by a constant multiple of its step size whenever β12<β2\beta_1^2<\beta_2, which holds for the values (0.9,0.95)(0.9,0.95) used in our experiments.

Learning rate scaling: We adopt the k\sqrt{k} 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 33 seeds. (Due to the limited time available during the rebuttal period, we excluded the 1B model.)

ModelOptimizerLearning rate scalingValidation loss
OLMo2-100MAdamW113.4522
OLMo2-100MAdamWk\sqrt{k}3.4347
OLMo2-100MAdamWkk3.6509
OLMo2-600MAdamW112.8840
OLMo2-600MAdamWk\sqrt{k}2.8482
OLMo2-600MAdamWkk3.1088

The best performance is obtained when the learning rate is scaled by k\sqrt{k} while the batch size grows by a factor of kk, which is the rule used in our experiments. Without scaling (f(k)=1f(k)=1), BG-aa still attains a lower validation loss than the small batch baseline. Hence, the gains of BG-aa do not rely solely on the learning rate scaling, although the k\sqrt{k} rule improves them further.

AuthorsOpenReview ↗

Response to Reviewer cNGo (2/2)

Question 1A : (B,G,a) parameters, variance ratio, and token indexing

We thank the reviewer for these questions. We have added the following details to the revised manuscript (Figure 3 and Appendix H).

Fitting objective and weighting: We fit (B,G,a)(B,G,a) by nonlinear least squares on the logarithm of the variance estimates, min⁡B,G>0, a∈[0,2] ∑i(log⁡v^i−log⁡(B2ria+G2))2.\min_{B,G>0,\ a\in[0,2]}\ \sum_i\left(\log\hat v_i-\log\left(B^2r_i^a+G^2\right)\right)^2. Fitting in log space measures the relative error, hence, measurements at small and large radii, whose variances differ by orders of magnitude, contribute at a comparable degree.

Variance ratio in Figure 3(b): The plotted quantity is the modeled ratio vtv0=B2∥xt−x0∥a+G2G2=1+B2G2∥xt−x0∥a,\frac{v_t}{v_0}=\frac{B^2\Vert x_t-x_0\Vert^a+G^2}{G^2}=1+\frac{B^2}{G^2}\Vert x_t-x_0\Vert^a, evaluated with the fitted (B,G,a)(B,G,a) and the distance ∥xt−x0∥\Vert x_t-x_0\Vert measured at every iteration of the BG-aa run.

Token indexing: The warmup and cosine schedules are indexed by the number of training tokens, not by the number of updates. The learning rate increases linearly over the first 5%5\% of the token budget and then follows a cosine decay to 10%10\% of its peak value. Since BG-aa changes the number of tokens per update, token indexing ensures that BG-aa and the fixed batch baselines follow the same schedule as a function of tokens, which is also the horizontal axis of Figure 3.

Weakness 3 and Question 2: Contribution of momentum when the target variance is matched.

We thank the reviewer for this comparison. In our analysis of SGDM, the momentum coefficient β\beta allocates oracle calls between the batch size and the number of iterations, while the optimal rate is preserved.

We additionally thank the reviewer for pointing out the 8x and 32x differences. We have identified that this resulted from loose constants in our original proof, which we have tightened in the revised manuscript. Theorem 3 now holds for ϵ2≤min⁡σ2(1−β2),LΔ\epsilon^2\le\min\\{\sigma^2(1-\beta^2),L\Delta\\}, with the same batch rule and η=cβϵ22Lσ2,T=⌈8Lσ2Δcβϵ4⌉,E[SFO]≤10LΔ[(σ2cβ+G2)ϵ−4+50a/2B2Δaϵ−(4+a)].\eta=\frac{c_\beta\epsilon^2}{2L\sigma^2},\qquad T=\left\lceil\frac{8L\sigma^2\Delta}{c_\beta\epsilon^4}\right\rceil,\qquad \mathbb{E}[\mathrm{SFO}]\le 10L\Delta\left[\left(\frac{\sigma^2}{c_\beta}+G^2\right)\epsilon^{-4}+50^{a/2}B^2\Delta^a\epsilon^{-(4+a)}\right].

Theorem 2 with target variance σ2/cβ\sigma^2/c_\beta leads to the same batch rule, step size, iteration count, and SFO bound, and its accuracy range contains that of the revised Theorem 3.

Increasing β\beta at a fixed σ2\sigma^2 reduces the required batch size by a factor of cβc_\beta and increases the iteration count by a factor of 1/cβ1/c_\beta, while the G2G^2 and B2B^2 terms of the SFO bound are unchanged. We have updated Theorem 3, its proof, and the discussion of the batch size and iteration trade-off in Appendix D of the revised manuscript.

We would also like to clarify why establishing the results with momentum is particularly important in the context of prior work. Fazla et al. (2026) establish the convergence of SGD under BG-0 noise, where the prescribed batch size grows with ∣xt−x0∣2\\|x_t-x_0\\|^2 and can therefore become very large. Our analysis under BG-aa shows that this requirement can be reduced, as the noise usually grows with an exponent a<2a<2 in practice, the corresponding dynamic batch size grows only with ∣xt−x0∣a\\|x_t-x_0\\|^a. Our analysis of SGDM further shows that, under the same noise and at the same query point, momentum reduces the batch size prescribed at each iteration by a factor of cβc_\beta for the same target variance. Hence, for a fixed target variance, the momentum coefficient can be adjusted according to the compute budget, reducing the need for a very large batch size with a trade-off in the number of iterations. Since momentum is standard in practice, it is important that this flexibility and the optimal rate are guaranteed for the momentum update itself.

Question 3: Dimension condition in Theorem 1.

Yes, the intended statement is existential over a sufficiently large dimension, and we thank the reviewer for pointing out that this should be made explicit. For fixed (L,Δ,B,G,a,ϵ)(L,\Delta,B,G,a,\epsilon) and any integer dd satisfying Eq. (33), the construction leads to a family of instances in Rd+1\mathbb{R}^{d+1} such that every algorithm incurs the stated cost on some instance in the family. Hence, the bound holds in every sufficiently large dimension.

Our result does not claim a lower bound in a fixed dimension as ϵ→0\epsilon\to 0. The required dimension is O~(T2/p)\tilde{\mathcal{O}}(T^2/p), where T=Θ(LΔ/ϵ2)T=\Theta(L\Delta/\epsilon^2) and 1/p=1+Θa((G2+B2(Δ/ϵ)a)/ϵ2)1/p=1+\Theta_a((G^2+B^2(\Delta/\epsilon)^a)/\epsilon^2), so it grows polynomially in 1/ϵ1/\epsilon. This requirement comes from the random-rotation argument for unrestricted randomized algorithms, which follows Arjevani et al. (2023). Since Theorems 2 and 3 hold in every dimension, the upper and lower bounds match in the worst case over dimension. We have fixed this statement in the revised manuscript.

AuthorsOpenReview ↗

Analysis of AdamW under BG-

We have extended our theory to include the analysis of AdamW under the BG-aa noise model, by extending a recent proof strategy from [1] together with the bounded-update argument of our SignSGDM analysis (Theorem 4). The result is stated in Theorem 5 (Section 3), with the complete statement and proof in Appendix G.

Theorem 5 shows that AdamW with dynamic batching retains the ϵ−(4+a)\epsilon^{-(4+a)} dependence for every finite a≥0a\ge0. Compared to [1], the noise level is controlled by the batch rule instead of being assumed, and the second-moment coefficient only needs to satisfy β12<β2<1\beta_1^2<\beta_2<1 (instead of β1≤β2≤β1\beta_1\le\beta_2\le\sqrt{\beta_1} in [1]). Hence, the theorem covers the values (β1,β2)=(0.9,0.95)(\beta_1,\beta_2)=(0.9,0.95) used in our experiments. Moreover, the factor 1−β11-\beta_1 in the batch rule plays the same role as the momentum factor in our SGDM and SignSGDM results, and reduces the prescribed batch size at the cost of more iterations. We also revised Section 4 so that the scheduler is stated for SGD, SGDM, SignSGDM, and AdamW. The batch size multiplier ktk_t is the same for all of them, and the batch sizes selected by our scheduler satisfy the variance condition of Theorem 5 in our AdamW experiments.

[1] Huan Li, Yiming Dong, and Zhouchen Lin. On the O(dK1/4)O(\frac{\sqrt{d}}{K^{1/4}}) convergence rate of AdamW measured by ℓ1\ell_1 norm. arXiv preprint arXiv:2505.11840v4, 2026.

I thank the authors for their response. They have mostly address my concerns. I will maintain my positive score.

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

The paper introduces the BG-aa stochastic noise model, which bounds gradient variance by G2+B2∣x−x0∣aG^2+B^2|x-x_0|^a and interpolates between bounded variance and quadratic BG noise. For smooth nonconvex optimization, it establishes lower and upper bounds with matching ϵ−(4+a)\epsilon^{-(4+a)} dependence for a∈[0,2]a\in[0,2], using dynamically batched SGD and SGDM. It fits the noise model using randomly perturbed parameter states and proposes a practical batch scheduler based on displacement from initialization.

Critical strengths

The paper studies an important practical question: how to select batch sizes during LLM pretraining. Its clearest theoretical contribution is a characterization of how the permitted variance-growth exponent affects oracle complexity, with matching dependence on ϵ\epsilon that recovers the bounded-variance and quadratic BG endpoints.

Critical weaknesses

1. The noise model has not been validated during actual training.

Section 2 measures variance at randomly perturbed weights, rather than checkpoints from a training run. Figure 3(b) also shows predictions from the fitted model, not measured variance. These experiments do not establish that noise grows during pretraining as the paper claims. The authors should measure variance at actual training checkpoints and check whether the fitted (B,G,a)(B,G,a) describe those measurements.

2. The theoretical extension is incremental, and key experimental baselines are missing.

Fazla et al. (2026) already establish the quadratic BG result and analyze distance-dependent dynamic batching. This paper extends the exponent from 22 to aa, using the same basic lower-bound construction and variance-control argument. The matching ϵ−(4+a)\epsilon^{-(4+a)} rate is useful, but the technical advance appears modest.

The experiments compare only against two fixed batch sizes. They should include batch-size warmup, which Merrill et al. study for OLMo, and an existing adaptive method such as DDP-Norm/FSDP-Norm from Lau et al., tested with AdamW on C4. Without these comparisons, it is unclear whether the proposed rule improves on existing batch schedules.

Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 687m (1/2)

Weakness 1: Relation to actual training trajectories

We thank the reviewer for their comments. We would like to clarify that Assumption 2 is a property of the oracle, not of the optimizer. For a fixed query point xx, let V(x) := \mathbb{E}_{\xi}\left\\|\nabla f(x;\xi)-\nabla f(x)\right\\|^2. The expectation is taken over the sample ξ\xi only, with xx held fixed, and it is not a conditional expectation along an optimizer's trajectory. Hence, VV is a deterministic function determined by the model and the data distribution, and Assumption 2 requires V(x)≤B2∣x−x0∣a+G2for every x∈Rd,i.e.,sup⁡∣x−x0∣=rV(x)≤B2ra+G2for every r≥0.V(x)\le B^2\\|x-x_0\\|^a+G^2\quad\text{for every }x\in\mathbb{R}^d,\qquad\text{i.e.,}\qquad \sup_{\\|x-x_0\\|=r}V(x)\le B^2r^a+G^2\quad\text{for every } r\ge0.

In our proofs, the bound is applied at the iterates. Since xtx_t is Ft\mathcal{F}_t-measurable and the samples ξt,1,…,ξt,bt\xi_{t,1},\dots,\xi_{t,b_t} are independent of Ft\mathcal{F}_t, the unbiased minibatch estimator satisfies Et∣gt−∇f(xt)∣2=V(xt)bt≤B2∣xt−x0∣a+G2bt.\mathbb{E}_t\\|g_t-\nabla f(x_t)\\|^2=\frac{V(x_t)}{b_t}\le\frac{B^2\\|x_t-x_0\\|^a+G^2}{b_t}. The iterates themselves are random and depend on the optimizer, its hyperparameters, and the realized samples. For instance, for SGD we have Et[xt+1−xt]=−η∇f(xt)\mathbb{E}_t[x_{t+1}-x_t]=-\eta\nabla f(x_t), so the displacement xt−x0x_t-x_0 is biased toward descent directions of ff rather than spread over the sphere x:∣x−x0∣=r\\{x:\\|x-x_0\\|=r\\}. Since our guarantees must hold for every trajectory the algorithm can produce, Assumption 2 is stated uniformly over xx.

Why we use random directions in Section 2: A training checkpoint reveals VV at a single optimizer-selected point per radius, which only satisfies V(xt)≤sup⁡∣x−x0∣=∣xt−x0∣V(x)V(x_t)\le\sup_{\\|x-x_0\\|=\\|x_t-x_0\\|}V(x). Thus, checkpoints can show that the bound is loose along a given path, but they cannot estimate the right-hand side of Assumption 2. To estimate it without the optimizer bias, in Section 2, we query x=x0+rux=x_0+ru with directions uu drawn independently of the data and of any optimizer, estimate V(x)V(x) with the unbiased minibatch estimator, and fit B2∣x−x0∣a+G2B^2\\|x-x_0\\|^a+G^2. Hence, the fitted BG-aa curve is an empirical upper bound on VV over each sphere, and the variance along a particular trajectory can lie well below it, depending on the optimizer. Because our this bound does not depend on a specific path, it also covers iterates that leave a given training path, e.g., when the optimizer, its hyperparameters, or the data distribution change.

Weakness 2: Novelty relative to Fazla et al. (2026)

We thank the reviewer for their comments. We emphasize our contributions and novelty below:

Theoretical contributions

  • Lower bound for every growth exponent and every randomized algorithm. We propose the generalized BG model and extend the lower bounds of Fazla et al. (2026) to cover every finite a≥0a\ge0. Moreover, our lower bound analysis holds for arbitrary randomized algorithms, including unbounded queries, arbitrary output points, and random stopping times, rather than only for zero-respecting algorithms as in Fazla et al. (2026). This requires combining the activation mechanism with the compressed random-rotation construction of Arjevani et al. (2023), for which we derive a new chain length and reveal probability calibrated to the distance-dependent variance budget B2(D/2)a+G2B^2(D/2)^a+G^2 (Appendix B).

  • Minimax characterization for a∈[0,2]a\in[0,2]: In Theorems 2 and 3, we show that dynamically batched SGD(M) attains the O(ϵ−(4+a))\mathcal{O}(\epsilon^{-(4+a)}) rate. With the target variance σ2=max⁡G2,ϵ2/2\sigma^2=\max\\{G^2,\epsilon^2/2\\}, the SGD bound matches all three terms of the established lower bound up to absolute constants, which results in a minimax characterization of the oracle complexity over the BG-aa class (Appendix B.4). We also identify the failure case of the BG-aa noise model under SGD(M) for convergence. Since a<2a<2 requires control of the aa-th moment of the displacement rather than the second moment, we identify that SGD(M) with dynamic batching rule can have an infinite expected cost (Proposition 1).

  • Momentum: We show that dynamically batched SGDM retains the optimal rate for every fixed momentum coefficient β∈[0,1)\beta\in[0,1). In the revised manuscript, we tightened its constants so that SGDM has the same guarantee as SGD at a matched target variance, while β\beta trades a smaller batch size for more iterations at a fixed target variance. Thus, we showed how momentum, which is standard practice, enables a trade-off between batch size vs. number of iterations. We believe this observation is important, as it showcases the importance of the momentum mechanism, particularly for problems that require a practically unachievable batch size.

AuthorsOpenReview ↗

Response to Reviewer 687m (2/2)

  • SignSGDM (new in the rebuttal): Theorem 4 analyzes SignSGD with momentum under our BG-aa noise model. This update shares two properties with Adam: it applies a nonlinear, coordinate-wise map to a momentum estimate, and the size of each coordinate of its update does not depend on the gradient magnitude. We highlight the advantage of this analysis, which also extends to Adam under certain conditions: it provides a deterministic bound on the displacement, yielding convergence results for every finite a≥0a\ge0, beyond the range a≤2a\le2 covered by Theorems 2 and 3.

Practical contributions

  • Measurement of noise growth in LLM pretraining. We established unbiased experiments to measure noise growth in LLM pretraining and vision model training, and observed that the noise growth in LLM pretraining is subquadratic, with fitted exponents a=0.98a=0.98, 1.381.38, and 1.491.49 that increase with model size, so the quadratic growth assumed by BG-00 overestimates the measured noise (Section 2). Our new ablation (Appendix G.3) shows that the scheduler is far more sensitive to aa than to BB and GG, as a 5%5\% change in aa changes the peak variance ratio by up to 82%82\% for OLMo2-1B. Hence, estimating the exponent, rather than fixing it at a=2a=2, is important in practice.

  • Adaptive Batching derived from the theory: Our scheduler follows the dynamic batching rule derived from our theoretical analysis. In OLMo2 pretraining on C4, it achieves a lower validation loss than both small and large batch training at all three model sizes under matched token budgets, while using only 8.76%8.76\%, 8.10%8.10\%, and 5.25%5.25\% of the iterations of small batch training and reducing its wall-clock time by approximately 40%40\%, 28%28\%, and 20%20\%.

  • Online and offline training. Our experiments also show that faster optimization does not always translate into better test performance, depending on the role of the gradient noise. Consistent with Vyas et al. (2024), in single-epoch LLM pretraining, the lower training loss of adaptive batching carries over to a lower validation loss. In multi-epoch image classification, adaptive batching also achieves a lower training loss than small batch training, but small batch training retains its test advantage, consistent with the implicit regularization effect of small batches (Keskar et al., 2017). Hence, we demonstrate that adaptive batching is particularly well suited to the online regime of modern LLM pretraining.

The importance of our work. Increasing the batch size during training is a common practice in LLM pretraining, yet the classical bounded variance analysis does not explain it, and the theoretical work behind the BG-0 model overestimates the noise growth in practice. Our work connects theory and practice, and introduces the generalized BG-aa noise model while containing both bounded variance and BG-0 as special cases, characterizes the resulting oracle complexity with matching lower and upper bounds, and turns the corresponding batch rule into a practical scheduler that improves pretraining efficiency. Thus, our work offers a theoretically grounded explanation for increasing the batch size during training, complementary to empirical approaches based on the gradient noise scale and the critical batch size, and bridges the gap between the theory of stochastic optimization and the practice of large scale training.

Weakness 3: Comparison Againt Baselines

We thank the reviewer for their comments. Our work studies adaptive batch scheduling from a theory-first perspective and provides a practical scheduler derived from our analysis, with an additional goal of explaining why common batch size schedulers help in practice. Our theory also complements the batch size warmup of Merrill et al., as in our LLM experiments, ∣x−x0∣a\\|x - x_0\\|^a grows and stabilizes early in training, so our schedule behaves more like a warmup. We agree that baseline comparisons would strengthen the paper, so we have implemented both schedulers suggested by the reviewer. Both use the same initial batch size as BG-aa. For DDP-Norm, we set η=0.25\eta = 0.25. We report the average validation loss over 33 seeds. (Due to the limited time available during the rebuttal period, we excluded the 1B model.)

ModelSchedulerValidation loss
OLMO2-100MBG-aa3.4347
OLMO2-100MMerrill et al.3.4403
OLMO2-100MLau et al.3.4475
OLMO2-600MBG-aa2.8482
OLMO2-600MMerrill et al.2.8906
OLMO2-600MLau et al.2.8994
AuthorsOpenReview ↗

Analysis of AdamW under BG-

We have extended our theory to include the analysis of AdamW under the BG-aa noise model, by extending a recent proof strategy from [1] together with the bounded-update argument of our SignSGDM analysis (Theorem 4). The result is stated in Theorem 5 (Section 3), with the complete statement and proof in Appendix G.

Theorem 5 shows that AdamW with dynamic batching retains the ϵ−(4+a)\epsilon^{-(4+a)} dependence for every finite a≥0a\ge0. Compared to [1], the noise level is controlled by the batch rule instead of being assumed, and the second-moment coefficient only needs to satisfy β12<β2<1\beta_1^2<\beta_2<1 (instead of β1≤β2≤β1\beta_1\le\beta_2\le\sqrt{\beta_1} in [1]). Hence, the theorem covers the values (β1,β2)=(0.9,0.95)(\beta_1,\beta_2)=(0.9,0.95) used in our experiments. Moreover, the factor 1−β11-\beta_1 in the batch rule plays the same role as the momentum factor in our SGDM and SignSGDM results, and reduces the prescribed batch size at the cost of more iterations. We also revised Section 4 so that the scheduler is stated for SGD, SGDM, SignSGDM, and AdamW. The batch size multiplier ktk_t is the same for all of them, and the batch sizes selected by our scheduler satisfy the variance condition of Theorem 5 in our AdamW experiments.

[1] Huan Li, Yiming Dong, and Zhouchen Lin. On the O(dK1/4)O(\frac{\sqrt{d}}{K^{1/4}}) convergence rate of AdamW measured by ℓ1\ell_1 norm. arXiv preprint arXiv:2505.11840v4, 2026.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.