acceptodds
Under review as a conference paper at ICLR 2027

Adaptive optimization improves scaling in quadratic neural networks

Abstract

We study the scaling laws of adaptive training algorithms for quadratic neural networks, and characterize scaling exponents parameterized by target complexity and model size. We demonstrate that an adaptive algorithm utilizing accumulated prediction errors can significantly improve the scaling behavior compared to fixed-learning-rate methods. Notably, this approach achieves statistically optimal exponents at any time-step without requiring manual learning rate tuning. Finally, we empirically demonstrate that the acceleration phenomenon due to adaptive learning rate generalizes: similar scaling improvements are observed under general activation functions and when employing practical adaptive algorithms that accumulate squared gradients.

Primary area:
learning theory
Keywords:
feature learning, scaling laws, adaptive algorithms, stochastic optimization, compute-optimal

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_rSyhOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the generalization error of a two layer quadratic-activated neural network trained via an adaptive optimizer in a student-teacher setting. The paper shows that the risk scaling matches that of an optimally tuned SGD. In addition, the analysis reveals two learning phases: one corresponding to noisy training and one corresponding to noiseless. Experiments validate the theoretical claims.

Critical strengths
  1. The paper derives an end-to-end risk bound for adaptive optimizers for a feature-learning network. Specifically, different from the majority of prior work, the theory is 1) for a feature-learning network, 2) adaptive optimizer, 3) jointly considers optimization and generalization. The relative novelty of the theoretical setting is a major strength of this paper.
Critical weaknesses

The major weaknessess are twofold:

  1. The proposed adaptive optimizer is very specific: the results apply only to a particular optimizer, and not a broad family that may plausibly include practical optimizers. In particular, equation (ADP) seems to suggest that when the loss is smaller, the step sizes get larger (unless I am misunderstanding), which seems to be the opposite of (or at least not aligned with) how practical adaptive optimizers like Adam operate.

  2. The connections with prior theory on adaptive optimizers is not clear. I understand that the approach of this work is to study the generalization error of a specific model on a specific task in a teacher-student setting. However, as the authors point out in the related work section, there has been extensive work on studying generalization/optimization of adaptive algorithms in other settings. It would be useful to compare how risk bounds derived from these methods compare to what the authors derive. For instance, the authors could consider a classical optimization bound for an adaptive algorithm on non-convex loss landscapes and combine it with a generic capacity-based generalization bound for the two layer network studied (something like the ERM bound referred to in Table 1) to provide an overall baseline risk bound.

Questions for authors

The questions relate to the two weaknesses above: 1a. Can the theory be extended to a broader/more flexible class of adaptive optimizers? 1b. How realistic is the adaptive optimizer analyzed? Are there practical optimizers with a similar form (not just similar risk/loss curves)? 2. How does the derived risk bound compare to prior theory on adaptive optimizers?

3 comments
AuthorsOpenReview ↗

Response to Reviewer rSyh (1/2): W1 and Q1

Thank you for the review. Your questions helped us state more precisely what the algorithm is and how it relates to practical methods. W2, Q2 and Q1a are answered in part 2/2.

W1, Q1b. Is the optimizer realistic? Yes. In our model, a loss-based rule and a gradient-based rule are driven by the same quantity: the loss our rule accumulates is essentially what RMSprop and Adam accumulate. For the weight waiw_{ai} (coordinate aa of neuron ii), the squared per-sample gradient has mean approximately

8rs2 P(Gt)(∥wi∥2+wai2),wai2≪∥wi∥2,\frac{8}{r_s^2}\ \mathcal P(G_t)\left(\Vert w_i\Vert^2+w_{ai}^2\right),\qquad w_{ai}^2\ll\Vert w_i\Vert^2 ,

with Gt=WtWt⊤/rsG_t=W_tW_t^\top/r_s. The second-moment estimate of RMSprop or Adam is therefore an aggregate of the past loss times a per-neuron factor ∥wi∥2\Vert w_i\Vert^2, with almost no dependence on the coordinate aa. Substituting it into their update gives, for neuron ii, a drift proportional to

γt (Ψ∗−Gt) wi∥wi∥,\gamma_t\ \frac{(\Psi_\ast-G_t)\ w_i}{\Vert w_i\Vert},

