An official website of the United States government
Free, publicly-accessible full text available January 1, 2027
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Meka, Raghu (Ed.)We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associated dual maximin optimization problem. Our method adds recursive regularization over a logarithmic number of rounds where each round consists of an approximate regularized primal optimization followed by the computation of a dual best response. We apply this result to obtain new state-of-the-art runtimes for solving matrix games in specific parameter regimes, obtain improved query complexity for solving the dual of the CVaR distributionally robust optimization (DRO) problem, and recover the optimal query complexity for finding a stationary point of a convex function.more » « less
-
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 $$d^{1.25-\delta}$$ bits of memory must make at least $$\tilde{Omega}(d^{1+(4/3)\delta})$$ first-order queries (for any constant $$\delta in [0,1/4]$$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $$\tilde{O}(d)$$ query bound for this problem obtained by cutting plane methods that use $$\tilde{O}(d^2)$$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro.more » « less
Full Text Available