Subsampling algorithms for semidefinite programming
From MaRDI portal
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.
Recommendations
Cites work
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
- Acceleration of Stochastic Approximation by Averaging
- Approximating Subdifferentials by Random Sampling of Gradients
- ARPACK Users' Guide
- Consistency of trace norm minimization
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Exact matrix completion via convex optimization
- Fast computation of low-rank matrix approximations
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast monte-carlo algorithms for finding low-rank approximations
- First-Order Methods for Sparse Covariance Selection
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 5485455 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- LAPACK Users' Guide
- Learning the kernel matrix with semidefinite programming
- Matrix algorithms. Vol. 2: Eigensystems
- Numerical methods for large eigenvalue problems
- On Estimating the Largest Eigenvalue with the Lanczos Algorithm
- On the distribution of the largest eigenvalue in principal components analysis
- Orthogonal Eigenvectors and Relative Gaps
- Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture
- Primal-dual subgradient methods for convex problems
- Robust Stochastic Approximation Approach to Stochastic Programming
- Sampling from large matrices
- Spectral algorithms
- The convergence behavior of Ritz values in the presence of close eigenvalues
- The design and implementation of the MRRR algorithm
- The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
- Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
Cited in
(10)- The sublinear operator method and selector problems
- Community detection with a subsampled semidefinite program
- Sublinear time algorithms for approximate semidefinite programming
- Scalable semidefinite programming
- Memory-efficient structured convex optimization via extreme point sampling
- Stochastic semidefinite optimization using sampling methods
- A stochastic approximation method for convex programming with many semidefinite constraints
- Riemannian Langevin algorithm for solving semidefinite programs
- Core-elements for large-scale least squares estimation
- Universal matrix sparsifiers and fast deterministic algorithms for linear algebra
This page was built for publication: Subsampling algorithms for semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168846)