where γt\gamma_t is the inverse root of this aggregated loss. These methods thus effectively reduce to the type of dynamics we analyze: a gradient method, normalized per neuron, whose step size is controlled by the aggregated loss. Our theory characterizes the optimal learning-rate schedule for such dynamics and shows that the aggregation rule of (ADP) attains it. The per-neuron normalization only changes constants: the squared neuron norms have mean Tr(Gt)\mathrm{Tr}(G_t) and variance approximately 2∥Gt∥F22\Vert G_t\Vert_F^2 across neurons, independently of the width. This is consistent with Figure 2, where RMSprop and Adam follow risk curves similar to those of our rule. We added this computation to the revised manuscript (Remark 1 in Appendix A).

W1. Is "smaller loss, larger step" opposite to Adam? No, it is the same direction. Adam and RMSprop divide by the root of the accumulated squared gradients, so smaller recent gradients give a larger effective step, and by the previous item squared gradients are proportional to the loss here.

Importantly, the step does not grow during training in general. νt\nu_t is a weighted sum, not an average: it is roughly tt times the recent average loss, and the rate is its inverse root. So the rate decays unless the loss falls faster than 1/t1/t. There are two regimes.

  • Noise-dominated regime. The loss cannot fall below σ2\sigma^2, so the accumulated loss grows linearly and the rate decays as 1/(σt)1/(\sigma\sqrt{t}) for every α\alpha (Fig. 3(a)). This is the classical AdaGrad decay.
  • Signal-dominated regime. The loss decays as t1−2αt^{1-2\alpha} and the rate behaves as tα−1t^{\alpha-1}. It decreases for α<1\alpha < 1 (Fig. 3(b)) and increases for α>1\alpha > 1, where the loss falls faster than 1/t1/t (Fig. 3(c)). The increase is capped by the stability constant and, for σ>0\sigma > 0, it ends at t≍σ−2/(2α−1)t\asymp\sigma^{-2/(2\alpha-1)}, when the noise takes over and the rate starts to decay. In both regimes the rate stays proportional to λj/P\lambda_j/\mathcal P, the strength of the feature being learned over the current loss (Step 5 of Section 4).

Why should the learning rate increase for α>1\alpha > 1? Because optimality requires it. SGD with a fixed learning rate attains at best the rate t(1−2α)/αt^{(1-2\alpha)/\alpha} in this setting (Table 1; Ren et al., 2025; Ben Arous et al., 2025), which for α>1\alpha > 1 is slower than the noiseless ERM rate t1−2αt^{1-2\alpha}. By the time change of Section 4, the risk at time tt is the fixed-rate risk curve evaluated at F∗(t)=∫0tγF_\ast(t)=\int_0^t\gamma, so reaching the ERM exponent requires F∗(t)≍tαF_\ast(t)\asymp t^{\alpha}: any scalar schedule that is optimal in this regime must increase, like tα−1t^{\alpha-1}. The increase is thus not an artifact of our rule. We agree that this regime is of limited practical relevance, since data are typically noisy and the increase is then transient. We leave practical scheduling in this regime as interesting future work (Limitation (iv)).

AuthorsOpenReview ↗

Response to Reviewer rSyh (2/2): W2, Q2 and Q1a

W2, Q2. Connection with prior theory on adaptive optimizers. Classical guarantees for adaptive methods (Ward et al., 2018; Li & Orabona, 2019; Défossez et al., 2020; all cited in Section 1.2) hold for general non-convex objectives, but under assumptions our problem does not satisfy: global smoothness and bounded stochastic gradients or noise. Here P\mathcal P is quartic in WW and the gradient noise is multiplicative, E∥∇L∥F2≍(d/rs) P(G) Tr(G)\mathbb E\Vert\nabla\mathcal L\Vert_F^2\asymp(d/r_s)\ \mathcal P(G)\ \mathrm{Tr}(G). Their conclusion is also weaker than a risk bound: they control a gradient norm, typically at rate O~(1/T)\tilde O(1/\sqrt{T}), whereas our random initialization is already near a saddle, with a vanishing gradient and excess risk about 11.

