PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning for Matrix Factorization and Sparse Coding

Julien Mairal, Francis Bach, Jean Ponce, Guillermo Sapiro

arXiv:0908.0050v2stat.MLcs.LGmath.OC

TL;DR

Large-scale dictionary learning and related matrix factorization problems require methods that adapt basis sets without repeatedly processing entire datasets. The paper proposes a stochastic online optimization algorithm with convergence guarantees, and reports faster performance across small and large datasets while extending it to several formulations.

  • Problem

    Large-scale dictionary learning is computationally difficult for batch methods, which are poorly suited to very large or changing training sets.

  • Method

    The paper introduces a stochastic online algorithm that alternates sparse coding with dictionary updates by minimizing quadratic surrogates, and extends it to other matrix factorization constraints.

  • Results

    The algorithm converges almost surely to a stationary point and is experimentally faster than batch alternatives on datasets containing millions of training examples.

  • Takeaways & Limitations

    The approach provides a parameter-efficient online framework for dictionary learning, non-negative matrix factorization, and sparse principal component analysis.

  • Takeaways & Limitations

    For constrained sparse coding using ℓ′′, the convergence analysis does not apply, although experiments report that the same strategy is efficient in practice.

Abstract

from arXiv · show

Sparse coding--that is, modelling data vectors as sparse linear combinations of basis elements--is widely used in machine learning, neuroscience, signal processing, and statistics. This paper focuses on the large-scale matrix factorization problem that consists of learning the basis set, adapting it to specific data. Variations of this problem include dictionary learning in signal processing, non-negative matrix factorization and sparse principal component analysis. In this paper, we propose to address these tasks with a new online optimization algorithm, based on stochastic approximations, which scales up gracefully to large datasets with millions of training samples, and extends naturally to various matrix factorization formulations, making it suitable for a wide range of learning problems. A proof of convergence is presented, along with experiments with natural images and genomic data demonstrating that it leads to state-of-the-art performance in terms of speed and optimization for both small and large datasets.

1. Introduction

The paper targets scalable learning of adaptive sparse representations and related matrix factorizations. It introduces an online algorithm with convergence guarantees and strong empirical performance across data sizes and formulations.

  • Motivation: Dictionary learning adapts basis elements to data and supports sparse representations in signal and image processing.The paper also relates this setting to non-negative matrix factorization and sparse principal component analysis.
  • Motivation: Large-scale training is difficult for iterative batch methods that access the whole dataset at every iteration.The issue is especially relevant for datasets with millions of samples or data that change over time.
  • Approach: The proposed online algorithm processes individual signals or mini-batches while using sparse-coding structure to reduce memory and computational costs.It sequentially minimizes quadratic surrogate functions over the constraint set.
  • Guarantees: The method is proven to converge almost surely to a stationary point of the objective function.The formulation uses a smooth nonconvex objective over a convex constraint set.
  • Results: Experiments report faster dictionary learning than previous approaches on small and large natural-image datasets.The paper also demonstrates learning from a 12-Megapixel photograph for image inpainting.
  • Extensions: The approach extends to large-scale non-negative matrix factorization and sparse principal component analysis while remaining effective on small datasets.Efficient projection procedures support extensions to different convex constraint sets.

2. Problem Statement

The paper formulates sparse dictionary learning as constrained matrix-factorization optimization over an expected data cost. It motivates an online alternative because empirical optimization is computationally demanding and stochastic-gradient performance depends on learning-rate choices.

  • Problem formulation: Dictionary learning represents signals with a dictionary D whose columns are basis atoms and whose sparse coefficients minimize a regularized coding loss.The dictionary may be overcomplete, with k > m.
  • Problem formulation: The ℓ1-regularized coding problem is also known as basis pursuit or the Lasso and yields sparse coefficient solutions.Constraining dictionary columns prevents arbitrarily large dictionary values.
  • Problem formulation: The joint optimization over dictionary D and coefficients α is not jointly convex, although it is convex in either variable when the other is fixed.This structure motivates alternating optimization approaches.
  • Objective: Minimizing empirical cost precisely is not necessarily the main goal because the target is the expected cost under the unknown data distribution.An inaccurately minimized empirical solution may have the same or better expected cost.
  • Existing methods: Classical stochastic gradient descent uses δt = a/(t + b), requiring dataset-dependent choices of a and b.Its performance can be competitive on large datasets when the learning rate is carefully chosen.
  • Proposed approach: The proposed method processes samples or mini-batches and sequentially minimizes a quadratic local surrogate using second-order information without explicit learning-rate tuning.This approach is designed for the specific structure of dictionary learning.

