CS Paper Radar

A new algorithmic approach for finding flat minima: critically damped Polyak stepsizes

Francesco Caporali, Jason M. Altschuler, Boris Hanin

cs.LG cs.AImath.OC ·submitted 2026-11-19 17:35 UTC · v1

Abstract

We present a new adaptive stepsize rule that biases gradient descent toward flatter minima in both theory and practice, and establish the first uniform-in-time guarantees for both sharpness and loss reduction for a broad class of locally quadratic objectives. Our critically damped Polyak (CDP) stepsizes multiply the classical Polyak rule by $4$ and a mild damping factor. The factor $4$ is critical in that it produces equioscillations around the manifold of minimizers $\mathcal{M}$ to leading order. Damping provably drives convergence to $\mathcal{M}$. CDP thus operates at the edge of stability by adapting its stepsizes to local curvature. Once the loss is small, its projected iterates follow gradient descent on $\log{λ_1(\nabla^2 \mathcal{L})}$ along $\mathcal{M}$ to leading order, paralleling the flatness bias of normalized gradient descent (Arora et al., 2022). Unlike normalized gradient descent, CDP step lengths shrink with the distance to $\mathcal{M}$, enabling convergence to an interpolating solution that locally minimizes sharpness at finite learning rate. We establish our theory for a broad class of non-negative losses with locally quadratic Morse-Bott structure near $\mathcal{M}$, capturing regular interpolation regimes in smooth overparameterized neural networks. Empirically, CDP stepsizes produce a flattening effect similar to that of Sharpness-Aware Minimization (SAM, Foret et al., 2021), reducing sharpness even in settings beyond our theory, including nonlinear teacher-student networks and fine-tuning of pre-trained LLMs.

Comment
56 pages, 19 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A lower bound for stepsize-based acceleration of gradient descent

