acceptodds
Under review as a conference paper at ICLR 2027

Unveiling Lookahead’s Potential in Sharpness-Aware Minimization: Convergence and Generalization Revisited

Abstract

Deep learning models have achieved remarkable success across various applications, but over-parameterized networks often suffer from overfitting and limited generalization, limiting their real-world performance. Sharpness-Aware Lookahead (SALA), which integrates Sharpness-Aware Minimization (SAM) with the lookahead mechanism, has been proposed to improve generalization, training stability, and convergence. However, recent theoretical studies suggest that lookahead may delay convergence, which appears to contradict empirical observations. This discrepancy raises a fundamental question: how does lookahead affect the generalization and optimization behavior of SAM? To answer this question, we develop a systematic theoretical framework to derive tighter generalization and excess risk bounds for SALA under relaxed assumptions. Our results show that the lookahead parameter affects optimization and generalization in opposite directions: 1) the optimization bound decays faster as increases, while 2) the generalization bound increases with through both the leading factor and the power-law term . We present detailed comparisons with prior theoretical studies and empirical observations to support the validity of our findings. Furthermore, the analysis extended to the stochastic gradient descent-based lookahead algorithm uncovers a similar impact of lookahead on generalization and optimization behaviors from both theoretical and empirical perspectives.

Primary area:
learning theory
Keywords:
Sharpness-Aware Minimization, Lookahead, Generalization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_GYupOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper theoretically studies how Lookahead affects SAM when they are tied together. Detailedly, it analyzes the generalization and optimization bounds of SALA and investigates the different roles of the Lookahead hyperparameters. The theorerical findings are also validated with empirical results.

Critical strengths

This paper is well-motivated and easy to follow. It theoretically reveals that the optimization bound negatively correlates with the lookahead parameter, while the generalization bound positively correlates with α\alpha. This finding suggests a tradeoff, which may be useful in tuning hyperparameters. Moreover, different from previous studies, the authors present the first generalization guarantee for SALA in the non-smooth setting.

Critical weaknesses

None

Questions for authors
  • I noticed most experiments are run with SGD, but I am not sure if the mometum has ever been used. If not, please run such a comparision and report whether the findings are universal.

  • In Section 4.1, the perturbation radiu ρ\rho is set to 0.0005, which is relatively small to the popular choice of 0.05. Please justify.

  • Given the theoretical implications, is there any practical advice on the choice of α\alpha and kk to balance the generalization and generalization?

3 comments

Q1: I noticed most experiments are run with SGD, but I am not sure if the momentum has ever been used. If not, please run such a comparison and report whether the findings are universal.

A1: Thank you for this suggestion. We have added a comparison between SGD and SGD with momentum in Appendix A.3. Figure 3 shows consistent trends across both optimizer settings: increasing α\alpha accelerates optimization convergence, whereas decreasing α\alpha reduces the empirical generalization gap. Moreover, the observed dependence on α\alpha is consistent with the exponential dependence predicted by our theoretical bounds. These results support the optimization and generalization trade-off and indicate that our findings are universal across the SGD and momentum-SGD settings evaluated here.

Q2: In Section 4.1, the perturbation radii ρ\rho is set to 0.0005, which is relatively small to the popular choice of 0.05. Please justify.

A2: Thank you for this comment. We have added experiments with ρ=0.05\rho=0.05 using SALA and ResNet-18 on CIFAR-10 in Appendix A.4: “Additional Results with a Larger Perturbation Radius”. The observed trends remain consistent: increasing α\alpha accelerates optimization convergence, whereas decreasing α\alpha reduces the empirical generalization gap. The results are also consistent with the exponential dependence on α\alpha predicted by our theoretical bounds, supporting our findings at a larger perturbation radius.

Our original choice of ρ=0.0005\rho=0.0005 was motivated by the small-perturbation regime considered in our excess-risk analysis, where we set ρ=1/n\rho=1/n. Although this fixed value does not equal 1/n1/n for every dataset, it is closer to the theoretical scale than ρ=0.05\rho=0.05 for the sample sizes considered. Moreover, comparable perturbation radii have also been used in prior work. For instance, Wang et al. [1] used ρ=0.0001\rho=0.0001 for their LookSAM baseline when training molecular graph transformer models, providing precedent for considering small perturbation radii in SAM-based methods.