3. Online Dictionary Learning

The online dictionary-learning procedure alternates sparse coding of incoming samples with constrained dictionary updates. It compresses past information into sufficient statistics and uses warm starts to make successive updates efficient.

  • Algorithm 1: At each iteration, the algorithm draws a sample, computes its sparse code using the previous dictionary, and updates the dictionary.The procedure can process i.i.d. samples one at a time.
  • Surrogate optimization: The quadratic surrogate aggregates past coefficients through a small set of sufficient statistics rather than retaining all previous samples and codes.The surrogate upper-bounds the empirical cost and converges to the same limit under the analysis.
  • Surrogate optimization: Warm-starting each dictionary update from the previous dictionary is efficient because successive surrogate functions become close for large t.This keeps successive dictionary estimates close under suitable assumptions.
  • Algorithm 1: Algorithm 1 requires an initial dictionary, a regularization parameter λ, and a specified number of iterations T.Its inner loop draws x_t from p(x).
  • Dictionary update: The dictionary update is performed by Algorithm 2 through sequential block-coordinate updates of dictionary columns.Each update optimizes the surrogate over the constraint set.

3.2 Sparse Coding

Sparse coding is the computational inner step of online dictionary learning, while implementation variants improve dictionary-update efficiency and adaptation to finite or large training sets. These variants trade additional mechanisms or tuning for faster convergence in selected settings.

  • Sparse coding: The sparse-coding subproblem is an ℓ1-regularized least-squares problem solved using LARS-Lasso because learned dictionaries can contain highly correlated columns.Coordinate-descent alternatives become slower in that setting.
  • Dictionary updates: The dictionary update uses parameter-free block-coordinate descent with warm restarts and stores summary matrices instead of all past samples and coefficients.Sparse coefficients and concentrated matrix statistics improve the efficiency of block updates.
  • Implementation variants: Exponential forgetting through parameter ρ improves convergence for large datasets but is not beneficial for smaller datasets in the reported experiments.The paper identifies n ≥100 000 as the practical regime where this extension is useful.
  • Implementation variants: Mini-batches can accelerate convergence because Gram-matrix computation makes decomposing multiple signals cheaper than repeating single-signal computation.The stated total complexity is O(k^2m + η(km + ks^2)).
  • Initialization: Initialization with A0 = t0I and B0 = t0D0 can slow the first updates and limit large deviations from the initial dictionary.This adapts a step-size-control idea from stochastic-gradient implementations.
  • Initialization: Unused dictionary atoms can be replaced with randomly selected training examples during optimization, especially when initialization is poor.The paper presents continuation as another option for difficult, highly regularized cases.

3.5 Link with Second-order Stochastic Gradient Descent

The paper relates its online dictionary-learning method to second-order stochastic gradient descent in a simplified unconstrained least-squares setting. The connection arises because recursive updates use gradient information together with an empirical Hessian sequence.

  • Second-order stochastic gradient descent replaces the learning rate with the inverse Hessian for unconstrained problems with twice differentiable expected cost.Its convergence is typically faster when the Hessian can be computed or approximated efficiently.
  • The method cannot be applied easily to dictionary learning because the problem is constrained and requires an inverse Hessian at every iteration.The paper nevertheless identifies similarities between the two algorithms.
  • In the comparison setting, coefficients are sampled independently of the dictionary and the optimization is unconstrained, yielding a least-squares estimation problem.These modifications make the setting different from the original dictionary-learning formulation.
  • The recursive formula for the simplified problem is equivalent to second-order stochastic gradient descent.The gradient at (x_t, α_t) is −(x_t−D_{t−1}α_t)α_t^T.
  • The empirical sequence (1/t)Σ_i converges to the objective Hessian, enabling a fast implementation related to the Kalman algorithm.This connects the update sequence to second-order curvature information.

4. Convergence Analysis

