PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization

Julien Mairal

arXiv:1306.4650v2stat.MLcs.LGmath.OC

TL;DR

Majorization-minimization is simple and broadly useful but must be scaled to large or potentially infinite data sets. The paper introduces stochastic surrogate updates, proves convex and non-convex convergence guarantees, and derives practical algorithms that match or outperform state-of-the-art methods in several large-scale applications.

  • Problem

    Majorization-minimization must be made scalable for expected-cost objectives arising from large-scale or possibly infinite data sets.

  • Method

    The paper builds and averages surrogate functions from single observations, then minimizes the resulting approximate surrogate at each iteration.

  • Results

    The framework achieves O(1/√n) expected convergence for convex problems, O(1/n) for strongly convex objectives, and almost-sure convergence to stationary points for suitable non-convex problems.

  • Takeaways & Limitations

    Derived algorithms match or outperform state-of-the-art solvers for large-scale convex problems and open new possibilities for non-convex optimization.

  • Takeaways & Limitations

    The stochastic scheme is practical only when its averaged surrogates have a compact parameterization and can be minimized easily over Θ.

Abstract

from arXiv · show

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.

1 Introduction

The paper makes majorization-minimization scalable through a stochastic scheme that updates surrogates from single observations. It establishes convergence guarantees and develops applications for large-scale convex, non-convex, and structured problems.

  • Motivation: Majorization-minimization iteratively minimizes an upper-bounding surrogate, monotonically driving the objective value downhill.The principle also underlies methods including expectation-maximization, DC programming, variational Bayes, and proximal algorithms.
  • Motivation: The proposed stochastic scheme targets expected-cost minimization for large-scale problems in machine learning and signal processing.It updates a surrogate using one observed data point at each iteration and minimizes the updated surrogate to obtain a new estimate.
  • Motivation: O(pn) storage in incremental majorization-minimization motivates a stochastic method whose memory load is independent of training-set size n.This enables applications to possibly infinite data sets or very large variable sizes p.
  • Theory: O(1/√n) convergence holds in finite-horizon convex settings, while O(1/n) holds for strongly convex objectives in infinite-horizon settings.For non-convex problems, the method almost surely converges to stationary points under suitable assumptions.
  • Applications: The framework yields a stochastic proximal gradient method, an online DC programming technique, and an online approach to structured sparse matrix factorization.The methods match state-of-the-art solvers for large-scale ℓ1-logistic regression, outperform batch alternatives for large-scale non-convex sparse estimation, and support varied losses or regularizers for matrix factorization.

2 Optimization with First-Order Surrogate Functions

The paper formalizes strongly convex first-order surrogates and uses them as the basis for batch and stochastic optimization. It also shows how common surrogate constructions support gradient, proximal-gradient, and DC-programming updates.

  • Surrogate framework: Majorization-minimization computes a surrogate g_n that majorizes f at iteration n and updates the estimate by minimizing g_n over Θ.The scheme's success depends on how well the surrogate approximates the objective.
  • Surrogate framework: First-order surrogate functions are strongly convex majorizers that touch f at κ and have a smooth approximation error with Lipschitz gradient.They belong to the class S_L,ρ(f, κ) defined by these properties.
  • Surrogate constructions: Lipschitz-gradient surrogates yield classical gradient-descent updates, with convexity and strong convexity adjusting the surrogate's strong-convexity parameter.The construction applies when f is differentiable with an L-Lipschitz gradient.
  • Surrogate constructions: Proximal-gradient surrogates apply when f splits into a smooth differentiable term and a convex term.When the smooth term has an L-Lipschitz gradient, the resulting surrogate belongs to S_2L,L(f, κ).
  • Scalability: The incremental alternative can reduce memory to O(pη) with η mini-batches, but this remains cumbersome when p is very large.The stochastic framework is introduced as the main contribution for large-scale problems.
  • Surrogate constructions: DC-programming surrogates linearize a differentiable concave component while retaining a surrogate for the remaining term.If the concave component has an L_2-Lipschitz gradient, the resulting surrogate has parameters S_L1+L2,ρ1(f, κ).

3 Stochastic Optimization