[1] Efficient Sharpness-Aware Minimization for Molecular Graph Transformer Models.

Q3: Given the theoretical implications, is there any practical advice on the choice of α\alpha and kk to balance the generalization and generalization?

A3: Our theoretical results suggest that the choice of α\alpha depends on several factors. Theorem 4.1 gives the excess-risk bound

ϵexc=O(T−αμ4L+T3ακ4Lnk+E[FS(w(S))]nkT3ακ8L).\epsilon_{exc}=O(T^{-\frac{\alpha\mu}{4L}}+\frac{T^{\frac{3\alpha\kappa}{4L}}}{nk}+\sqrt{\frac{E[F_S(w(S))]}{nk}}T^{\frac{3\alpha\kappa}{8L}}).

If E[FS(w(S))]=0E[F_S(w(S))]=0, balancing the optimization and generalization terms yields the heuristic choice

α~=min⁡1,4Llog⁡(μnk3κ)(μ+3κ)log⁡T.\tilde{\alpha}=\min\\{1,\frac{4L\log(\frac{\mu nk}{3\kappa})}{(\mu+3\kappa)\log T}\\}.

If E[FS(w(S))]>0E[F_S(w(S))] > 0 is fixed, the square-root generalization term T3ακ8Lnk\frac{T^{\frac{3\alpha\kappa}{8L}}}{\sqrt{nk}} dominates the other generalization term. Balancing it with the optimization term yields

α~=min⁡1,4Llog⁡(4μ2nk9κ2E[FS(w(S))])(2μ+3κ)log⁡T.\tilde{\alpha}=\min\\{1,\frac{4L\log(\frac{4\mu^2nk}{9\kappa^2 E[F_S(w(S))]})}{(2\mu+3\kappa)\log T}\\}.

These estimates offer additional insight into the trade-off of α\alpha established above. Within the corresponding interior regime and with nn and kk fixed, shorter training horizons favor a larger α\alpha to accelerate optimization, whereas longer training horizons favor a smaller α\alpha to control the growing generalization contribution. See Theorem 4.1 and Remark 4.2 for details.

Our current analysis does not provide a principled rule for selecting the number of inner updates kk. We acknowledge this limitation and leave a more detailed investigation of its selection to future work.

Many thanks for the detailed response. I would like to raise my score.

Thank you for taking the time to carefully consider our response. We sincerely appreciate your positive reassessment and support.

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

This paper studies the optimization and generalization behavior of Sharpness-Aware Lookahead (SALA), which performs several inner SAM updates followed by an interpolation between the slow weights and the final fast weights. Its central objective is to characterize how the interpolation parameter α\alpha affects optimization error, generalization error, and excess risk.

The research question is relevant, but the current version has substantial issues in its assumptions, the compatibility of its optimization and stability guarantees, and the claimed sharpness of the analysis.

Critical strengths
  1. Understanding how the Lookahead interpolation affects optimization, stability, and predictive performance is useful. Studying these quantities together through an excess-risk decomposition is an appropriate direction.

  2. The algorithm retains the normalized perturbation used in SAM, and the manuscript explicitly defines the perturbation to be zero when the gradient vanishes. This provides a clear algorithmic object for the analysis.

  3. The paper includes multiple architectures and datasets, reports training loss, generalization gap, and validation loss, and describes three-seed experiments with standard-deviation shading. These choices make the qualitative behavior easier to assess.

Critical weaknesses
  1. Theorems 3.3 and 3.9 do not explicitly invoke the PL condition introduced in Assumption 2.5, although their proofs use it in Appendix B.3 and B.5. Without PL, the stated smoothness and boundedness assumptions are insufficient. If global PL is intended as a standing assumption, a more fundamental issue remains. As currently stated on Rd\mathbb R^d, global upper boundedness, global smoothness, and global PL exclude any nonconstant empirical objective.

  2. The claimed removal of bounded-gradient assumptions is not supported by the smooth main results. Theorems 3.1, 3.3, 3.7, and 3.9 assume that each loss is nonnegative, globally LL-smooth, and bounded by one. Lemma B.2 immediately implies