Under assumptions including bounded data, surrogate strong convexity, and sparse-coding uniqueness, the analysis establishes almost-sure convergence of the surrogate and objective values and convergence toward stationary points. The guarantees concern nonconvex optimization and therefore do not imply convergence to a global optimum.

  • Assumptions: The proof assumes compactly supported data, strictly convex quadratic surrogates with lower-bounded Hessians, and a sufficient condition ensuring unique sparse codes.These assumptions provide boundedness and uniqueness properties used in the convergence analysis.
  • Assumptions: Invertibility of D^TΛDΛ guarantees uniqueness of the sparse-coding solution, although dictionaries violating this condition can be constructed.An elastic-net penalty can enforce numerical stability, but the analysis omits that penalization.
  • Scope of guarantee: Because the optimization is nonconvex, the algorithm is not guaranteed to find a global optimum.The paper notes that stationary points have nevertheless often been empirically adequate for practical applications.
  • Surrogate convergence: The surrogate ˆf_t acts asymptotically as a surrogate for f because ˆf_t(D_t) and f_t(D_t) converge almost surely to the same limit.The analysis also establishes ||f_t−f||∞→0 almost surely.
  • Surrogate convergence: The parameter changes satisfy D_t−D_{t−1}=O(1/t), although this alone does not ensure convergence of D_t.The bound guarantees convergence of a related positive sum used in the proof.
  • Regularity: Under the assumptions, the sparse-coding loss is continuously differentiable and ∇f(D) is Lipschitz on the feasible set.The proof uses boundedness, uniqueness, and uniform Lipschitz continuity of the sparse-code solution.
  • Stationarity: The sequence D_t approaches the set of stationary points almost surely, and first-order necessary optimality conditions hold asymptotically.This is the paper’s strongest convergence result for the nonconvex dictionary-learning objective.

5. Extensions to Matrix Factorization

The algorithm extends dictionary learning to multiple matrix factorization formulations by varying coefficient regularizers and dictionary constraints. These extensions cover non-negative matrix factorization, sparse principal component analysis, constrained sparse coding, and related structured models.

  • Using Different Regularizers for α: Different regularizers for α, including positivity, elastic net, group Lasso, and non-convex penalties, adapt the algorithm to varied sparsity structures.Theoretical convergence is not established for non-convex regularizers such as the ℓ0 and ℓp pseudo-norms with p < 1.
  • Using Different Constraint Sets for D: Alternative convex constraint sets for D impose non-negativity, dictionary sparsity, or piecewise-constant sparse columns while preserving efficient projection-based updates.The proposed constraint sets include non-negative, elastic-net, and fused-lasso variants.
  • Using Different Constraint Sets for D: The algorithm remains guaranteed to converge to a stationary point when projections onto the chosen column-wise constraint sets can be computed efficiently.The fused-lasso projection can be solved by a homotopy method in O(ks), where s is the number of piecewise-constant parts in the solution.
  • Non-negative Matrix Factorization: Non-negative matrix factorization is handled by constraining D and α_i to non-negative components, with a modification that supports large n and guarantees a stationary point.When λ = 0, the non-negative sparse coding formulation is equivalent to NMF.
  • Sparse Principal Component Analysis: Sparse principal component analysis is formulated as sparse matrix factorization using ℓ1 regularization for α and optional sparsity constraints on D.This formulation connects SPCA to dictionary learning while allowing sparse components without requiring the same PCA formulation choices.
  • Constrained Sparse Coding: For the ℓ′′ case, the algorithm lacks the paper’s theoretical analysis because the expected cost has no quadratic surrogate, although experiments indicate practical efficiency.The method computes α_t by solving Eq. (16) while keeping the A_t and B_t updates unchanged.

6. Experimental Validation

Experiments on natural images, face data, genomic data, and a 12-Megapixel image show that the online method is efficient across matrix-factorization tasks and scales to large settings.

  • Online vs. Batch: The online algorithm systematically outperforms its batch counterpart across training-set sizes and desired precisions, often by dramatic computation-time differences.Figure 1 reports test objective as a function of training time on a logarithmic scale.
  • Comparison with Stochastic Gradient Descent: Carefully tuned stochastic gradient descent achieves results similar to the proposed method, whereas increasing its learning-rate parameter worsens early iterations.The comparison uses a learning rate of the form a/(ηt + b), with selected parameters a = 200,000 and b = 400,000.
  • Non-Negative Matrix Factorization and Sparse Coding: The proposed method provides a significant speed improvement over Lee and Seung’s NMF and Hoyer’s NNSC on three face-image datasets.Reported objective values are compared as functions of computation time, with the proposed approach including dictionary learning and a subsequent sparse-coding step.
  • Feature Learning Comparisons: PCA produces spatially spread features, NMF produces localized face features on datasets D and E, and neither localizes features on natural patches F.Feature visualizations use red for positive values, blue for negative values, and white for zero values.
  • Genomic Data: On genomic data, the method exhibits performance generally similar to Witten et al.’s PMD, although the experiment is intended primarily to demonstrate applicability rather than establish a careful comparison.The authors state that stronger conclusions about relative performance would require more experiments.
  • Large-Scale Image Processing: A dictionary with 256 elements was learned from roughly 7 × 10^6 undamaged color patches in about 8 minutes using eight cores, enabling text removal from a 12-Megapixel image.The application is illustrative rather than a thorough evaluation against state-of-the-art inpainting methods on standard datasets.

