Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning
Qiang Heng [email protected] · 2025
Read Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning by Qiang Heng [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04247.txt.
Introduction
Qiang Heng and Caixing Wang stake out a middle path in optimization: cheaper than second-order methods, faster than first-order ones, in a 2025 paper. First-order steps are cheap but crawl; second-order steps fly but demand expensive matrix inversions each round. Their trick is to minimize a fixed-curvature quadratic cap over the true objective at every step.
Because the cap's curvature never changes, its matrix factorization is computed once and reused across iterations and even across regularization settings. The framework, QMME, adds momentum-style extrapolation and comes with convergence guarantees under standard assumptions, analyzed through the cap's induced norm. Applied to large kernel learning problems, including a new equation-based model for multinomial regression, it beat established rivals in reproducible Julia experiments. It also paired well with sketching approximations. The authors pitch the reuse idea as the real export.
Catalog record
| CREATOR | Qiang Heng [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-04247
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning Qiang Heng [email protected] Abstract First-order methods in convex optimization offer low per-iteration cost but often suffer from slow convergence, while second-order methods achieve fast local convergence at the expense of costly Hessian inversions. In this paper, we highlight a middle ground: minimizing a quadratic majorant with fixed curvature at each iteration. This strategy strikes a balance between per-iteration cost and convergence speed, and crucially allows the reuse of matrix decompositions, such as Cholesky or spectral decompositions, across iterations and varying regularization parameters. We introduce the Quadratic Majorization Minimization with Extrapolation (QMME) framework and establish its sequential convergence properties under standard assumptions. The new perspective of our analysis is to center the arguments around the induced norm of the curvature matrix H H . To demonstrate practical advantages, we apply QMME to large-scale kernel regularized learning problems. In particular, we propose a novel Sylvester equation modelling technique for kernel multinomial regression. In Julia-based experiments, QMME compares favorably against various established first- and second-order methods. Furthermore, we demonstrate that our algorithms complement existing kernel approximation techniques through more efficiently handling sketching matrices with large projection dimensions. Our numerical experiments and real data analysis are available and fully reproducible at https://github.com/qhengncsu/QMME.jl . 1 1 footnotetext: Corresponding author. † † shortheadings: Inertial Quadratic Majorization Minimization / Heng and Wang † † firstpage: 1 † † editor: My editor keywords Quadratic Majorization, Momentum Extrapolation, Kernel Methods, Numerical Linear Algebra, Nyström Approximation 1 Introduction In this article, we are primarily concerned with minimizing a smooth and convex function f:\mathbb{R}^{n}\rightarrow\mathbb{R} for which the following quadratic majorization is globally available: f(y)\leq f(x)+\nabla f(x)^{\top}(y-x)+\frac{1}{2}(y-x)^{\top}H(y-x), (1) where H\in\mathbb{R}^{n\times n} is a positive definite symmetric matrix. Distinct from the Newton-Raphson algorithm, H here is a constant matrix and does not depend on the current iterate. If we make the further assumption that f is twice-differentiable, then the matrix H is an upper bound of the actual Hessian matrix \nabla^{2}f(x) . Conversely, if we have \nabla^{2}f\preceq H , meaning H-\nabla^{2}f is always positive semidefinite, then the quadratic upper bound ( 1 ) follows from the integral \displaystyle f(y) \displaystyle= \displaystyle f(x)+\nabla f(x)^{\top}(y-x) \displaystyle+\,(y-x)^{\top}\!\int_{0}^{1}\nabla^{2}f[x+t(y-x)](1-t)\,dt\,(y-x). In particular, if \nabla f is L -Lipschitz and H=LI_{n} ( I_{n} is the identity matrix), then ( 1 ) represents the well-known quadratic upper bound for functions with Lipschitz continuous gradient. In this paper, we are interested in the more general case where H is non-diagonal and contains curvature information of f . Leveraging the quadratic majorization ( 1 ) , the majorant h(x) of f(x) at x=x^{k} writes as f(x)\leq h(x|x^{k})=f(x^{k})+\nabla f(x^{k})^{\top}(x-x^{k})+\frac{1}{2}(x-x^{k})^{\top}H(x-x^{k}). (2) The iteration x^{k+1}=\text{argmin}_{x}\;h(x|x^{k}) is an instance of majorization minorization (MM) algorithm ( Hunter and Lange 2004 ) that ensures monotonic descent of f(x^{k}) . Since H remains constant, matrix decompositions such as Cholesky or spectral decompositions can be recycled across all iterations. Such an MM algorithm may not achieve the superlinear rates of convergence of Newton methods ( Nesterov and Polyak 2006 ; Doikov et al. 2022 ) , but the computational savings from recycling the same matrix decomposition can produce highly competitive algorithms for many important problems in statistics ( Heng et al. 2025 ) . Since H is only an approximation of the actual Hessian matrix, the quadratic MM algorithm typically requires many more iterations than Newton-Raphson, although it typically converges much faster than conventional first-order methods. Fortunately, the quadratic MM framework is also amenable to acceleration by extrapolation. We define Quadratic Majorization Minorization with Extrapolation (QMME) as the following iteration: \displaystyle y^{k} \displaystyle= \displaystyle x^{k}+\beta_{k}(x^{k}-x^{k-1}), \displaystyle x^{k+1} \displaystyle= \displaystyle\underset{x\in\mathbb{R}^{n}}{\text{argmin}}\quad\langle\nabla f(y^{k}),x\rangle+\frac{1}{2}\|y^{k}-x\|_{H}^{2}, (3) where \beta_{k}\in[0,1) is the extrapolation coefficient and \|x\|_{H}=\sqrt{x^{\top}Hx} . We note that selecting an appropriate sequence of \beta_{k} is a vital issue for the practical efficiency of QMME. 1.1 Contributions We propose the Quadratic Majorization-Minimization with Extrapolation (QMME) algorithm for convex optimization. To adapt extrapolation to the objective’s local geometry while preserving global convergence, we adopt a hybrid restart strategy ( O’Donoghue and Candès 2012 ; Wen et al. 2018 ) that combines periodic and adaptive restarts. By establishing the descent property of a potential function similar to the one in Wen et al. 2017 and Wen et al. 2018 , we establish subsequential convergence of our algorithm when extrapolation coefficients are bounded away from 1 and prove global convergence under the Kurdyka–Łojasiewicz (KL) property ( Bolte et al. 2007 ; Attouch and Bolte 2009 ; Attouch et al. 2010 ; Attouch et al. 2013 ) . The novel aspect of our analysis is to leverage the scaled norm induced by the curvature matrix H . Using the same technique, we also explore connections with inertial Krasnoselskii–Mann iterations ( Maulén et al. 2024 ) . With a few technical variations, we generalize our algorithm and theory to the scenario of composite optimization in the appendix. We chose to focus on smooth optimization in the main paper since composite optimization deviates from the theme of recycling matrix decompositions and also kernel regularized learning. To avoid diluting the main message of the paper, we present the algorithm and theory for composite optimization as an extension. To demonstrate QMME’s efficacy, we apply it to a key problem in statistical machine learning, namely kernel regularized learning with random sketching ( Schölkopf and Smola 2002 ; Mendelson and Neeman 2010 ; Yang et al. 2017 ) . The examples we consider include kernel-smoothed quantile regression ( Li et al. 2007 ; Wang and Feng 2024 ) , kernel logistic regression ( Keerthi et al. 2005 ) , and kernel multinomial regression ( Zhu and Hastie 2005 ; Karsmakers et al. 2007 ) . For each, we derive Hessian upper bounds and present normal equations for minimizing the quadratic majorant. Notably, for kernel multinomial regression, we introduce a novel Sylvester equation technique that greatly reduces per-iteration complexity. We describe multinomial regression models using both the standard parameterization (coefficient matrix X has q-1 columns) and the full parameterization (coefficient matrix X has q columns). Our MM algorithms recycle matrix factorizations (Cholesky, spectral, Schur) across iterations and sometimes across regularization parameters. For kernel quantile and logistic regression, QMME outperforms first- and second-order methods when projection dimension is sufficiently large. For kernel multinomial regression, the advantage of QMME over existing methods is decisive, especially when the number of classes q is large. To summarize succinctly, our contributions are: • Theoretically, we integrate a scaled norm analysis technique with the optimization framework of Wen et al. 2017 and Wen et al. 2018 to investigate the convergence properties of a quadratic MM algorithm incorporating extrapolation. This integration allows us to establish subsequential convergence in general settings and global convergence under the Kurdyka–Łojasiewicz (KL) property. By drawing connections to inertial Krasnoselskii–Mann iterations ( Maulén et al. 2024 ) , we can relax the KL assumption by imposing additional restrictions on the extrapolation step size \beta_{k} . We also generalize our algorithm and theory to the case of composite optimization in the appendix. • Algorithmically, we develop efficient new algorithms for kernel regularized learning with random sketching that recycle matrix decompositions. By scaling more effectively to larger projection dimensions, our optimization algorithms complement existing kernel approximation techniques such as Nyström approximation ( Williams