Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract)

1. [Alon et al., 1999] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the fre- quency moments. Journal of Computer and system sci- ences, 58(1):137-147, 1999.
2. [Anstreicher, 2000] Kurt M Anstreicher. The volumetric bar- rier for semidefinite programming. Mathematics of Oper- ations Research, 25(3):365-380, 2000.
3. [Arjevani and Shamir, 2015] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28, 2015.
4. [Atkinson and Vaidya, 1995] David S Atkinson and Pravin M Vaidya. A cutting plane algorithm for convex programming that uses analytic centers. Mathematical Programming, 69(1):1-43, 1995.
5. [Balcan et al., 2012] Maria Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. Distributed learning, communication complexity and privacy. In Conference on Learning Theory, pages 26-1. JMLR Workshop and Con- ference Proceedings, 2012.
6. [Balkanski and Singer, 2018] Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex opti- mization: Adaptivity lower bounds for non-smooth convex minimization. arXiv preprint arXiv:1808.03880, 2018.
7. [Bar-Yossef et al., 2004] Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004.
8. [Beame et al., 2018] Paul Beame, Shayan Oveis Gharan, and Xin Yang. Time-space tradeoffs for learning finite func- tions from random evaluations, with applications to poly- nomials. In Conference On Learning Theory, pages 843- 856. PMLR, 2018.
9. [Bertsimas and Vempala, 2004] Dimitris Bertsimas and San- tosh Vempala. Solving convex programs by random walks. Journal of the ACM (JACM), 51(4):540-556, 2004.
10. [Braun et al., 2017] Gábor Braun, Cristóbal Guzmán, and Sebastian Pokutta. Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Transactions on Information Theory, 63(7), 2017.
11. [Braverman et al., 2016] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Com- munication lower bounds for statistical estimation prob- lems via a distributed data processing inequality. In Pro- ceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1011-1020, 2016.
12. [Braverman et al., 2020] Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. The gradient complexity of linear regression. In Conference on Learn- ing Theory, pages 627-647. PMLR, 2020.
13. [Bubeck et al., 2019] Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in Neural Information Processing Systems, 32, 2019.
14. [Bubeck, 2014] Sébastien Bubeck. Convex optimiza- tion: Algorithms and complexity. arXiv preprint arXiv:1405.4980, 2014.
15. [Clarkson and Woodruff, 2009] Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the stream- ing model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 205-214, 2009.
16. [Dagan and Shamir, 2018] Yuval Dagan and Ohad Shamir. Detecting correlations with little memory and communi- cation. In Conference On Learning Theory, pages 1145- 1198. PMLR, 2018.
17. [Dagan et al., 2019] Yuval Dagan, Gil Kur, and Ohad Shamir. Space lower bounds for linear prediction in the streaming model. In Conference on Learning Theory, pages 929-954. PMLR, 2019.
18. [Duchi et al., 2013] John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical mini- max rates. In 2013 IEEE 54th Annual Symposium on Foun- dations of Computer Science, pages 429-438. IEEE, 2013.
19. [Fletcher and Reeves, 1964] R. Fletcher and C. M. Reeves. Function minimization by conjugate gradients. The Com- puter Journal, 7(2), 1964.
20. [Garg et al., 2014] Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estimation and dimensionality. Advances in Neural Infor- mation Processing Systems, 27, 2014.
21. [Garg et al., 2018] Sumegha Garg, Ran Raz, and Avishay Tal. Extractor-based time-space lower bounds for learning. In Proceedings of the 50th Annual ACM SIGACT Sympo- sium on Theory of Computing, pages 990-1002, 2018.
22. [Hestenes and Stiefel, 1952] M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6), 1952.
23. [Khachiyan et al., 1988] Leonid G Khachiyan, Sergei Pavlovich Tarasov, and II Erlikh. The method of inscribed ellipsoids. In Soviet Math. Dokl, volume 37, pages 226-230, 1988.
24. [Kol et al., 2017] Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Pro- ceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1067-1080, 2017.
25. [Levin, 1965] Anatoly Yur'evich Levin. An algorithm for minimizing convex functions. In Doklady Akademii Nauk, volume 160, pages 1244-1247. Russian Academy of Sci- ences, 1965.
26. [Liu and Nocedal, 1989] Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale op- timization. Mathematical Programming, 45(1-3), 1989.
27. [McCormick, 2005] S Thomas McCormick. Submodular function minimization. Handbooks in operations research and management science, 12:321-391, 2005.
28. [Moshkovitz and Moshkovitz, 2017] Dana Moshkovitz and Michal Moshkovitz. Mixing implies lower bounds for space bounded learning. In Conference on Learning The- ory, pages 1516-1566. PMLR, 2017.
29. [Moshkovitz and Moshkovitz, 2018] Dana Moshkovitz and Michal Moshkovitz. Entropy samplers and strong generic lower bounds for space bounded learning. In 9th In- novations in Theoretical Computer Science Conference. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
30. [Nemirovski and Yudin, 1983] Arkadij Nemirovski and David Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
31. [Nemirovski, 1994] Arkadi Nemirovski. On parallel com- plexity of nonsmooth convex optimization. Journal of Complexity, 10(4):451-463, 1994.
32. [Nesterov, 1989] Ju E Nesterov. Self-concordant func- tions and polynomial-time methods in convex program- ming. Report, Central Economic and Mathematic Insti- tute, USSR Acad. Sci, 1989.
33. [Nesterov, 2003] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
34. [Nocedal, 1980] Jorge Nocedal. Updating quasi-Newton ma- trices with limited storage. Mathematics of Computation, 35(151), 1980.
35. [Papadimitriou and Roughgarden, 2008] Christos H Pa- padimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3):1-29, 2008.
36. [Pilanci and Wainwright, 2017] Mert Pilanci and Martin J Wainwright. Newton sketch: A near linear-time optimiza- tion algorithm with linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205-245, 2017.
37. [Raz, 2017] Ran Raz. A time-space lower bound for a large class of learning problems. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, pages 732-742. IEEE, 2017.
38. [Raz, 2018] Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. Journal of the ACM, 66(1):1-18, 2018.
39. [Shamir, 2014] Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and esti- mation. Advances in Neural Information Processing Sys- tems, 27, 2014.
40. [Sharan et al., 2019] Vatsal Sharan, Aaron Sidford, and Gre- gory Valiant. Memory-sample tradeoffs for linear regres- sion with small error. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 890-901, 2019.
41. [Shor, 1977] Naum Z Shor. Cut-off method with space ex- tension in convex programming problems. Cybernetics, 13(1):94-96, 1977.
42. [Simchowitz et al., 2018] Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. Tight query com- plexity lower bounds for pca via finite sample deformed wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1249-1259, 2018.
43. [Simchowitz, 2018] Max Simchowitz. On the randomized complexity of minimizing a convex quadratic function. arXiv preprint arXiv:1807.09386, 2018.
44. [Steinhardt and Duchi, 2015] Jacob Steinhardt and John Duchi. Minimax rates for memory-bounded sparse lin- ear regression. In Conference on Learning Theory, pages 1564-1587. PMLR, 2015.
45. [Steinhardt et al., 2016] Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statis- tical queries. In Conference on Learning Theory, pages 1490-1516. PMLR, 2016.
46. [Sun et al., 2021] Xiaoming Sun, David P Woodruff, Guang Yang, and Jialin Zhang. Querying a matrix through matrix-vector products. ACM Transactions on Algorithms (TALG), 17(4):1-19, 2021.
47. [Vaidya, 1989] Pravin M Vaidya. A new algorithm for mini- mizing convex functions over convex sets. In 30th Annual Symposium on Foundations of Computer Science, pages 338-343. IEEE Computer Society, 1989.
48. [Woodworth and Srebro, 2016] Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing com- posite objectives. Advances in neural information process- ing systems, 29, 2016.
49. [Woodworth and Srebro, 2017] Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex optimization. arXiv preprint arXiv:1709.03594, 2017.
50. [Woodworth and Srebro, 2019] Blake Woodworth and Nathan Srebro. Open problem: The oracle complexity of convex optimization with limited memory. In Conference on Learning Theory, pages 3202-3210. PMLR, 2019.
51. [Woodworth et al., 2021] Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference on Learning Theory, pages 4386-4437. PMLR, 2021.
52. [Xu et al., 2020] Peng Xu, Fred Roosta, and Michael W Ma- honey. Newton-type methods for non-convex optimiza- tion under inexact hessian information. Mathematical Pro- gramming, 184(1):35-70, 2020.
53. [Yudin and Nemirovskii, 1976] DB Yudin and Arkadi S Ne- mirovskii. Informational complexity and efficient methods for the solution of convex extremal problems. Matekon, 13(2):22-45, 1976.
54. [Zhang et al., 2013] Yuchen Zhang, John C Duchi, Michael I Jordan, and Martin J Wainwright. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In Conference on Neural In- formation Processing Systems, pages 2328-2336. Cite- seer, 2013.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Introduction

