PaperlayerView exact revision on arXiv

Source-linked AI summary

Large-Scale Convex Minimization with a Low-Rank Constraint

Shai Shalev-Shwartz, Alon Gonen, Ohad Shamir

arXiv:1106.1622v1cs.LGstat.ML

TL;DR

The paper studies convex optimization over large matrices constrained to have low rank, a problem that is generally NP-hard. It introduces GECO, a greedy method that selects leading singular-vector directions and corrects the resulting components. The method has formal competitiveness guarantees and is applied to matrix completion and robust low-rank approximation.

  • Problem

    Minimizing a convex smooth function under a matrix rank constraint is generally NP-hard, despite applications including collaborative filtering and robust low-rank approximation.

  • Method

    GECO directly minimizes the rank-constrained objective by greedily selecting leading singular vectors of a gradient matrix and optimizing over the accumulated components.

  • Results

    The paper derives formal competitiveness guarantees and applies GECO to matrix completion and robust low-rank matrix approximation.

  • Takeaways & Limitations

    GECO is designed to scale to large matrices because its iterations use only a few power-method iterations, with runtime O(N log(n)) when the approximation tolerance is constant.

  • Takeaways & Limitations

    Robust low-rank approximation has no known efficient algorithm for obtaining the global optimum under a rank constraint.

Abstract

from arXiv · show

We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (approximately) finding the left and right singular vectors corresponding to the largest singular value of a certain matrix, which can be calculated in linear time. This leads to an algorithm which can scale to large matrices arising in several applications such as matrix completion for collaborative filtering and robust low rank matrix approximation.

1. Introduction

The paper develops a greedy approximation approach for convex minimization under a low-rank constraint, which is generally NP-hard. It reformulates low rank as sparsity, enables efficient singular-vector selection, and applies the method to matrix completion and robust low-rank approximation.

  • The objective is convex and smooth, but the non-convex rank constraint makes the problem generally NP-hard.
  • The method represents matrices using an infinite-dimensional vector λ, where low rank corresponds to sparsity in λ.
  • The reformulation applies a greedy algorithm for convex minimization under the sparsity constraint ∥λ∥0 ≤r.
  • The infinite coordinate search becomes finding leading left and right singular vectors of a certain matrix.
  • The algorithm is applied to matrix completion and robust low-rank matrix approximation, with experiments on large-scale movie recommendation data sets.The paper also reports a new sample complexity bound for matrix completion.
  • Unlike trace-norm methods, the approach directly tackles rank minimization and provides formal competitiveness guarantees relative to matrices with small trace norm.

2. The GECO algorithm

GECO incrementally builds a low-rank matrix by selecting singular-vector directions and fully correcting their coefficients through convex optimization. Approximate singular-vector computation and implementation choices make the method scalable, while replacement steps and regularization extend its use.

  • GECO represents a matrix through singular-vector pairs and coefficients, with rank at most r admitting a representation using ∥λ∥0 ≤r.
  • The algorithm adds one vector pair, minimizes R(UBV^T) over the accumulated components, computes an SVD of B, and updates U and V.
  • Each iteration selects the unit vectors maximizing the derivative magnitude, which are the leading left and right singular vectors of ∇R(A(λ)).
  • The leading singular-vector search can use approximate maximization, including a power method with runtime O(N log(n)) when τ is constant.
  • GECO can replace a component when zeroing the smallest singular value strictly decreases the objective, avoiding a rank increase in that case.
  • For large r, full correction may be expensive, so restricting B to a diagonal matrix reduces Step 6 to an optimization over i variables.

3. Analysis

GECO has formal competitiveness guarantees: after r iterations, it competes with bounded-trace-norm matrices, and under additional strong-convexity assumptions, with rank-r matrices.

  • Competitive analysis: GECO’s analysis establishes competitiveness after r iterations against matrices whose trace norm is bounded as a function of r.The section presents this as the first theorem’s guarantee.
  • Trace-norm guarantee: For a β-smooth objective and tolerance τ, Theorem 1 guarantees R(A) ≤ R(Ā) + ϵ for every comparator satisfying its stated trace-norm condition.The theorem applies to GECO and its variants.
  • Competitive analysis: Under additional assumptions, GECO can also compete with matrices whose rank is at most r.The stronger comparison requires strong convexity over the singular vectors of the comparator.
  • Rank guarantee: The second theorem requires σ-strong convexity over the comparator’s singular vectors and likewise guarantees R(A) ≤ R(Ā) + ϵ.Strong convexity is defined over supports restricted to a selected set of singular-vector pairs.

4. Application I: Matrix Completion

For matrix completion, GECO exploits sparse observed-entry gradients and power-method singular-vector computation, while its analysis yields a sample-complexity guarantee.

  • 4. Application I: Matrix Completion: Matrix completion predicts an unknown target matrix from a random subset of observed entries, such as user ratings in the Netflix problem.The low-rank matrix A is fitted to agree approximately with Y on observed entries.
  • 4.1. Analysis: GECO’s matrix-completion gradient has at most |E| nonzero elements, enabling Step 4 to run with the power method in O(|E| log(n)) time.The gradient entry is 2(A_i,j − Y_i,j) on observed entries and zero elsewhere.
  • 4.1. Analysis: For matrix completion, the smoothness parameter is at most 2/|E|.This bound is used in the application-specific GECO analysis.
  • 4.1. Analysis: When ||Ā||_tr is of order √(mn), order n^3/2 observed entries suffice to learn Y, matching recent trace-norm learning guarantees.The statement assumes m ≤ n and reports the resulting sample scale.

