Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning

By Julien Mairal. 2014

332 citations recorded by the source corpus.

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 nonconvex 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 nonconvex 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 solving machine learning problems such as logistic regression when the number of training samples is large enough, and we demonstrate its usefulness for sparse estimation with nonconvex penalties.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, methodology): “The second approach is to use Stochastic Gradient Descent (SGD) [26, 6] or a more recent variant [4, 27, 21, 22, 1].”
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “We now describe how the Finito [9] and MISOμ [10] methods are closely related to SAGA.”
Robust Aggregation for Federated Learning (2019, background): “In particular, it is the iterative minimization of a first-order surrogate in the sense of [63, 64].”
D2: Decentralized Training over Decentralized Data (2018, methodology): “Variance reduction technology There have been many methods developed for reducing the variance in SGD, including SVRG [Johnson and Zhang, 2013], SAGA [Defazio et al., 2014], SAG [Schmidt et al., 2017], MISO [Mairal, 2015], and mS2GD [Koneˇcn`y et al., 2016].”
A Universal Catalyst for First-Order Optimization (2015, methodology): “More importantly, it also applies to incremental algorithms such as SA G [24], SAGA [6], Finito/MISO [7, 14], SDCA [25], and SVRG [27].”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “The convergence rate of SGD can be further improved with the so-called variance-reduction technique [9, 11, 17, 24, 25, 31, 32, 35, 36].”
Finito: A faster, permutable incremental gradient method for big data problems (2014, background): “While this work was under peer review, a tech report (?) was put on arXiv that establishes the convergence rate of MISO with step α = 1 and with β = 2 as 1− 13n per step.”
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives (2015, methodology): “Another possible solution is to tackle the non-strongly convex case directly [2, 14, 18], without using any dummy regularizer.”
Optimal Black-Box Reductions Between Optimization Objectives (2016, methodology): “ parameter. This makes the algorithm hard to apply in practice. For this reason, many algorithm designers invent direct algorithms to solve Case 2, 3, or 4. This includes SAG [20], SAGA [4], and MISO [14] for the nite sum form of Case 2; the algorithms [8, 10, 19] for solving the general form of Cas”
On the Linear Convergence of the Approximate Proximal Splitting Method for Non-smooth Convex Optimization (2014, background): “Other relevant works are [16, 23] which provide the convergence analysis for a general class of inexact BCD methods.”
Distributed Mini-Batch SDCA (2015, methodology): “Our analysis allows for flexible sampling schemes, including where data is distribute across machines, and combines a dependence on thsmoothness of the loss and/or the data spread (measured through the spectral norm).”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “Alternative variance-reduced method include MISO (Mairal, 2015), FINITO (Defazio et al., 2014b), SDCA (Shalev-Shwartz, 2016), dfSDCA (Csiba & Richt´arik, 2015), AdaSDCA (Csiba et al., 2015), QUARTZ (Qu et al., 2015), SBFGS (Gower et al., 2016), SDNA (Qu et al., 2016), SARAH (Nguyen et al., 2017) and”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, unknown): “, 2014a), MISO (Mairal, 2015), FINITO (Defazio et al.”
Learning With Single-Teacher Multi-Student (2018, background): “Majorization minimization (MM) algorithms substitute a simple optimization problem for a difficult optimization problem (Hunter and Lange 2004; Mairal 2015; Lange 2016).”