7. Conclusion

The paper introduces a stochastic online algorithm for dictionary learning, proves its convergence, and reports faster performance than batch alternatives on large datasets.

  • The paper introduces a stochastic online algorithm for learning dictionaries adapted to sparse coding tasks.The method is designed for datasets that may contain millions of training examples.
  • A convergence proof is provided for the proposed algorithm.
  • The algorithm is significantly faster than batch alternatives on large datasets and avoids careful learning-rate tuning required by regular stochastic gradient methods.
  • The approach is extended to other matrix factorization formulations.

Appendix A. Theorems and Useful Lemmas

This appendix collects optimization and probability results used to establish the paper’s theoretical guarantees, including differentiability, stochastic-process convergence, and empirical-process control.

  • The appendix provides theorems and lemmas from optimization and probability literature for use in the paper.
  • Danskin’s theorem gives directional differentiability of an optimal value function and differentiability when the minimizer is unique.
  • A sufficient condition ensures that a stochastic process converges almost surely through a quasi-martingale argument.
  • A Donsker-class lemma supplies uniform empirical-process control under boundedness and regularity assumptions.
  • A positive-converging-sums lemma concludes that a nonnegative sequence tends to zero under summability and bounded-increment conditions.

Appendix B. Efficient Projections Algorithms

The appendix develops efficient projection procedures that let the online algorithm accommodate multiple constraint formulations.

  • The section addresses efficient projection of a vector onto two constraint sets to extend the algorithm to various formulations.

B.1 A Linear-time Projection on the Elastic-Net Constraint

This section presents a linear-time method for projecting vectors onto an elastic-net constraint set, with extensions to non-negative constraints and a convergence guarantee.

  • B.1 A Linear-time Projection on the Elastic-Net Constraint: The elastic-net projection problem is formulated for a vector in R^m under an elastic-net constraint.
  • B.1 A Linear-time Projection on the Elastic-Net Constraint: Algorithm 3 extends earlier projection methods to solve the elastic-net case with γ > 0.
  • B.1 A Linear-time Projection on the Elastic-Net Constraint: Lemma 4 states that Algorithm 3 solves the projection problem for b in R^m, γ ≥ 0, and τ > 0.
  • B.1 A Linear-time Projection on the Elastic-Net Constraint: The derivation uses a Lagrangian, closed-form minimization for fixed λ, convexity, strong duality, and complementary slackness.
  • B.1 A Linear-time Projection on the Elastic-Net Constraint: The method identifies the active set S(λ⋆) and computes λ⋆ in closed form, achieving O(m) average-case convergence.
  • B.1 A Linear-time Projection on the Elastic-Net Constraint: The non-negative case is handled by replacing |b[j]| with max(b[j], 0), while γ = 0 recovers the earlier algorithm.

B.2 A Homotopy Method for Solving the Fused Lasso Signal Approximation

The section develops a homotopy method for fused-lasso signal approximation by transforming the problem into a weighted Lasso and exploiting structured computations. The resulting procedure follows regularization paths and solves the key system in O(ms) operations, where s is the number of nonzero values in the optimal solution.

  • Homotopy formulation: The proposed homotopy solves P(τγ1, τγ2, τγ3) across all τ and can provide constrained-problem solutions for every ε.For the related constrained formulation, the regularization path is followed until the constraint becomes unsatisfied.
  • Solution structure: Knowing the solution of P(0, γ2, 0) permits obtaining P(γ1, γ2, γ3) in linear time using soft thresholding and the stated solution relation.For γ3 = 0, u⋆(γ1, γ2, 0) is obtained by soft thresholding u⋆(0, γ2, 0); the lemma supplies the broader reduction.
  • Problem transformation: The substitution v[1] = u[1] and v[i] = u[i] − u[i − 1] recasts the simplified problem as a weighted Lasso.The weights are w1 = 0 and wi = γ2 for i > 1, with a lower-triangular matrix D.
  • Efficient implementation: The structured matrix D and its transpose can be applied in O(m) operations using recursive cumulative-sum formulas.These recursions replace direct O(m^2) computation for the relevant matrix products.
  • Efficient implementation: The active-set inverse has a closed form, allowing the homotopy implementation to avoid matrix inversion and Cholesky factorization.The resulting system in Eq. (23) is solved in O(ms) operations, where s is the number of nonzero values of the optimal solution v.
Loading 0908.0050v2…