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

Julien Mairal

Source-linked AI summary

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

Julien Mairal

arXiv:1402.4419v3Feb 18, 2014math.OCcs.LGstat.ML

TL;DR

Large-scale machine learning often requires minimizing a large sum of continuous functions, while standard majorization-minimization does not by itself provide scalable optimization guarantees. The paper introduces MISO with first-order surrogate functions, proves non-convex stationarity and convex convergence results, and reports competitive large-scale applications.

Problem
The paper addresses how to make majorization-minimization scalable for minimizing large sums of continuous functions arising in machine learning.
Method
MISO incrementally minimizes first-order surrogate functions whose approximation errors are smooth, extending the majorization-minimization principle to large-sum objectives.
Results
MISO obtains asymptotic stationary-point guarantees for non-convex problems, convex convergence rates, and competitive performance for large-scale logistic regression and sparse estimation.
Takeaways & Limitations
The approach applies to a broad class of non-convex, including non-smooth, problems and provides incremental composite-optimization rules competitive with state-of-the-art large-scale solvers.
Takeaways & Limitations
The non-convex analysis provides no convergence rate, and some improved convex rates require substantially stronger surrogate-curvature assumptions.

Abstract

from arXiv · show

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. In this paper, 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. In our experiments, we 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 non-convex penalties.

1. Introduction.

The paper scales majorization-minimization to large sums of functions through an incremental scheme, with convergence guarantees for non-convex and convex settings and applications to machine learning.

Motivation: Majorization-minimization repeatedly minimizes locally tight upper bounds, decreasing the objective at every iteration but not guaranteeing solution quality.Its simplicity has made the principle widely used across scientific fields.
Problem: The paper targets minimizing a large sum of continuous functions over a convex parameter set, a structure motivated by large-scale machine learning.Each component function can measure parameter adequacy for one observed data point.
Approach: MISO uses an incremental scheme whose per-iteration cost is independent of the number of functions when the upper bounds are appropriately chosen.The method uses first-order surrogate functions whose approximation error is differentiable with Lipschitz continuous gradient.
Guarantees: For non-convex problems, the paper establishes almost sure convergence and asymptotic stationary-point guarantees; for convex problems, it provides rates for expected objective values.Strongly convex surrogates yield additional convergence-rate results.
Experiments: Experiments show MISO matches cutting-edge logistic-regression solvers and supports incremental DC programming for sparse estimation with non-convex penalties.The reported applications address large-scale machine learning and sparse estimation.

2. Majorization-minimization with first-order surrogate functions.

The paper formalizes majorization-minimization with first-order surrogates whose smooth approximation errors support convergence analysis, then introduces the basic surrogate-minimization procedure.

Majorization-minimization principle: At iteration n, the basic scheme minimizes a surrogate g_n of f near the current estimate θ_{n−1} and updates θ_n to a minimizer.When the surrogate uniformly majorizes f and is tight at the current estimate, the objective decreases monotonically.
Majorization-minimization principle: The approximation error h_n = g_n − f measures the discrepancy introduced by replacing the objective with its surrogate.The figure presents this error as the difference between the surrogate and objective functions.
First-order surrogate functions: First-order surrogates require the approximation error to be L-smooth, with zero value and zero gradient at the reference point.L-smooth means differentiable with an L-Lipschitz continuous gradient.
First-order surrogate functions: These surrogates permit control of approximation error through smoothness, forming a building block for the convergence analysis.The analysis also considers the subset of ρ-strongly convex first-order surrogates.
Convergence results: The analysis derives asymptotic stationary-point guarantees and, for convex objectives, non-asymptotic rates including O(1/n) and linear convergence in strongly convex cases.The results adapt convergence arguments used for proximal gradient methods.

2.1. Non-convex convergence analysis.

Under boundedness and surrogate assumptions, the non-convex analysis proves monotonic objective decrease and asymptotic stationarity, including a composition-based extension.