Machine learning is intricately linked with continuous optimization, and gradient-based optimization methods are the main workhorse of modern machine learning. In this work, our goal is to understand how computational considerations affect the ability to efficiently optimize a function. A natural starting point to examine this is the canonical setting of minimizing a convex function f : Rd → R given access to a first-order oracle. A first-order oracle returns the function evaluation and (sub)gradient (f(x),∇f(x)) when queried at any point x. The goal is to understand how many queries to the first-order oracle are necessary to minimize the function.

Understanding the first-order query complexity for minimizing convex functions has been foundational in optimization theory [Nemirovski and Yudin, 1983]. There are methods that, given any 1-Lipschitz, convex f : Rd → R accessible via a first-order oracle, compute an ϵ-approximate minimizer over the unit ball with just O(min{ϵ-2 , d log(1/ϵ)}) first order queries. This query complexity is known to be worst-case optimal [Nemirovski and Yudin, 1983].

∗This paper was initially published in the 35th Annual Conference on Learning Theory (COLT 2022).

O(ϵ-2 ) queries is achievable using (sub)gradient descent. Variants of gradient-descent are the most widely used optimization methods for modern machine learning settings, owing to their simplicity and computational efficiency. In particular, subgradient descent solves the problem using a total of O(dϵ-2 ) computation time (assuming arithmetic operations on O(log(d/ϵ))-bit numbers take constant time), and only requires O(d log(1/ϵ))-bits of memory.