\le 2\sqrt{Lf(w,z)} \le 2\sqrt L.$$ Consequently, these assumptions already imply a uniform gradient bound and global Lipschitz continuity of the loss. The repeated description of these results as covering “gradient-unbounded” settings is therefore inaccurate. 3. An elementary stability argument appears to provide a better dependence on $T$ under the same assumptions and schedule. The preceding bounded-gradient implication also raises a concrete concern about the necessity and sharpness of the proposed framework. Let $G=2\sqrt L$ and write the SAM gradient as $g_\rho(w,z)=\nabla f(w,z)+e_\rho(w,z), \|e_\rho(w,z)\|\le L\rho.$ For two runs on neighboring datasets with shared initialization and sampling indices, a direct first-moment distance argument gives $D^+\le(1+L\eta)D+2\eta C, C=L\rho+\frac Gn.$ Here, the same-sample event contributes at most $(1+L\eta)D+2L\eta\rho$, while the replaced-sample event has probability $1/n$ and contributes at most $D+2G\eta$. No Lipschitz assumption on the normalized gradient direction is needed. Set $P_t=\prod_{j=1}^k(1+L\eta_{j,t})$ and $A_t=1-\alpha+\alpha P_t$. The outer interpolation yields $D_t\le A_tD_{t-1}+\frac{2C}{L}(A_t-1), D_T\le\frac{2C}{L}\left(\prod_{t=1}^T A_t-1\right).$ Under the same condition $\eta_{j,t}\le1/(4Lkt)$ as Theorem 3.1, $P_t\le e^{1/(4t)}$. Using $\log(1-\alpha+\alpha e^x)\le\alpha x+x^2/8$ gives $\prod_tA_t=O(T^{\alpha/4})$. Lipschitz continuity of the loss then implies \$|\epsilon_{\mathrm{gen}}| \le GD_T=O\!\left((\rho+1/n)T^{\alpha/4}\right).\$ With the paper's choice $\rho=1/n$, this becomes $O(T^{\alpha/4}/n)$, with a better asymptotic dependence on $T$ for fixed $\alpha>0$, without an additional low-training-risk assumption or a restriction on $kT/n$. The authors should compare against this direct argument under identical assumptions and schedules. In addition, the $\alpha$-dependent optimization–generalization trade-off was already a central result of [Zhou et al. (2021)](https://proceedings.neurips.cc/paper/2021/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf).
Questions for authors
  1. Is PL intended globally on Rd\mathbb R^d or only on a restricted region? How do the authors avoid the constant-objective implication of global boundedness, smoothness, and PL? If a local formulation is intended, what guarantees that all relevant iterates and perturbations remain in the region?
  2. In what precise sense do the smooth nonconvex results allow unbounded gradients, given that Lemma B.2 and f≤1f\le1 already imply a uniform gradient bound? How should Table 1 be revised?
  3. What settings differ between Figure 1 and Figure 2(d–f), and why do their final validation-loss rankings differ for the same reported architecture and dataset?
  4. Which experiments satisfy the assumptions and parameter conditions of the corrected theorems? Can the authors provide a controlled stability experiment that examines the claimed dependence on TT, kk, and nn?
5 comments

Q1: Theorems 3.3 and 3.9 do not explicitly invoke the PL condition introduced in Assumption 2.5, although their proofs use it in Appendix B.3 and B.5. Without PL, the stated smoothness and boundedness assumptions are insufficient. If global PL is intended as a standing assumption, a more fundamental issue remains. As currently stated on RdR^d, global upper boundedness, global smoothness, and global PL exclude any nonconstant empirical objective.

A1: Thank you for carefully examining our assumptions. We have revised Theorems 3.3 and 3.9 to explicitly require the PL condition and highlighted these changes in blue. We have also checked the main text and the appendix to ensure that the theorem statements are consistent with the assumptions used in their proofs.