The stochastic scheme minimizes an evolving weighted surrogate built from one sampled data point per iteration, with convergence guarantees for convex and non-convex expected-cost optimization. Its guarantees include optimal-order rates under convexity and almost-sure stationary-point convergence under suitable non-convex assumptions.

  • Algorithm: The algorithm samples one data point, constructs a surrogate for its loss, updates a weighted average surrogate, and minimizes that average to obtain the next estimate.For convex problems, optional averaging schemes are also proposed.
  • Algorithm: The method is practical only when the averaged surrogates have compact parameterizations and can be minimized efficiently over the feasible set.Concrete examples are developed later in the paper.
  • Convex case: O(1/√n) is achieved for convex objectives in a finite-horizon setting under uniformly bounded subgradients and the condition ρ = L.The bound uses the averaging scheme corresponding to option 2 and is generally unimprovable without further assumptions.
  • Strongly convex case: O(1/n) is achieved for strongly convex objectives under assumptions (A) and (B), using ρ = L + µ and the option 3 averaging scheme.The rate is optimal up to a multiplicative constant for strongly convex functions.
  • Non-convex case: Almost-sure convergence of objective values and stationary-point guarantees hold for non-convex problems under boundedness, directional-derivative, weight, and surrogate-parameterization assumptions.Without parameterized surrogates, convergence of the weighted empirical risk does not by itself guarantee stationary limit points of the expected cost.
  • Non-convex case: The non-convex analysis extends beyond first-order surrogates to partially separable objectives, while retaining the conclusions of Propositions 3.3 and 3.4.This extension is motivated by the paper’s non-convex sparse-estimation formulation.

4 Applications and Experimental Validation

The paper applies its stochastic majorization-minimization framework to stochastic proximal gradient descent, online DC programming, and structured sparse coding. Experiments compare these methods with batch or established solvers and demonstrate practical scalability and useful regularization effects.

  • Stochastic Proximal Gradient Descent Algorithm: SMM uses stochastic proximal gradient updates for large-scale ℓ1-logistic regression, with sparse-data updates costing O(s).Here s is the number of nonzeros in the current sample gradient.
  • Stochastic Proximal Gradient Descent Algorithm: SMM often produces a reasonable solution after one epoch and outperforms LIBLINEAR in the low-precision regime, whereas LIBLINEAR is preferred for high precision.The comparison uses 1, 2, 3, 4, 5, 10, and 25 passes over the training set across three regularization regimes.
  • Online DC Programming for Non-Convex Sparse Estimation: The online DC programming method targets non-convex sparse estimation by applying the stochastic framework to a non-convex regularizer and an online sequence of updates.The method is compared with a batch reweighted-ℓ1 procedure.
  • Online DC Programming for Non-Convex Sparse Estimation: The batch reweighted-ℓ1 algorithm converges after 2 or 3 weight updates but suffers from local minima, while the stochastic algorithm converges more slowly and provides significantly better solutions.The experiments use rcv1 and webspam with medium regularization; batch iterations can include several training-data passes.
  • Online Structured Sparse Coding: For structured sparse coding, the method learns dictionaries with a group penalty that encourages neighboring pixels to become zero together.On 400,000 whitened natural image patches, a dictionary of size K = 256 took a few minutes using one pass with mini-batches of size 100.

5 Conclusion

The paper concludes that stochastic majorization-minimization scales to millions of training samples while retaining strong theoretical and practical value. Its derived algorithms match or outperform state-of-the-art methods for large-scale convex problems and expand possibilities for non-convex problems.

  • Conclusion: The stochastic majorization-minimization algorithm scales to millions of training samples.The conclusion identifies scalability as a central practical property of the framework.
  • Conclusion: Derived algorithms match or outperform state-of-the-art methods for large-scale convex problems and open new possibilities for non-convex ones.The paper proposes future work on curvature-exploiting surrogate functions for badly conditioned datasets.

A Mathematical Background and Useful Results

This section supplies convex-analytic and probabilistic tools for analyzing stochastic majorization-minimization. It establishes surrogate properties, recursive quantities, and auxiliary convergence lemmas used in the convex analysis.

  • Convex tools: Subdifferential equality lets a surrogate inherit the objective’s first-order information when their difference is differentiable with zero gradient at the current point.For convex f and g, if h = g − f is differentiable at θ with ∇h(θ) = 0, then ∂f(θ) = ∂g(θ).
  • Convex tools: Strong convexity provides lower bounds and second-order growth inequalities around minimizers, supporting control of distances and surrogate errors.The section states both a lower bound for strongly convex functions and a second-order growth property on convex sets.
  • Probabilistic tools: Quasi-martingale and non-negative-series lemmas convert summability and bounded variation conditions into almost-sure convergence results.The stochastic lemma additionally uses expectation bounds and almost-sure increment control to show X_n converges almost surely to zero.
  • Surrogate analysis: First-order surrogate functions are strongly convex approximations whose approximation errors are controlled through recursive averaged objectives and auxiliary sequences.The stochastic surrogate lemma extends the corresponding deterministic basic-properties result under convexity and assumption (A).
  • Convex analysis: The convex analysis combines bounded subgradients, strong convexity, and conditional-expectation identities to derive recursive bounds for the stochastic algorithm.The proof uses coincident subdifferentials, bounded subgradients, and the filtration induced by past information.

B.2 Non-convex Analysis