By fixing the model we give up that generality, and in exchange we can go beyond these assumptions and show the benefit of adaptivity directly: an explicit risk curve with α\alpha-dependent exponents, the learning-rate schedule that produces it, and a comparison with fixed-rate SGD (Table 1, Figs. 1–2). For instance, in the signal-dominated phase with α>1\alpha > 1 the adaptive rate increases and the risk decays as t1−2αt^{1-2\alpha}, against t(1−2α)/αt^{(1-2\alpha)/\alpha} for a fixed rate.

Closest high-dimensional analysis. Collins-Woodfin et al. (2024) analyze AdaGrad-Norm for least squares on horizons proportional to dd, and they observe transitions similar to ours, driven by a very similar mechanism. First, with label noise their learning rate decays as 1/t1/\sqrt{t}, as ours does in the noise-dominated phase. Second, without noise, their exponent β+δ\beta+\delta (in their notation) plays the role of our 1/α1/\alpha: their decaying-rate regime gives our schedule tα−1t^{\alpha-1} and risk t1−2αt^{1-2\alpha} for α<1\alpha < 1. Their constant-rate regime corresponds to α>1\alpha > 1 and gives the fixed-rate exponent (1−2α)/α(1-2\alpha)/\alpha; the discount in our rule is what lets the rate increase there and reach 1−2α1-2\alpha. Our setting extends this mechanism to a non-convex feature-learning model, with time scales beyond O(d)O(d). We highlighted this connection in Section 1.2 of the revised manuscript.

Q1a. Can the theory cover a broader class? In part it already does, since the mechanism is not tied to the specific rule, as discussed above. It has three ingredients. (i) For the squared loss, the squared gradient is the loss times a slowly varying factor, so accumulating squared gradients tracks the loss. (ii) A scalar learning rate acts as a change of time on the fixed-rate dynamics; this holds for every scalar rule. (iii) The inverse square root of the accumulated loss keeps the learning rate in a constant ratio to the signal-to-noise level of the feature being learned.

Within our model, the analysis therefore extends to any polynomial discount with q>2α−2q > 2\alpha-2, and to rules that accumulate squared gradient norms instead of the loss, up to the factor Tr(Gt)\mathrm{Tr}(G_t), which stays bounded for α>1\alpha > 1. For RMSprop and Adam, the computation in part 1/2 and Figure 2 indicate the same type of loss-controlled dynamics; a proof for per-parameter methods and momentum remains open (Limitation (iii)).

We expect the same mechanism beyond quadratic networks, since learning is incremental there as well. Our experiments with ReLU and absolute-value activations (Figure 2) already show similar scaling behavior. Extending the theory to general link functions is an interesting direction for future work (Limitation (i)).

Thank you for the detailed response. This largely resolves my concerns and I remain in favor of acceptance.

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

This paper analytically derives neural scaling laws of an adaptive training algorithm in one-hidden-layer, teacher-student regression with quadratic activations. The authors consider a limit of large input dimension, a hidden width extensive in the input dimension, and a teacher with power-law distributed hidden node coefficients. They begin with a gradient flow analysis, before deriving results for finite step-size online stochastic gradient descent. Training uses an adaptive learning rate depending on accumulated loss. With this adaptive learning rate, nearly optimal sample complexity exponents are achieved compared to fixed learning rate schedules, where the learning rate would need to be scheduled manually depending on the total number of update steps. Numerical experiments, including also different activation functions and different, practically used adaptive algorithms, corroborate the results.

Critical strengths

Given their widespread use, analyzing adaptive algorithms is an important issue. Along with the feature learning regime, extensive network width, and a power law in the teacher, the authors present considerable analytical results.

The use of quadratic activation functions is of significant contemporary interest, especially due to their tractability.

Demonstrating information-theoretically optimal exponents of loss scaling, up to polylog factors, within an online stochastic gradient setup establishes a valuable connection between empirical risk minimization and online algorithms.

The presentation of the proof techniques is very clear.

Critical weaknesses

The adaptive aspect of the analyzed algorithm is limited to a single adaptive learning rate schedule. This does not account for the typical property of parameter-specific adaptivity found in practical adaptive algorithms, such as Adam.

The learning rate adapts based on an accumulated loss. The learning rate adapts based on accumulated loss. Unlike other adaptive algorithms, it does not depend on (stochastic) gradients.

Minor points:

There is a typo in lines 110-112: a minus sign is missing from the exponents of d/Nd/N. Currently, the risk would increase with the sample size NN.

