Better LMO-based Momentum Methods with Second-Order Information

• URL: http://arxiv.org/abs/2512.13227v1
• Date: Mon, 15 Dec 2025 11:43:09 GMT
• Title: Better LMO-based Momentum Methods with Second-Order Information
• Authors: Sarit Khirirat, Abdurakhmon Sadiev, Yury Demidovich, Peter Richtárik,
• Abstract summary: Hessian-Corrected Momentum (HCM) aims to improve momentum convergence rates.<n>Hessian-Corrected Momentum can adapt to the geometry of the problem and achieve a faster rate than traditional momentum.<n>We extend the Linear Minimization Oracle framework by integrating HCM, and provide convergence guarantees under relaxed smoothness and arbitrary norm settings.
• Score: 48.580700968416444
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The use of momentum in stochastic optimization algorithms has shown empirical success across a range of machine learning tasks. Recently, a new class of stochastic momentum algorithms has emerged within the Linear Minimization Oracle (LMO) framework--leading to state-of-the-art methods, such as Muon, Scion, and Gluon, that effectively solve deep neural network training problems. However, traditional stochastic momentum methods offer convergence guarantees no better than the ${O}(1/K^{1/4})$ rate. While several approaches--such as Hessian-Corrected Momentum (HCM)--have aimed to improve this rate, their theoretical results are generally restricted to the Euclidean norm setting. This limitation hinders their applicability in problems, where arbitrary norms are often required. In this paper, we extend the LMO-based framework by integrating HCM, and provide convergence guarantees under relaxed smoothness and arbitrary norm settings. We establish improved convergence rates of ${O}(1/K^{1/3})$ for HCM, which can adapt to the geometry of the problem and achieve a faster rate than traditional momentum. Experimental results on training Multi-Layer Perceptrons (MLPs) and Long Short-Term Memory (LSTM) networks verify our theoretical observations.

Related papers

• Majorization-Minimization Networks for Inverse Problems: An Application to EEG Imaging [4.063392865490957]
  Inverse problems are often ill-posed and require optimization schemes with strong stability and convergence guarantees.<n>We propose a learned Majorization-Minimization (MM) framework for inverse problems within a bilevel optimization setting.<n>We learn a structured curvature majorant that governs each MM step while preserving classical MM descent guarantees.
  arXiv  Detail & Related papers  (2026-01-23T10:33:45Z)
• Improved Convergence in Parameter-Agnostic Error Feedback through Momentum [49.163769734936295]
  We study normalized error feedback algorithms that combine EF with normalized updates, various momentum variants, and parameter-agnostic, time-varying stepsizes.<n>Our results hold with decreasing stepsizes and small mini-batches.
  arXiv  Detail & Related papers  (2025-11-18T13:47:08Z)
• Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
  We propose a new family of algorithms that uses the linear minimization oracle (LMO) to adapt to the geometry of the problem.<n>We demonstrate significant speedups on nanoGPT training using our algorithm, Scion, without any reliance on Adam.
  arXiv  Detail & Related papers  (2025-02-11T13:10:34Z)
• E$^2$M: Double Bounded $α$-Divergence Optimization for Tensor-based Discrete Density Estimation [3.9633191508712398]
  We present a generalization of the expectation-maximization (EM) algorithm, called E$2M algorithm.<n>It circumvents this issue by first relaxing the optimization into minimization of a surrogate objective based on the Kullback-Leibler (KL) divergence.<n>Our approach offers flexible modeling for not only a variety of low-rank structures, including the CP, Tucker, and Train formats.
  arXiv  Detail & Related papers  (2024-05-28T14:28:28Z)
• Neural-Kernel Conditional Mean Embeddings [26.862984140099837]
  Kernel conditional mean embeddings (CMEs) offer a powerful framework for representing conditional distribution, but they often face scalability and challenges. We propose a new method that effectively combines the strengths of deep learning with CMEs in order to address these challenges. In conditional density estimation tasks, our NN-CME hybrid achieves competitive performance and often surpasses existing deep learning-based methods.
  arXiv  Detail & Related papers  (2024-03-16T08:51:02Z)
• PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates [17.777466668123886]
  We introduce PROMISE ($textbfPr$econditioned $textbfO$ptimization $textbfM$ethods by $textbfI$ncorporating $textbfS$calable Curvature $textbfE$stimates), a suite of sketching-based preconditioned gradient algorithms. PROMISE includes preconditioned versions of SVRG, SAGA, and Katyusha.
  arXiv  Detail & Related papers  (2023-09-05T07:49:10Z)
• Scalable Optimal Margin Distribution Machine [50.281535710689795]
  Optimal margin Distribution Machine (ODM) is a newly proposed statistical learning framework rooting in the novel margin theory. This paper proposes a scalable ODM, which can achieve nearly ten times speedup compared to the original ODM training method.
  arXiv  Detail & Related papers  (2023-05-08T16:34:04Z)
• Meta-Learning with Neural Tangent Kernels [58.06951624702086]
  We propose the first meta-learning paradigm in the Reproducing Kernel Hilbert Space (RKHS) induced by the meta-model's Neural Tangent Kernel (NTK) Within this paradigm, we introduce two meta-learning algorithms, which no longer need a sub-optimal iterative inner-loop adaptation as in the MAML framework. We achieve this goal by 1) replacing the adaptation with a fast-adaptive regularizer in the RKHS; and 2) solving the adaptation analytically based on the NTK theory.
  arXiv  Detail & Related papers  (2021-02-07T20:53:23Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.