On the other hand, building on the O(d2 log(1/ϵ)) query complexity of the well-known ellipsoid method [Yudin and Nemirovskii, 1976; Shor, 1977], different

ods achieve a query complexity of O(d log(1/ϵ)), e.g. center of mass with sampling based techniques [Levin, 1965; Bertsimas and Vempala, 2004], volumetric center [Vaidya, 1989; Atkinson and Vaidya, 1995], inscribed ellipsoid [Khachiyan et al., 1988; Nesterov, 1989]; these methods are perhaps less frequently used in practice and large-scale learning. This is due to the fact that they are more complex than simple gradient descent based approaches, they all use at least Ω(d3 log(1/ϵ))-time and Ω(d2 log(1/ϵ)) bits of memory.

Though state-of-the-art cutting plane methods have larger computational overhead compared to gradient descent and are sometimes regarded as impractical in different settings, for small enough ϵ, they give the state-of-the-art query bounds. Further, in different theoretical settings, e.g. semidefinite programming [Anstreicher, 2000], submodular optimization [McCormick, 2005] and equilibrium computation [Papadimitriou and Roughgarden, 2008], cutting-plane-methods have yielded state-of-the-art runtimes at various points of time. This leads to the natural question of what is needed of a method to significantly outperform gradient descent and take advantage of the improved query complexity enjoyed by cutting plane methods? Can we design methods that obtain optimal query complexities while maintaining the practicality of gradient descent methods?