To address the incompatibility identified by the reviewer, we have revised the proof framework and removed the global boundedness assumption f∈[0,1]f\in[0,1]. The revised optimization analysis uses the PL condition, smoothness, and the curvature lower bound λmin⁡(∇2f(w,z))≥−κ\lambda_{\min}(\nabla^2 f(\mathbf w,z))\geq-\kappa. These conditions admit nonconstant objectives; an example is f(w)=w2+3sin⁡2wf(w)=w^2+3\sin^2 w, w∈Rdw\in\mathbb R_d [1].

[1] Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition.

Q2: The claimed removal of bounded-gradient assumptions is not supported by the smooth main results. Theorems 3.1, 3.3, 3.7, and 3.9 assume that each loss is nonnegative, globally LL-smooth, and bounded by one . Lemma B.2 immediately implies ∥∇f∥≤2Lf≤2L\|\nabla f\|\leq 2\sqrt{L f}\leq2\sqrt{L} Consequently, these assumptions already imply a uniform gradient bound and global Lipschitz continuity of the loss. The repeated description of these results as covering “gradient-unbounded” settings is therefore inaccurate.

A2: Thank you for pointing this out. We have revised the proof framework and removed the assumption f∈[0,1]f\in[0,1]. We have also revised the corresponding descriptions in the main text to state more precisely that our analysis removes the uniform bounded-gradient assumption.

Specifically, we use the self-bounding property of nonnegative smooth functions, ∥∇f∥2≤2Lf\|\nabla f\|_2\leq 2\sqrt{Lf}, to control the gradient norm through the loss value. This allows us to derive stability bounds under smoothness, nonnegativity, and a finite initial empirical risk, E[FS(w0)]=O(1)E[F_S(\mathbf w_0)]=O(1), without requiring a uniform bound on the gradients. The latter requirement, imposed in previous analyses, can exclude even simple least-squares regression.

With the revised proof framework, we obtain the tighter stability bound O(T3ακ4Lnk)O(\frac{T^{\frac{3\alpha\kappa}{4L}}}{nk}), compared with the previous bound O(Tαn)O(\frac{T^\alpha}{n}), where λmin⁡(∇2f(w,z))≥−κ\lambda_{\min}(\nabla^2 f(\mathbf w,z))\geq-\kappa. Since κ\kappa controls only the magnitude of negative curvature, it can be substantially smaller than LL [2,3]. When κ≪L\kappa\ll L, the exponent 3ακ/(4L)3\alpha\kappa/(4L) is much smaller than α\alpha, yielding substantially slower growth with TT and thus a tighter asymptotic stability bound.

[2] Empirical Analysis of the Hessian of Over-Parametrized Neural Networks.

[3] An Investigation into Neural Net Optimization via Hessian Eigenvalue Density.

Q3: Under the same assumptions and step-size schedule, treating the SAM gradient as the original gradient plus a perturbation bounded by LρL\rho yields a direct first-moment stability bound: $ \epsilon_{ {gen}} =O\left((\rho+1/n)T^{\alpha/4}\right) $.

A3: Thank you for providing this direct argument. Under the original bounded-loss assumptions, it yields the stated bound O(Tα/4/n)O(T^{\alpha/4}/n). In the revised manuscript, we have removed the bounded-loss assumption f∈[0,1]f \in [0,1] and adjusted the proof framework accordingly.

Specifically, we use the Hessian lower bound λmin⁡(∇2f(w,z))≥−κ\lambda_{\min}(\nabla^2 f(w,z)) \geq -\kappa to obtain

∥w′−η∇f(w^′,z)−(w−η∇f(w^,z))∥2≤(1+ηκ)∣w′−w∣2+2Lηρ.\|w' - \eta\nabla f(\hat{w}',z)- (w - \eta\nabla f(\hat{w},z))\|_2\leq (1+\eta\kappa) |w'-w|_2+ 2L\eta\rho.