Stationarity criterion: For non-convex objectives, the analysis evaluates convergence through asymptotic stationary-point conditions rather than convergence to a global or local minimum.A stationary point has no feasible descent direction.
Main guarantee: Assuming f is bounded below and surrogates are first-order plus either majorizing or strongly convex, Algorithm 1 decreases f monotonically and reaches asymptotic stationarity.The objective sequence is non-increasing and convergent under these assumptions.
Main guarantee: The proof links diminishing surrogate error to vanishing gradients or directional-derivative residuals at the iterates.The majorizing and strongly convex cases provide alternative routes to the same stationarity conclusion.
Composition extension: The composition extension applies when f = f′ ◦ e, e is Lipschitz continuous, and the surrogate is constructed as a majorizing surrogate in the composed space.Under these conditions, the conclusions of the main non-convex proposition hold.
Scope and limitation: The non-convex analysis provides convergence guarantees but no convergence rate, including for the composition case where g_n − f need not be L-smooth.The authors characterize non-convex convergence results as inherently weak.

2.2. Convex analysis.

For convex objectives, first-order surrogate minimization yields sublinear convergence rates and stronger rates under strong convexity, while stronger surrogate curvature assumptions improve constants.

General convex case: The convex analysis adapts proximal-gradient proof techniques to derive convergence rates for first-order surrogate minimization.The resulting rates include the classical sublinear behavior O(1/n).
General convex case: For convex, bounded-below objectives with bounded level sets, the analysis establishes an O(1/n)-type rate for the objective gap.The proof uses telescoping inequalities and the notation r_n = f(θ_n) − f⋆.
Strongly convex case: When f is strongly convex, the analysis derives a stronger rate for convergence of the objective value toward f⋆.The proof uses strong convexity to relate objective gaps to distances from a minimizer.
Strongly convex surrogates: Using ρ-strongly convex surrogates with ρ ≥ L gives slightly better convergence-rate constants than the basic first-order-surrogate assumption.This result applies to both convex and strongly convex objectives.
Scope and limitation: The improved-rate condition is substantially stronger because ρ ≥ L implies that f is convex, and ρ > L implies (ρ−L)-strong convexity.Thus, the sharper constants come with a narrower applicability condition.

2.3. Examples of first-order surrogate functions.

The paper develops first-order surrogate constructions for smooth, composite, non-convex, Jensen, variational, and robust objectives. These surrogates connect majorization-minimization to gradient, proximal-gradient, reweighted-ℓ1, alternate-minimization, and related algorithms.

Smooth functions: A smooth function admits a classical quadratic upper-bound surrogate whose minimization is equivalent to a gradient descent step.The surrogate is L-strongly convex and L-smooth, while its approximation error is 2L-smooth; stronger smoothness classes hold under convexity assumptions.
Composite optimization: For composite objectives f = f1 + f2 with L-smooth f1, the surrogate yields one proximal gradient step.When f2 is the ℓ1-norm, the proximal operator can be computed efficiently and produces iterative soft-thresholding for sparse estimation.
Non-convex penalties: Concave smooth components produce majorizing surrogates used in difference-of-convex programming and sparse estimation with non-convex penalties.For logarithmic penalties, minimizing the surrogate gives a reweighted-ℓ1 update; analogous constructions cover other concave penalties and group sparsity.
Variational surrogates: Variational surrogates reduce block-structured optimization to alternate minimization while preserving smoothness-based majorization properties.Strong convexity in one block and Lipschitz gradient conditions yield a surrogate with L′′ = 2L′ + L^2/µ; convexity can improve this to L′.
Jensen surrogates: Jensen surrogates provide uncommon first-order constructions with non-asymptotic convergence rates not previously studied for this class.Their smoothness constants depend on the weight parameter ν and norms of x, including L′ = L∥x∥2∞∥x∥0 for ν = 0 and L′ = L∥x∥2^2 for ν = 2.
Jensen surrogates: Jensen-based EM surrogates do not generally satisfy the paper’s smooth-error assumption because their approximation errors need not be L-smooth.The analysis may therefore apply to some, but not all, EM algorithms.

3. An incremental majorization-minimization algorithm: MISO.

MISO makes majorization-minimization incremental for large sums by updating one surrogate at a time, with convergence guarantees spanning non-convex, convex, and composite optimization.

