Sublinear time algorithms for approximate semidefinite programming
From MaRDI portal
Publication:304246
DOI10.1007/S10107-015-0932-ZzbMATH Open1346.90656OpenAlexW806902362MaRDI QIDQ304246FDOQ304246
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
Recommendations
Online algorithms; streaming algorithms (68W27) Large-scale problems in mathematical programming (90C06) Randomized algorithms (68W20) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Prediction, Learning, and Games
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- User-friendly tail bounds for sums of random matrices
- Learning the kernel matrix with semidefinite programming
- Online learning and online convex optimization
- Sparse Approximate Solutions to Semidefinite Programs
- A sublinear-time randomized approximation algorithm for matrix games
- Solving variational inequalities with stochastic mirror-prox algorithm
- The multiplicative weights update method: a meta-algorithm and applications
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A simpler approach to matrix completion
- A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Subsampling algorithms for semidefinite programming
- Sublinear optimization for machine learning
- Smoothing technique and its applications in semidefinite optimization
Cited In (16)
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Sparse Approximate Solutions to Semidefinite Programs
- Generalized conditional gradient for sparse estimation
- Title not available (Why is that?)
- Finding Sparse Solutions for Packing and Covering Semidefinite Programs
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Computational methods for solving nonconvex block-separable constrained quadratic problems
- Title not available (Why is that?)
- Riemannian Langevin algorithm for solving semidefinite programs
- An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
- Core-elements for large-scale least squares estimation
- Subsampling algorithms for semidefinite programming
- Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems
- Scalable semidefinite programming
- Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
- Optimizing over the growing spectrahedron
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)
