arXiv:2501.15941stat.MLcs.LG2025-01被引 4

SAPPHIRE算法让大规模机器学习模型训练更快更稳,尤其适合病态条件问题。

SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning

  • 用随机投影预处理解决目标函数病态问题,提升优化稳定性。
  • 在lasso和逻辑回归上比SAGA等方法快20倍,且收敛速度与条件数无关。
  • 适用于非凸目标或低频更新预处理器的场景,工程落地性强。

正则化经验风险最小化(rERM)在基因组学、广告等数据密集型领域日益重要,传统随机梯度方法常因病态目标和非光滑正则项导致收敛慢、计算开销大。为此,我们提出SAPPHIRE算法——基于随机投影的近似预处理与海森矩阵不精确性结合的方差缩减方法。该算法通过预处理缓解病态问题,采用缩放近端映射处理非光滑正则项,实现对最优解的条件数无关线性收敛,为病态复合大规模凸机器学习问题提供高效可扩展的解决方案。在lasso和逻辑回归上的大量实验表明,SAPPHIRE通常比Catalyst、SAGA、SVRG等常见方法快20倍。这一优势在目标函数非凸或预处理器更新频率较低时依然显著,体现出其鲁棒性和实际有效性。

原文摘要 · Abstract (English)

Regularized empirical risk minimization (rERM) has become important in data-intensive fields such as genomics and advertising, with stochastic gradient methods typically used to solve the largest problems. However, ill-conditioned objectives and non-smooth regularizers undermine the performance of traditional stochastic gradient methods, leading to slow convergence and significant computational costs. To address these challenges, we propose the $\texttt{SAPPHIRE}$ ($\textbf{S}$ketching-based $\textbf{A}$pproximations for $\textbf{P}$roximal $\textbf{P}$reconditioning and $\textbf{H}$essian $\textbf{I}$nexactness with Variance-$\textbf{RE}$educed Gradients) algorithm, which integrates sketch-based preconditioning to tackle ill-conditioning and uses a scaled proximal mapping to minimize the non-smooth regularizer. This stochastic variance-reduced algorithm achieves condition-number-free linear convergence to the optimum, delivering an efficient and scalable solution for ill-conditioned composite large-scale convex machine learning problems. Extensive experiments on lasso and logistic regression demonstrate that $\texttt{SAPPHIRE}$ often converges $20$ times faster than other common choices such as $\texttt{Catalyst}$, $\texttt{SAGA}$, and $\texttt{SVRG}$. This advantage persists even when the objective is non-convex or the preconditioner is infrequently updated, highlighting its robust and practical effectiveness.

优化算法大规模学习预处理

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。