Sublinear time algorithms for approximate semidefinite programming

DOI10.1007/s10107-015-0932-zzbMath1346.90656OpenAlexW806902362MaRDI QIDQ304246

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

semidefinite programmingonline algorithmslarge scale optimizationsublinear algorithms

Mathematics Subject Classification ID

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

Related Items

Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Unnamed Item ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems ⋮ Generalized Conditional Gradient for Sparse Estimation ⋮ Scalable Semidefinite Programming

Cites Work

• User-friendly tail bounds for sums of random matrices
• Smoothing technique and its applications in semidefinite optimization
• A sublinear-time randomized approximation algorithm for matrix games
• A Randomized Mirror-Prox Method for Solving Structured Large-Scale Matrix Saddle-Point Problems
• Online Learning and Online Convex Optimization
• 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
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• Subsampling Algorithms for Semidefinite Programming
• Sublinear optimization for machine learning
• A Simpler Approach to Matrix Completion
• Sparse Approximate Solutions to Semidefinite Programs
• Prediction, Learning, and Games
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item