Subsampling Algorithms for Semidefinite Programming

Abstract

We derive a stochastic gradient algorithm for semidefinite optimization using randomization techniques. The algorithm uses subsampling to reduce the computational cost of each iteration and the subsampling ratio explicitly controls granularity, i.e. the tradeoff between cost per iteration and total number of iterations. Furthermore, the total computational cost is directly proportional to the complexity (i.e. rank) of the solution. We study numerical performance on some large-scale problems arising in statistical learning.

Final version, to appear in Stochastic Systems

References in corpus (4)

• Consistency of trace norm minimization
• Tracy--Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
• Exact Matrix Completion via Convex Optimization
• Smooth Optimization with Approximate Gradient

Cited by in corpus (7)

• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Randomized algorithms for matrices and data
• A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality
• A Matrix Hyperbolic Cosine Algorithm and Applications
• A Rank-1 Sketch for Matrix Multiplicative Weights
• Tensor sparsification via a bound on the spectral norm of random tensors
• Near-Optimal Entrywise Sampling of Numerically Sparse Matrices