In this work, we take memory as a lens to understand the computational complexity of first-order convex optimization. Not only is memory usage one of the most fundamental measures of computational complexity for an algorithm, memory considerations can also play a crucial role in contemporary learning and optimization settings. In addition, as we show in this work, using memory as a lens offers the possibility of proving a clean unconditional separation between simple/complex techniques-as also judged by other measures such as their running time. This perspective on the role of memory in optimization is also well-articulated in the openproblem paper of [Woodworth and Srebro, 2019].

We show that memory plays a critical role in attaining optimal query complexity for convex optimization. Our main result is the following theorem which shows that any algorithm whose memory usage is sufficiently small (though still superlinear) must make polynomially more queries to a firstorder oracle than cutting plane methods. Specifically, any algorithm that uses significantly less than d1.25 bits of memory requires a polynomial factor more first order queries than the optimal O(d log(d)) queries achieved by quadratic memory cutting plane methods.

Theorem 1 For some ϵ ≥ 1/ poly(d) and any δ ∈ [0, 1/4] the following is true: any algorithm which outputs an ϵ-optimal point with probability at least 2/3 given first order oracle access to any 1-Lipschitz convex function must use either at least d1.25-δ bits of memory or make ˜Ω(d1+ 43 δ ) first order queries (where the ˜Ω notation hides poly-logarithmic factors in d).

Beyond shedding light on the complexity of a fundamental memory-constrained optimization problem, we provide several tools for establishing such lower bounds. In particular, we introduce a set of properties which are sufficient for an optimization problem to exhibit a memory-lower bound and provide an information-theoretic framework to prove these lower bounds. We hope these tools are an aid to future work on the role of memory in optimization.

This work fits within the broader context of understanding fundamental resource tradeoffs for optimization and learning. For many settings, establishing (unconditional) query/time or memory/time tradeoffs is notoriously hard-perhaps akin to P vs NP (e.g. providing time lower bounds for cutting plane methods). Questions of memory/query and memory/data tradeoffs, however, have a more information theoretic nature and hence seem more approachable. Together with the increasing importance of memory considerations in large-scale optimization and learning, there is a strong case for pinning down the landscape of such tradeoffs, which may offer a new perspective on the current suite of algorithms and inform the effort to develop new ones.

1.1 Technical Overview and Contributions

To prove Theorem 1, we provide an explicit distribution over functions that is hard for any memory-constrained randomized algorithm to optimize. Though the proof requires care and we introduce a variety of machinery to obtain it, this lower bounding family of functions is simple to state. The function is a variant of the so-called "Nemirovski" function, which has been used to show lower bounds for highly parallel non-smooth convex optimization [Nemirovski, 1994; Bubeck et al., 2019; Balkanski and Singer, 2018].

Formally, our difficult class of functions for memory size M is constructed as follows: for some γ > 0 and some N = ˜O (d2 /M ) let v1, . . . , vN be unit vectors drawn i.i.d. from the d dimensional scaled hypercube vi i.i.d. ∼ Unif (d-1/2Hd ) and let a1, . . . , a⌊d/2⌋ be drawn i.i.d. from the hypercube, aj ∼ Unif (Hd) where αHd := {±α}d . Let A = (a1, . . . , a⌊d/2⌋ ) and define

Formula not decoded

Rather than give a direct proof of Theorem 1 using this explicit function we provide a more abstract framework which gives broader insight into which kinds of functions could lead to non-trivial memory-constrained lower bounds, and which might lead to tighter lower bounds in the future. To that end we introduce the notion of a memory-sensitive class which delineates the key properties of a distribution over functions that lead to memory-constrained lower bounds. We show that for such functions, the problem of memory constrained optimization is at least as hard as the following problem of finding a set of vectors which are approximately orthogonal to another set of vectors:

Definition 2 ( Orthogonal Vector Game, informal version)

Given A ∈ {±1}d/2×d , the Player's objective is to return a set of k vectors {y1, . . . , yk} which satisfy

