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
- 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?)
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
- ARPACK Users' Guide
- Acceleration of Stochastic Approximation by Averaging
- Approximating Subdifferentials by Random Sampling of Gradients
- 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 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 computation of low-rank matrix approximations
- 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
- 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 Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
- The convergence behavior of Ritz values in the presence of close eigenvalues
- The design and implementation of the MRRR algorithm
- Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
Cited in
(10)- Stochastic semidefinite optimization using sampling methods
- Sublinear time algorithms for approximate semidefinite programming
- Community detection with a subsampled semidefinite program
- 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
- Scalable semidefinite programming
- Memory-efficient structured convex optimization via extreme point sampling
- The sublinear operator method and selector problems
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)
