Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization

By Julien Mairal. 2013

168 citations recorded by the source corpus.

Majorization-minimization algorithms consist of iteratively minimizing a majorizing surrogate of an objective function. Because of its simplicity and its wide applicability, this principle has been very popular in statistics and in signal processing. In this paper, we intend to make this principle scalable. We introduce a stochastic majorization-minimization scheme which is able to deal with large-scale or possibly infinite data sets. When applied to convex optimization problems under suitable assumptions, we show that it achieves an expected convergence rate of $O(1/\sqrt{n})$ after $n$ iterations, and of $O(1/n)$ for strongly convex functions. Equally important, our scheme almost surely converges to stationary points for a large class of non-convex problems. We develop several efficient algorithms based on our framework. First, we propose a new stochastic proximal gradient method, which experimentally matches state-of-the-art solvers for large-scale $\ell_1$-logistic regression. Second, we develop an online DC programming algorithm for non-convex sparse estimation. Finally, we demonstrate the effectiveness of our approach for solving large-scale structured matrix factorization problems.

Subfields: Artificial Intelligence, Biomedical Engineering, Computational Mechanics

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 Biomedical Engineering

In Computational Mechanics

Citations in the corpus

NoPeek: Information leakage reduction to share activations in distributed deep learning (2020, background): “…exact form is detailed in [50]: The iterative update for maximization of the above objective is based on a variant of majorization-minimization [51, 52] and is given by Z t = HZ t − 1 where for a ﬁxed γ 2 , some α and where are constants, and S X , y = k Y L Y − βk X L X for a tuning parameter β ,…”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “Since the first version of our work was published in [39], MISO has also been extended by other authors in [57] using the alternating direction method of multipliers framework.”
MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels (2017, background): “By Lemma A.5 in (Mairal, 2013), to show (cid:12)(cid:12)(cid:12)(cid:12) (cid:12)(cid:12)(cid:12)(cid:12) To do so, we ﬁrst recall a useful fact: for any two vectors a , b and any ﬁnite-dimensional vector norm · , We have: where the ﬁrst inequality is an application of Jensen’s inequality, the…”
On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes (2018, background): “(Alber et al., 1998, Proposition 2)(Mairal, 2013, Lemma A.5) Let ( a t ) t 1 , ( b t ) t 1 be two non-negative real sequences.”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “…al., 2017), stochastic average gradient algorithms (Roux et al., 2012; Defazio et al., 2014a), stochastic majorization-minimization algorithms (Defazio et al., 2014b; Mairal, 2013), hybrid methods (Konecn`y and Richt´arik, 2013), and dual coordinate methods (Shalev-Shwartz and Zhang, 2013, 2016).”
A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, methodology): “Motivated by the BSUM framework, the authors of [20] and [84] suggest using an inexact version of the SAA method, in which a sequence of upper bounds of the objective are minimized.”
Support points (2016, methodology): “) Note that the compactness condition on X in Theorem 8 is needed to prove the convergence of stochastic MM algorithms, since it allows for an application of the law of large numbers (see [40] for details).”
Meta-Weight-Net: Learning an Explicit Mapping For Sample Weighting (2019, background): “[69] Julien Mairal.”
Sparse Modeling for Image and Vision Processing (2014, methodology): “In a nutshell, the algorithm works by using a stochastic version of the majorization-minimization principle [Mairal, 2013].”