5. Application II: Robust Low Rank Matrix Approximation

GECO extends low-rank approximation beyond efficiently solvable Frobenius objectives to robust convex discrepancies, using smoothed l1 objectives such as Huber loss.

  • 5. Application II: Robust Low Rank Matrix Approximation: Low-rank approximation minimizes a discrepancy d(A,Y), but Frobenius-norm minimization is sensitive to outliers.The Frobenius formulation is efficiently solvable via SVD, motivating more robust discrepancies.
  • 5. Application II: Robust Low Rank Matrix Approximation: No efficient algorithm is known for globally minimizing the l1 discrepancy under a rank constraint.This motivates the approximate optimization approach developed in the paper.
  • Robust objectives: GECO can efficiently find a low-rank matrix that approximately minimizes any convex discrepancy measure d, including robust l1-based objectives.The algorithm requires smoothness, which the raw l1 norm does not satisfy.
  • Huber-loss analysis: For the Huber-loss objective, the smoothness parameter is at most 1/n^2.The bound follows because the scalar Huber loss has smoothness parameter 1 and the objective averages over entries.
  • Huber-loss analysis: GECO can find A with d(A,Y) ≤ d(Ā,Y)+ϵ while maintaining rank(A)=O(||Ā||^2).This is the stated Huber-loss corollary for any comparator Ā.

6. Experiments

GECO was evaluated on three MovieLens datasets using approximate singular-vector updates and compared with JS. GECO reduced test RMSE faster, with dataset-dependent final error and overfitting behavior.

  • GECO was evaluated on MovieLens100K, MovieLens1M, and MovieLens10M collaborative-filtering datasets.The datasets contain 10^5, 10^6, and 10^7 ratings, respectively.
  • The experiments used update-vector variants, additional replacement steps, and 30 power iterations for ApproxSV.The replacement-step parameter was q = 20.
  • GECO decreased test RMSE much faster than the JS algorithm as rank increased.Figure 1 plots test-set RMSE against rank for all three datasets, with the horizontal line showing JS's minimal error.
  • GECO had slightly larger error on MovieLens100K, slightly smaller error on MovieLens1M, and the same error on MovieLens10M.These comparisons are reported for the achieved test error across the three datasets.
  • GECO began overfitting beyond rank 4 on MovieLens100K, while JS began overfitting after about 30 iterations.On MovieLens1M, GECO achieved smaller error because JS's trace-norm constraint produced higher estimation error.

7. Discussion

The discussion presents GECO as a scalable greedy method for convex minimization under rank constraints. Its iterations use a small number of power-method steps, and the paper identifies further application areas.

  • GECO minimizes a convex function subject to a rank constraint through an efficient greedy approach.
  • Each GECO iteration uses O(log(n)) power-method iterations, allowing the method to scale to large matrices.
  • The authors intend to apply GECO to multiclass classification and learning fast quadratic classifiers.

A.1. Proof of Theorem 1

The proof introduces a smoothness-based lemma for greedy updates in the infinite-dimensional sparse-vector formulation. The lemma relates an approximate singular-vector direction to a guaranteed objective decrease.

  • Lemma 3 assumes β-smoothness and compares a minimizer supported on I with a competing vector supported on ¯I.It defines s as the competing vector's ℓ1 norm and uses an ApproxSV direction computed from the gradient.
  • The lemma establishes the existence of an update size η for which the quadratic upper bound Qp,q(η) controls the objective after a greedy coordinate update.

Proof

The proof combines sign normalization, smoothness, convexity, and the ApproxSV update rule to bound the decrease in objective error at each rank increase. Iterating this bound yields the theorem's approximation guarantee.

  • Sign normalization lets the proof assume a nonnegative comparator vector and a nonpositive gradient correlation for the selected singular-vector pair.
  • Smoothness bounds the updated objective by the quadratic function Q_u,v(η) for every η ≥ 0.
  • Convexity and support optimality relate the gradient terms to the comparator gap f(¯λ) − f(λ).
  • Choosing η = (f(λ) − f(¯λ))(1 −τ)/(sβ) produces the key decrease inequality used in the proof.
  • The rank-increase update guarantees a non-increasing loss, and the theorem follows once the error bound reaches ϵ.The proof invokes the smoothness parameter, comparator trace norm, rank, and ApproxSV accuracy in the final bound.

A.2. Proof of Theorem 2

The proof represents the reference matrix through its SVD and applies strong convexity to bound the associated coefficient vector. Norm and rank identities then connect this bound to the matrix quantities, completing the argument via Theorem 1.

  • The reference matrix is represented through its SVD by a vector whose zero-norm equals the matrix rank.
  • Strong convexity of f over the support of the SVD vector provides a bound involving its squared 2-norm, sparsity, f(0), and σ.
  • The proof converts the vector bound using ∥¯A∥tr = ∥¯λ∥1, rank(¯A) = ∥¯λ∥0, and f(0) = R(0).
  • The theorem follows by combining the preceding argument with Theorem 1.
Loading 1106.1622v1…