1. ∀i ∈ [k], yi is approximately orthogonal to all the rows of A : ∥Ayi∥∞ / ∥yi∥2 ≤ d-4 .
2. The set of vectors {y1, . . . , yk} is robustly linearly independent: denoting S0 = ∅, Si = span(y1, . . . , yi), ∥∥∥ProjSi-1 (yi)∥∥∥2 / ∥yi∥2 ≤ 1 - 1/d2 ,

where the notation ProjS(x) denotes the vector in the subspace S which is closest in ∥·∥2 to x. The game proceeds as follows: The Player first gets to observe A and store a M-bit long Message about A. She does not subsequently have free access to A, but can adaptively make up to m queries as follows: for i ∈ [m], based on Message and all previous queries and their results, she can request any row i ∈ [d/2] of the matrix A. Finally, she outputs a set of k vectors as a function of Message and all m queries and their results.

Note that the Player can trivially win the game for M ≥ Ω(dk),m = 0 (by just storing a satisfactory set of k vectors in the Message) and for M = 0,m = d/2 (by querying all rows of A). We show a lower bound that this is essentially all that is possible: for A sampled uniformly at random from {±1}d/2×d , if M is a constant factor smaller than dk, then the Player must make at least d/5 queries to win with probability at least 2/3. Our analysis proceeds via an intuitive information-theoretic framework, which could have applications for showing query lower bounds for memoryconstrained algorithms in other optimization and learning settings.

2 RelatedWork

2.1 Memory-sample Tradeoffs for Learning

There is a recent line of work to understand learning under information constraints such as limited memory or communication constraints [Balcan et al., 2012; Duchi et al., 2013; Zhang et al., 2013; Garg et al., 2014; Shamir, 2014; Arjevani and Shamir, 2015; Steinhardt and Duchi, 2015; Steinhardt et al., 2016; Braverman et al., 2016; Dagan and Shamir, 2018; Dagan et al., 2019; Woodworth et al., 2021]. Most of these results obtain lower bounds for the regime when the available memory is less than that required to store a single datapoint (with the notable exception of [Dagan and Shamir, 2018] and [Dagan et al., 2019]). However the breakthrough paper [Raz, 2017] showed an exponential lower bound on the number of random examples needed for learning parities with memory as large as quadratic. Subsequent work extended and refined this result to multiple learning problems over finite fields [Moshkovitz and Moshkovitz, 2017; Beame et al., 2018; Moshkovitz and Moshkovitz, 2018; Kol et al., 2017; Raz, 2018; Garg et al., 2018].

Most related to our line of work is [Sharan et al., 2019], which considers the continuous valued learning/optimization problem of performing linear regression given access to randomly drawn examples from an isotropic Gaussian. They show that any sub-quadratic memory algorithm for the problem needs Ω(d log log(1/ϵ))) samples to find an ϵ-optimal solution for ϵ ≤ 1/dΩ(log d) , whereas in this regime an algorithm with memory ˜O(d2 ) can find an ϵ-optimal solution with only d examples. Since each example provides an unbiased estimate of the expected regression loss, this translates to a lower bound for convex optimization given access to a stochastic gradient oracle. However the upper bound of d examples is not a generic convex optimization algorithm/convergence rate but comes from the fact that the linear systems can be solved to the required accuracy using d examples.

There is also significant work on memory lower bounds for streaming algorithms, e.g. [Alon et al., 1999; Bar-Yossef et al., 2004; Clarkson and Woodruff, 2009; Dagan et al., 2019], where the setup is that the algorithm only gets a single-pass over a data stream.

2.2 Lower Bounds for Convex Optimization

Starting with the early work of [Nemirovski and Yudin, 1983], there is extensive literature on lower bounds for convex optimization. Some of the key results in this area include classical lower bounds for finding approximate minimizers of Lipschitz functions with access to a subgradient oracle [Nemirovski and Yudin, 1983; Nesterov, 2003; Braun et al., 2017], including recent progress on lower bounds for randomized algorithms [Woodworth and Srebro, 2016; Woodworth and Srebro, 2017; Simchowitz et al., 2018; Simchowitz, 2018; Braverman et al., 2020; Sun et al., 2021]. For more details, we refer the reader to surveys such as [Nesterov, 2003] and [Bubeck, 2014].