This replaces the expansion factor 1+ηL1+\eta L obtained from smoothness alone with 1+ηκ1+\eta\kappa. When κ<L\kappa < L, the resulting expansion factor is smaller.

To compare directly with your argument, we additionally impose the same bounded-gradient assumption ∣∇f(w,z)∣≤G|\nabla f(w,z)| \leq G and use the same schedule ηj,t≤1/(4Lkt)\eta_{j,t} \leq 1/(4Lkt).

For 0<κ≤L0 < \kappa \leq L, our argument yields the generalization bound O((ρ+1/n)Tακ/(4L))O((\rho+1/n)T^{\alpha\kappa/(4L)}), compared with O((ρ+1/n)Tα/4)O((\rho+1/n)T^{\alpha/4}) from smoothness alone.

Thus, the exponent is reduced by a factor of κ/L\kappa/L. This refinement is relevant when the magnitude of the most negative Hessian eigenvalue is small relative to the smoothness constant, as suggested by empirical studies of neural-network Hessians [2, 3].

The derivation is as follows. Combining the two sampling cases gives

\leq (1+\kappa\eta_{j,t})E[\Vert v_{j,t}-v_{j,t}^{(i)}\Vert_2] +2\eta_{j,t}(L\rho+G/n).$$ Iterating the inner-loop recursion and applying the Lookahead update yield $$E[\Vert w_t-w_t^{(i)}\Vert_2]+\frac{2}{\kappa}(L\rho+\frac{G}{n})\leq(1-\alpha+\alpha\prod_{j=1}^{k}(1+\kappa\eta_{j,t}))(E[\Vert w_{t-1}-w_{t-1}^{(i)}\Vert_2]+\frac{2}{\kappa}(L\rho+\frac{G}{n})).$$ Since $w_0=w_0^{(i)}$ and $\eta_{j,t} \leq 1/(4Lkt)$, we obtain $$E[\Vert w_T-w_T^{(i)}\Vert_2]\leq\frac{2}{\kappa}(L\rho+\frac{G}{n})[\prod_{t=1}^{T}(1-\alpha+\alpha\exp(\frac{\kappa}{4Lt}))-1].$$ $$E[\Vert w_T-w_T^{(i)}\Vert_2]\leq\frac{2}{\kappa}(L\rho+\frac{G}{n})[\exp(\frac{\alpha\kappa}{4L}\sum_{t=1}^{T}\frac{1}{t}+\frac{\kappa^2}{128L^2}\sum_{t=1}^{T}\frac{1}{t^2})-1].$$ $$E[\Vert w_T-w_T^{(i)}\Vert_2]\leq\frac{2}{\kappa}(L\rho+\frac{G}{n})[\exp(\frac{\alpha\kappa}{4L}+\frac{\kappa^2\pi^2}{768L^2})T^{\frac{\alpha\kappa}{4L}}-1].$$ The second inequality uses $\log(1-\alpha+\alpha e^x)\leq\alpha x+x^2/8$ for $\alpha\in[0,1]$. By the $G$-Lipschitz continuity of the loss, $$|\epsilon_{gen}|\leq\frac{G}{n}\sum_{i=1}^{n}E[\Vert w_T-w_T^{(i)}\Vert_2]=O((\rho+\frac{1}{n})T^{\frac{\alpha\kappa}{4L}}).$$ In particular, setting $\rho=1/n$ gives $|\epsilon_{gen}|=O(T^{\alpha\kappa/(4L)}/n)$. **Q4:** Is PL intended globally on $\mathbb{R}^d$ or only on a restricted region? How do the authors avoid the constant-objective implication of global boundedness, smoothness, and PL? If a local formulation is intended, what guarantees that all relevant iterates and perturbations remain in the region? **A4:** The PL condition is intended to hold globally on $\mathbb R^d$. To address the issue raised by the reviewer, we have removed the global boundedness assumption on the loss. The revised assumptions require the loss to be smooth, nonnegative, and to satisfy the PL condition. Nonnegativity imposes only a lower bound, so these assumptions do not force the objective to be constant. A simple example is the least-squares loss. Since our formulation is global, no additional argument is needed to ensure that the iterates and perturbations remain within a restricted region. **Q5:** In what precise sense do the smooth nonconvex results allow unbounded gradients, given that Lemma B.2 and $f\le 1$ already imply a uniform gradient bound? How should Table 1 be revised? **A5:** We have removed the assumption $f\in[0,1]$ from the revised analysis. The self-bounding inequality $\|\nabla f\|_2\leq 2\sqrt{Lf}$ still holds, but without a uniform upper bound on $f$, it no longer implies a uniform gradient bound. Thus, the revised results allow gradients that are not uniformly bounded, rather than requiring gradients to be unbounded. We have also updated the stability bounds reported in Table 1 and highlighted the changes in blue.

