Efficient convex optimization requires superlinear memory

DOI10.1145/3689208MaRDI QIDQ6993537zbMATH OpenFDO

Authors Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant

Publication date 25 April 2025

Published in Journal of the ACM (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3689208

zbMATH Keywords

convex optimizationcutting planes methodsfirst-order methodsmemory lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25)

Cites work

• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• A cutting plane algorithm for convex programming that uses analytic centers
• A faster cutting plane method and its implications for combinatorial and convex optimization
• A survey of nonlinear conjugate gradient methods
• A time-space lower bound for a large class of learning problems
• An improved cutting plane method for convex optimization, convex-concave games, and its applications
• An information statistics approach to data stream and communication complexity
• Communication lower bounds for statistical estimation problems via a distributed data processing inequality
• Communication-efficient distributed statistical inference
• Computing correlated equilibria in multi-player games
• Entropy samplers and strong generic lower bounds for space bounded learning
• Extractor-based time-space lower bounds for learning
• Fast learning requires good memory: a time-space lower bound for parity learning
• Function minimization by conjugate gradients
• Hanson-Wright inequality and sub-Gaussian concentration
• High-dimensional probability. An introduction with applications in data science
• High-dimensional statistics. A non-asymptotic viewpoint
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 4123531 (Why is no real title available?)
• scientific article; zbMATH DE number 6135091 (Why is no real title available?)
• scientific article; zbMATH DE number 7788399 (Why is no real title available?)
• Local privacy and statistical minimax rates
• Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
• Memory-query tradeoffs for randomized convex optimization
• Memory-sample tradeoffs for linear regression with small error
• Methods of conjugate gradients for solving linear systems
• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• Newton-type methods for non-convex optimization under inexact Hessian information
• Numerical linear algebra in the streaming model
• On parallel complexity of nonsmooth convex optimization
• On the limited memory BFGS method for large scale optimization
• Querying a Matrix through Matrix-Vector Products
• Solving convex programs by random walks
• Sub-sampled Newton methods
• Submodular function minimization
• The space complexity of approximating the frequency moments
• The volumetric barrier for semidefinite programming.
• Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
• Time-space hardness of learning sparse parities
• Updating Quasi-Newton Matrices with Limited Storage

This page was built for publication: Efficient convex optimization requires superlinear memory

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