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

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˜(d2) 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 d2−δ bits of memory must make Ω˜(d1+δ/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 d2−δ memory, the number of queries required is Ω˜(d1+δ). This resolves a Conference on Learning Theory 2019 open problem. Funding: This work was partly supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0263] and the Office of Naval Research [Grant N00014-18-1-2122]. [ABSTRACT FROM AUTHOR]

Copyright of Mathematics of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)