Q6: What settings differ between Figure 1 and Figure 2(d–f), and why do their final validation-loss rankings differ for the same reported architecture and dataset?

A6: Thank you for pointing this out. This was a labeling error, which we have corrected in the revised manuscript. Specifically, Fig. 2(d–f) reports results for VGG-11 on CIFAR-100, whereas Fig. 1 reports results for ResNet-18 on CIFAR-100. The validation-loss rankings therefore correspond to different architectures. We have corrected the experimental description and provided more details of the VGG-11 experimental settings in Appendix A.2.

Q7: Which experiments satisfy the assumptions and parameter conditions of the corrected theorems?

A7: Our experiments primarily examine how α\alpha affects optimization and generalization. The ResNet-18/SALA experiments on CIFAR-100 use cross-entropy loss, which is nonnegative and globally smooth with respect to the logits. Appendix A.5, “Additional Results under Convex Hölder-Continuous Gradients,” further considers a loss with Hölder-continuous gradients under the corresponding assumptions on the score functions. These experiments provide empirical support for the effects of α\alpha on optimization and generalization.

Q8: Can the authors provide a controlled stability experiment that examines the claimed dependence on TT, kk, and nn?

A8: Figures 1–5 illustrate the effect of training duration: as training progresses, the training loss decreases, consistent with the tighter optimization bound for larger TT, while the empirical generalization gap, measured as test loss minus training loss, tends to increase. These observations concern optimization and generalization rather than a direct measurement of stability.

We have also added experiments examining the effect of nn on generalization. And details are provided in Appendix A.5: “Additional Results on the Effect of Training Sample Size”. Specifically, we train ResNet-18 on CIFAR-10 using SALA and vary n∈500,1000,2000,4000,8000n\in\\{500,1000,2000,4000,8000\\} while fixing the number of inner updates at T=200T=200.

In practice, kk is typically set to a small constant and is not the primary focus of our analysis. We leave a controlled investigation of its effect to future work.

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

The paper uses stability and optimization bounds to study how the interpolation coefficient affects SALA and SGD-based Lookahead, with experiments illustrating the proposed trade-off.

Critical strengths

The unified treatment of the two optimizers is worthwhile, and the Hölder extension adds scope. The three-seed interpolation sweeps provide useful empirical motivation.

Critical weaknesses
  1. The central excess-risk rates are not established as stated. Theorems 3.1/3.7 retain an empirical-risk term that disappears in Theorem 4.1/Corollary 4.3; optimization convergence does not justify removing it. Even granting Remark 3.2's risk assumption, the SALA bound retains a Tα+1/n2T^{\alpha+1}/n^2 contribution. The advertised rate therefore needs an explicit joint growth regime. This directly affects the paper's main trade-off claim.

  2. The learning-rate statement also needs correction: Theorems 3.3/3.9 allow any sufficiently small step size, whereas the proofs use a specific reciprocal schedule. The displayed residual does not vanish at α=1/2\alpha=1/2.

  3. Figures 1 and 2(d–f) are both labeled ResNet-18/SALA on CIFAR-100, yet give different validation-loss rankings. For α=0.1\alpha=0.1, the final loss is approximately 2.3 in Fig. 1 and 1.7–1.8 in Fig. 2. Section 4.1 does not explain a protocol difference. Until reconciled, these figures cannot reliably support the empirical interpretation.

  4. The “gradient-unbounded” description is misleading for the smooth results: global smoothness and 0≤f≤10\leq f\leq1 already imply ∥∇f∥2≤2L\|\nabla f\|^2\leq2L.