Incremental scheme: MISO updates one randomly selected function surrogate per iteration, while maintaining approximate surrogates for the remaining components.Its per-iteration cost is independent of T when the upper bounds are appropriately chosen.
Convex convergence: For convex objectives, the analysis gives sublinear rates O(T/n) generally and linear rates for strongly convex objectives, applying notably to proximal-gradient surrogates.The iterates’ average is used in the convex analysis.
Incremental scheme: First-order surrogates approximate the objective up to an error with a Lipschitz continuous gradient, supporting the convergence analysis.The non-convex analysis assumes majorizing surrogates belonging to this class.
Non-convex convergence: With probability one, MISO inherits the batch scheme’s non-convex convergence conclusions, including almost sure convergence of objective values and asymptotic stationary-point guarantees.The analysis also extends to compositions when component maps are C-Lipschitz and surrogate compositions satisfy the stated majorization conditions.
Strong convexity: When T ≥ 2L/µ, minorizing surrogates can yield faster rates for µ-strongly convex functions, with a rate similar to SAG.The resulting rate improves significantly over the original rate, but the method may diverge when T is small.
Scope and heuristics: Proposition 3.4 applies only to strongly convex problems, while larger practical step sizes are supported by heuristics rather than theory outside that setting.For non-strongly-convex cases, the more conservative rule should be preferred theoretically.
Composite optimization: For composite optimization, MISO provides non-convex guarantees and a linear strongly-convex rate, although that rate is not as fast as SDCA’s.An empirical heuristic using a smaller-than-theoretical L was observed to work well in practice, while MISO2 lacks theoretical guarantees.

4. Experimental validation.

The experiments evaluate MISO variants on large-scale logistic regression and non-convex sparse estimation, showing strong performance under several settings but sensitivity to memory, mini-batching, and heuristic choices.

ℓ2-logistic regression: The evaluation uses six publicly available datasets for ℓ2-regularized logistic regression, with relative duality gap measured against passes over data and CPU time.The experiments compare incremental methods, stochastic gradient descent, FISTA, and SDCA under multiple implementation variants.
Implementation constraints: For sparse datasets, MISO0, MISO1, and MISO2 require O(Tp) memory, motivating mini-batch variants with O(dpT) storage.The mini-batch storage cost matches the dataset size, but mini-batching makes sparse-data MISO slower than on dense datasets.
ℓ2-logistic regression: SAG, SDCA, and MISOµ were consistently fastest and performed similarly, except MISOµ can diverge when T < 2L/µ.For strongly convex problems, MISOµ is generally at least as good as MISO1 and MISO2, subject to this condition.
ℓ2-logistic regression: MISO1 and MISO2 substantially outperform MISO0, while SGD-h performs well initially but is not competitive with incremental methods after several data passes.MISO0 does not outperform ISTA without line search, whereas MISO1 and MISO2 perform significantly better.
Non-convex sparse estimation: MISO2 has mixed sparse-estimation performance: it beats MISO1 in one case but converges to the stationary point θ=0 in some others.The experiments initialize methods away from θ=0 because that point is often a bad stationary point for this problem.
Non-convex sparse estimation: In sparse estimation with non-convex penalties, line-search methods outperform methods without line search, and MISO1 converges faster than other approaches on most datasets.MISO1 does asymptotically better than MM-LS on five datasets after 50 epochs and slightly worse on real-sim.

5. Conclusion.

The paper develops majorization-minimization algorithms for large sums, covering broad non-convex settings and composite convex optimization. It also situates MISO among related variants and identifies extensions for future work.

The proposed algorithms minimize large sums of functions using the majorization-minimization principle.
For non-convex, including non-smooth, problems, the approach provides convergence and asymptotic stationary point guarantees.
For convex composite optimization, the paper proposes incremental rules that are competitive with state-of-the-art solvers for large-scale logistic regression.
MISO is discussed alongside block-coordinate and stochastic majorization-minimization algorithms, and has been extended using an alternating direction method of multipliers framework.
Future work includes removing the large-sample condition T ≥2L/µ, extending convergence proofs to proximal settings, acceleration, and stability under inexact surrogate minimization.

Appendix A. Basic definitions and useful results.

The appendix defines directional derivatives, stationarity, Lipschitz continuity, and strong convexity, then gives regularity results for residual and optimal value functions.

Definitions: A directional derivative is the one-sided limit of objective change along a specified direction and equals the gradient inner product when differentiability holds.
Definitions: A feasible point is stationary when every feasible directional derivative from that point is nonnegative.
Definitions: L-Lipschitz continuity bounds function-value differences by L times the Euclidean distance between inputs.
Definitions: Strong convexity is defined by subtracting a quadratic term so that the resulting function is convex.
Useful results: Subtracting smooth or strongly convex functions preserves quantified regularity under the conditions stated in Lemma A.5, while minimizing a strongly convex variable yields a differentiable value function with an explicit gradient.