acceptodds
Under review as a conference paper at ICLR 2027

Minimax Limits of Adaptive Averaging and Batching in SGD

Abstract

Averaging SGD checkpoints can improve on the last iterate, while larger batches reduce gradient noise but consume more samples. We ask how much these choices can improve the worst-case guarantee under prescribed learning rates and the fixed SGD update rule. To characterize these limits, we study convex quadratics with curvature at most and additive IID noise, using convex averages with the same averaging weights in every coordinate. We prove that, for fixed batch sizes, choosing averaging weights from the observed trajectory has the same minimax value as fixing them optimally before training. For joint averaging and batching, integer batch sizes may also adapt to training feedback, with a total sample budget and a maximum batch size per update enforced on every run. The minimax value then equals that of the best randomized plan specifying all batch sizes and averaging weights before training, independently of the instance and samples. These randomized plans can strictly improve on deterministic plans. Both equalities hold for any positive learning-rate sequence, with the worst case taken over all finite dimensions. For inverse-root rates , , we further prove that the optimal additional risk above the exact noiseless minimax value for the same rates is , with updates, samples, and maximum batch size . Here is a fixed integer, and initialization and noise budgets are fixed, positive, and finite. We conclude that these exact values provide benchmarks for comparing learning-rate sequences and bounding the improvement available beyond feasible averaging and batching plans.

Primary area:
optimization
Keywords:
Stochastic Gradient Descent, Checkpoint Averaging, Adaptive Minibatching, Minimax Analysis, Learning-Rate Schedules, Convex Quadratic Optimization, Sample Allocation

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_vTT3OpenReview ↗
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 Θ(C−1/2T−3/4+log(T)/T)\Theta(C^{-1/2} T^{-3/4} + log(T)/T). 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 dd, 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 log(T)/Tlog(T)/T 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
AuthorsOpenReview ↗

Author response to Reviewer vTT3

Thank you for the questions. For fixed dd, gains may remain despite the all-finite-dimension equality. We bound fixed-batch gains for any TT, 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\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,VdfixV_d^{\rm ad},V_d^{\rm fix} be the adaptive/fixed scalar minimax values at dimension at most dd. For any T,γT,\gamma and fixed BB, take a common adversary with kbk_b bias atoms, knk_n noise atoms, and value LAL_A. Let U>0U>0 upper-bound fixed class risk, r=⌊(d−kb)/kn⌋≥1r=\lfloor(d-k_b)/k_n\rfloor\ge1, and α=[1−(T+2log⁡(2kn/δ))/r]+2\alpha=[1-(\sqrt T+\sqrt{2\log(2k_n/\delta)})/\sqrt r]_+^2 for 0<δ<10<\delta<1. Replication gives

1−VdadVdfix≤1−(1−δ)αLAU.1-\frac{V_d^{\rm ad}}{V_d^{\rm fix}}\le 1-(1-\delta)\alpha\frac{L_A}{U}.

The bound can be loose for r≲Tr\lesssim T. At (T,B,γ)=(2,(1,1),(1,1))(T,B,\gamma)=(2,(1,1),(1,1)), a Rademacher oracle lower and continuum fixed-plan upper sharpen it.

Dimension bound dd3365129
Relative minimax gain upper0.8431%0.8431\%0.4151%0.4151\%0.2072%0.2072\%

