用固定曲率二次近似加速核学习,兼顾速度与效率
Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning
- 每轮用固定曲率的二次上界替代原问题,降低计算开销
- 在核多元回归中构建新型Sylvester方程模型,提升求解效率
- 适合大规模核学习场景,尤其擅长处理高维投影矩阵
一阶优化方法虽每轮开销低但收敛慢,二阶方法虽快却需昂贵的海森逆运算。本文提出一种中间路径:在每轮迭代中最小化具有固定曲率的二次上界,平衡计算成本与收敛速度,并可复用如Cholesky或谱分解等矩阵分解结果,跨迭代及不同正则化参数使用。我们引入带外推的二次上界最小化(QMME)框架,在标准假设下证明其序列收敛性。分析核心在于曲率矩阵 $H$ 所诱导的范数。通过应用于大规模核正则化学习问题,提出一种新型Sylvester方程建模方法用于核多元回归。在Julia实现的实验中,QMME优于多种经典一阶与二阶方法。此外,本算法能高效处理高维投影矩阵,与现有核近似技术形成互补。所有实验与真实数据分析均在 https://github.com/qhengncsu/QMME.jl 完全可复现。
原文摘要 · Abstract (English)
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$. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。