Questions for authors

Under what explicit risk and growth assumptions do the full bounds yield Theorem 4.1 and Corollary 4.3?

4 comments

Q1: The central excess-risk rates are not established as stated. Theorems 3.1/3.7 retain an empirical-risk term that disappears in Theorem 4.1/Corollary 4.3; optimization convergence does not justify removing it. Even granting Remark 3.2's risk assumption, the SALA bound retains a Tα+1/n2T^{\alpha+1}/n^2 contribution. The advertised rate therefore needs an explicit joint growth regime. This directly affects the paper's main trade-off claim.

A1: Thank you for this comment. We have revised Theorem 4.1 and Corollary 4.3 and re-examined the contribution of the empirical-risk term to the excess-risk bounds. Specifically, we show that the excess risk can be controlled by the optimization error and the average model stability: ϵexc≤2ϵopt+Lϵstab+2LE[FS(w(S))]⋅ϵstab\epsilon_{exc}\leq 2\epsilon_{opt}+L\epsilon_{ stab}+\sqrt{2L \mathbb E[F_{S}(w(S))]\cdot\epsilon_{ stab}}. The derivation is provided in Lemma B.7.

For SALA, we obtain the excess-risk bound O(T−αμ4L+T3ακ4Lnk+E[FS(w(S))]nk T3ακ8L)O(T^{-\frac{\alpha\mu}{4L}}+\frac{T^{\frac{3\alpha\kappa}{4L}}}{nk}+\sqrt{\frac{ E[F_{S}(w(S))]}{nk}}\,T^{\frac{3\alpha\kappa}{8L}}), where E[FS(w(S))]nk T3ακ8L\sqrt{\frac{ E[F_{S}(w(S))]}{nk}}\,T^{\frac{3\alpha\kappa}{8L}} captures the additional contribution of the empirical-risk term. When $ E[F_{S}(w(S))]=0$, the bound becomes O(T−αμ4L+T3ακ4Lnk)O(T^{-\frac{\alpha\mu}{4L}}+\frac{T^{\frac{3\alpha\kappa}{4L}}}{nk}). When $ E[F_{S}(w(S))]=O(1)$, it becomes O(T−αμ4L+T3ακ8Lnk)O(T^{-\frac{\alpha\mu}{4L}}+\frac{T^{\frac{3\alpha\kappa}{8L}}}{\sqrt{nk}}). Both cases illustrate how α\alpha controls the trade-off between optimization and generalization.

Regarding the contribution Tα+1/n2T^{\alpha+1}/n^2, our previous presentation did not make the joint growth assumption sufficiently explicit. We assume kT/n=O(1)kT/n=O(1), under which the stability bound simplifies to O(T3ακ4Lnk)O(\frac{T^{\frac{3\alpha\kappa}{4L}}}{nk}). Thus, under this assumption, our discussion of the trade-off governed by α\alpha remains valid. We have now explicitly stated this assumption in the text introducing Theorem 4.1 and Corollary 4.3.

Q2: The learning-rate statement also needs correction: Theorems 3.3/3.9 allow any sufficiently small step size, whereas the proofs use a specific reciprocal schedule. The displayed residual does not vanish at α=1/2\alpha=1/2.

A2: Thank you for pointing this out. We have revised Theorems 3.3 and 3.9 to consistently specify the learning-rate schedule η=14Lkt\eta=\frac{1}{4Lkt} and have made this explicit in both the main text and the appendix. Since kk is typically a small positive constant, with k=5k=5 in our experiments, this corresponds to an O(1/t)O(1/t) decay schedule, which is commonly used in both theory and practice.

In the revised manuscript, we have also relaxed the assumptions in the optimization analysis by removing the bounded-loss assumption f∈[0,1]f\in[0,1]. The resulting convergence bound is O(T−αμ4L+ρ2)O(T^{-\frac{\alpha\mu}{4L}}+\rho^2), which vanishes for every α∈(0,1]\alpha\in(0,1], including α=1/2\alpha=1/2. This also broadens the range of α\alpha covered by our analysis.