The population risk and the per-example loss are initially introduced as P\mathcal{P} and L\mathcal{L}, respectively, but in line 367, the notation seems to switch to plain PP and LL (similarly in the appendix).

The character ϵ\epsilon is overloaded: the first occurrence is as label noise, but then it is used as a stability constant.

The use of the term risk is slightly ambiguous. Sometimes it means excess risk (σ2\sigma^2 subtracted), and sometimes it means full population risk. The figures do not explicitly state what is plotted.

Questions for authors

Can the authors give an intuition why the adaptive learning rate schedule, depending on accumulated loss, could share characteristics with adaptive algorithms closer to ones used practically (based on gradients, adaptive per parameter)?

Are the slopes / guide to the eyes in the figures always fitted? And if so, what is the fitting procedure, and can you discuss deviations between theory prediction and the potential fits?

Are there any restrictions or assumptions on teacher width rr compared to the student width rsr_s in the theoretical derivation? Is the regime rs>rr_s > r shown in Figure 1(a) compatible with the theory?

3 comments
AuthorsOpenReview ↗

Response to Reviewer tvqf (1/2): W1, W2 and Q1

Thank you for the constructive review and the careful list of minor points (answered in part 2/2).

W1, W2. A single, loss-based learning rate versus per-parameter, gradient-based methods. In our model, a loss-based rule and a gradient-based rule are driven by the same quantity: the loss our rule accumulates is essentially what RMSprop and Adam accumulate.

The per-sample gradient with respect to wiw_i, the weight vector of neuron ii, is the residual times a vector that does not depend on the label,

∇wiLt+1(Wt)=22rs (y^t+1−yt+1)(xt+1xt+1⊤−Id)wi,\nabla_{w_i}\mathcal L_{t+1}(W_t)=\frac{2\sqrt{2}}{r_s}\ (\hat y_{t+1}-y_{t+1})\left(x_{t+1}x_{t+1}^\top-I_d\right)w_i ,

and the squared residual is the per-sample loss. Squared gradients are therefore proportional to the loss, so a loss-based rule is a gradient-based rule here (W2). For W1, the square of the aa-th entry of this gradient, which is what RMSprop and Adam accumulate for the weight waiw_{ai}, has mean approximately

8rs2 P(Gt)(∥wi∥2+wai2),wai2≪∥wi∥2,\frac{8}{r_s^2}\ \mathcal P(G_t)\left(\Vert w_i\Vert^2+w_{ai}^2\right),\qquad w_{ai}^2\ll\Vert w_i\Vert^2 ,

with Gt=WtWt⊤/rsG_t=W_tW_t^\top/r_s. The second-moment estimate of RMSprop or Adam is therefore an aggregate of the past loss times a per-neuron factor ∥wi∥2\Vert w_i\Vert^2, with almost no dependence on the coordinate aa.

Substituting this estimate into their update gives, for neuron ii, a drift proportional to

γt (Ψ∗−Gt) wi∥wi∥,\gamma_t\ \frac{(\Psi_\ast-G_t)\ w_i}{\Vert w_i\Vert},

where γt\gamma_t is the inverse root of this aggregated loss. These methods thus effectively reduce to the type of dynamics we analyze: a gradient method, normalized per neuron, whose step size is controlled by the aggregated loss. Our theory characterizes the optimal learning-rate schedule for such dynamics, the one that tracks the signal-to-noise ratio of the feature being learned, and shows that the aggregation rule of (ADP) attains it.

The per-neuron normalization only changes constants. Under the dynamics of Section 4, the squared neuron norms ∥wi∥2\Vert w_i\Vert^2 are nearly equal at initialization. Later in training they have mean Tr(Gt)\mathrm{Tr}(G_t) and variance approximately 2∥Gt∥F22\Vert G_t\Vert_F^2 across neurons, neither of which depends on the width, so the per-neuron time scales differ by factors of order one. This is consistent with Figure 2, where RMSprop and Adam follow risk curves similar to those of our rule.

We added this computation to the revised manuscript (Remark 1 in Appendix A). It is a heuristic, and a rigorous analysis of per-parameter methods is left for future work (Limitation (iii)).