2.3 Memory-limited Optimization Algorithms

While the focus of this work is lower bounds, there is a long line of work on developing memory-efficient optimization algorithms, including various techniques that leverage second-order structure via first-order methods such as Limited-memory-BFGS [Nocedal, 1980; Liu and Nocedal, 1989] and the conjugate gradient (CG) method for solving linear systems [Hestenes and Stiefel, 1952] and various nonlinear extensions of CG [Fletcher and Reeves, 1964] and methods based on subsampling and sketching the Hessian [Pilanci and Wainwright, 2017; Xu et al., 2020].

3 Proof Strategy

We describe a broad family of optimization problems which may be sensitive to memory constraints (also see Fig. 2 for an overview). As suggested by the Orthogonal Vector Game (Definition 2), the primitive we leverage is that finding vectors orthogonal to the rows of a given matrix requires either large memory or many queries to observe the rows of the matrix. With that intuition in mind, let f : Rd → R be a convex function, let A ∈ Rn×d , let η be a scaling parameter, and let ρ be a shift parameter; define Ff,A,η,ρ(x) as the maximum of f (x) and η ∥Ax∥∞ - ρ:

Formula not decoded

We often drop the dependence of η and ρ and write Ff,A,η,ρ simply as Ff,A. Intuitively, for large enough scaling η and appropriate shift ρ, minimizing the function Ff,A(x) requires minimizing f(x) close to the null space of the matrix A. Any algorithm which uses memory Ω(nd) can learn and store A in O(d) queries so that all future queries are sufficiently orthogonal to A; thus this memory rich algorithm can achieve the information-theoretic lower bound for minimizing f(x) roughly constrained to the nullspace of A.

However, if A is a random matrix with sufficiently large entropy then A cannot be compressed to fewer than Ω(nd) bits. Thus, for n = Ω(d), an algorithm which uses only memory o(d2-δ ) bits for some constant 0 < δ ≤ 1 cannot remember all the information about A. Suppose the function f is such that in order to continue to observe new information about the function, it is insufficient to submit queries that belong to some small dimensional subspace of the null space of A. Then a memory constrained algorithm must re-learn enough information about A in order to find new vectors in the null space of A and make queries which return new information about f.

To show our lower bound, we take f in (3.1) to be the Nemirovski function:f(x) = max

Formula not decoded

where the vectors v1, . . . , vN are unit vectors drawn i.i.d. from the d dimensional scaled hypercube vi i.i.d. ∼ Unif (d-1/2Hd ) and we refer to them as "Nemirovski vectors". With this choice of f, the overall function Ff,A(x) has certain "memory-sensitive" properties. In particular, to reveal new Nemirovski vectors an algorithm cannot make queries which lie in a low-dimensional subspace. In addition, because of the ∥Ax∥∞ term in the definition of Ff,A(x), queries which reveal new Nemirovski vectors must also be sufficiently orthogonal to A. Together, these properties imply that a sequence of queries which reveals a new set of Nemirovski vectors must also be winning queries for the Orthogonal Vector Game (Definition 2). This allows us to leverage our information-theoretic memory-query tradeoffs for the Orthogonal Vector Game. We show that the algorithm must reveal a sufficiently large number of Nemirovski vectors to optimize Ff,A(x), therefore we can repeatedly apply the lower bound for the Orthogonal Vector Game to show our final lower bound.

Acknowledgments

AM and GV were supported by NSF Awards CCF-1704417, CCF-1813049, Frontier Award 1804222 and DOE award DESC0019205. AM was also supported by J. Duchi's Office of Naval Research Award YIP N00014-19-2288 and NSF Award HDR 1934578. VS was supported by NSF CAREER Award CCF-2239265 and a Amazon Research Award. AS was supported by a Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039, a PayPal research award, and a Sloan Research Fellowship.

Machine-readable versions of this paper, for tools and AI agents:

• Markdown — metadata, abstract, full text and references
• JSON — metadata and structured references
• BibTeX