Q3: Figures 1 and 2(d–f) are both labeled ResNet-18/SALA on CIFAR-100, yet give different validation-loss rankings. For$\alpha=0.1$, the final loss is approximately 2.3 in Fig. 1 and 1.7–1.8 in Fig. 2. Section 4.1 does not explain a protocol difference. Until reconciled, these figures cannot reliably support the empirical interpretation.

A3: Thank you for pointing out this inconsistency. We have corrected it in the revised manuscript. Specifically, panels (d–f) of Fig. 2 show results for VGG-11 on CIFAR-100, whereas Fig. 1 shows results for ResNet-18 on CIFAR-100. The curves therefore correspond to different architectures, explaining the difference in validation losses. We have corrected the experimental description and provided further details of the VGG-11 experimental settings in Appendix A.2.

Q4: The “gradient-unbounded” description is misleading for the smooth results: global smoothness and 0≤f≤10 \leq f \leq 1 already imply ∣∇f∣2≤2L|\nabla f|^2 \leq 2L.

A4: Thank you for this clarification. We have revised the proof framework to remove the assumption f∈[0,1]f \in [0,1]. We have also replaced “gradient-unbounded” in the main text with more precise wording, such as “removing the bounded-gradient assumptions used in existing analyses.” Specifically, we use the self-bounding property of nonnegative smooth functions, ∥∇f∥2≤2Lf\|\nabla f\|_2 \leq 2\sqrt{Lf}, to control the gradient norm through the loss value, without imposing a uniform bounded-gradient assumption.

The revised analysis also yields a tighter stability bound, O(T3ακ4Lnk)O(\frac{T^{\frac{3\alpha\kappa}{4L}}}{nk}), compared with the previous bound O(Tαn)O(\frac{T^\alpha}{n}), where λmin⁡(∇2f(w,z))≥−κ\lambda_{\min}(\nabla^2 f(w,z)) \geq -\kappa.

Since κ\kappa controls only the magnitude of negative curvature, it can be substantially smaller than LL [1,2]. When κ≪L\kappa \ll L, the exponent 3ακ/(4L)3\alpha\kappa/(4L) is much smaller than α\alpha, yielding substantially slower growth with TT and thus a tighter asymptotic stability bound.

[1] Empirical Analysis of the Hessian of Over-Parametrized Neural Networks.

[2] An Investigation into Neural Net Optimization via Hessian Eigenvalue Density.

Q5: Under what explicit risk and growth assumptions do the full bounds yield Theorem 4.1 and Corollary 4.3?

A5: Thank you for this question. Our original statement omitted some assumptions. We have revised Theorem 4.1 and Corollary 4.3 accordingly and highlighted the changes in blue.

Specifically, we assume that f(w,z)f(\mathbf{w},z) satisfies LL-smooth, nonnegative, the PL condition, and λmin⁡(∇2f(w,z))≥−κ\lambda_{\min}(\nabla^2 f(\mathbf{w},z)) \geq -\kappa. With the learning-rate schedule ητ,t=14Lkt\eta_{\tau,t} = \frac{1}{4Lkt}, perturbation radius ρ≤1n\rho \leq \frac{1}{n}, and assumptions kT/n=O(1)kT/n = O(1) and E[FS(w0)]=O(1)\mathbb{E}[F_S(\mathbf{w}_0)] = O(1), the full bounds yield the revised results in Theorem 4.1 and Corollary 4.3.

Thank you again for your time and feedback. We would be grateful to hear whether our response and revisions have fully addressed your concerns. If any questions remain or any points need further clarification, we would welcome the opportunity to discuss them with you and provide additional explanations.

Thanks for the rebuttal and correcting the figure labeling mistake. Although the authors revised the theorems, added the missing assumptions, and reworked the proofs to remove the bounded-loss issue, these are major changes to the core theoretical results that need a full re-verification beyond the rebuttal period. So I keep my rating at 2.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.