cs.LG math.OCstat.ML ·2026-08-11 ·Jianhao Ma, Yuxin Chen
benchmarktheoryhighly cited similarity 0.65
Abstract

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of $O(T^{-1})$ (where $T$ denotes the number of iterations) to $O\big(T^{-\log_2(1+\sqrt{2})}\big)$ using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical $Ω(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $Ω(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.

0.44

Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence

cs.LG math.NA ·2026-08-22 ·Rodion Podorozhny
benchmark similarity 0.64
Abstract

Overparameterized networks often have ill-conditioned, saddle rich loss landscapes. They are usually trained with first-order methods that struggle on those landscapes, while many second-order methods stay infeasible at scale. Some scalable cubic methods replace the Hessian by a computationally cheap approximation and drop the exact block curvature. This paper introduces ARC-block, a blockwise adaptive regularization with cubics (ARC) optimizer. For each parameter tensor it minimizes a cubic model over the true block Hessian, with a per-block adaptive cubic constant and a monotone guard on the full loss. Large tensors are handled matrix-free in a Lanczos-built Krylov subspace. ARC-block's CubicKrylov subsolver's descent is monotone with a per-block cubic decrease bound. For exact steps, and for Krylov steps that meet the Cartis--Gould--Toint residual test, we provide an $\mathcal{O}(\sqrt{B}\varepsilon^{-3/2})$ sweep bound above a cross-block coupling floor. Another subsolver, ARC-$\varphi_1$, uses a trust-controlled exponential relaxation step. Among the cubic Newton methods evaluated here, these are the only ones whose steps stay exact on every parameter block (within the Krylov subspace), including on a $91.4$M-parameter implicit neural representation (INR). Run to convergence on FINER 2D image-fitting INR network, ARC-$\varphi_1$ reaches $133.5$ dB peak signal-to-noise ratio (PSNR), with no post peak collapse. Tuned Adam peaks at $78.2$ dB at $2{,}629$ s (step ${\sim}625$k, about $44$ minutes), further steps degrade its PSNR. On the same benchmark, SOAP, L-BFGS, and the scalable diagonal cubic method AdaCubic stay at or below Adam's $78.2$ dB peak. Over the benchmark's 20 images, run to a plateau rule, ARC-$\varphi_1$'s per-image PSNR has median $132.4$ and mean $131.5\pm3.3$ dB against tuned Adam's $72.8\pm4.5$ dB.

0.40

Affine-invariant Cubic Newton with Weak Learners

cs.LG stat.MLmath.OC ·2026-10-24 ·Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon
top venue similarity 0.64
Abstract · Accepted to 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global $\mathcal{O}(1/γ^{12}k^2)$ rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy $γ^{12}$ dependence on a worst-case `weak gradient edge' $γ$. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values $\overlineΘ_k$ along the optimization path and directional improvements $δ_k$ in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by $δ_k$. Under semi-strong self-concordance, we establish a global $\mathcal{O}(1/\overlineΘ_k^4 k^2)$ rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.

0.34

Distance-Certified Polyak-type Stepsizes for Subgradient Methods under Hölder Growth

eess.SY math.OC ·2026-11-15 ·Kornpholkrit Weraarchakul, Yang Zheng
theory similarity 0.63
Abstract

In this paper, we consider nonsmooth convex optimization under a H{ö}lder growth condition, with quadratic growth and weak sharp minima as two important special cases. Existing subgradient methods often employ predetermined decaying stepsize schedules, whereas the classical Polyak stepsize selects its stepsize adaptively but requires knowledge of the optimal value. We introduce a new distance-certified subgradient method (\DCSG) that follows a one-step optimization principle analogous to that underlying the Polyak stepsize, without requiring the optimal value. Specifically, \DCSG{} maintains a valid upper certificate for the current squared distance to the solution set. The method selects each stepsize by minimizing the worst-case upper bound on the next squared distance over all distances consistent with this certificate. We show that the resulting minimax problem admits a closed-form solution, yielding an explicit adaptive stepsize update. Under uniformly bounded subgradients, \DCSG{} improves upon the convergence rate of the classical subgradient method and matches the state-of-the-art rates for Lipschitz convex optimization under H{ö}lder growth. In particular, it achieves linear convergence under sharp growth. Numerical experiments illustrate the performance of \DCSG.

0.23

Classification with Large-Step Gradient Descent: Unifying Self-Stabilization and Convergence Rates

cs.LG math.OC ·2026-11-12 ·Salma Tarmoun, Lachlan Ewen MacDonald, Konstantinos Emmanouilidis, Ziqing Xu, René Vidal
similarity 0.63
Abstract

Neural networks are often trained with gradient descent (GD) using step sizes that exceed classical stability thresholds, a regime where standard convergence theory no longer applies. Despite exhibiting non-monotonic loss and oscillatory dynamics, this regime frequently leads to faster convergence and better generalization. Existing theoretical perspectives offer complementary but incomplete insights: one identifies a self-stabilization mechanism that drives GD toward flat regions but does not yield convergence rates; another derives rigorous rates for specific losses but does not explain the underlying stabilization mechanism; and a third unifies these views for overparameterized least squares, but relies on the existence of a minimizer manifold, which is absent in classification settings. In this work, we extend this unified geometric perspective to exponential-tail losses, including logistic and cross-entropy losses in separable linear classification, where the loss infimum is not attained at any finite parameter. We identify a curvature-defined reference subspace that replaces the role of the minimizer manifold, yielding a coupled dynamical system in which orthogonal oscillations are damped by parallel progress along directions of decreasing sharpness. Under regularity conditions, which we verify for logistic and multiclass cross-entropy losses on symmetric data models, we derive explicit bounds for the iterates, not just the loss, covering both the unstable and stable regimes, and revealing a three-phase damping structure in the latter. Our analysis further uncovers a transient implicit bias induced by large step sizes: although GD converges asymptotically to the max-margin direction, large steps can leave persistent orthogonal residuals and, in certain geometries, amplify them, affecting finite-time alignment with the max-margin direction.

0.06

Do Flatter Minima Drive Better Generalization? An Algorithmic Separation in Grokking

cs.LG ·2026-10-08 ·Mohnish Harwani
similarity 0.63
Abstract

Flat loss landscapes have long been linked to better generalization in neural networks. However, its role as a causal mechanism for generalization is less established. Grokking provides an unique testbed to understand this distinction: models are prone to fit observed data using non-generalizing structure and remain in that regime for prolonged periods, transitioning to generalization only under particular training conditions. In this work, we study whether flat loss landscapes can act as a driving mechanism in this transition. While recent work has argued for flatness as a necessary geometric condition for this transition, we find that biasing training toward flatter solutions using sharpness-aware minimization (SAM) is insufficient to reliably induce this transition, despite producing flatter solutions. However, when SAM is paired with mechanisms that drive generalization such as weight decay, an interesting property emerges: SAM can accelerate the transition to generalizing solutions by up to 4x at the epoch-level. We theoretically untangle this relationship between SAM and weight decay using a minimal interpolating two-layer ReLU model with both memorizing and generalizing solutions. We show that even in this simple setup, flatness alone cannot distinguish a memorizing solution from a generalizing one, while weight decay favors generalizing solutions. However, under a local stability analysis, there exists a window where a memorizing interpolant is locally stable under gradient descent but unstable under SAM in the low-norm regime, which can explain SAM's ability to accelerate this transition. Overall, our results provide a more interpretable account of the role of flatness in driving generalization, especially in settings where models are vulnerable to minimizing loss through learning non-generalizing structure.

0.10

Beyond Conventional Federated Learning via High-Order Regularization

cs.LG stat.ML ·2026-09-09 ·Alireza Kabgani, Masoud Ahookhosh
similarity 0.63
Abstract

Federated clients that perform several local optimization steps can return parameter displacements with widely different magnitudes. The quadratic regularization of FedProx grows linearly with displacement and therefore offers limited control over the contrast between ordinary and unusually large client movements. We here introduce HiFedProx, which replaces the quadratic penalty with a scale-matched power-type regularizer indexed by $p\geq2$. All powers have the same regularization-gradient magnitude at a reference displacement $R$, while every $p>2$ gives a weaker response below $R$ and a stronger response above it. An exact affine reference calculation shows that increasing $p$ compresses relative displacement disparities, although very large powers approach fixed-radius behavior and increase local curvature. HiFedProx combines this geometry with finite-budget stochastic client optimization and same-minibatch Armijo backtracking. In paired five-seed experiments on a frozen 60-writer FEMNIST subset, a common-parameter study over $p\in\{2,3,4,5,6,7,8\}$ shows similar clean-training performance but substantial gains under composite stress. The lowest moderate- and severe-stress losses occur at $p=7$ and $p=6$, improving over $p=2$ by $11.44\%$ and $23.16\%$, respectively. Although displacement-tail ratios continue to decrease through $p=8$, predictive performance peaks in an intermediate range and Armijo trial cost increases with $p$. These results indicate that the exponent should be calibrated rather than maximized. In our experiments, $p=5$--$7$ provides the most useful range.

0.33

Adaptively Incorporating Directional Hints into Zeroth-Order Optimization

cs.LG math.OC ·2026-09-08 ·Alexander Ryabchenko, Jian Qian, Wenlong Mou
similarity 0.62
Abstract

We study zeroth-order optimization of nonconvex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order $O(1/T)$ rate and the zeroth-order $O(d/T)$ rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on nonconvex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.

0.28