Q1. In short: in this model the per-coordinate statistics of RMSprop and Adam reduce to an aggregate of the past loss times a per-neuron factor, so these methods reduce to the same type of loss-controlled dynamics as our rule. The computation is in our response to W1 and W2 above.

AuthorsOpenReview ↗

Response to Reviewer tvqf (2/2): minor points, Q2 and Q3

Minor points. All accepted.

  • Table 1. Thank you. The ERM entries now read (N/d)1−2α(N/d)^{1-2\alpha} and (N/d)(1−2α)/(2α)(N/d)^{(1-2\alpha)/(2\alpha)}. In the adaptive row, the symbol inside the bracket is now ∧\wedge, as in Theorems 1 and 2.
  • Notation. P\mathcal P and L\mathcal L are now used throughout, including line 367 and Appendices C–D.
  • Overloaded ϵ\epsilon. The stability constant is renamed ϵopt\epsilon_{\mathrm{opt}}; ϵ\epsilon is kept for the noise variable in the labels.
  • "Risk". In the revised manuscript, "risk" refers to the excess risk R=P−σ2=∥Gt−Ψ∗∥F2R=\mathcal P-\sigma^2=\Vert G_t-\Psi_\ast\Vert_F^2 (defined at the end of Section 2.1), and P\mathcal P is called the population loss; Step 5 of Section 4, which called P\mathcal P a risk, is corrected. All figures plot the excess risk: note that the curves in Fig. 1(a) fall below σ2=0.25\sigma^2=0.25. The caption of Figure 2 and Appendix A now say so. Q2. Yes, all slopes shown in the figures are fitted. We fit a line by least-squares regression in log–log coordinates over the range where the curve is linear; this range was selected by visual inspection, and the reported number is the slope of the fitted line.

Figure 1 allows a comparison with the theory for α=1.25\alpha=1.25. In the noise-dominated phase the fitted and predicted slopes agree closely: −0.60-0.60 in Fig. 1(a) and −0.61-0.61 in Fig. 1(b), against the prediction (1−2α)/(2α)=−0.6(1-2\alpha)/(2\alpha)=-0.6. In the first phase the fitted slopes are −1.26-1.26 in Fig. 1(a) and −1.41-1.41 in Fig. 1(b), against the prediction 1−2α=−1.51-2\alpha=-1.5. They are shallower because this phase is short: it ends at t≍σ−2/(2α−1)t\asymp\sigma^{-2/(2\alpha-1)}, a few rescaled time units for σ=0.5\sigma=0.5, so the fitting window overlaps the transition to the second phase. Fig. 1(b), which uses smaller σ\sigma and has a longer first phase, is closer to the prediction.

In the revised manuscript, the caption of Figure 2 describes the fitting procedure, and each panel reports the fitted slope of our algorithm's curve, which the caption compares with the theoretical values. In both cases the fits agree with the noise-dominated prediction (1−2α)/(2α)(1-2\alpha)/(2\alpha). For α=1.0\alpha=1.0, the fitted slopes are −0.51-0.51 (quadratic), −0.46-0.46 (ReLU) and −0.48-0.48 (absolute value), against the prediction −0.5-0.5. For α=1.25\alpha=1.25, they are −0.60-0.60, −0.55-0.55 and −0.63-0.63, against the prediction −0.6-0.6.

Q3. No relation between them is assumed: r≍dβr\asymp d^\beta with β∈(0,1]\beta\in(0,1], and rs≥Ωα(1)r_s\ge\Omega_\alpha(1) in Theorem 1 or rs≫log⁡2dr_s\gg\log^2 d in Theorem 2. The width enters only through the approximation term ∑i>rsλi2\sum_{i > r_s}\lambda_i^2, which is an empty sum when rs≥rr_s\ge r, as in Fig. 1(a) (rs=1024r_s=1024, r=512r=512). So that regime is compatible with the theory.

Thank you for the detailed reply. The new remark on RMSprop and Adam, together with the other revisions, resolves most of my concerns, and I continue to support acceptance.

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

This paper studies adaptive optimization in quadratic teacher–student networks with power-law signal strengths. The proposed algorithm adjusts a global learning rate using accumulated prediction losses. By analyzing sequential feature learning through an effective-time equation, the authors derive risk scaling exponents in both signal-dominated and noise-dominated regimes. Experiments compare a single adaptive run against fixed-learning-rate SGD tuned for different training horizons, and examine whether Adam and RMSprop show similar behavior.

