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

• 成果类型: Article; Early Access
• 署名作者: Blanchard, Moise; Zhang, Junhui; Jaillet, Patrick
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0208
• 发表日期: 2024
• 关键词: algorithm

摘要

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-plane algorithms in dimension d , which use O ( d 2 ) memory and O ( d ) queries, are Pareto optimal for both convex optimization and the feasibility problem, up to logarithmic factors. Precisely, building upon techniques introduced in previous works, we prove that to minimize 1-Lipschitz convex functions over the unit ball to 1/d4 accuracy, any deterministic first-order algorithms using at most d 2-6 bits of memory must make ohm ( d 1 +6/3 ) queries for any 6 is an element of [ 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-6 memory, the number of queries required is ohm ( d 1 +6 ) . This resolves a Conference on Learning Theory 2019 open problem.