Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
Julien Mairal Inria, LEAR Team, Laboratoire Jean Kuntzmann, CNRS, Univ. Grenoble Alpes. 655, avenue de l’Europe, 38330 Montbonnot, France. ().
Abstract
Majorization-minimization algorithms consist of successively minimizing a sequence of upper bounds of the objective function. These upper bounds are tight at the current estimate, and each iteration monotonically drives the objective function downhill. Such a simple principle is widely applicable and has been very popular in various scientific fields, especially in signal processing and statistics. We propose an incremental majorization-minimization scheme for minimizing a large sum of continuous functions, a problem of utmost importance in machine learning. We present convergence guarantees for non-convex and convex optimization when the upper bounds approximate the objective up to a smooth error; we call such upper bounds “first-order surrogate functions”. More precisely, we study asymptotic stationary point guarantees for non-convex problems, and for convex ones, we provide convergence rates for the expected objective function value. We apply our scheme to composite optimization and obtain a new incremental proximal gradient algorithm with linear convergence rate for strongly convex functions. Our experiments show that our method is competitive with the state of the art for solv
中文速览
大规模机器学习训练时需要最小化海量样本损失之和，传统随机梯度法收敛慢、批量方法计算贵，如何兼顾速度与效率是个核心难题。作者提出了一种名为 MISO（增量代理优化）的算法框架，核心思路是"多数化-最小化"（majorization-minimization）：每轮迭代只处理一个样本，用一个局部紧的上界函数（称为"一阶代理函数"）代替真实目标来求解，每步计算量与样本总数无关。理论上，作者证明了非凸问题的渐近驻点收敛性，以及凸问题的显式收敛速率——对强凸目标函数可达线性收敛速率，与 SAG、SDCA 等最优增量算法同级别。实验表明，MISO 在大规模逻辑回归上媲美业界顶尖方法，还能有效处理非凸惩罚项下的稀疏估计问题，为非凸增量优化提供了一个统一且实用的理论框架。
原文 arXiv:1402.4419;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1402.4419v3