Critical strengths
  • The paper provides a useful explanation of how adaptive learning rates can improve scaling laws. As training progresses toward weaker features, the algorithm adjusts its learning rate based on the remaining loss and noise level. This allows a single adaptive run to approach the performance of fixed-learning-rate SGD tuned separately for different training horizons. The transition between signal-dominated and noise-dominated regimes also provides insight into how the learning rate should change during feature learning.
  • The theoretical analysis extends beyond population dynamics to online stochastic updates. The quadratic model allows the authors to characterize the Gram-matrix dynamics explicitly, while controlling the interaction between accumulated losses, adaptive learning rates, and stochastic feature recovery is technically nontrivial. The experiments across different training horizons, activation functions, and optimizers provide further support for the proposed mechanism.
Critical weaknesses
  • The noiseless scaling result needs a clearer statement of its validity range and a more complete asymptotic argument. Section 4 gives F∗′(t)=1V(t)+ϵ,V(t)≥0F_*'(t)=\frac{1}{\sqrt{V(t)+\epsilon}},V(t)\geq 0. For any fixed ϵ>0\epsilon>0, this implies F∗(t)≤tϵF_*(t)\leq \frac{t}{\sqrt{\epsilon}}. Thus, the claimed noiseless scaling F∗(t)≍tαF_*(t)\asymp t^\alpha for α>1\alpha>1 cannot hold for arbitrarily large t. The authors should clarify whether this result requires V(t)≫ϵV(t)\gg\epsilon or a joint limit with ϵ→0\epsilon\to0, and how this affects the online guarantee.
  • The dominant-balance argument in Section 4 drops the term qF∗′(t)/(2t)qF_*'(t)/(2t), which is of the same order as F∗′′(t)F_*''(t) under the proposed power-law ansatz. This term seems particularly important for the increasing-learning-rate regime. Since Appendix B refers back to Section 4 as the proof of Theorem 1, a more complete justification would be helpful.
  • The experimental implementation of ADP is not entirely clear. The theoretical algorithm uses a time-varying polynomial discount, while Appendix A mentions an ADP second-moment parameter β2\beta_2 shared with Adam and RMSprop. It is unclear whether the experiments use the proposed polynomial discount or a fixed exponential moving average. These two choices can behave differently as the loss approaches the noise floor. Clarifying the exact update rule and hyperparameter settings would help establish how closely the experiments validate the theory.
Questions for authors

See Weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer fNDz

We thank our reviewer for the careful reading. Both technical points (W1, W2) are correct. They lead to a corrected statement of Theorem 1 and to a corrected dominant-balance step in Section 4. The exponents in the paper are unchanged; the range of validity and the constants are now explicit. Below, ϵopt\epsilon_{\mathrm{opt}} denotes the stability constant (renamed from ϵ\epsilon in the revision).

W1. The stability-constant floor. We agree: F∗′(t)=(V(t)+ϵopt)−1/2≤ϵopt−1/2F_\ast'(t)=(V(t)+\epsilon_{\mathrm{opt}})^{-1/2}\le\epsilon_{\mathrm{opt}}^{-1/2}, so F∗(t)≍tαF_\ast(t)\asymp t^\alpha with α>1\alpha > 1 cannot hold for all tt at fixed ϵopt\epsilon_{\mathrm{opt}}. The signal-dominated law requires V(t)≳ϵoptV(t)\gtrsim\epsilon_{\mathrm{opt}}, as you suggest. The corrected statement, for q>2α−2q > 2\alpha-2 and t≥1t\ge 1, is

F∗(t)≍min⁡{tα, t/σ, t/ϵopt}.F_\ast(t)\asymp\min\lbrace t^{\alpha},\ \sqrt{t}/\sigma,\ t/\sqrt{\epsilon_{\mathrm{opt}}}\rbrace.

