Sublinear time algorithms for approximate semidefinite programming

DOI10.1007/S10107-015-0932-ZMaRDI QIDQ304246zbMATHOpenAlexFDO

Authors Dan Garber, Elad Hazan

Publication date 25 August 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-015-0932-z

zbMATH Keywords

online algorithmslarge scale optimizationsemidefinite programmingsublinear algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Large-scale problems in mathematical programming (90C06) Randomized algorithms (68W20) Semidefinite programming (90C22)

Recommendations

• Subsampling algorithms for semidefinite programming
• Online Semidefinite Programming.
• Sparse Approximate Solutions to Semidefinite Programs
• Approximating semidefinite packing programs
• scientific article; zbMATH DE number 2088028

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
• A simpler approach to matrix completion
• A sublinear-time randomized approximation algorithm for matrix games
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Learning the kernel matrix with semidefinite programming
• Online learning and online convex optimization
• Prediction, Learning, and Games
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Smoothing technique and its applications in semidefinite optimization
• Solving variational inequalities with stochastic mirror-prox algorithm
• Sparse Approximate Solutions to Semidefinite Programs
• Sublinear optimization for machine learning
• Subsampling algorithms for semidefinite programming
• The multiplicative weights update method: a meta-algorithm and applications
• User-friendly tail bounds for sums of random matrices

Cited in

(16)

• scientific article; zbMATH DE number 2081093 (Why is no real title available?)
• An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• Generalized conditional gradient for sparse estimation
• Scalable semidefinite programming
• Sparse Approximate Solutions to Semidefinite Programs
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• Computational methods for solving nonconvex block-separable constrained quadratic problems
• Optimizing over the growing spectrahedron
• Core-elements for large-scale least squares estimation
• Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• Subsampling algorithms for semidefinite programming
• scientific article; zbMATH DE number 7559394 (Why is no real title available?)
• Riemannian Langevin algorithm for solving semidefinite programs
• Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

This page was built for publication: Sublinear time algorithms for approximate semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q304246)