The non-convex analysis establishes uniform convergence of weighted empirical objectives under entropy and boundedness assumptions. These results support almost-sure convergence arguments for the stochastic scheme.

  • Uniform convergence: Uniform convergence applies when the loss-function class is sufficiently simple in entropy and assumptions (A), (C), and (D) hold.The analysis invokes empirical-process results to obtain a uniform law of large numbers for the empirical cost.
  • Convergence analysis: The analysis uses weighted empirical-risk recursions and Jensen’s inequality to derive the desired convergence bounds for the non-convex setting.Several recursive inequalities are summed and combined with uniform-convergence estimates.
  • Uniform convergence: The weighted empirical objective converges uniformly to the population objective almost surely under the stated assumptions.The proof controls successive differences and applies the stochastic non-negative-series lemma.
  • Surrogate behavior: Strong convexity of the surrogates bounds objective decreases by weighted iterate changes, linking surrogate minimization to control of successive iterates.The argument uses the majorization relation and bounded subgradients to obtain a bound proportional to Rw_n||θ_n − θ_{n−1}||².

C.3 Proof of Proposition 3.2

This proof derives the convergence rates for the strongly convex case by separately controlling auxiliary sequences and then transferring those bounds to expected objective error.

  • Rate derivation: The proof establishes convergence rates for several recursively defined quantities before bounding the expected objective gap.The argument proceeds by induction and considers separate cases for the relevant rate expression.
  • Rate derivation: The auxiliary sequence C_n is bounded inductively by a term proportional to R²w_n/ρ.The induction starts at n = 1 and extends the bound to all n ≥ 1.
  • Rate derivation: The auxiliary sequence A_n is shown inductively to satisfy A_n ≤ δw_n, with δ defined from the initial and problem-dependent quantities.The proof obtains the recursion from Lemmas B.5 and B.4 and then applies induction.
  • Objective bound: Jensen’s inequality transfers the bound on the auxiliary quantity B_n to the expected objective gap E[f(θ̂_n) − f⋆].The proof concludes the objective-rate argument after establishing the preceding auxiliary bounds.

C.4 Proof of Proposition 3.3

This proof combines quasi-martingale convergence, uniform convergence, and surrogate-gradient control to show almost-sure convergence and an asymptotic stationary-point condition.

  • Almost-sure convergence: A quasi-martingale theorem yields almost-sure convergence of the minimized averaged surrogate sequence under boundedness and summable positive variations.The proof constructs non-negative summable terms and applies the convergence theorem to the sequence of surrogate values.
  • Almost-sure convergence: The averaged empirical objective converges almost surely to the same limit as the averaged surrogate because their difference converges to zero.The proof uses Lemma A.5 together with Lipschitz and bounded approximation errors.
  • Population objective: Uniform convergence then transfers almost-sure convergence from the averaged empirical objective to the population objective evaluated at the iterates.The proof explicitly invokes Lemma A.6 after establishing convergence of the averaged empirical sequence.
  • Stationarity: The surrogate-gradient norm converges to zero, providing the asymptotic stationary-point condition.This follows from Lipschitz-gradient control, vanishing surrogate error, and the surrogate minimization condition.
  • Stationarity: Compactness supplies convergent subsequences used to pass to limiting surrogate inequalities and identify limiting stationary behavior.The proof selects subsequences for both iterates and auxiliary variables before taking limits.

Proof of

The proof establishes convergence by showing the approximation gradients vanish and the limiting function is differentiable with zero gradient at the limit point.

  • Uniform convergence of the surrogate components implies uniform convergence of the combined approximation function to its limit.
  • The approximation gradients at the iterates converge to zero as the iteration index grows.
  • The limiting function is differentiable at the limit point and has zero gradient there, establishing the required stationarity condition.

C.6 Proof of Proposition 3.5

The proof of Proposition 3.5 adapts the convergence arguments to a setting where the approximation error may be nonsmooth, replacing gradient convergence with directional-derivative control.

  • The proof retains strong convexity of the surrogate component through convexity of its composed terms.
  • The main missing property is smoothness of the approximation error, so the earlier propositions require targeted modifications.
  • Uniform Lipschitzness and boundedness of the approximation errors remain available under Proposition 3.5’s assumptions.
  • Because the approximation error is not differentiable, the proof replaces gradient convergence with convergence of directional derivatives.
  • For the two-component case, separate approximation errors and their derivatives converge to zero, allowing the modified proposition to be concluded.

D Additional Experimental Results

The appendix reports additional experimental plots for the logistic-regression and DC-programming experiments, plus dictionary visualizations for the matrix-factorization experiment.

  • Figures 4 and 5 provide additional experimental comparisons complementing the results in Section 4.1.
  • Figures 6 and 7 provide additional plots from the experiment in Section 4.2.
  • Figures 8, 9, and 10 show three dictionaries corresponding to the experiment in Section 4.3.
Loading 1306.4650v2…