Concretely:

  • α≤1\alpha\le 1: the results are unchanged for any ϵopt=O(1)\epsilon_{\mathrm{opt}}=O(1).
  • α>1\alpha > 1, σ>0\sigma > 0: the noise-dominated rate is unchanged for any ϵopt=O(1)\epsilon_{\mathrm{opt}}=O(1). The signal-dominated phase that precedes it requires ϵopt≲σ(4α−4)/(2α−1)\epsilon_{\mathrm{opt}}\lesssim\sigma^{(4\alpha-4)/(2\alpha-1)}; for larger ϵopt\epsilon_{\mathrm{opt}}, the learning rate is capped at ϵopt−1/2\epsilon_{\mathrm{opt}}^{-1/2} during that phase.
  • α>1\alpha > 1, σ=0\sigma=0: F∗≍tαF_\ast\asymp t^\alpha holds only for t≲ϵopt−1/(2α−2)t\lesssim\epsilon_{\mathrm{opt}}^{-1/(2\alpha-2)}. On a horizon TT it requires ϵopt≲T2−2α\epsilon_{\mathrm{opt}}\lesssim T^{2-2\alpha}. We updated Theorems 1 and 2 accordingly, and added this point to the limitations (item (iv)).

W2. The dropped term. Thank you for pointing this out. We agree: with F∗=CtuF_\ast=Ct^u, the term qF∗′/(2t)qF_\ast'/(2t) is of order tu−2t^{u-2}, the same as F∗′′F_\ast'', so it cannot be dropped. Keeping it changes the constants but not the exponents. The equation reads

F∗′′(t)≈−12(R(tlog⁡d)+σ2)F∗′(t)3+q2tF∗′(t),F_\ast''(t) \approx -\frac{1}{2}\left(R(t\log d) + \sigma^2\right) F_\ast'(t)^3 + \frac{q}{2t}F_\ast'(t),

and the terms balance as follows.

Noise-dominated regime (u=1/2u = 1/2):

−14Ctu−2≈−116σ2C3t3u−3+Cq4tu−2.-\frac{1}{4} C t^{u - 2} \approx -\frac{1}{16} \sigma^2 C^3 t^{3u - 3} + \frac{Cq}{4} t^{u - 2}.

The exponents agree because 3u−3=u−23u-3=u-2, and the constants agree for C=2q+1/σC = 2 \sqrt{q+1}/\sigma.

Signal-dominated regime (σ→0\sigma \to 0, u=αu=\alpha): writing R≃cRF∗(1−2α)/αR\simeq c_R F_\ast^{(1-2\alpha)/\alpha},

Cα(α−1)tu−2≈−12cRC(1−2α)/αt1−2α⋅α3C3t3u−3+Cqα2tu−2.C \alpha (\alpha - 1) t^{u - 2} \approx -\frac{1}{2} c_R C^{(1 - 2\alpha)/\alpha} t^{1 - 2\alpha} \cdot \alpha^3 C^3 t^{3u - 3} + \frac{C q \alpha}{2} t^{u - 2}.

The exponents agree because 1−2α+3α−3=α−21-2\alpha+3\alpha-3=\alpha-2, and the constants agree for C1/α=(q+2−2α)/(cRα2)C^{1/\alpha}=(q+2-2\alpha)/(c_R\alpha^2).

Positivity of the last constant requires q>2α−2q > 2\alpha-2, which is the condition in the corrected statement. We updated Step 4 of Section 4 accordingly.

W3. What the experiments run. Thank you for pointing this out. The revised Appendix A states the following.

  • ADP (Figs. 1–2). We use the accumulator update of Eq. (3.6), with βt\beta_t and qq as in Theorem 2.
  • RMSprop and Adam (Fig. 2). We use their standard update rules, given in Appendix A, including the normalization factor (1−β2)(1-\beta_2) in the second-moment update. We considered two choices of β2\beta_2: the usual constant value β2=0.999\beta_2 = 0.999, and the time-varying value β2,t=1−βt\beta_{2,t} = 1-\beta_t, with βt\beta_t as in Theorem 2. For both methods the time-varying choice performed significantly better, and it is the one shown in Figure 2. For Adam, a constant β1=0.99\beta_1 = 0.99 performed significantly better than a time-varying one, and it is the one shown.
  • Learning rates. For ADP, we swept the base learning rate over a logarithmically spaced grid in [10−3,2][10^{-3}, 2] and report the best value. RMSprop and Adam use the same base learning rate as ADP. Our theory covers the aggregation rule of (ADP); the comparison with RMSprop and Adam in Figure 2 is empirical (see Limitation (iii)).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.