At inverse-root T=32,d=19,B=1T=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)(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=3T=3 witness is certified in Appendix G.2. New certificates enumerate all 141 and 1,107 integer allocations at T=6,8T=6,8, optimizing the full scalar simplex, with q=2,C=3q=2,C=3 and L=D=σind=Δˉ=1L=D=\sigma_{\mathrm{ind}}=\bar\Delta=1.

New setting (Δˉ=1\bar\Delta=1)Certified risk reduction of mixture over all deterministic plans
T=6T=6, constant rates≥0.0488%\geq0.0488\%
T=6T=6, linearly decreasing rates≥0.1950%\geq0.1950\%
T=8T=8, constant rates≥0.0525%\geq0.0525\%

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+log⁡TT),s∈{rel,det,mix,pred}.E_T^s(C)=\Theta\left(C^{-1/2}T^{-3/4}+\frac{\log T}{T}\right),\quad s\in\{\mathrm{rel},\mathrm{det},\mathrm{mix},\mathrm{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 qTqT and cap. Long lookback already costs order log⁡(T)/T\log(T)/T above V0V_0. Otherwise, J=Θ(log⁡T)J=\Theta(\log T) disjoint blocks have feasible noise curvatures affecting the output. With only qTqT samples, one block receives at most qT/JqT/J. The corresponding instance forces noise of order J/(qT)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)(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.

Gain over output-aware triangular allocation (10−510^{-5} nats/token)98.33% CI (10−510^{-5})
4.0618[3.7701, 4.3535]

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.

Thanks for the authors' detailed response. It addresses my concern. I will hold my score.

Reviewer_NdimOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper examines how averaging checkpoints and selecting appropriate batch sizes can improve the worst-case guarantee of stochastic gradient descent (SGD) when both the learning rates and the update rule are fixed. The framework considers convex quadratics with additive independent and identically distributed (IID) noise, outputs that are convex combinations of the checkpoints using common scalar weights, and a total sample budget along with a per-update limit on batch size. It establishes two exact minimax equalities that hold for any positive rate sequence and for the worst-case scenario across all finite dimensions: (i) when the batch sizes are fixed, history-dependent averaging weights are no better than optimally chosen fixed weights; and (ii) when both averaging and batching are carried out jointly, history-dependent policies achieve the same result as the best data-independent randomized strategy, a strategy which can strictly outperform deterministic ones. The lower bounds are obtained by using a common spectral adversary through compact minimax duality together with noise replication in such a way that a single Gram-matrix concentration event is sufficient to control all the weights and the sample partitions. For inverse-root learning rates, the extra risk above the noiseless minimax value is Θ(C−1/2T−3/4+log⁡T/T)\Theta(C^{-1/2}T^{-3/4}+\log T/T), a value achieved by tail averaging with a specific integer allocation of the samples. Certified numerical results demonstrate a reversal in the order of two rate sequences that have the same noiseless endpoint polynomial, provide an upper bound on the further improvement that could be made over feasible plans, and show that a feasible plan can be distinguished from all nondecreasing-weight policies. Supplementary experiments involving a 124-million-parameter language model test a local quadratic prediction regarding how changes in the averaging weights affect the value of sample allocation.

Critical strengths

The two equalities are clean and hold for arbitrary positive rates, including those with sign-changing transfer factors.

The replication-plus-Gram-event argument handles weights and batches from the same noisy trajectory, where fixed-weight risk identities fail.

Theorem 3 separates the roles of the batch cap and total sample budget. It identifies the saturation scale and provides a matching explicit construction with finite-horizon constants.

The randomized-versus-deterministic witness and the separation from nondecreasing-weight policies are verified with exact rational or directed-rounding arithmetic.

The results allow statements such as "a cap-16 plan is within 0.218% of the optimum over all admissible rules" and enable comparison of rate sequences by full policy-class value.

The paper distinguishes Float64 guards from certified bounds, separates exploratory from prespecified studies, and reports failed experiments.

Critical weaknesses

The equalities need the supremum over all finite dimensions; the value of feedback at a fixed small dimension is left open, and the paper's own experiments show adaptive gains persist at a fixed dimension.

Fixed Hessian, additive IID noise, and shared scalar weights exclude random sample Hessians and coordinatewise outputs; Section 3.4 shows the output-set restriction changes the value.

The minimax values bound class guarantees, not typical-instance performance, and adaptive methods may help on favorable instances.

Sufficient horizons are astronomically large (about 101210^{12} for simplified constants), and the explicit construction's analytic bound is about 74×74\times the certified finite-budget value, so it is not a practical selector.

Certified examples use small horizons (T=3,8,64T=3,8,64), a specific 72-sequence library, q=2q=2, and unit budgets. The ranking reversal has a tiny persistence radius, and only 8 of 66 randomization settings resolved strictly.

Only two anchors, 128-update continuations, plain SGD, and inference conditional on fits and anchors; the local model underpredicts by 13--20%, the fitted output selector failed, and the experiments do not test the minimax claims or end-to-end efficiency.

The main text is dense with quantifier bookkeeping and forward references to a very long appendix, and the many value notations (Vrel,Vdet,Vmix,VpredV^{\mathrm{rel}}, V^{\mathrm{det}}, V^{\mathrm{mix}}, V^{\mathrm{pred}}) are hard to track.

Questions for authors

The supremum over all finite dimensions is required in Theorems 1 and 2. As Figure 1 and Table G.2 show, adaptive gains continue to exist at a fixed value of r. Yet the size of the improvement from using history-dependent weights or batches at dimension d must still be characterised, at least in a simple case such as when T=2 or for a bounded-dimension class, as a function of both d and T. If the gain is non-negligible at dimensions of practical interest, what should a reader make of the assertion that feedback has no minimax value?

It follows from Proposition B.1 that when spectral (coordinatewise) weights are allowed, the value is strictly reduced even at T=1T=1, for d≥2d \ge 2. Does the argument based on the common adversary and replication apply to the larger class of outputs (whether or not HH is known)? Does the inverse-root additional-risk rule from Theorem 3 still hold? If not, what is the principal obstacle? This will show how much of the paper's conclusions apply to output classes actually used in practice, such as per-parameter EMA.

The local-model prediction gives a value 13 to 20 per cent lower than the observed interaction. The fitted output selector did not work (see Appendix J). The study uses two anchors and 128 update continuations. Apart from showing that output-dependent sampling effects occur, which claim of the theory does this experimentation address? Could an experiment check a quantity predicted by the theory, for example the allocation-versus-window trade-off in Theorem 3 or the benefit of a randomized plan?

2 comments
AuthorsOpenReview ↗

Author Response to Reviewer Ndim

Thank you for the questions. On feedback, Theorems 1–2 rule out improved worst-case guarantees over all finite dimensions relative to fixed weights or independent randomized plans. Fixed-dd gains remain possible. We give a general d,Td,T bound. On outputs, scalar upper bounds remain feasible, but matching lowers need new arguments. On experiments, LM tests output-aware allocation and quadratic certificates test cap and randomization.

1. Fixed-dimensional feedback. Let Vdad,VdfixV_d^{\rm ad},V_d^{\rm fix} denote adaptive/fixed scalar minimax values at dimension at most dd. Appendix B.4 bounds any TT, positive rates and fixed batches. Let a common spectral adversary have kbk_b bias atoms, knk_n noise atoms and lower LAL_A. Take a full-class fixed-plan upper U>0U>0 and r=⌊(d−kb)/kn⌋≥1r=\lfloor(d-k_b)/k_n\rfloor\ge1. Define

α=[1−T+2log⁡(2kn/δ)r]+2.\alpha=\left[1-\frac{\sqrt T+\sqrt{2\log(2k_n/\delta)}}{\sqrt r}\right]_+^2.

For δ∈(0,1)\delta\in(0,1), replication yields 1−Vdad/Vdfix≤1−(1−δ)αLA/U1-V_d^{\rm ad}/V_d^{\rm fix}\le1-(1-\delta)\alpha L_A/U. Rates and batches enter LA,UL_A,U. The bound may be loose at moderate dd. Exact T=2,B=(1,1),L=D=σ∗=1T=2,B=(1,1),L=D=\sigma_*=1 certificates are tighter.

Rates γ\gammad=33d=33d=65d=65d=129d=129
(1/2,1/2)(1/2,1/2)≤0.7577%\le0.7577\%≤0.3779%\le0.3779\%≤0.1877%\le0.1877\%
(1,1)(1,1)≤0.8431%\le0.8431\%≤0.4151%\le0.4151\%≤0.2072%\le0.2072\%
(1/2,1/4)(1/2,1/4)≤0.6199%\le0.6199\%≤0.3245%\le0.3245\%≤0.1691%\le0.1691\%

The table covers all adaptive averages at fixed batches. At inverse-root T=32,d=19,B=1T=32,d=19,B=1, the 95%-simultaneous statistical upper is 13.196% under IID Gaussian sampling. Oracle gains are not minimax gains. Sharp fixed-(d,T)(d,T) gaps and joint batching remain open. Worst-case guarantees do not rule out task-specific gains.

2. Larger outputs. The common-adversary lower bound does not transfer unchanged. It needs shared weights. Proposition B.1 gives scalar 22/3/62^{2/3}/6 versus spectral 1/41/4 at T=1,d≥2T=1,d\ge2, with HH known to both oracles. In Theorem 3's hard instance, choosing endpoint for bias and x0x_0 for noise attains noiseless risk. The old witness loses its positive additional-risk lower bound. Scalar plans retain feasible total-risk upper bounds. A matching law needs a new lower bound and noiseless baseline. Unknown-HH coordinatewise values remain open. Common-decay EMA is shared-scalar, distinct per-parameter decays are not.

3. LM relevance. Eq. (13) predicts fixed-Hessian output loss Llocal(w,B)=β(w)+∑jvj(w)/BjL_{\rm local}(w,B)=\beta(w)+\sum_jv_j(w)/B_j. Here vj(w)v_j(w) is update-jj noise contribution to the output with weights ww. For fixed ww, β(w)\beta(w) is batch-independent. Optimizing the sum predicts allocation. LM tests allocation, not minimax equality.

The 124M plain-SGD study uses 3 independent runs, 6 late anchors, 32 paired streams with matched contexts. At T=256,N=2048T=256,N=2048, every plan returns last-128 average HoutH_{\rm out}. AHA_H and triangular PHP_H target HoutH_{\rm out}, while AEA_E targets endpoint.

AHA_H vsGain (10−510^{-5} nats/token)98.33% CI
Triangular PHP_H4.0618[3.7701, 4.3535]
Uniform22.0428[21.3576, 22.7279]
Endpoint-fit AEA_E107.8529[105.4728, 110.2330]

All Bonferroni-adjusted intervals are positive conditional on anchors, fits and holdout. Only the first two meet the precision target. T=1024T=1024 comparisons match budgets within horizon.

T=1024T=1024 anchorGain (10−510^{-5})95% CI
22.4850[2.0633, 2.9067]
31.9302[1.6154, 2.2451]

At cap 16, both output windows favor matched allocations.

AnchorLast-128 gain with AHA_HLast-64 gain with AQA_Q
28.6323×10−58.6323\times10^{-5}11.8774×10−511.8774\times10^{-5}
38.9751×10−58.9751\times10^{-5}13.9310×10−513.9310\times10^{-5}

All four CIs exclude zero. Caps 16/32 give identical plans (max batch 14), not general saturation. AHA_H worsens endpoint/EMA versus uniform. Predictions remain low, originally 12.59%–20.40%, and 9.01%/11.25% for a different contrast. Appendix J's selector still fails. Gains exclude fitting costs.

4. Quadratic certificates. With inverse-root rates, q=2,c=1/2q=2,c=1/2, unit budgets, a feasible plan is compared against a relaxed lower bound for all quadratic-class policies.

TT, plan cap vs bound capTotal-risk gapAdditional-risk gap
8192, 16 vs 64≤0.3229%\le0.3229\%≤3.1762%\le3.1762\%

No cap-64 feedback rule can reduce worst-case total risk by 1%. Additional risk subtracts exact V0V_0. For Theorem 2, mixture uppers are below lowers for all deterministic integer plans at q=2,C=3q=2,C=3.

SettingCertified randomized reduction
T=6T=6, constant rates≥0.0488%\ge0.0488\%
T=6T=6, linear rates≥0.1950%\ge0.1950\%
T=8T=8, constant rates≥0.0525%\ge0.0525\%

Five settings remain unresolved. The analytic construction is not a finite-budget selector. No LM minimax or randomization claim is made.

Thank you to the authors for their rebuttal, which clarifies the scope of the results. I am satisfied with the additional experiments and clarifications, which address my concerns and strengthen the manuscript. I appreciate the authors' efforts and will raise my rating from 2 to 3.

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

Under a quadratic form target with a fixed Hessian and additive IID noise, the authors study the minimax value of checkpoint averaging and minibatch allocation for SGD with prescribed positive learning rates. Returned estimates are convex checkpoint averages with the same scalar weights in every coordinate. The worst case ranges over all finite dimensions. Theorem 1 shows that trajectory-dependent averaging has the same minimax value as optimally chosen fixed weights. Theorem 2 allows predictable integer batching under a pathwise sample budget and batch cap. Numeric studies are performed to illustrate their theory.

Critical strengths

Theorems 1 and 2 identify the best worst-case guarantee even when the output can use the full observed trajectory and batches can depend on past observations. The proof combines a common spectral adversary with a Gaussian replication event that controls all related coefficient vectors and sample partitions simultaneously. Theorem 3 establishes matching cap-dependent bounds above the exact noiseless value.

Critical weaknesses

The authors only considered the very special quadratic form. Based on the quadratic form assumption, they developed a thorough asymptotic theory. What happens if the target is only convex (which is more general), not just quadratic?

Questions for authors

deal with the following issues: (i) convex losses with additive noise, (ii) least squares with random design, and (iii) locally quadratic losses as T → ∞, which parts of Theorems 1–3 and the Section 5 certificates are expected to hold? Lower bounds are covered by B.5; the real question is the upper bounds and equalities.

2 comments
AuthorsOpenReview ↗

Author response to Reviewer G9f6

Thank you for asking which upper bounds and equalities of Theorems 1–3 and Section 5 hold beyond fixed-Hessian quadratics. Several upper-bound arguments extend, but the exact minimax equalities require new matching bounds. For Theorems 1–2, the quadratic lower bounds remain valid for any larger instance class containing the original quadratics. We also provide a fixed-plan upper bound for smooth convex losses with additive noise. The smooth-convex upper bound alone does not establish an equality for the larger class. For Theorem 3, the upper additional-risk order transfers to locally quadratic losses if the approximation remainder and the change in the exact noiseless value are uniformly controlled at the additional-risk order. The sharp law still requires a matching lower bound. Section 5 certificates remain valid in the original quadratic class. Extending the certificates requires valid upper and lower endpoints for the larger class. For random-design least squares, the sample Hessian is random. The risk calculation must also account for feature fourth moments. We give the bounds, calculations, and corresponding experiments for the three requested settings below.

(i) Smooth convex losses with additive noise.

For an LL-smooth convex FF, assume E∥x0−x∗∥2≤D2\mathbb E\|x_0-x^*\|^2\leq D^2, deterministic batches, conditionally centered noise with variance at most σind2/Bt\sigma_{\mathrm{ind}}^2/B_t, and 0<γt≤1/L0<\gamma_t\leq1/L. The fixed scalar convex output xˉγ=∑t<Tγtxt/∑t<Tγt\bar x_\gamma=\sum_{t<T}\gamma_t x_t/\sum_{t<T}\gamma_t satisfies

\frac{D^2+\sigma_{\mathrm{ind}}^2\sum_{t<T}\gamma_t^2/B_t} {2\sum_{t<T}\gamma_t}.$$ The bound follows from $\langle\nabla F(x),x-x^*\rangle\ge F(x)-F^*+\|\nabla F(x)\|^2/(2L)$, the distance recursion, and Jensen's inequality. A one-step smooth Huber loss tests whether the original quadratic minimax value remains an upper bound for smooth convex losses. Even the best checkpoint average has higher loss (Table 1). **(ii) Least squares with random design.** The population loss remains quadratic, but random sample Hessians add $(aa^\top-H)(x_t-x^*)$ to gradient noise, introducing fourth moments. In our one-dimensional family, $\mathbb Ea^2=h$, $\operatorname{Var}(a^2)=h^2(p^{-1}-1)$, and label noise is centered with unit variance. For $x^*=0$ and $s_t=\mathbb E x_t^2$, the exact recursion is $$s_{t+1}=\left[(1-\gamma_t h)^2+ \frac{\gamma_t^2h^2(p^{-1}-1)}{B_t}\right]s_t +\frac{\gamma_t^2h}{B_t}.$$ The multiplicative-noise term and cross-time moments give exact fixed-plan risks. Our random-design comparison fixes the population Hessian and optimum-noise covariance but varies the fourth moment. In Table 1, the first two rows compare one-step examples with the quadratic value at $L=D=\gamma_0=T=1$. The last row compares fixed-instance risks. | Controlled example | Additive quadratic reference | True risk / lower bound | Difference | |---|---:|---:|---:| | Smooth Huber, $T=1$, noiseless | $2/27\approx0.07407$ | $\geq1/6\approx0.16667$ | Separation from additive quadratic reference | | Random-design LS, $T=1$, noiseless optimum | $2/27\approx0.07407$ | $\geq1/8=0.125$ | Separation from additive quadratic reference | | Random-design LS, $T=64$, $p=1/8$, uniform half-tail | $0.01355199$ | $0.01700126$ | $+25.45\%$ | The examples do not disprove adaptive/fixed minimax equality. **(iii) Locally quadratic losses as $T\to\infty$.** Let $Q(x)=x^\top Hx/2$ with $x^*=F^*=0$, $H=\nabla^2F(0)$, and $0\preceq H\preceq LI$. Couple a fixed plan $(w,B)$ under the nonlinear and quadratic models using identical noise, rates, and initialization. Suppose $\mathbb E Q(\bar y_w)\leq U$, $e_w^2\geq\mathbb E\|\bar x_w-\bar y_w\|^2$, and $\eta_w\geq\mathbb E|F(\bar x_w)-Q(\bar x_w)|$. Then $$\mathbb E F(\bar x_w)\leq U+\sqrt{2LU}\,e_w+\frac L2e_w^2+\eta_w.$$ With total approximation error $\rho_T$, the bound is $U+\rho_T$, giving $U[1+o(1)]$ if $\rho_T=o(U)$. Local assumptions also require controlling trajectories leaving the region. Our smooth nonquadratic half-tail test with fixed local Hessian and $\varepsilon=D=1$ gives | Updates $T$ | Paired residual / quadratic prediction | |---|---:| | 64 | 15.38% | | 1024 | 0.0554% | The residuals support fixed-plan approximation. A minimax extension requires uniform remainder bounds over the enlarged class. **Consequences for Theorems 1–3 and Section 5.** Theorems 1–2 require matching minimax bounds over larger classes. For Theorem 3, write $\Psi_T(C)=C^{-1/2}T^{-3/4}+\log(T)/T$. The upper order transfers if $U-V_0$, the uniform remainder, and the noiseless-value change are all $O(\Psi_T(C))$ uniformly over the target class and caps. The sharp law also needs a matching lower bound. For Section 5, a fixed-plan upper endpoint can be increased by a verified uniform remainder. Ranking and optimality-gap certificates need valid lower endpoints for the target class.
Reviewer_G9f6OpenReview ↗

response to rebuttal

Thanks the authors for their rebutal which clarifies the scope of the results. However, my original concern about their generality remains. The central minimax equalities are still established only for fixed-Hessian quadratics with additive noise. The proposed local quadratic extension depends on uniform approximation and noiseless-baseline estimates at the additional-risk scale, which have not been established for a broader class. I therefore regard the response as improving the interpretation and positioning of the existing contribution without sufficiently strengthening its generality to justify raising my score to 4. That being said, I am still overall positive about the paper. Thus I keep my rating of 3 (weak acceptance).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.