Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal

2023/02/09 by Blanchard, Moïse, Zhang, Junhui, Jaillet, Patrick · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2302.04963

Abstract

We give query complexity lower bounds for convex optimization and the related feasibility problem. We show that quadratic memory is necessary to achieve the optimal oracle complexity for first-order convex optimization. In particular, this shows that center-of-mass cutting-planes algorithms in dimension d which use O(d²) memory and O(d) queries are Pareto-optimal for both convex optimization and the feasibility problem, up to logarithmic factors. Precisely, we prove that to minimize 1-Lipschitz convex functions over the unit ball to 1/d⁴ accuracy, any deterministic first-order algorithms using at most d^2-δ bits of memory must make Ω(d^1+δ/3) queries, for any δ∈[0,1]. For the feasibility problem, in which an algorithm only has access to a separation oracle, we show a stronger trade-off: for at most d^2-δ memory, the number of queries required is Ω(d^1+δ). This resolves a COLT 2019 open problem of Woodworth and Srebro.

Cited by

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

Related

• Memory-Query Tradeoffs for Randomized Convex Optimization
• Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
• Efficient Convex Optimization Requires Superlinear Memory
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes