marsden22a@v178@PMLR

Total: 1

#1 Efficient Convex Optimization Requires Superlinear Memory [PDF4] [Copy] [Kimi5] [REL]

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

We show that any memory-constrained, first-order algorithm which minimizes d-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most d1.25δ bits of memory must make at least Ω(d1+(4/3)δ) first-order queries (for any constant δ[0,1/4]). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal ˜O(d) query bound for this problem obtained by cutting plane methods that use ˜O(d2) memory. This resolves one of the open problems in the COLT 2019 open problem publication of Woodworth and Srebro.

Subject: COLT.2022 - Award