On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems
From MaRDI portal
(Redirected from Publication:5853570)
Abstract: Smooth convex minimization over the unit trace-norm ball is an important optimization problem in machine learning, signal processing, statistics and other fields, that underlies many tasks in which one wishes to recover a low-rank matrix given certain measurements. While first-order methods for convex optimization enjoy optimal convergence rates, they require in worst-case to compute a full-rank SVD on each iteration, in order to compute the projection onto the trace-norm ball. These full-rank SVD computations however prohibit the application of such methods to large problems. A simple and natural heuristic to reduce the computational cost is to approximate the projection using only a low-rank SVD. This raises the question if, and under what conditions, this simple heuristic can indeed result in provable convergence to the optimal solution. In this paper we show that any optimal solution is a center of a Euclid. ball inside-which the projected-gradient mapping admits rank that is at most the multiplicity of the largest singular value of the gradient vector. Moreover, the radius of the ball scales with the spectral gap of this gradient vector. We show how this readily implies the local convergence (i.e., from a "warm-start" initialization) of standard first-order methods, using only low-rank SVD computations. We also quantify the effect of "over-parameterization", i.e., using SVD computations with higher rank, on the radius of this ball, showing it can increase dramatically with moderately larger rank. We extend our results also to the setting of optimization with trace-norm regularization and optimization over bounded-trace positive semidefinite matrices. Our theoretical investigation is supported by concrete empirical evidence that demonstrates the extit{correct} convergence of first-order methods with low-rank projections on real-world datasets.
Recommendations
- Provable accelerated gradient method for nonconvex low rank optimization
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- Low-rank optimization with trace norm penalty
- Low-rank inducing norms with optimality interpretations
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A simpler approach to matrix completion
- A Singular Value Thresholding Algorithm for Matrix Completion
- Convex optimization: algorithms and complexity
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Exact matrix completion via convex optimization
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- First-order methods in optimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems
- Low-rank optimization with trace norm penalty
- Practical sketching algorithms for low-rank matrix approximation
- Robust principal component analysis?
- Sparse Approximate Solutions to Semidefinite Programs
- User-friendly tail bounds for sums of random matrices
Cited in
(13)- A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
- Quartic first-order methods for low-rank minimization
- Efficient proximal mapping computation for low-rank inducing norms
- Provable accelerated gradient method for nonconvex low rank optimization
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- Low-rank optimization with trace norm penalty
- Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity
- On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
- Reexamining low rank matrix factorization for trace norm regularization
- Nonsmooth projection-free optimization with functional constraints
- Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes
- Low-rank extragradient methods for scalable semidefinite optimization
- Low-rank matrix completion with Poisson observations via nuclear norm and total variation constraints
This page was built for publication: On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853570)
