- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the minimax limits of adaptive averaging and batching in stochastic gradient descent. The authors establish that, for fixed batch sizes, choosing averaging weights from the observed training trajectory has exactly the same minimax value as fixing them optimally before training. For joint averaging and batching, they further show that integer batch sizes may also adapt to training feedback without improving the worst-case guarantee, subject to a total sample budget and a maximum batch size per update. The paper also demonstrates that randomized batching plans can strictly outperform deterministic plans, and that under an inverse-square-root learning rate the additional risk attains the optimal order . Overall, the paper provides a fairly complete minimax characterization of adaptive averaging and batching in SGD.
Critical strengths
1.The theoretical contribution is novel and addresses a practically important question: whether adaptive averaging or batching can improve worst-case performance relative to pre-fixed strategies.
2.The minimax lower bounds are derived through careful dimension-replication and concentration arguments, and the resulting risk law is clean and interpretable.
3.The additional-risk formula is practically useful. It gives a concrete quantitative guideline for choosing averaging and batching schedules under a sample budget.
4.The paper combines theory with experiments, which helps connect the theoretical findings with empirical practice.
Critical weaknesses
1.The theoretical setting is heavily restricted to convex quadratic losses and exact SGD with additive Gaussian noise. This limits its direct applicability to non-convex deep learning and adaptive gradient methods.
2.The main minimax equivalence is established for a shared scalar averaging weight across all coordinates. In practice, coordinate-wise or layer-wise weights are often used, and the paper does not adequately justify this modeling gap.
3.The improvement of randomized batching plans over deterministic plans is demonstrated only on small-scale examples. Whether this advantage persists in realistic large-scale problems remains unclear.
Questions for authors
1.For a fixed, moderate dimension , can one characterize the optimal adaptive averaging strategy, or at least bound the gap between adaptive and pre-fixed averaging?
2.What is the intuitive mechanism underlying the improvement of randomized batching plans over the best deterministic plan? Does the improvement depend on the dimension or the spectral structure of the problem?
3.The risk law contains a term that is attributed to integer batch-size constraints. If batch sizes were relaxed to real values or randomized fractions, would this term disappear? Does this suggest that the integer constraint is the fundamental cause of the extra cost?
2 comments
Thanks for the authors' detailed response. It addresses my concern. I will hold my score.
Author response to Reviewer vTT3
Thank you for the questions. For fixed d, gains may remain despite the all-finite-dimension equality. We bound fixed-batch gains for any T, while optimal policies remain open. Regarding randomization, mixing complete plans can reduce worst-case risk because one instance must be fixed before the plan is drawn. Spectral responses matter, not dimension alone. Regarding the logarithmic term, log(T)/T persists for real batches. The logarithmic cost comes from a shared budget across time scales, not integer rounding.
1. Feedback at moderate dimension.
Let Vdad,Vdfix be the adaptive/fixed scalar minimax values at dimension at most d. For any T,γ and fixed B, take a common adversary with kb bias atoms, kn noise atoms, and value LA. Let U>0 upper-bound fixed class risk, r=⌊(d−kb)/kn⌋≥1, and α=[1−(T+2log(2kn/δ))/r]+2 for 0<δ<1. Replication gives
1−VdfixVdad≤1−(1−δ)αULA.
The bound can be loose for r≲T. At (T,B,γ)=(2,(1,1),(1,1)), a Rademacher oracle lower and continuum fixed-plan upper sharpen it.
At inverse-root T=32,d=19,B=1, E1 gives a 95%-simultaneous statistical gap upper of 13.196%, not a deterministic certificate. Positive oracle gains do not prove positive minimax gains. Sharp general gaps remain open.
2. Randomization, spectra, and dimension.
The adversary sees the mixture and fixes one instance before an independent seed selects (w,B). Different plans can have their largest risks at different curvatures. Averaging squared transfer kernels before maximizing over one adversary can lower worst-case risk. A mixture does not beat its best deterministic component on one fixed instance.
Risk depends on spectra and bias/noise budgets. Dimension can limit admissible spectra. At fixed curvature and total variance, replication preserves plan risks. Replication controls feedback, not mixing gains.
The original T=3 witness is certified in Appendix G.2. New certificates enumerate all 141 and 1,107 integer allocations at T=6,8, optimizing the full scalar simplex, with q=2,C=3 and L=D=σind=Δˉ=1.
Each mixture upper bound is below a lower bound for all deterministic integer plans. Five settings remain unresolved. The certificates concern the quadratic class, not large-scale LM gains.
3. Real batches and the logarithmic term.
The term remains after relaxing integrality. Under Theorem 3's inverse-root rates and fixed positive budgets, additional risk above the exact noiseless value satisfies
ETs(C)=Θ(C−1/2T−3/4+TlogT),s∈{rel,det,mix,pred}.
The classes are real batches, deterministic and randomized integer plans, and predictable policies.
Appendix D.3 proves the real-batch lower bound at budget qT and cap. Long lookback already costs order log(T)/T above V0. Otherwise, J=Θ(logT) disjoint blocks have feasible noise curvatures affecting the output. With only qT samples, one block receives at most qT/J. The corresponding instance forces noise of order J/(qT). The proof takes a maximum over alternative instances, not a sum of their noise budgets. Theorem 2 transfers the bound to randomized integer and feedback policies.
Independent randomization over feasible real plans cannot improve the relaxed value. Joint convexity in (w,B) makes the mean real plan feasible and no worse. The mean batches need not be integers. Integrality can affect finite-budget values but does not cause the logarithmic term.
Scope and LM evidence.
The additive IID class assumes the stated second moments, not Gaussian noise. Gaussian replication supplies lower-bound instances. Common-decay EMA and tail averaging use shared scalar weights. Different per-parameter decays need new matching bounds.
Our 124M plain-SGD study uses three independent runs, six late anchors, and 32 paired streams per anchor. Each allocation returns the last-128-state average under fixed rates and sample budget.
The Bonferroni interval is conditional on anchors, fits, and holdout. Gains are positive at all six anchors. The LM result tests output-dependent allocation, not minimax equalities or randomization.