Memory-Constrained Algorithms for Convex Optimization
Authors: Moise Blanchard
Junhui Zhang
Patrick Jaillet
Venue: NeurIPS 2023 poster (2023)
Keywords: Convex optimization
feasibility problem
first-order methods
memory constraints
cutting planes
oracle complexity

Abstract: We propose a family of recursive cutting-plane algorithms to solve feasibility problems with constrained memory, which can also be used for first-order convex optimization. Precisely, in order to find a point within a ball of radius $\epsilon$ with a separation oracle in dimension $d$---or to minimize $1$-Lipschitz convex functions to accuracy $\epsilon$ over the unit ball---our algorithms use $\mathcal O(\frac{d^2}{p}\ln \frac{1}{\epsilon})$ bits of memory, and make $\mathcal O((C\frac{d}{p}\ln \frac{1}{\epsilon})^p)$ oracle calls. The family is parametrized by $p\in[d]$ and provides an oracle-complexity/memory trade-off in the sub-polynomial regime $\ln\frac{1}{\epsilon}\gg\ln d$. While several works gave lower-bound trade-offs (impossibility results)---we explicit here their dependence with $\ln\frac{1}{\epsilon}$, showing that these also hold in any sub-polynomial regime---to the best of our knowledge this is the first class of algorithms that provides a positive trade-off between gradient descent and cutting-plane methods in any regime with $\epsilon\leq 1/\sqrt d$. The algorithms divide the $d$ variables into $p$ blocks and optimize over blocks sequentially, with approximate separation vectors constructed using a variant of Vaidya's method. In the regime $\epsilon \leq d^{-\Omega(d)}$, our algorithm with $p=d$ achieves the information-theoretic optimal memory usage and improves the oracle-complexity of gradient descent.

Memory-Constrained Algorithms for Convex Optimization
Moïse Blanchard Operations Research Center MIT
Junhui Zhang Operations Research Center MIT Cambridge, MA 02139 junhuiz@mit,
Cambridge, MA 02139 moisebêmit.. edu
Patrick Jaillet
Department of Electrical Engineering and Computer Science MIT
Cambridge, MA 02139 jaillet@mit edu
Abstract
We propose family of recursive cutting-plane algorithms to solve feasibility problems with constrained memory, which can also be used for first-order convex optimization. Precisely, in order to find point within a ball of radius c with a separation oracle in dimension d-or to minimize 1-Lipschitz convex functions to accuracy over the unit ball-our algorithms use O In !) bits of memory, and make O((C In ()) oracle calls, for some universal constant C' > 1. The family trade-off the sub-polynomial regime In >> In d. While several works gave lower-bound trade-off's (impossibility results) 33 -e explicit here their dependence with In 7 showing that these also hold in any sub- nub-polynomial regime- to the best of our knowledge this is the first class of algorithms that provides positive trade-off between gradient descent and cutting-plane methods in any regime with e S /d. The algorithms divide the d variables into p blocks and optimize over blocks sequentially, with approximate separation vectors constructed using variant of Vaidya's 's method. In the regime < d- our algorithm with p d achieves the information-theoreet optimal memory usage and improves the oracle-complexity of gradient descent.
is parametrized by p E [d] and provides an oracle-complexxtyymeeees
Introduction
Optimization algorithms are ubiquitous in machine learning, from solving simple regressions training neural networks. Their essential roles have motivated numerous studies on their efficiencies, which are usually analyzed through the lens of oracle-complexity: given oracle (such function value, or subgradient oracle), how many calls to the oracle are needed for an algorithm to output an approximate optimal solution? (34). However, ever-growing problem sizes have shown an inadequacy in considering only the oracle-complexity and have motivated the study of the trade-off' between oracle-complexity and other resources such as memory [52 31 and communication 25
45
33
53
51 50].
In this work, we study the oracle-com maalle-cmpleexitymemmor trade-off for first-order non-smooth convex optimization, and the closely related feasibility problem, with a focus on developing memory efficient
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(deterministic) algorithms. Since [52] formally posed as open problem the question of characterizing this trade-off, there have been exciting results showing what is impossible: for convex optimization in
R. (31) shows that any randomized algorithm with d1.25-6 bits of memory needs at least () (2(13+46/3 queries, and this has later been improved for deterministic algorithms to d'-6 bits of memory or (d(++//)) queries by (5); in addition (5) shows that for the feasibility problem with separation oracle, any algorithm which uses d2-6 bits of memory needs least (dd queries.
Despite these recent results on the lower bounds, all known first-order convex optimization algorithms that output an e-suboptimal point fall into two categories: those that have quadratic memory in the dimension d but can potentially achieve the optimal (dd In 4) query complexity, as represented by the center-of-mas method, and those that have O query complexity but only need the optimal On 2) bits of memory, represented by the classical gradient descent (52) In addition, the mbeve-mentioned memory bounds apply only between queries, and in particular the center-of-mas method (2) is allowed to use infinite memory during computations.
We propose a family of memory-constrainee algorithms for the stronger fcasibility problem in which one aims to find a point within set Q containing a ball of radius e, with access to separation oracle. In particular, this can be used for convex optimization since the subgradient information provides a separation vector. Our algorithms use O d" In !) bits of memory (including during computations) and O(C) á by the user. Intuitively, in the context of convex optimization, the algorithms are based on the idea that for any function fax, y) convex in the pair (ær, y). the partial minimum miny f [ax, y) as a function of x: is still convex and, using a variant of Vaidya's method proposed in (27]. our algorithm can approximate subgradients for that function miny fax y). thereby turning an optimization problem with variables (a: y) to one with just æ. This idea, applied recursively with the variables divided into p blocks, gives our family of algorithms and the above-mentioned memory and query complexity. The main algorithmic contribution is in how we design the recursive dimension reduction procedure: technical step of the design and analysis is to ensure that the necessary precision for recursive computations can be achieved using low memory. Last, our algorithms account for memory usage throughout computations, as opposed to simply between calls to the gradient oracle, which was the traditional approach in the literature.
p In ))² queries for some universal constant C 2 1, and a parameter p E [d] that can be chosen
When p 1, our algorithm is a conttry- version of Vaidya's method 48 improves over the center-of-mass (52) method by a factor of In in terms of memory while having optimal oracle-complexity. The improvements provided by our algorithms are more significant in regimes when e very small in the dimension increasing the parameter p can further reduce the memory usage of Vaidya's method (p 1) by factor In // In d, while still improving over the oracle-complexity of gradient descent. In particular, in a regime In poly(In d), these memory improvements are only in terms of In d factors. However, in sub-polynomial regimes with potentially In d' for some constant e > O, these provide polynomial improvements to the memory of standard cutting-plane methods.
and
As summary, this paper makes the following contributions.
Our class of algorithms provides trade-off between memory-usage and oracle-complexity whenever In ! >> In d. Further, taking p = improves the memory-usage from center-of- mass (2 by a factor In c. while preserving the optimal oracle-complexity.
For In 1 2 2(d In d). our algorithm with p = d is the first known algorithm that outperforms gradient descent in terms of the oracle-complexity. but still maintains the optimal O(d ) memory usage.
We show how to obtain a In ! dependence in the known lower-bound trade-offs 31 5
confirming that the onede-complexity/mmerrr trade-off is necessary for any regime e S Vd
2 Setup and Preliminaries
In this section, we precise the formal setup for our results. We follow the framework introduced in 52 to define the memory constraint on algorithms with access to oracle O : S - R which

---

takes as input a query E S and outputs response (q) E R. Here, the algorithm is constrained to update an internal M-bit memory between queries the oracle.
Definition 2.1 (M-bit memory- constraied algorithm [52] 51. O be oracle. An M-bit memory- conatro-cnnstraineed algorithm is specified by a query fumction Viueryy : {0, 1] - and an update function Vuudate : {0, 1 x S X + {0, 10M The algorithm starts with the memory state Memory, = 0 and iteratively makes queries to the oracle. At iteration L, it makes the query q: Vywery (MeerryMMeorrmme to the oracle, receives the response = Ogg)) then updates its memory Memory, = d'uddote (Memoryy-119t. (6, Tt)-
The algorithm can stop at any iteration and the last query is its final output. Importantly this model does not enforce constraints on the memory usage during the computation of Papdate and Veuery This is ensured in the stronger notion of a memory conssrriidd algorithm with computations. These are precisely algorithms that have constrained memory including for computations, with the only specificity that they need decoder function é make queries to the oracle from their bit memory, and a discretization function 1o to write a discretized response into the algorithm's 's memory.
Definition 2.2 (M-bit memory-constraime constrained algorithm with computations). Let O : S + R be an oracle. We suppose that we are given a decoding function & {0, + S and a discretization function // x - {0.1}* such that (r, n) E {0, 13 for all E R. An M-bit memory- constrained algorithm with computations is only allowed to use an M-bit memory in {0. } even during computations. The algorithm has three special memory placements Q, N, R. Say the contents of Q and N are q and n. respectively. To make query. R must contain at least n bits. The algorithm submits q to the encoder which then submits the query b(q) to the orucle. I = (((()) is the oracle response, the discretization function then writes (b(r, n) in the placement R.
Feasibility problem. In this problem, the goal is to find a point æ E Q, where Q C Ca := [-1, 1] is a convex set. We choose the cube [-1, 1] as prior bound for convenience in our later algorithms, but the choice of norm for this prior ball can be arbitrary and does not affect our results. The algorithm has access to a separation oracle Os Ca + {Success} U Rd, such that for a query x E Rd either returns Success æ E Q. or a separating hyperplane g E Rd i.c., such that g x < g x' for any x' Q. We suppose that the separating hyperplanes are normalized, ligllz = 1. An algorithm solves the feasibility problem with accuracy e if the algorithm is successful for any feasibility problem such that Q contains c-ball Bz(x" c) for x Ca.
As an important remark, this formulation asks that the separation oracle is consistent over time: when queried at the exact same point æ, the oracle always returns the same separation vector. In this context, we can use the natural decoding function & which takes as input d sequences of bits and outputs the vector with coordinates given by the sequences interpreted in base 2. Similarly, the natural discretization function v takes as input the separation hyperplane g and outputs a discretized version up to the desired accuracy. From now, we can omit these implementation details and consider that the algorithm can query the oracle for discretized queries x, up to specified rounding errors.
Remark 2.1. An algorithm for the feasibility problem with accuracy c/ c/(2/)) can be used for first- order convex optimization. Suppose one aims to minimize a 1-Lipschitz convex function f over the unit ball, and outpul an e-suboptimal solution, i.e., find a point x: such that f(x)) S mi [(y) +e. A separation oracle for Q = {x f(x) S min B.(01) f(y) + c} is given at a query x by the subgradient information from the first- oracle: 0f(())
for
[[][2)]] Its computation can also be carried out memory-efficiente up to rounding errors since if (1)) S </(2Vd), the algorithm can return and already has the guarantee that x an c-suboptimal solution (Ca has diameter 2 /v))) Notice that because f is 1-Lipschitz, Q contains a bull of radius e/ e/(2Vd) (the factor 1/(2/d) is due to potential boundary issues). Hence, it suffices to run the algorithm for the feasibility problem while keeping in memory the queried point with best function value.
2.1 Known trade-offs between oracle-complexity and memory
Known lower-bound trade-off's All known lower bounds apply to the more general class of memory-constraimg algorithms without computational constraints given in Definition 2.1 34 first showed that OdInn ?) queries are needed for solving convex optimization to ensure that one finds an e-suboptimal solution. Further, O(d !) bits of memory are needed even just to output solution in
3

---

the unit ball with accuracy (52). These historical lower bounds apply in particular to the feasibility problem and are represented in the pictures of Fig. aas the dashed pink region.
More recently. (31] showed that achieving both optimal oracle-comllextty and optimal memory is impossible for convex optimization. They show that possibly randomized algorithm with d'-22-6 bits of memory makes at least (0(14466/3 queries. This result was extended for deterministic algorithms in [5) which shows that deterministic algorithm with d' bits of memory makes (d/+//3) queries. For the feasibility problem, they give an improved trade-off:: any deterministic algorithm with d2-6 bits of memory makes (0)d"=6) queries. These trade-offs are represented in the left picture of Fig. Tas as the pink, red, and purple solid region, respectively. Using a clever and more careful analysis. 11 showed that similar lower bounds can be carried out for deterministic algorithms as well.
Known upper-bound trade-offs. Prior to this work, to the best of our knowledge only two algorithms were known in the achieve the optimal oracle-complexity O In 4) but use quadratic memory. The memory-constraine
landscape. First, cutting- algorithms
(MC) center-of-min -asss method analyzed in [52] uses in particular Od In² () memory. Instead, if one uses Vaidya's 's method which only needs to store ((d) cuts instead of O(d 2), we show that one can achieve (d In 4) memory. These algorithms only use the separation oracle and hence apply to both convex optimization and the feasibility problem. On the other hand, the
gradient descent for convex optimization (52) uses the optimal Odd In ?) memory but makes O iterations. While the analysis in (52) is only carried for convex optimization, we can give a modified proof showing that gradient descent can also be used for the feasibility problem.
2.2 Other related works
Vaidya's method [48 38 and the variant [27] that we use in our algorithms, belong to the family of cutting- -lann methods. Perhaps the simplest example of an algorithm in this family the center-of-mass. method, which achieves the optimal Od 2) oracle-complexity but is computa- tionally intractable, and the only known random walk-based implementation (4) has computational complexity (dd In )). Another example is the ellipsoid method, which has suboptimal Odd In !) query complexity, but has improved computational complexity Old In :). [8] pointed out that Vaidya's method achieves the best of both worlds by sharing the Od 2) optimal query complexity of the center-of-mass, and achieving a computational complexity of (d In ! In a major breakthrough, this computational complexity was improved to O(d In !) in (2)). then to Odd In }) in (22). We refer to 8 27 22
for more detailed comparisons of these algorithms.
Another popular convex optimization algorithm that requires quadratic memory is the Broyden- Fletcher- Conn----G-ababbbaeae Shanno (BFGS) algorithm [43 7 20 21J. which stores an approximated inverse Hessian matrix as gradient preconditioner. Several works aimed to reduce the memory usage of BFGS; in particular, the limited memory BFGS (L-BFGS) stores few vectors instead of the entire approximated inverse Hessian matrix [3|,00] 330. However, it is still an open question whether even the
original BFGS converges for non-smooth convex objectives
(29
Lying at the other extreme of the oracle-commlexity/nennno achieves the optimal memory usage but requires significantly more queries than center-of-mass. or Vaidya's method in the regime E S Jta There is a rich literature of works aiming to speed up gradient descent, such as the optimized gradient method 117 [6]. Nesterov's Acceleration (35) the triple momentum method [41), geometric descent (9). quadratic averaging [18). the information- theoretic exact method [46]. or Sttee----tlleSeeee method (23). Interested readers can find a comprehensive survey on acceleration methods in [12). However, these acceleration methods usually require additional smoothness or strong convexity assumptions (or both) on the objective function, due the known S2( 3 query lower bound in the lcrge-scale regime c 2 va for any first order method where the query points lie in the span of the subgradients of previous query points (36).
trade-off is gradient descent, which
Besides accelerating gradient descent, researchers have investigated more efficient ways to leverage
subgradients obtained in previous iterations. Of interest are bundle methods [3] 24 28 that have
ww < 2.373 is the exponent of matrix multiplication

---

found a wide range of applications 447 26]. In their simplest form, they minimize the sum of the maximum of linear lower bounds constructed using past oracle queries, and a regularization term penalizing the distance from the current iteration variable. Although the theoretical convergence rate of the bundle method the same as that of gradient descent, practice, bundle methods can benefit from previous information and substantially outperform gradient descent (3]
Our works are focused on high-accuracy regimes, when the accuracy sub-polynomial. We note that for their lower-bound result on randomized algorithms, (TT] also required sub-polynomial accuracies, which raises the question whether this a general phenomenon for the study of memory- algorithms in convex optimization. This also relates our work to the study of low- oow-dimensional problems-or or even constant dimension-whiie which has been investigated in the literature [49 10).
Last, the increasing size of optimization problems has also motivated the development of communicatonn-effiieet optimization algorithms in distributed settings such as [25 40 42 45
33 53 51 50). Moreover, recent works have explored the trade-off between sample complexity and memory/communicatioo complexity for learning problems under the streaming model, with notable contributions including [6.
13 14
32)
3
Main results
We first check that the memory-constraing gradient descent method solves feasibility problems. This was known for convex optimization [52] and the same algorithm with a modified proof gives the following result. For completeness, the proof is given in Appendix
Proposition 3.1. The memory-constrainee gradient descent algorithm solves the feasibility problem with accuracy e S Va using O(d In 4) bits of memory and O separation oracle calls.
Our main contribution a class of algorithms based on Vaidya's cutting-plane method that provide a query- complexit memory tradeoff for optimization in R More precisely, we show the following, where w < 2.373 the exponent of matrix multiplication, such that multiplying two n x n matrices runs in On))) time.
Theorem 3.2. For any 1 SSpp S d, there is a deterministic first-order algorithm that solves the feasibility problem in dimension for accuracy S Ja using O Oi In )) bits of memory (includ- ing during computations), with ( p In L)P) calls to the separation oracle, and computational complexity
where C 2 1 is universal constant.
For simplicity, in Section we describe algorithms that achieve this trade-off without computation concerns (Definition 2.1). which already provide the main elements of our method. The proof
of oracle-complexity and memory usage is given in Appendix A In Appendix B we consider
computational constraints and give corresponding algorithms using the cutting-plane method of [27].
To better understand the implications of Theorem 3.2. is useful to compare the provided class of algorithms to the two algorithms known in the oracle-comee cowoee--oomleext/memmmooo tradeoff landscape: the memory--costtrained center-of-mass method and the memory-constraiee constrained gradient descent (52).
For p = 1, our resulting procedure, which is essentially a memory-constraiee has optimal oracle-complexity O(dIn 2) and uses (dd In 2) bits of memory. This improves by In factor the memory usage of the center-of (dd In? !) memory and had the same optimal oracle-complexity.
Vaidya's algorithm,
algorithm provided in (22 which used
Next. we recall that the conttry-onstrained gradient descent method used the optimal number Od 1) bits of memory (including for computations), and sub-optimal O(})) oracle-complexity While the memory of our algorithms decreases with their oracle-complexity is exponential in This significantly restricts the values of p for which the cropleccmpyyextt improved over that of gradient descent. The range of application of Theorem is given in the next result, where V and A represent maximum and minimum respectively.
Corollary 3.1. The algorithms given in Theorem 3.2 effectively provide tradeoff O la Precisely, this provides a tradeoff between
Ind Ad).
* using Old In () memory with optimal Ond 2) oracle-compleste and
5

---

Oracle complexity
Regime Ind <
Regime 52(d
In
< dlnd
In
MC-GD
1/c²
1/e²
lu
In
/4/3
In
MC-Vaidya
dln
MC-Center dln of Mass (22)
dln
1
4//4 Ind
In
d'ind
Iu
d !
I dl in?
d In2 d
d
Memory (bits)
Figure 1: Trade-offs between available memory and first-order complexxyy for the feasibility problem over the unit ball. MCC-Memorycoonstrangge corresponds to the regime >> d-Q(d) and 6 S 1/poly(d) and the right picture represents the regime S d-)(d) For both figures, the dashed pink "L." (resp. green inverted "L") region corresponds historical lower (resp. upper) bounds for randomized algorithms. The solid pink (resp. red) lower bound tradeoff is due to [3T] (resp. (5) for randomized algorithms (resp. deterministic algorithms). The purple region and deterministic algorithms (5). All these lower-bound trade-off's are represented with their in
GD-Gradient Descent. The left picture
lower bound tradeoff for the feasibility problem for accuracy e
dependence (Theorem 3.3 We use nenttry-co Vaidya's method to gain factor In 1 in memory compared to memory-constee constriindd center-of-mass (52). which gives the light green region, and a class of algorithms represented in dark green, that allows trading query-complexity for an extra In / In factor saved in memory (Theorem 3.2). The dark green dashed region in the left figure emphasizes that the area covered by our class of algorithms depends highly the regime for the accuracy E: the resulting improvement in memory is more significant as e is smaller. In the regime when S ddd(d) (right figure), our class of algorithms improves over the oracle-complexity of gradient descent while keeping the optimal memory Od 4).
ussing (dd In d )) memory with O A (C'nn !)d) oracle-complexty.
Importantly, for 6 panay taking p d yields an algorithm that uses the optimal memory Oddnn' !) and has an improved query complexity over gradient descent. In this regime of small (virtualfy constant) dimension, for the same memory usage, gradient descent has a query complexity that is polynomial in ( while our algorithm has poly-logarithmic dependence in e, Os(In !), where O₂ hides an exponential constant in It remains open whether this In dependence in the oracle- complexity is necessary. To the best of our knowledge, this is the first example of an algorithm that improves over gradient descent while keeping its optimal memory usage in any regime where e S V still provides constraine center-of-nee -aas in the standard regime < [2 Fig. depicts the trade-offs in the two regimes mentioned earlier.
While this improvement holds only in the exponential regime S ब Theorem 3.2 still a non-trivial trade-off whenever In 1 > In d, and improves over the known
Last, we note that the lower-bound trade-off's presented in 31 5) do not show dependence in the accuracy e. Especially in the regime when In _ >> dn this yields sub-optimal lower bounds (in fact even in the regime e 1/poly(d), our more careful analysis improves the lower bound on the memory by In d factor). We show with simple arguments that one can extend their results to include a In factor for both memory and query complexity. Fig. presented these improved lower bounds.

---

Theorem 3.3. For e S 1/poty(d) and any ò E [0, 1] (the notation S2 hides In (1) d factors),
any (randomized) algorithm guaranteed to minimize 1-Lipschitz convex functions over the unit ball with accuracy uses d5/1-6 In bits of memory or makes (1)++18/3 In } queries,
2. any deterministic algorithm guaranteed to minimize 1-Lipschitz convex functions over the unit ball with accuracy uses d In c. bits of memory or makes (ddd In queries,
3. any deterministic algorithm guaranteed to solve the feasibility problem over the unit ball with uccuracy uses d2-6 In bits of memory or makes (2(d++6 In queries.
The proof is given in Appendix C and the arguments therein could readily used to exhibit the In dependence of potential future works improving over these lower bounds trade-offs.
Sketch of proof. At a high level, 31 use barrier term | where A has O(d) rows: if an algorithm does not have enough memory, A cannot be fully stored which in turn incurs a sub-optimal cracle-complexity. To achieve a In : improvement in memory (Appendix C.I). we modify the sampling of rows of A, from uniform on vertices of the hypercube to uniform in an c-net. The proof can then be adapted accordingly. Last, one can improve the oracle-complexity by In / factor (Appendix C.2 using a standard rescaling argument (34).
4 Memory-constrained feasibility problem without computation
In this section, we present a class of algorithms that are memory-constrained according to Defini- tion 2. and achieve the desired memory and oralle-complexity bounds. We emphasize that the memory constraint is only applied between calls to the oracle and as a result, the algorithm is allowed infinite computation memory and computation power between calls the oracle.
We start by defining discretization functions that will be used in our algorithms. For E 0 and E [-,, we pose Discretize (1r, <) sign(a:) [L/a//EJ. Next, we define the discretization Discretize, for general dimensions d 2 1. For any x E and & > O,
Discretize,(zr, E) = (Discretizei (o1.e/Va)
Discretize; (zd.)
4.1 Memory-constrained Vaidya's method
Our algorithm recursively uses Vaidya's cutting-plane method 48 and subsequent works expanding on this method. We briefly describe the method. Given a polyhedron P {x Ax 2 b). we define s((rr) = a. x - b, and S_ = diag(s: (() (x:), i E [d)). We will also use the shorthand A, = S A. The volumetric barrier is defined as
VA,((x) = In det (A_ Ag).
2
At each step. Vaidya's method queries the volumetric center of the polyhedron, which is the point minimizing the volumetric barrier. For convenience, we denote by VolumetricCenter this function, i.e, for any A E Rmmxd and b E Rd defining non-empty polyhedron P = {x: Ax 2 b).
VolumetricCenterr( A, b) = arg min Am VA,6(z).
When the polyhedron is unbounded, can for instance take VolumetricCenterrA. method makes use of leverage scores for each constraint i of the polyhedron, defined as a; " Ji.. where H = A Ag- We are now ready to define the update procedure for the polyhedron considered by Vaidya's volumetric method. We denote by P, the polyhedron stored in memory after making t queries. The method keeps in memory the constraints defining the current polyhedron and the iteration index & when these constraints were added, which will be necessary for our next procedures. Hence, the polyhedron will be stored in the form Pa = {(k,, a; b;), E [m]]. and the associated constraints are given via (a: Ax > b) where AT [ai...., am) and b [b,,... bm.. By abuse of notation, we will write VolumetricCenter/e the polyhedron VolumetricCenter b) where A and b define the constraints stored in P.
O. Vaidya's
for the volumetric center of
7

---

Initially, the polyhedron is simply Cd, these constraints are given -1 index for convenience, and they will not play role in the next steps. At each iteration, if the constraint E [m] with minimum leverage score o, falls below given threshold mins it is removed from the polyhedron. Otherwise, we query the volumetric center of the current polyhedron and add the separation hyperplane as
constraint to the polyhedron. We bound the number of iterations of the procedure by
T d) = cc.d [1.4 2lnd 2n 1/0min)) )
where mmin and c are parameters that will be fixed shortly. Instead of making a call directly to the oracle Og, instead suppose that one has access an oracle O Ia IR where Ia (Z. (R2xIId+11) has exactly the shape of the memory storing the information from the polyhedron. This form of oracle is used in our recursive calls to Vaidya's method. For example, such an oracle can simply be Last, in our recursive method, we will not assume that oracle responses are normalized. As a result, we specify that if the norm of the response is too small, we can stop the algorithm. We assume however that the oracle already returns discretized vectors, which will be ensured in the following procedures. The cutting-plas With an appropriate choice of parameters, this procedure finds an approximate
O:P P E Za + VecVolumtrriCeeteerrr
algorithm is formally described
in Algorithm I solution of feasibility problems. We base the constants from (
Input: Tu - Rd, 6, { E (0,1) Let mar = (b, d) and initialize Po : (1-1((1,,, 11), (-1, es; -1); i [d]
for 1 o...., , do
if (x: Aa: 2 b) =0 then return Pa:
min 0, < Omin then
Pi+1 Pe \ ((.)),;b;))) where arg minge|m] 0i & Ca then Pe+1 = Peu (ou(((1))) ((-1, sign(ww,),, -1]} where j E [d] has ( >
else if w = VolumetricCenterr/
else
g O(P)) and b = a _
where w = VolumetricCenterr()
10
P.+1 = P, [(,, (,, (b)
if | < then return P++1:
end
13 return Pr Pmmantl
Algorithm 1: Memory-constrained Vaidya's volumetric method
0.001 Re 715. Let 8, E (0, 1) and O : Ia - Rd. Write P (Kk, ai, bi), E [m]] as the output of Algorithm run with O, and &. Then,
Lemma 4.1. Fix amin = 0.04 and c
m
min 2,20, 1E(m], Exemm] Au=1
max
A1aa y b.) max min (a. b,) S 8.
DECA
mcCa 4E(m)
From now, we use the parameters Omin = 0.04 and c 1/0.0014 as in Lemma 4.1 Since the memory of both Vaidya's method and center-of-mas consists primarily the constraints, we recall an important feature of Vaidya's method that the number of constraints at any time is Od).
Lemma 4.2 (148) I ). At any time while running Algorithm 7 the number of constraints of the current polyhedron is at most
Omin
4.2 A recursive algorithm
We write Cm+n = C x C₂ and aim to apply Vaidya's method to the first m coordinates. To do so, we need approximate a separation oracle on these m coordinates only, which corresponds giving separation hyperplanes with small values for the last n coordinates. This can be achieved using the following auxiliary linear program. For P In. define
m
min A:20, rE[m], DEC, Eiejm] ,,=1
max
Ma y bb). m = IP]
(Panx (P))((P)
8

---

where as before, A and b define the constraints stored in P. The procedure to obtain an approximate separation oracle on the first coordinates C, is given in Algorithm 2 and using Lemma 4.] we can show that this procedure provides approximate separation vectors for the first coordinates.
Input: 5, &. Og In + R and O2 Zn - R
Run Algorithm with 0, and Oy obtain polyhedron P
Solve Paux (P*) to get solution X
1P*) and X Discretize( X* 4 Initialize Po = [(-1((1, -1), (-1 (-1- ex -1), i [d] and u = 0 E R
Store k- = (k; E [m/] where
for t 0, 1, ..... max; k; do
if k for some E [m]] then
9, (P().)
u < Discretizem + ()
Update P. to get Pi+1 as in Algorithm
end
11 return u
Algorithm 2: ApprosSeprationVeecorr.. 0ÿ)
The next step involves using this approximation recursively. We write d= Ei= k; and interpret Ca Ck. .... x Cr.- In particular, for æ: E Ca. write (x1,.... Fpp) where E Cs. for i [p]. Applying Algorithm recuursively, we can obtain an approximate separation oracle for the first coordinates Ck X x Ch.. However, storing such separation vectors would be memory-expensive e.g., for = p. that would correspond to storing the separation hyperplanes from the oracle Os directly. Instead, given E [t], Algorithm 3 recursively computes the æ; component of approximate separation oracle for the first variables .1)...,...). via the procedure ApproxOracle((..))
S SE.siiiis... p() E Is, for E [i]. Os C. Rd
if's then VolumetricCenter/ Ar, b,) where (Ar, b,) defines the constraints stored in ppt) for [p]
2r
(91..... 9p) Oz(11..... xp)
return Discretizex, (g).C)
5 end
Define O2 Ix.41 + R& ApproxOractes,s.o, 1,j, P(1) ...... p(.).
7 Define O, Ik, + R++ as ApproxOracles.. (i + 1, p(1),...,(((,
return ApprosSeparationVector, (Oz,
(O.,onn,eeettr......000 0g)
Algorithm 3: ApproxOracles,.o0. ((1),((), p())
We then ApproxOracleg...0 1,, to solve the original problem with the memory- constrained Vaidya's method. In Appendix A, we show that taking ó = 17 and & 32d572 the desired oralle-complexity and memory usage. The final algorithm is given in Algorithm
Ameac achieves
Input: E. and Os C. + Rd a separation oracle Check Throughout the algorithm, if Og returned Success query return Run Algorithm with parameters and & and oracle ApproxOracle 11, Algorithm 4: Memory-constraine algorithm for convex optimization
A geometric illustration of the recursive step. In Figure 2 give 2-dimensional feasibility problem with target p* (p",pā) and two blocks (i.e. p 2) as an illustration of our recursive approach (Algorithm 2 to construct an approximate separating hyperplane for "reduced" problem.
Suppose a step of the Algorithm the current value of the x1 coordinate c. aim to find an p and Vaidya) to find two separating hyperplanes (the two blue hyperplanes). Lemma 4.1 then guarantees the existence of convex combination of the 2 blue hyperplanes the
approximate separating hyperplane between (i.e. the
Algorithm m2 first runs Algorithm ]

---

312
31 = Pi
21 =C
Figure 2: Intuition for the recursive procedure in Algorithm Using the separation hyperplanes (blue) found by Algorithm [ i.e., the memory-cone memory-constrained Vaidya, it constructs approximate separation hyperplane (red) between and the target æ = Pi.
red hyperplane- which approximately parallel to the 22 r2-axxi and thus can serve as an approximate separating hyperplane between pi and
Sketch of proof. At the high level, the algorithm recursively runs Vaidya's method Algorithm| [ for each level of computation E [p]. Since each run of Algorithm requires O In 2) queries, the total number of calls to the oracle, which is exponential in the number of levels, ( In ())
As for the memory usage, the algorithm mainly needs to keep in memory the constraints defining the polyhedrons at each level i [p]. From Lemma 4.2 each polyhedron only requires (e)) constraints that each require ( d In +) bits of memory. Hence, the total memory needed O de }). The main difficulty lies in showing that the algorithm successful. To do so, we need to show that the precision in the successive approximated separation oracles Algorithm 2 is sufficient. To avoid exponential dependence of the approximation error in p-which would be prohibitive for the memory usage of method-ead run of Vaidya's method Algorithm iis run for more iterations than the precision of the separation vectors would classically allow. To give intuition, if the separation oracle came from a convex optimization subgradient oracle for function f. the iterates at level do converge the true "minimizer" of ming, (I ................................ Z.). where (.) milg,.1- .....p............. f(, E ... Tp). but instead converge to a close enough point while still providing meaningful approximate subgradients at the higher level i 1 (in Algorithm 2
Discussion and Conclusion
To the best of our knowledge, this work is the first to provide some positive trade-off between oracle-complexity and memory-usage for convex optimization or the feasibility problem, as opposed to lower-bound impossibility results [3 [. Our trade-off's are more significant in a high accuracy regime: when In & se d', for e > 0 our trade-off's are polynomial, while the improvements when In poly(In d) are only in d factors. A natural open direction (52) is whether there exist We also show that the exponential regime In In d). gradient descent is not Pareto-optimal. Instead, one can keep the optimal memory and decrease the dependence in of the oracle-complexity from 1 to (In !)dd The question of whether the exponential dependence in necessary left open. Last, our algorithms rely on the consistency of the oracle, which allows re-computations. While this is classical assumption, gradient descent and classical cutting-plane methods do not need it; removing this assumption could be interesting research direction (potentially, this could also yield stronger lower bounds).
algorithms with polynomial trade-offs in that
10

---

Acknowledgments and Disclosure of Funding
This work was partly funded ONR grant N00014-18-1-2122, AFOSR grant FA9550-19-1-0220 and AFOSR grant FA9550-23-1-0118..
References
[1] Kurt M Anstreicher. "On Vaidya's volumetric cutting plane method for convex programming". In: Mathematics of Operations Research 22.1 (1997), pp. 63-89.
[2] Kurt Anstreicher. "Towards a practical volumetric cutting plane method convex pro- gramming". In: SIAM Journal on Optimization 9.1 (1998), pp. 190-206.
[3] Aharon Ben-Tal and Arkadi Nemirovski. "Non-euclidean restricted memory level method for large-scale convex optimization". In: Mathematical Programming 102.3 (Jan. 2005), pp. 407- 456.
[4] Dimitris Bertsimas and Santosh Vempala. "Solving convex programs by random walks". In: Journal of the ACM (JACM) 51.4 (2004), pp. 540-556.
[5] Moise Blanchard, Junhui Zhang, and Patrick Jaillet. "Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of- is Pareto-Optimal". In: arXiv preprint wwxXiv2302.04900 (2023).
[6] Mark Braverman al. "Communication Lower Bounds for Statistical Estimation Problems via Distributed Data Processing Inequality". In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. STOC '16. Cambridge, MA, USA: Association for Computing Machinery, 2016, pp. 1011-1020.
[7] C. G. Broyden. "The Convergence of Class of Double-rank Minimization Algorithms 1. General Considerations". In: IMA Journal of Applied Mathematics 6.1 (Mar. 1970), pp. 76-90. [8] Sébastien Bubeck. "Convex Optimization: Algorithms and Complexity". In: Foundations and Trends0 in Machine Learning 8.3-4 (2015), pp. 231-357.
[9] Sébastien Bubeck, Yin Tat Lee, and Mohit Singh. A geometric alternative to Nesterov's accelerated gradient descent. 2015.
[10] Sébastien Bubeck and Dan Mikulincer. "How trap gradient flow". In: Conference Learning Theory. PMLR. 2020, pp. 940-960.
[11] Xi Chen and Binghui Peng. "Memory-Quee Querryyy--uuyuuoe Tradeoffs for Randomized Convex Optimization". In: arXiv preprini arXiv::306. /2534 (2023).
[12] Alexandre d' Aspremont, Damien Scieur, and Adrien Taylor. "Acceleration Methods". In: Foundations and Trendy@ in Optimization 5.1-2 (2021), pp. 1-245.
[13] Yuval Dagan, Gil Kur, and Ohad Shamir. "Space lower bounds for linear prediction in the streaming model".. In: Proceedings of the Thirty-Second Conference on Learning Theory. Ed. by Alina Beygelzimer and Daniel Hsu. Vol. 99. Proceedings of Machine Learning Research.
PMLR, 25-28 Jun 2019, pp. 929-954.
[14] Yuval Dagan and Ohad Shamir. "Detecting Correlations with Little Memory and Communica- tion". In: Proceedings of the 31st Conference On Learning Theory. Ed. by Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. Vol. 75. Proceedings of Machine Learning Research. PMLR, June 2018, pp. 1145-1998.
[15] James Demmel, Ioana Dumitriu, and Olga Holtz. "Fast linear algebra is stable". In: Numerische Mathematik 108.1 (2007). pp. 59-91.
[16] Kim Donghwan and Jeffrey Fessler. "Optimized first-order methods for smooth convex mini- mization" In: Mathematical Programming 159 (June 2014).
[17] Yoel Drori and Mare Teboulle. "Performance of first-order methods for smooth convex min- imization: a novel approach". In: Mathematical Programming 145.1 (June 2014), pp. 451- 482.
[18] Dmitriy Drusvyatskiy, Maryam Fazel, and Scott Roy. "An Optimal First Order Method Based on Optimal Quadratic Averaging". In: SIAM Journal on Optimization 28.1 (2018), pp. 251-
271.
[19] Uriel Feige and Gideon Schechtman. "On the optimality of the random hyperplane rounding technique for MAX CUT". In: Random Structures & Algorithms 20.3 (2002), pp. 403 403-440.

---

[20] R. Fletcher. "A new approach to variable metric algorithms". In: The Computer Journal 13.3 (Jan. 1970), pp. 317-322.
[21]
Donald Goldfarb. "A Family of Variable-Metric Methods Derived by Variational Means". In: Mathematics of Computation 24.109 (1970), pp. 23-26.
[22] Haotian Jiang et al. "An Improved Cutting Plane Method for Convex Optimization, Convex- Concave Games, and Its Applications". In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020. Chicago, IL, USA: Association for Com- puting Machinery, 2020, pp. 944-953.
[23] Jonathan Kelner et al. "Big-Step-Litte-Ster Efficient Gradient Methods for Objectives with Multiple Scales". In: Proceedings of Thirty Fifth Conference on Learning Theory. Ed. by Po-Ling Loh and Maxim Raginsky. Vol. 178. Proceedings of Machine Learning Research. PMLR, Feb. 2022. pp. 2431-2540.
[24] Guanghui Lan. "Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization". In: Mathematical Programming 149.1 (Feb. 2015), pp. 1-45. algorithms for decen- tralized and stochastic optimization". In: Mathematical Programming 180.1 (Mar. 2020), pp. 237-284.
[25] Guanghui Lan, Soomin Lee, and Zhou. "Commmnicction-
[26] Quoe Le, Alex Smola, and S.V.N. Vishwanathan. "Bundle Methods for Machine Learning.. In: Advances in Neural Information Processing Systems. Ed. by J. Platt al. Vol. 20. Curran Associates, Inc., 2007.
[27] Yin Tat Lee, Aaron Sidford, and Sam Chiu bai Wong. "A faster cutting plane method and its implications for combinatorial and convex optimization". In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 1049-1065.
[28] Claude Lemaréchal, Arkadi Nemirovski, and Yurüi Nesterov. "New variants of bundle methods".
In: Mathematical Programming 69.1 (July 1995), pp. 111-147.
[29] Adrian S. Lewis and Michael L. Overton. "Nonsmooth optimization via quasi-Newton meth- ods". In: Mathematical Programmiing 141.1 (Oct. 2013), pp. 135-163.
[30] Dong C. Liu and Jorge Nocedal. "On the limited memory BFGS method for large scale optimization". In: Mathematical P Programming 45.1 (Aug. 1989), pp. 503-528.
[31] Annie Marsden al. "Efficient convex optimization requires superlinear memory". In: Confer- ence on Learning Theory. PMLR. 2022, pp. 2390-2430.
[32] Dana Moshkovitz and Michal Moshkovitz. "Mixing Implies Lower Bounds for Space Bounded Learning". In: Proceedings of the 2017 Conference on Learning Theory. PMLR, 2017,
pp. 1516-1566.
[33] João F. C. Mota al. "D-ADMM: A Communication--ffiiieee Distributed Algorithm for Separable Optimization". In: IEEE Transactions on Signal Processing 61.10 (2013), pp. 2718- 2723.
[34] Arkadi Nemirovski and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. A -nter--ntersciencce publication. Wiley, 1983.
[35] Yurii Nesterov. "A method of solving a convex programming problem with convergence rate (1//k²)". In: Dokl. Akad. Nauk SSSR 269 (3 1983). pp. 543-547.
[36] Yurii Nesterov. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2003.
[37] Jorge Nocedal. "Updating Quasi-Newter Matrices with Limited Storage". In: Mathematics of Computation 35.151 (1980), pp- 773-782.
[38] Srinivasan Ramaswamy and John E Mitchell. A long step cutting plane algorithm that uses the volumetric barrier. Tech. rep. Citeseer, 1995.
[39] Ran Raz. "A Time-Space Lower Bound for Large Class of Learning Problems". In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 2017, pp. 732- 742.
[40]
Sashank J. Reddi et al. "AIDE: Fast and Communication Efficient Distributed Optimization". In: ArXiv abs/1600.0066 06879 (2016).
[41] B. Van Scoy, R. A. Freeman, and K. M. Lynch. "The Fastest Known Globally Convergent Orrer Method for Minimizing Strongly Convex Functions". In: IEEE Control Systems Letters PP.99 (2017), pp. 1-1.
12

---

[42] Ohad Shamir, Nati Srebro, and Tong Zhang. "Communication-Efiee Effiiceent Distributed Optimiza- tion using an Approximate Newton-type Method". In: Proceedings of the 31st International Conference on Machine Learning. Ed. by Eric P. Xing and Tony Jebara. Vol. 32. Proceedings of Machine Learning Research 2. Bejing, China: PMI.R, 22-24 Jun 2014, pp. 1000-1008.
[43] D. F. Shanno. "Conditioning of Quasi-Newton Methods for Function Minimization". In: Mathematics of Computation 24.111 (1970), pp. 647-656.
[44] Vatsal Sharan, Aaron Sidford, and Gregory Valiant. "Memory-Sample Tradcoff's for Linear Regression with Small Error". In: Proceedings of the 51st Annual ACM SIGACT Symposium on
Theory of Computing. STOC 2019. Association for Computing Machinery. 2019, pp. 890-901.
[45] Virginia Smith al. "CoCoA: A General Framework for Communication- Efficcient Distributed Optimization", In: J. Mach. Learn Res. 18.1 (Jan. 2017). pp. 119008638..
[46] Adrien Taylor and Yoel Drori. "An optimal gradient method for smooth strongly convex minimization". In: Mathematical Programming 199.1 (May 2023), pp. 557-594.
[47] Choon Hui Teo et al. "Bundle Methods for Regularized Risk Minimization". In: Journal of Machine Learning Research 11.10 (2010), pp- 311-365.
[48] Pravin M Vaidya. "A new algorithm for minimizing convex functions over convex sets". In: Mathematical programming 73.3 (1996), pp. 291-341.
[49] Stephen A Vavasis. "Black-box complexity of local minimization". In: SIAM Journal on Optimization 3.1 (1993), pp. 60-80.
[50] Jialei Wang, Weiran Wang, and Nathan Srebro. "Memory and Communication Efficient Dis- tributed Stochastic Optimization with Minibatch Prox". In: Proceedings of the 2017 Conference Learning Theory. Ed. by Satyen Kale and Ohad Shamir. Vol. 65. Proceedings of Machine Learning Research. PMLR, July 2017, pp. 1882-1919.
[51] Jianqiao Wangni et al. "Gradient Sparsification for Communication---ficcee Distributed Optimization". In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS' 18. Montréal, Canada: Curran Associates Inc.. 2018, pp. 1306- 1316.
[52] Blake Woodworth and Nathan Srebro. "Open problem: The oracle complexity of convex opti- mization with limited memory". In: Conference on Learning Theory. PMLR. 2019, pp. 3202- 3210.
[53] Yuchen Zhang, John C. Duchi, and Martin J. Wainwright. "Communication-efficae algorithms for statistical optimization". In: 2012 IEEE S1st IEEE Conference Decision and Control (CDC). 2012, pp. 6792-6792.
13

---

Therefore, for A Proof of the query complexity and memory usage of Algorithm
First, we give simple properties on the discretization functions. One can easily check that for any E C,
> Discretizee e)ll 5 and ||Discretize_(a, E)ll - |
(I)
Further, can easily check that represent any output of Discretizea <), one needs at most din 2v (d () bits.
We next prove Lemma 4.1
Proof of Lemma 4.7 We first consider the case when the algorithm terminates because of query == OP:: such that |لو|| 6/(2vd) d). Then, for any x E Ca. one directly has
g gT x b g (x -w- S 2vdlgll s
where w is the volumetric center of the resulting polyhedron. In the second inequality we used the fact that w E Ca. otherwise the algorithm would not have terminated at that step.
We next turn to the other cases and start by showing that the output polyhedron does not contain ball of radius 8. This immediate if the algorithm terminated because the polyhedron was empty. We then suppose this was not the case, and follow the same proof as given in (2). Algorithm and the one provided in ( coincide when removing constraint of the polyhedron. Hence,
[
suffices consider the case when add constraint. We the notation À [ ,
6 = [b_ bm+1] for the updated matrix A and vector b after adding the constraint. We also denote w = VolumetricCenter(( (A, b) (resp. W = VolumetricCenter(A (, b)) the volumetric center of the polyhedron before (resp. after) adding the constraint. Next, we consider the vector (b')T
[b [w], which would have been obtained if the cut was performed at w exactly, We then denote w' = VolumetricCenteer (A, b'). Then proof of (2) shows that
(w') Z VA.(ww) + 0.0340.
We now observe that by construction, we have bm+1 2 aw so that the polyhedron associated to (A, b) is more constrained than the one associated to (A, b'). As result, we have V 2 V A.B (z), for any æ E R2d such that Ax 2 b. Therefore,
V),((+) (wo) 2 VV, 2 Vw, + 0.0340.
This ends the modifications in the proof of (2). With the notations of this paper, we still have AV+ = 0.340 and AV- = 0.326, so that AV = 0.0014. Then, because proof shows that the procedure is successful for precision 8: the final polyhedron (A, b) returned by Algorithm[Idoee (Toes not contains a ball of radius > As a result, whether the algorithm performed all Tmaz iterations not, {x Ax > b} does not contain ball of radius > 8', where A and define the constraints stored in the output P. Now letting m be the objective value of the right optimization problem, there exists Ca such that for all < T. g. (æc ca) any x' E Ba(x, m) one has
AV. the same
Vi E [m], a, x' b, 2 m + a (x' x)
m | x 2 0.
In the last inequality we used |a.|| S 1. This implies that the polyhedron contains Ba( m). Hence, m < 6.
This ends the proof of the right inequality. The left equality a direct application of strong duality for linear programming.
We now prove that Algorithm 4 has the desired oracle-complexity and memory usage.
We first describe the recursive calls of Algorithm 3 in more detail. To do so, consider running the pro- cedure ApproxOracle(i.p) p(1), p(0) where < p, which corresponds to running Algorithm for specific oracles. We say that this is a level-i run. Then, the algorithm performs at most 27 k
calls to ApproxOracle(i 1, + 1, ((1) ..... p(O) :), where the factor 2 comes from the fact that
14

---

Vaidya's method Algorithm is effectively run twice in Algorithm 2 The solution to Paae has many components constraints in the last polyhedron, which is at most omin 1 by Lemma 4.2
Ri+1
Hence, the number of calls ApproxOracle(i + 1, p())....... p(O,) :) is at most 1++1 1. In total, that is (k In })) calls to the level i + 1 of the recursion.
We next aim to understand the output of running ApproxOracle P()). We denote by A(P(!) the solution Paux (P*) computed at 1.2 of the first call to Algorithm 2 where P is the output polyhedron of the first call to Algorithm| [ Denote by S(P()) the set of indices of coordinates from A(P()) for which the procedure performed call to ApproxOracle(2, 1, (,)) .). In other words, S(P()) contains the indices of all coordinates of ((P()), except those for which the corresponding query lay outside of the unit cube, or the initial constraints of the cube. For any index ( E S(P(1), let p! denote the state of the current polyhedron (Pe in 1.7 of Algorithm 2) when that call was performed. Up to discretization issues, the output of the complete procedure
Σ
(p((()) ApproxOracle(2. 1, p(1) p!
(ES))())
We continue in the recursion, defining A(P(1), p(2)) and S(P(1), p(2)) for all E S(P())), until we define all vectors of the form A(P("), p(3) ..... P()) and sets of the form S(P()),pf P(()) for i + 1 S r S - 1. To simplify the notation and emphasize that all these polyhedra depend on the recursive computation path, we adopt the notation
br = A1. (P(1) P(2)
P(())
Sla...d- == S(P()) p(2) ....,,!."" P(.))
We recall that these polyhedron are kept in memory to query their volumetric center. For ease of notation, we write I VolumetricCenter((P)) and we write c/a...... VolumetricCenter(P
for 2 < r S P. where .2............................ 4--1 were the indices from the computation path leading up to P(!)) Last, we write Os (Os. Os.p), where Oz Ca - 12 is the "x," component of Os, for all i [p].
With all these notations, we will show that the output of ApproxOradle(i.j j()) p(),pp)) pp(2) ...., approximately equal to the vector
, P(()) is
G(i,j, d'a d'a
Σ
- xhtadea........ ... .
(s, damndy
KIIES, 412554111 11554
with the convention that for = p. d == da...,,,,a d
G(p,j. 11, c²2,
The corresponding computation tree is represented in Fig. For convenience, omitted the term j =
We start the analysis with simple result showing that if the oracle Os returns separation vectors of norm bounded by one, then the responses from ApproxOracle also lie in the unit ball.
Lemma A.1. Fix d, & E (0, 1), 1 < j S S and an oracle Os (Os.i...,,O0p Suppose that Os takes values the unit ball. For any E [i] let p(.)) E Ix, represent bounded polyhedrons with VolumetricCenter((P
C. + Rdd,
E Ck.. Then, one has
|ApproxOracles..om (())
((0) 11
Proof. We prove this by simple induction on For convenience, we define the point æ = VolumetricCenter(PP))) If p. we have
|ApproxOraclen..oo (i.. ..... p(.)) || Discretize;; (2), xp). mp))()1l
< |00ss ( ( <
15

---

G(1)
11
m2
G(2,c!)
G(2,c22)
G(2,cm)a)
N
Naala
22.mm
G(3,d2,,d.))
G(3,c4,,ddlg)
((3,d?2,demm)))
G(p ,.c.,,................. dk.mppp))
X
Os,(c'h, ..... c Os,(chh, claannd
Osg(dh , che
Figure 3: Computation tree representing the recursive calls to ApproxOracle starting from the calls to ApproxOracle(1,1, 1) from Algorithm
where in the first incquality used Eq (1) and in the second incquality we used the fact that Os(xi,...,,a Fp) has norm at most one. Now suppose that the result holds for + S p. Then by con- struction, the output ApproxOracles.. (i,j; P(2) ..... p(!) is the result of iterative discretizations. Using Eq ( and the previously defined notations, we obtain
[|ApproxOraclea..oo P > ?.)
Σ
Xaaonds AtroxOradeesg,, ...., ...,,,!!, pl(ttt
11.
In the last inequality, we used the induction hypothesis together with the fact that Ene Maumdbaa < using Eq TT. This ends the induction and the proof.
We now ready compare the output of Algorithm to G(i, (1, c²a c',,..., dlainis). (e...,,damnit.)
Lemma A.2. Fix 8, & E (0, 1). 1 S j S i S p and an oracle Og (Os. Os.n) Ca + Rdd. Suppose that Os takes values in the unit ball. For any E [i] let p(:)) E Ix, represent bounded polyhedron with VolumetricCenter(((""
Ck. Denote x, = c((pf)) for r E [i]. Then,
AAproxOOrade,.o (1, , .(.)) G(i, x #1...., x;)] s ds.
Jmin
Proof. We prove by simple induction on i that
0o (L.j,(()) p.())) G(i, (1..,,,,...,
2 Tmin
<
1
+
(ke41 ....++.++
+ kp) + 2(p 2(p-i) g.
-1)
First, for i p. the result is immediate since the discretization is with precision (1.4 of Algorithm 3 Now suppose that this is the case for i S and any valid values of other parameters. For conciseness,
write G (P(2) ...., p(.-))) Next, recall that by Lemma 4.2 | < & 1. Hence,
16

---

the discretizations due to 1.8 of Algorithm 2 can affect the estimate for at most that number of rounds. Then, have
ApproxOracdesg.os (i-,, G)
Σ
Nam.. ApproxOOrrOOr s,oss (L, G, ((!)))
1,88'2004411
h;
1)
1
moi
where X/ the discretized coefficients that are used during the computation 1.8 of Algorithm 2 Now using Lemma A.I. we have
Σ
(flaminh yla... ApproxOraclea.oo. (I.J.
S S
X iond 1111
+1)
+
mmin
In the last inequality we used the fact that has at most using the induction for each term of the sum, and the fact that E. X
Ry + 1 non-zero coefficients. As result,
omen
obtain
||pproxOracless.oo. (i 1, G) G(i 1, 21 ,.,,, 2;-1)]
2
2ki
(ks+1 + +...+
+ kp) + 2(p - E
2 E,
min
O Umin
which completes the induction. Noting that h++1 +... ...+ kp S k1 + +... kp S and p i ends the proof.
Next, we show that the outputs of Algorithm provide approximate separation hyperplanes for the first i coordinates (z......a) D.).
Lemma A.3. Fix å, E (0, 1 iisis and oracle Os = (O5,1, Os.)) C.s + Rd for accuracy > O. Suppose that Os takes values the unit ball Ba(0, 1). For any s E [i] let P(1) E Ik. represent a bounded polyhedron with VolumetricCenter(( (P(,)) E Ck,- Denote x, = c(p( for r E [i]. Suppose that when running ApproxOracleas.oaa (i, p(1) ,...,P P.)))) ), no successful vector was queried. Then, any vector x² (æi.... 2x) E Ca such that Ba(x* (e) is contained in the successfil set satisfies
8d5/2
(ir .....
xx) 2c
mmin & d8.
Proof. For i Sr p and j S r, we use the notation
9 1: ie ApproxOraddess.o.tt.. .....
..... ...))
Using Lemma A.2 we always have for j E [r].
[g le - GGr, x ..,..,, x; dlit dit 4d
5.
(2)
Umin
Also, observe that by Lemma A.I the recursive outputs of ApproxOracle always have norm bounded by one.
Next, let Th41...rrr be the set of indices corresponding coordinates of X 441.-..6 for which the procedure ApproxOracle did not call for a level-r computation. These correspond to 1. constraints from the initial cube Po. or 2. cases when the volumetric center out of the unit cube (1.6-7 of Algorithm[] [ and as a result, the index of the added constraint was -1 instead of the current iteration index t. Similarly above, for any T Thei.ndr-1, denote by gr le the corresponding
17

---

vector a, We recall that by construction, this vector is of the form He, for some j E [k,]. Then, from Lemma since the responses of the oracle always have norm bounded by one, for all y, CR
Σ
(ill (g) ) ( dillinnrr s 8.
(3)
1, TUT 1
For conciseness, we use the shorthand (SU T) = Sharondo-s Th which contains all indices from coordinates of X 1411-do-1 In particular,
E
Alttonad 1.
(4)
1,E(SUT))--mmde
We now proceed to estimate the precision the vectors G(i, C1,.... 2x, as approximate separation hyperplanes for coordinates (zI,..., Ri). Let xx E Ca such that Ba(x", is within the successful set. Then, for any choice of 4+1 E ES,..., E Slit1idd-- since we did not query a successful vector, we have for all 2 E Ba(x" .c),
Os Oz(..........................0 3 chil chi (ellmm)) (#1..... T din ..... ((ll)nm))))) 20.
As result, because the responses from Os have unit norm,
Os(a1,.... Bie cli+1 cl-in--d (a* (2:1..... 3. d c 26 6.
(5)
Now write x² (Ei...., F7y). In addition the previous equation, for 4,1 S....., lp-1 gl+ta....7>22 and any 4 Th one has ( x + 1 because x' is within the cube Cu and at least at distance from the constraints of the cube. Similarly as when 1, E Sle4ts-nrtr1,, for any 1, Th.t...rrr we denote by cli+1....f the volumetric center of the polyhedron p(() along the corresponding computation path, 4. corresponded to an added constraints when ci $ Ck, Otherwise, if 1, corresponded to the constraint = te, of the initial cube, we pose cl44 a.
Now by construction, in both cases one has (g) d 1. ch ch......d S -1 (1.7 of Algorithm 1p. Thus,
(o ) (x) dl
Recalling Eq 4 we then sum all equations of the form Eq ( and Eq (6 along the computation path, to obtain
(A): =
Σ
Me+1 ... Xl4rr.ddp
WAIES.....
1.8
O2(11, ................................ Di, chi1
chil Thl (#I,... I,, diii..... ,..., chilmnnoo)
Σ
Σ
Nhts Nhtemnde ( T(x; - di-sundd) 2 E.
#ISrSP
h11ES...dd 4e0
Now using the convention
G(r, L1, Li clit2 ..... ditl)ole)) == g glriodd
4 E T.uumbb
for any 4+1 E S,..... S,...,,h-11 Slitimndo-2 we can write
(A) = Σ
G(i, r, ",,,,,,,,,,
2z) T.);), xx) +
Σ
Σ
15i
#11rSp
I-IES
4. 1e
Σ
G(r, Bi dlt ..... , ditimdde (T (x) chtimmd))
x
We next relate the terms G to the output of ApproxOracle. For simplicity, let write G (D(2) ...., p(t)), which by abuse of notation was assimilated to (a),.... .x.). Recall that by con- struction and hypothesis, all points where the oracle was queried belong to Ca. so that for instance
18

---

- chil || I 2 < 2vd for any 4 E Shilmnde
Using the above equations together
with Eq 2 and Lemma A.2 gives
ApproxOraalesggoo... (i, G) (2 kxp) + 8/2
Σ
E
mmn
itIrrsp
4HEES.... 4 1E8/4timii
8d
14+1 ... 1
Σ
Nltimaa (gltt (xx elitinndl) + Mmi
Le((SUT) tittotrrrt
8pd3/2
I
++ (p-
10--16 1)8 +
ApproxOradees,oo.. (1, G) (x+ x,)
mmn
rsi
where in the second inequality, used Eq 3 Using p d, this ends the proof of the lemma.
We are now ready to show that Algorithm 4 is a valid algorithm for convex optimization.
Theorem A.1. Let E (0, 1) and Os : C. + R be a separation oracle such that the successful set contains a ball of radius Pose ó ta and { = smin.. Next, let p 2 1 and .y...., kp S _ such that +...+ kp d With these parameters, Algorithm 4 finds a successful vector with (C In d) queries and using memory ( In for some universal constant C
Proof. Suppose by contradiction that Algorithm f never queried successful point. Then, with the chosen parameters. Lemma A.3 shows that, for any vector (zf...., x such that Ba( ee) is within the successful set, with the same notations, one has
8d
o (i. P/ ...., P.I)) x.) 2
d8
e 2
min
Now denote by (at, b.) the constraints that were added at any time during the run of Algorithm when using the oracle ApproxOracle with = = 1. The previous equation shows that for all such constraints,
a, x - b. a. (z) w)) = -
where W, is the volumetric center of the polyhedron at time & during Vaidya's method Algorithm Now, since the algorithm terminated, by Lemma 4.1 we have that
min(a, a b.) < 6.
This is absurd since + This ends the proof that Algorithm 4 finds successful vector.
We now estimate its oralle-copplexity and memory usage. First, recall that a run of ApproxOracle of level i makes O(ks+1 In 3) calls to level-(i 1) runs of ApproxOracle. As result, the oracle- complexity Qale; ki,..., .,....,,)))) kp) satisfies
(n In x...X (Ckyp (n
(o'd
d
log 2)²
d P
Qule;ki..... kp)
for some universal constants C, C' > 2.
We now the memory of the algorithm. For each level i [p) of runs for ApproxOracle, keep memory placements for
the value j(ó of the corresponding call to ApproxOracle(t,.00.) (for 1.6-7 Algorithm 3): (In d) bits,
2. the iteration number (1) during the run Algorithm or within Algorithm (In In bits
3. the polyhedron constraints contained in the state of p(t) O k; In bits,
19

---

Table 1: Memory structure for Algorithm
p
j
j()) ((1)
j(p)
Iteration index
k1, a1, bj
h2, a2 b2
Polyhedron
p(u)
p(p)
km am bm ki, A1
Computed dual variables
(k+
x,(1))=
his X2
(k) (p) X)(e)
Working
(p))
separation vector
4. potentially, already computed dual variables X and their corresponding vector of constraint indices k" (1.3 of Algorithm 2 O(k; x In {) bits,
5. the working vector ( (updated 1.8 of Algorithm 2 Okk, In ) bits.
The memory structure is summarized in Table 1
We can then check that this memory is sufficient run Algorithm An important point is that for any run of ApproxOracle(i., j, -), in Algorithm 2 after running Vaidya's method Algorithm and storing the dual variables X and corresponding indices k* within their placements (K* (6) X (1)
(1.1-3 of Algorithm 2). the iteration index ((() and polyhedron p(i) memory placements are reset and can be used again for the second run of Vaidya's method (l.4-10 of Algorithm 2). During this second run, the vector u is stored its corresponding memory placement (*) and updated along the algorithm. Once this run is finished, the output of ApproxOracle(i.. j, :) is readily available in the placement (1) For p, the algorithm does not need to wait for the output of level-(i + 1) computation and can directly the j(P))th -th component of the returned separation vector from the oracle Os. As result, the number of bits of memory used throughout the algorithm is at most
M = Σ
k In
) =
(
)
d2 In
This ends the proof of the theorem.
We can already give the useful range for for our algorithms, which will also apply to the case with computational-menal constraints Appendix
Proof of Corollary 3.1 Suppose 2 7.. Then, for some Pmar O
Cla 2ln from Theorem 3.2 yields ((+) craple-complexity. On the other hand, if S Je, we can take
d, the algorithm
Pmaz = d, which gives an oracle-complexity O((C'nn 1)
B Memory-constrained feasibility problem with computations
In the last section we gave the main ideas that allow reducing the storage memory. However, Algorithm does not account for memory constraints in computations as per Definition 2.2 For instance, computing the volumetric center VolumetricCenterr(? already requires infinite memory for infinite precision. More importantly, even if one discretizes the queries, the necessary precision and computational power may be prohibitive with the classical Vaidya's method Algorithm [ Even finding feasible point in the polyhedron (let alone the volumetric center) using only the constraints is itself computationally intensive. There has been significant work make Vaidya's 's method computationally These works address the issue of computational tractability, but the memory issue 2
tractable 48
20

---

is still present. Indeed, the precision depends among other parameters on the condition number of the matrix H in order to compute the leverage scores Ø; for i [m], which may not well-conditioned. Second, to avoid memory overflow, we also need to ensure that the points queried have bounded norm, which again not a priori guaranteed the original version Algorithm
To solve these issues and also give a computationally--fiiei Algorithm[neeed to be modified. In particular, the volumetric barrier needs to include regularization terms. Fortunately, these have already been studied in [27] In a major breakthrough, this paper gave a cutting-plane algorithm with (dd In I(1 d runtime complexity, improving over the seminal work from Vaidya and subsequent works which had (dd In ((2) 4) runtime complexity, where (dd)) ) is the computational complexity of matrix multiplication. To achieve this result, they introduce various regularizing terms together with the logarithmic barrier. While the main motivation of (27) was computational complexity,
algorithm, the cutting- planne subroutine
side effect, these regularization terms also ensure that computations can be carried with efficient memory. We then use their method as a subroutine.
For the sake of exposition and conciseness, we describe simplified version of their method, that is also deterministic. This comes at the expense of suboptimal running time O(d2+w In ((1) 1). We recall that our main concern is in memory usage rather than achieving the optimal runtime. The main technicality of this section is to show that their simplified method is numerically stable, and we emphasize that the original algorithm could also be shown to be numerically stable with similar techniques, leading to a time improvement from (d +w) to Ódd). The memory usage, however, would not be improved.
B.1 A memory-efficient Vaidya's method for computations, via 22
Fix a polyhedron we define the new leverage scores (xx); (A, A₂ + - 'AA )r, and & (x) = diag (z)).
{x Ax 2 b}. Using the same notations as for Vaidya's 's method in Section 4.1
Let (xx))= = min, (x) Last, let (x) = A (c. + T (x) A₂ + AI, where ce > is a constant
parameter to be defined. In (27). they consider minimizing the volumetric-anallyic hybrid barrier function
m
1
p(x)
Ce
Σ In (x) + In det (A
A. AI) 1
We can check 27 that
Vp(œ) A (ce 1 1++((z)) Xx,
where is the vector of ones. The following procedure gives a way to minimize this function efficiently given good starting point.
Input: Initial point (0) E P {x: Ax 2 b}
Input: Number of iterations r >
Given (I(Vp(=(())
(())0)) ((
I 100
1
v Ce + ++(x((0)) =
for k- = 1o do
[p(p(((())) (0)) < 2(1
57 I'n then Break;
(k) (k-1) -V
end
Output: (k))
Algorithm 5: (r) Centering( ,))
We then present their simplified aatting-plane method.
In both Algorithm 3 and Algorithm notice that the updates require to compute in particular the leverage scores (x),, which can be computed in O(d)) time using their formula. To achieve the Old In 2(1) !) computational complexity, an amortized computational cost (dd) is needed. The algorithm from (27) achieves this through various careful techniques aiming to update estimates of these leverage scores. The above cutting-plane algorithm is exactly that of (27) when these estimates are always exact (i.e. recomputed at each iteration). which yields the d=-2 overhead time complexity. particular, the original proof of convergence and correctness of 27 directly applies to this simplified algorithm.
21

---

Input: e, and separation oracle O : Ca - R2
Check Throughout the algorithm, if s; (x(()) 2e for some then return (Pt, 2(1))
Initialize x²()) and Po = ei -0--11)) 1); (-1, -1,-,), -1), i [d]}
2
for / 2 0
min (xx())); I ca then Pi+1 = Pe (kk,, az.by) by)} where j E arg [m] ()(x(());
3
5
else
if x') $ Ca then a sign((z)) where E arg mingeld 1o/01:
else a = 0(x());
Let b - a (1) Ca
-1/2 Va (A A
Pa+1 = PaU U ((t, a, b)]
x (++1) = Centering(x!" (1) c2)
10
I1
end
Algorithm 6: An efficient cutting-plame method, simplified from 27
remains to check whether one can implement this algorithm with efficient memory, corresponding to checking this method's numerical stability.
Lemma B.1. Suppose that each iterate of the centering Algorithm ( (((0000)) is com-
puted up to precision (1 - In (l.2), and (k)) is computed up to an error Ç (k)) with ||5 (k) (x)0)) S 2 (1 84) Y (I.3). Then, Algorithm 5 oulputs (k) such that [|Vp(z(()))ll (le- 3(1 64 ''n
and all iterates computed during the procedure satisfy ||ST,) (s(x(()) (xx( S 10
Proof. As mentioned above, without computation errors, the result from [27] would apply directly. Here, we simply adapt the proof to the case with computational errors to show that it still applies. I Vce + u(xx(0)). We prove by induction that Denote Q = (x(())) for convenience. Let r) = Too
(|xe(t) x 1Q < 9n, [Vp(z(())l S (1 64 3'7 for all S. r. For a given iteration t, denote
((+-1) (k-1)) Q (k=)) the result of the exact computation. The same arguments as | [+(++))
in the original proof give
x 101 - 97,, and
V
11 S (1
32 (V)
Now because (1+1)
|| 10 l|q 10n, that (1t11)ll $ 1/: we have || (++1) x (0
lq
27 Lemma I] gives v²p(y(u)) 3 8Q()(u)) = 16Q, where y(u) xl(+1) + u (1= ((+1)
for u E [0, 1). Thus,
[v((((+))) Vr(a s /// V V p(y(u)) ((41))
Q-1
< <16][a((+1) x ((+1))lQ
Now by construction of the procedure, if the algorithm performed iteration + 1, we have [|Vp(z(0)) l|q 2 (1 ) Combining this with the fact that || (c+1) x. (c-1)) s goo 7. obtain
V
S [Vp((((+))) vp(a + (V((
1 \Vp(2<"))lo-1
1
64
We now write
| (+1) - -x 101
[|
x
(k+1))
llQ + - 1
1
(
k=0
1
< +
1 -
n s 9n.
64
7=0
22

---

The induction is now complete. When the algorithm stops, either the steps were performed, in which case the induction already shows that (ll & (1 )"n, Otherwise, if the algorithm terminates at iteration k. because [V((((()) Il (see 1.2 of Algorithm 5
lلا- was computed to precision (1 64 )' 17, we have
(1)
02)
(1 (1- 1 ) 64
VV((> ( lll . S 64 n
64
7=
n.
The same argument as in the original proof shows that at each iteration t,
|xx(0) - x x0 11
1
I 200) (+) - s(xx())))
(|xx(0)
2000 A S
v /u(x(01) + Ce
10"
This ends the proof of the lemma.
Because of rounding errors, Lemma B.1 has an extra factor compared to the original guarantee in
(27] Lemma 14]. To achieve the same guarantee, it suffices to perform 70 > ln(3)/ In (11((1 64 additional centering procedures most. hence, instead of performing 200 centering procedures during the cutting plane method, we perform 270 (1.10 of Algorithm op. stability of the main Algorithm [
We next turn to the numerical
Lemma B.2. Suppose that throughout the algorithm, when checking the stopping criterion min (xx))) < 2c, the quantities s;(x)) were computed with accuracy c. Suppose that at each iteration of Algorithm O the leverage scores (b(x(()) are computed up to multiplicative precision es cx/4 (1.3), that when a constraint added, the response of the oracle a (L.7) is stored perfectly but b (L8) is computed up to precision 52( )n) Further suppose that the centering Algorithm 5 is run with numerical approximations according to the assumptions in Lemmal B.1 Then, all guarantees for the original algorithm in (27) hold, up to a factor 3 f e.
Proof. We start with the termination criterion. Given the requirement on the computational accuracy, we know that the final output x satisfies min:e[m] szxx) I 3e. Further, during the algorithm, if it does not stop, then one has min.e[m] sx(x)) 2 e, which is precisely the guarantee of the original algorithm in [27
We next turn to the computation of the leverage scores 1.4. In the original algorithm, only a ca esstimate computed. Precisely, one computes a vector (*(*) such that for all E [d], (xx()), s
w; < (1 + c)))(x(()), then deletes constraint when min wi (t) S ca. In the adapted algorithm, let (()()),, denote the computed leverage scores for E [d]. By assumption, we have
(1 -1- (1-cs/4)((=())) S (1)) S (1 +1+00 ca (z)))
Up to re-defining the constant Cu as (1 - c4/4) (()) is precisely within the guarantee bounds of the algorithm. For the accuracy the separation oracle response and the second-term value 6, [27 emphasizes that the algorithm always changes constraints by a ő amount where 8 = 21 Va) so that
an inexact separation oracle with accuracy Q S suffices. Therefore, storing Q 5
Va accuracy
of the second term keeps the guarantees of the algorithm. Last, we checked in Lemma B. that the
centering procedure Algorithm S satisfies all the requirements needed in the original proof [7
For our recursive method, we need an efficient cutting-plane method that also provides proof (certificate) of convergence. This is also provided by [27] that provide proof that the feasible region has small width in one of the directions a, of the returned polyhedron.
Lemma B.3. (27 Lemma 28] Let (P, xx (A4)s) be the output of Algorithm 7 Then, æ is feasible, ||0||2 < 3vd, Xj 2 0f all and E, X; = 1. Further,
and b)) 50500 (e In 2)
Σ A.a
We are now ready to show that Algorithm 6 can implemented with efficient memory and also provides a proof of the convergence of the algorithm.
23

---

Input: E <> and separation oracle O: :C RR Run Algorithm 6 to obtain a polyhedron P and feasible point x Centering (e, 64 (,Ca)
3 A (,t,,
Σ (x
for all
s((=))
sy(m*)
Output: (P,x*
(A:))
Algorithm 7: sutting-plane algorithm with certified optimality
Proposition B.1. Provided that the output of the oracle are vectors discretized to precision poly(
and have norm at most 1, Algorithm 7 can be implemented with Odd In 4) bits of memory to output a certified optimal point according to Lemma B.3 The algorithun performs Od () calls to the separation oracle and runs in O -w In O(1) 1ime.
Proof. We already checked the numerical stability of Algorithm i Lemma B.2 It remains to check the next steps of the algorithm. The centering procedure is stable again via Lemma B.1 It also suffices to compute the coefficients Ny up to accuracy O(e/(vd In(d/c) to keep the guarantees desired since by construction all vectors a; have norm at most one.
now remains show that the algorithm can be implemented with efficient memory. We recall that at any point during the algorithm, the polyhedron P has at most (dd) constraints [27] Lemma 22]. Hence, since we assumed that each vector a, composing a constraint is discretized to precision poly()), we can store the polyhedron constraints with (d In ()) bits of memory. The second terms b are computed up to precision ((e/vV) hence only use O(d In {) bits of memory. The algorithm also keeps the current iterate ((1) in memory. These are all bounded throughout the memory ||z (vdd) 27 Lemma 23], hence only require O( ) bits of memory for the desired accuracy.
Next, the distances the constraints are bounded at any step of the algorithm: s,(x()) I O(Vd)
[27] Lemma 24], hence computing (x(x(() to the required accuracy is memory-efficient. Recall that from the termination criterion, except for the last point, any point during the algorithm satisfies (x))) (x) 2 for all constraints
[m]. In particular, this bounds the eigenvalues of Q since XI 3 (x) (A + m(ce + 1)/e2) Thus, the matrix is sufficiently well-conditioned to achieve the accuracy guarantees from Lemma B.1 using Odd In 1 memory during matrix inversions (and matrix multiplications). Similarly, for the computation of leverage scores, we use (ar = diag(A A. (A_ Ag + - where AI < A A. + AI < (A + me -2E.. This same matrix inversion appears when computing the second term of an added constraint. Overall, all linear algebra operations are well conditioned and implementable with required accuracy with (d In 4) memory.
Using fast matrix multiplication, all these operations can be performed in Ö(d)) time per iteration of the cutting- -lane algorithm since these methods are also known to be numerically stable (15). Thus, the total time complexity is O(d In 0(1) 4). The oraele-copplexity still has optimal O(d In d) craplc-complxxity as in the original algorithm.
Up to changing e to c c/ 2). the described algorithm finds constraints given by a, and b, i [m]] returned by the normalized separation oracle, coefficients X i [m], and a feasible point x² such that for any vector in the unit cube, z E Cd, one has
min a. z 2 :E(m]
Σ Ai(aT x ba) =E(m]
Σ Aa; 1mmm]
(x' (0--2)+
Σ Aa(aT bi) Se. xc(m)
This effeettivly replaces Lemma
B.2 Merging Algorithm 7 within the recursive algorithm
Algorithms 2 to from the recursive procedure need to slightly adapted to the new format of the autting-planc method's output. In particular, the oracles do not take as input polyhedrons (and
24

---

eventually query their volumetric center as before), but directly take as input an point (which is an approximate volumetric center).
Input: c. O2 Cn mm and 0g C, R
Run Algorithm with parameter e 6/(dIn ;) and Oy to obtain (P",æ", x", [m²) where m 1P* and X < Discretize(2',
2 Store k* [k;
3 Initialize Po = e;, -1), (-1 e, - 1), i [d], x = and let u E R"
e;,
for i 0, 1, ,.......
max; max; do
if = : for some E [m] then
9= = -x(((())
<- Discretizem (u x)
Update P. to get P4+1. and (+) to get (+++1) as Algorithm
end
10 return u
Algorithm 8: Approsseprrtionveettssss00000000
Input: 5 jisiiss (r) Ca. for E [i], Os Ca - Rd
if then
(1......9 =0(())). :..,,,.,,, return Discretizesy ()
end
Define O2 : CR.11 IR ApproxOraclesg +,,,,,1 1, ,,..., x01)
Define Og Che.i - Ri as ApproxOracle (i 1, x 20(.,,)()))
return ApproxSeparraioonVettrr.gg
0,)) Algorithm ApproxOracle (1 a1)),
Input: 5. E, and Os Cu - IR separation oracle
Check Throughout the algorithm, if Og returned Success query æ, return Run Algorithm 6 with parameters and & and oracle ApproxOradles..oo (1, 1, Algorithm 10:
algorithm for convex optimization
The same proof for Algorithm shows that Algorithm runn with the parameters in Theorem A. also outputs a successful vector using the same oracle-complexity We only need to analyze the memory usage in more detail.
Proof of Theorem 3.2
As mentioned above, we will check that Algorithm 10 with the same pa- rameters 8 4d and & Omint in Theorem A.I satisfics the desired requirements. We have already checked its correctness and oracle-copllextty Using the same arguments, the computational where ComplexityCuttinglaasee is the
complexity is of the form O (O (CooplleiiyyCuttinggheae
computational complexity of the cutting
method used, i.e., here of Algorithm 7 Hence, the
computational complexity is (((((dpp) 1 1+= In o(1) dy²) for some universal constant C 2 2. We
now turn to the memory. In addition the memory of Algorithm 4 described in Table !
we need
a placement for all E [p] for the current iterate ()); O bits.
2. placement for computations, that is shared for all layers (used compute leverage scores, centering procedures, etc. By Proposition B. since the vectors are always discretized to precision ç. this requires O(max;ejpl k? bits.
3. the placement Q to perform queries is the concatenation of the placements (zx(),.... x (v))):
no additional bits needed.
4. placement N to store the precision needed for the oracle responses: OIn bits
25

---

5. placement R to receive the oracle responses: O(dIn } bits.
The new memory structure is summarized Table
With the same arguments as the original proof of Theorem A.I this memory is sufficient to run the algorithm and perform computations, thanks the computation placement. The total number of bits used throughout the algorithm remains the same, O )). This ends the proof of the theorem.
Table 2: Memory structure for Algorithm
10
p
Oracle response
Precision
j
j(l)
j(m)
(R
Rp)
N
Iteration index
g(1)
((P)
k1, 01, by
Polyhedron
p(1)
82, 02 b2
P(r)
km, Clm bm
Current
(x(1)
ar(st
Computation memory
iterate
Ai. Ai Ag. Ab
Computed dual variables
(k*,
)=
(k=(P) x-60)
Working
(1)
w
separation vector
C Improved oracle-complexxty/memryy lower-bound trade-offs
We recall the three oncce-ccomlexxtyymemory lower-bound trade-offs known in the literature.
First, 31 showed that any (including randomized) algorithm for convex optimization uses 15 memory or makes +46/3) queries.
2. Then, [5] showed that any deterministic algorithm for convex optimization uses df-6 memory or makes ((x2++6/3) queries.
3. Last, show that any deterministic algorithm for the feasibility problem uses d2-5 memory or makes (+6)++6) queries.
Although these papers mainly focused the regime 1/poly(d) and result In = O(I d), neither of these lower bounds have an explicit dependence in e. This can lead to sub-optimal lower bounds whenever In ! >> In d. Furthermore, in the exponential regime do not effectively give useful lower bounds. Indeed, in this regime, one has d O(dIn !) and as a result, the lower bounds provided are weaker than the classical ((d 2) lower bounds for oracle-complexity (34) and memory [52). In particular, in this exponential regime, these results fail to show that there is any trade-off between oracle- complexiy and memory.
2014j these results
In this section, we aim to explicit the dependence in of these lower-bounds. We show with simple modifications and additional arguments that one can roughly multiply these cracle-complexity and memory lower bounds by a factor In 1 each. We split the proofs in two. First give arguments to improve the memory dependence by factor in which is achieved by modifying the sampling of the rows of the matrix A defining a wall term common to the functions considered in the lower bound proofs 53..5) Then show how improve the oracle-complexity dependence by additional ! In factor, via a standard rescaling argument.
C.1 Improving the memory lower bound
We start with some concentration results on random vectors. gave the following result for random vectors in the hypercube.
26

---

Lemma C.1 (3)).. Let h ~ u({+1)"). Then, for any t E (0. and any matrix Z [21,... 24] E Ruxk with orthonormal columns,
P(I hello 22)
Instead, we will need similar concentration result for random unit vectors in the unit sphere. Lemma C.2. Let le & d and æ1,...., D. be & orthonormal vectors, and ( S 1.
|20 yl S C i [k] <
PP Py-a(((4-1)
- (V2c)*
Proof. First, by isometry, we can suppose that the orthonormal vectors are simply e1...., Ct. We now prove the result by induction d. For d the result holds directly. Fix d 2 2, and 1 S Then, if Sn is the surface area of S the n-dimensional sphere, then
P PIVll
Sa-2 26 20 T(d/2) Sa-1 Vd Vidr(d/2-11)
Va
S
V
Conditionally the value of yı, the vector (22,...., ,,,.)))))))))))..... ya) follows uniform distribution the (d - 2)-sphere of radius /1 - 87. Then,
IP (Maal S S 2sisklyn = -Panu(ssan) | vd(1 - v4)
S 25isk
Vd
Now recall that since |011| | I 1/Vdd we have d(1 - xx9) 2 d 1. Therefore, using the induction,
|25 s Vd-1 / $
2
k-1
P 11ll S Vd
2 2 y/
TP (
/T
Combining this equation with Eq ends the proof.
We next use the following lemma to partition the unit sphere 1d-1
Lemma C.3 (19 Lemma 21). For any 0 < < 7/2, the sphere Srt-1 can be partitioned into ( = (1(1)88 equal volume cells, each of diameter at most 8.
Following the notation from (5), we denote by V/8 {Vi(0), [N(6)]} the corresponding partition, and consider set of representatives Dj (b) E [N()]] S such that for all [N)) b,(5) E (5)).. With these notations we can define the discretization function da as follows
$s = (8),
V2(0).
We then denote by Us the distribution of cis (z) where z (d(d-11 is sampled uniformly on the sphere. Note that because the cells of V have equal volume, Us is simply the uniform distribution the discretization Dz.
We are now ready to give the modifications necessary to the proofs, to include a factor In for necessary memory. For their lower bounds, (3I exhibit a distribution of convex functions that are hard to optimize. Building upon their work 5 construct classes of convex functions that are hard to optimize, but that also depend adaptively on the considered optimization algorithm. For both. the functions considered barrier term of the form ||A loc. where A is a matrix of = d/2 rows that are independently drawn as uniform on the hypercube (({+1))d) The argument shows that memorizing is necessary certain extent. As result, the lower bounds can only apply for a memory of at most (dd2) bits, which is sufficient to memorize such binary matrix. Instead, we draw rows independently according to the distribution Us where d e. We explicit the corresponding adaptations for each known trade-off. We start with the lower bounds from [5) for ease of exposition; although these build upon those of 31 their parametrization makes the adaptation more straightforward.
27

---

C.1.1 Lower bound of (5) for convex optimization and deterministic algorithms
For this lower bound, we use the exact same form of functions as they introduced,
Up U2.10 p'1 1722 )
max
max | - 17, 100 a, PSPmon,
with the difference that rows of A are take i.i.d. distributed according Us instead of ({+1)))) As a remark, they use n n= [d/4] rows for A. Except for v/. we keep all parameters 7/ 72, etc as in the original proof, and we will take 8' = and that the original construction also needs the discretization Φs. This is used during the optimization procedure which constructs adaptively this class of functions, and only needs d = poly(1/d) instead of 8 of order
2v The reason why we introduced 8' instead of d
Theorem C.1. For S 1/(2d4.5) and any E [0, 11, a deterministic first-order algorithm guaranteed to minimize 1-Lipschitz convex functions over the unit ball with e accuracy uses at least d2-6 6 bits of memory or makes (/(3)+ queries.
With the changes defined above, can easily check that all results from (5) which reduce convex optimization to the optimization procedure, then the optimization procedure to their Orthogonal Vector Game with Hints (OVGH) (5) Game 2], are not affected by our changes. The only modifications to perform are to the proof of query lower bound for the OVGH [3] Proposition 14]. We emphasize that result.
the distribution of A is changed in the optimization procedure but also in OVGH
Proposition C.2. Let 2 20 M4 (og(d)))++
n1ogg(/2((+88 /dj) I. And let < a, 3 S 1 such that al a(Vd/3)3/ s
c/vd where < S 1. If the Player wins the adapted OVGH with probability at least 1/2, then 30 logg d m ! (V2((++())))) -1d
Proof. We use the same proof and only highlight the modifications. The proof is unchanged until the step when the concentration result Lemma C.T is used. Instead, we use Lemma C.2 With the same
notations as in the original proof, we constructed [k/5] orthonormal vectors Z 2....... <T/65]
such that all rows a of A' (which is A up to some observed and unimportant rows) one has
l T alloc S Vd
Next, by Lemma we have
{
a
a
Ds
aaloo
alloo S
5 Vdl
}
< (Dyl 100l-Paail (1z"ali alloo S S
Panills
< |Dyl P P |1ZT2/1a S 5 Va + 8
[6/5]
< (D&l (V2(s + 5' d'vii)
Hence, using the same arguments as in the original proof, we obtain
H(A' Y) S (n m) (Ioss [Dar + P(E)
k 5
loga (V2(c - -8va))
where E is the event when the algorithm succeeds at the OVGH game. In the next step, we need to bound (A V) HG. where stores hints received throughout the game, G stores observed rows of A during the game, and j. c are auxiliary variables. The latter can be treated as in the original proof. We obtain
H(A V) H(G.j,c)
2 (AA) - H(G) - I(A; V- - 3m logg (2d) 2 (n m.) log, [D5r] - 3m log, (2d) - I(A, V).
Now the same arguments as in the original proof show that we still have I(A, V) I 3km log, d 1, and that as result, if M is the number of bits stored in memory,
M 2
log2 10
(n -)) - 3km log, d - 1 - 3d (2d)
V
8'
Then, with the same arguments as in the original proof, we can conclude.
28

---

We are now ready to prove Theorem C.1 With the parameter & = [20 the same arguments, we show that an algorithm solving the convex optimization up to precision // (2vd) d) = e yields an algorithm solving the OVGH where the parameters a satisfy
3dd (2g(d))++ and
n logg /24 /24
2g and 3 72
vd
7/03
d
4
We can then apply Proposition C.2 with Ç = c/e/2. Hence, if Q is the maximum number of queries of the convex optimization algorithm, we obtain
(1
(1 1+
30 loga d
-
Pm/a + +12
z
log2 dec
1/2
8 61
where in the last inequality we used c _ 1/(2d4.5).
As a result, with the same arguments, we obtain
d 15/3
1/3 1n3
Q=
(M + In Ind 1n 2/3
This ends the proof of Theorem C.1
C.1.2 Lower bound [5] for feasibility problems and deterministic algorithms
We improve the memory dependence by showing the following result.
Theorem C.3. For c = 1/(48d and any E [0, 1], a deterministic algorithm guaranteed to solve the feasibility problem over the unit ball with e accuracy uses at least d2-6 makes at least (1()++)) queries.
8 In bits of memory or
We use the exact same class of feasibility problems and only change the parameter which constrained successful points satisfy || A V/, well as the rows of A that sampled i.i.d. from Mg. The other parameter 1/: = 11/2v/d unchanged. We also take = c. Because the rows of A are already normalized, we can take 7/0 = directly. Then, the same proof as in (5) shows that if an algorithm solves feasibility problems with accuracy c, there an algorithm for OVGH for parameters = 7//111 and = 7)1 /2. Then, we have ar v(vd/3)54 < 12d and we can apply Proposition C.2 with 12d 7/o 12...... Similar computations above then show that 2 d/(8 61), with
k O M++iddd so that the query lower bound finally becomes
In
Q2Ω Ω
(M + In
Remark C.1. The more careful mualysis-involving the discretization Dj of the unit sphere at scale ó instead of the hypercube {=1] -allowdll add a In 1 factor the final query lower bound but also an additional In d factor for both convex- movex-optimization and feasibility -iiility--roblem results. Indeed, the improved Proposition C.2 shows that the OVGH with adequate parameters requires O(d) queries, instead of O(dj In dd in [5 Proposition 14]. At a high level, each hint queried brings information Od In d) but memorizing binary matrix A E {+1]
[tt1][d/A) (d/4) xd only requires d? bits of memory: hence the query lower bound is limited to O'd/ In d). Instead, memorizing the matrix A where each row lies in D5 requires (d In :) memory, hence querying d hints (total information (d In d)) is not prohibitive for the lower bound.
C.1.3 Lower bound of [31] for convex optimization and randomized algorithms
We aim to improve the result to obtain the following.
Theorem C.4. For e S l/d and any ó E [0, 1], any (potentially randomized) algorithm guaranteed
to minimize 1- 1-Lipschitz convex functions over the unit ball with accuracy uses at least dl.20 21.25-0 In bits of memory or makes (161+18/3) queries.
29

---

The distribution considered in 31 is given by the functions
max
d d - 1, max
(
d6
sE[N]
where I d is parameter, A has [d/2] rows drawn i.i.d. from 4(f=1)"), and the vectors vs are drawn i.i.d. from the rescaled hypercube v; ((d=11/((=1))) We adapt the class of functions by simply changing pre-factors as follows
mmx A0 1, iE(N)
max (1; x iry) ir)))
(8)
where A has the same number of rows but they are draw i.ddd from Uss and 6, f > 0 are parameters to specify. We use the notation y instead of i as the previous sections because (31) already use
a parameter which in our context can interpreted as r 1/(pVd). We choose the parameters 16 and 8' =.
Again, as for the previous sections, the original proof can be directly used to show that if an algorithm guaranteed to find 16v/ (2 c)-suboptimal point for the above function class, there an algorithm that wins at their Orthogonal Vector Game (OVG) [T Game IJ, with the only difference that the parameter d' (1.8 of OVG) is replaced by v Vdu. OVG requires the output to be robustly- inneeeedeed (defined in (1) and effectively corrssoonds to 3 = 1/d in OVGH. As result, there is successful algorithm for the OVGH with parameters a ddu and A = I/d² and that even completely ignores the hints. Hence, we can now directly use Proposition C.2 with Ç d=+25/16 p (from the assumption S d we have ( S 1/vd). This shows that with the adequate choice of k O (+ ), the query lower bound is (2dd).
d
Putting things together, a potentially randomized algorithm for convex optimization that uses M memory makes at least the following number of queries
Nd 1:
d4/3
dln
Q 2
=Ω
1/3
M dlnnd
C.2 Proof sketch for improving the query-complexity lower bound
1 We now turn to improving the query-complexity lower bound by a factor In At the high level, the idea is to replicate these constructed "difficult" class of functions at In similarly to the manner that the historical (2d In } lower bound is obtained for convex optimization (34). This argument relatively standard and we only give details in the context of improving the bound from (3I) for randomized algorithms in convex optimization for conciseness. This result uses a simpler class of functions, which greatly eases the exposition. We first present the construction with
In different scales or levels,
2 levels, then present the generalization = = ind) (
levels. For convenience, write
d4/3
dln
4/3
M,)) =
1/3
M + d
This is the query lower bound given in Theorem C.5
for convex optimization algorithms with memory
M that optimize the defined class of functions (Eqq
(8) to accuracy
C.2.1 Construction of a bi-level class of functions FA.IL. to optimize
In the lower-bound proof, 31 introduce the point
PA)
T
2
[E[N]
where PA- is the projection onto the orthogonal space to the rows of A. They show that with failure probability most 2/ d. æ has good function value
1, max (0) x i7) < 5 P
F. FA, = max |-|||
A
loo
sE[N]
8/N
30

---

GA, (x)
GA. (Ø)
HEa (1 || x112)
2612
GA.v; (3) + 462
+
3
18
1662 3
+ [a
V2,
i7)
E2/9
Figure 4: Representation of the procedure to rescale the optimization function.
This is shown in [3 Lemma 25]. On the other hand, from Theorem C.4 during the first
Q (c; a,
queries of any algorithm, with probability at least 1/3, all queries are at least μ u/616v/ N ( --ubopttimll compared to z in function value [31] Theorem 28, Lemma 14 and Theorem 16]. Precisely, if FA, is the sampled function to optimize, with probability at least 1/3,
/
J
(x,)( 2 (z)
16V 2 FA)(())
+ 16vd'
V 11.
As a result, can replicate the term | (v. -i7) at smaller scale within the ball Ba 1/(16/))) For convenience, we introduce & 1/(16yd) which will be the scale of the duplicate function. We separate the wall term ||Ax||o for convenience. Hence, we define
GA,,, (2) == μ max (vi,æ0 -n)
VE[N]
GA (x) max G A., (x),, GA,,, (x)
1 ir
}}}}}
max
1 +
x x
max
U2
18 iE[N]
///
An illustration of the construction is given in Fig. by adding the wall term:
4 The resulting optimization functions given
F FA,,, (x) = max | lc u1 GA,u, (x)}
F FA 02 (x) max { Ax |oc GAv, [x))
We first explain the choice parameters, First observe that since || = O. we have GA., (x) FA,, (.)). We can then check that for all E Ba(0, 1),
G GA < max { GA.u, (x), GA,,, (.) +
2 uE2
)
(9)
Further, for any x (2 (2/3), since FA.,, 1-Lipschitz, we can easily check that
GA,,,,12 G.., (x)
M6= max 1+ || 2112,
E2 + &
2 uE2.
18 JE[M]
max
U2
Eg/9
Thus, GA, (x) does not coincide with GA,", (w) on Ba( E2/3). Then, the || - T 2112 term ensures that any minimizer of GA,,a. is contained within the closed ball Ba( E2)3) Also, to obtain a / susuoptiaal solution of FA.,,,gg the algorithm needs to find what would be uEb-subopl solution of F FA,,, while receiving the same response when optimizing the latter.
31

---

Next, for any a E (2/9), the term max check that for (2/9),
17
lies in [-1, Hence, we
E2/9
GAv.Ley GA.. (+) -A
1
3
T 22,
x
17
(10)
3
18
54
NE
E2/
We now argue that FA.m... acts as duplicate function. Until the algorithm reaches a point with function value at most A.,,, (x) + 4,2. the optimization algorithm only receives responses consistent with the function FA.v, by Eq Pp. Next, all minimizers of FA, are contained in Ba E2/3), which was the goal of introducing the term in || - 2l12. As result, optimizing F'Av,, on this ball is equivalent to minimizing
F0 (v) max ||Ay|| 0c 12, 02 V2 max 2 in), 3dllull, y E Ba(0,3), iE
where
y
Ea/9
The function has been rescaled by a factor /2/9 compared to FA. so that 2 &2 .. (x) 3p. By
91
uba 1/2 6p, C2 -
& CA (z) 3u + uL2, and d2
μ12 Eo V2
Eq (T). the two first terms of FA,u, preponderant for y Ba(0, 1).
The form of FA,uz is very similar to the original form of functions
F FA,0z max ||Av|la p/ uá max 22 -1)
[E[N]
In fact, the same proof structure for the query-ccomllexity/memrry lower-bound can be applied in this case. The main difference is that originally one had μ² μقz here would instead have 4 = #2 + C2 = (p//E2) and μrر = 1/2 = ((E2)). Intuitively, this corresponds to increasing the accuracy to ) factor & is due to the fact that FA,e, was rescaled by factor {2/9 compared to FA.e, u.. and second factor & is due to the fact that within FA, va. we have μير = ((((f))while while the query lower bound similar to that obtained for (ee/E). As a result, during the first
Q2 Q 0==0(0(
M.
E2
queries of any algorithm optimizing FA.... with probability at least 1/3 on the sample A and U2. all queries are least -(eb))ssubpptiall compared to
Σ (A2,)))). RE(N)
y = 2
We are now ready to give lower bounds on the queries of an algorithm minimizing FA,,,. to accuracy O(rE)). Let Tz be the index of the first query with function value most GA.,, (o) + PL2z- We already checked that before that query, all responses of the oracle are consistent with minimizing FA,. hence on an event & of probability at least 1/3, one has T2 2 Q1- Next, consider the hypothetical case when at time T2, the algorithm is also given the information of æ and is allowed to store this vector. Given this information, optimizing F FA reduces to optimizing F FA.0z since we already know that the minimum is achieved within Ba E2/3). Further, any query outside of this ball either
returns vector V1.; which does not give any useful information for the minimization (v) and V2 are sampled independently and given).
returns a row from A, as covered by the original proof.
Hence, on an event & of probability at least 1/3, even with the extra information of ã., during the next Q2 queries starting from T2, the algorithm does not query a ((uE)) -uboptimal solution to FA vs. This holds a fortiori for the model when the algorithm is not given o at time Tz.
32

---

C.2.2 Recursive construction of a p-level class of functions FA.......rp
inductively construct the sequence of functions F FA.. F2 PA, PA.0 "2 etc. Formally, the induction is constructed as follows: let (0p)p2 be an i.i.d. sequence of N iid. vectors (UR,))E[N) sampled from the rescaled hypercube d' (=1] Next, we pose
Similarly in the last section,
GA.,; (x) = (1(1) max vE[N]
TT.
x:(1) s(l)
in)
where (x(2) x()) = 0 and g(2) = For k 2 1, we pose
((k)
(k+1) (b)
Σ
PA (DK,)); and
F(k) = G
ay + 11 Ex+1,
2
KE[N]
for certain parameter Ek+11 to be specified. We then define the next level as
E
G (2)1))..)4 = max
G GA (2), G. (o(h+t))
1+ x (1++1)|l2 122
Ex+1
Ex+1 max
U Uk+i,
x x(kt1) ) -in) }}}
max
(kk
+ 6
+
18
iE[N]
s(k)
We then pose (k+1)) optimization functions are defined simply as
1 (2 1 /5 and ((++1) = 511) which closes the induction. The
FA Ux.1 (x) max ||Ax|100 μ. G GA GA (x))
We checked before that we can use & = 1/(16vd). For general A: 2 O, given that the form of the function slightly changes to incorporate the absolute term (see FA,v.). this constant may differ slightly. In any case, one has & @(1/vá). Now fix a construction level p 2 1 and for any k [p]. let Th be the first time that point with function value at most F(k) queried. For convenience let To = O. Using the same arguments as above recursively, we can show that on an event & with probability least 1/3.
M, Th TT s(k)
Next note that the sequence (b)] is decreasing and by construction, if one finds (1( Sp+1 -ubooptiaa point of FA......,,,, then this point has value at most F(P), As result, for an algorithm that finds ((P) -uboopiiall point, the times .o...., Tp are all well defined and non non-decreasing. We recall In in )
that μ dev Therefore, we can still have pz)(p) < Ve and j((P) Ep+1 2 ² for O Combining these observations, we showed that when optimizing the functions FA. accuracy ((p(0)) = (2)2),, the total number of queries Q satisfies
4/3 In
d M + dllndd
4/3
B[Q] 2 3
Σ Q ( =
In
1/3
kE
Changing to 2 proves the desired result.
Theorem C.5. For S 1/d and any = [0, 1). any (potentially randomized) algorithm guaranteed to minimize 1-Lipschitz convex functions over the unit ball with accuracy uses at least 2.225-3 bits of memory or makes +-883+ In }) queries.
The same recursive construction can be applied to the results from Theorems C.I and C.3 to improve their oracle-complexity lower bounds by a factor In I albeit with added technicalities due to the adaptivity of their class of functions. This yiclds Thcorem 3.3
33

---

Input:
Number of iterations T, computation accuracy S 1, target accuracy e << Initialize: a
for turt=0 00...... do
Query the oracle at x: successful then return 4;;
Receive separation vector with accuracy ?)
Update a as x
cg to accuracy
end return x
Algorithm 11: Memory-constrained gradient descent
D Memory-constrained gradient descent for the feasibility problem
In this section, prove simple result showing that memory-constrrined gradient descent applies to the feasibility problem. We adapt the algorithm described in (52].
We now prove that this memory-consttrined gradient descent gives the desired result of Proposi- tion 3.1
Proof of Proposition 3.7 Denote by the state of æ at iteration i, and 9, (resp- g,) the separation oracle without rounding errors (resp. with rounding errors) at t;. By construction,
|0e+1 (ar, eg.ill s and llø. 9: S n
(11)
As result, recalling that l!9.ll = 1,
| x 11 + - x=" 1))² < (1|æ; +eg, x0 [1 | teg, x= 101| 20n 20n-
By assumption, Q contains ball Ba(x", E) for x' Ba(0, 1). Then, because g, separates from Ba(x* <), one has g, (xx - xx) 2 c. Therefore,
| x < a xx" 2 2cg. (a, x²) + 11 20n
s c x=1 -e" 20n
Then, take 17 = e2/40 and T itteaation was performed, we have using the previous equation
2
2² 2 ST
ØT x" || <
w x x²11
-T < 4
2
Hence, ær is e-suboptimal solution.
We now turn the memory usage gradient descent. It only needs to store æ and g up to the desired accuracy (c2)). Hence, this storage and the internal computations be done with O(d ) memory. Because we suppose that S I this gives the desired result. va
34


Reviews:
[{"review_id": "o06corH8Zj", "reviewer": "Reviewer_snNf", "summary": "The authors study memory vs oracle calls trade-off for convex optimization. The examples of problems they consider are: To find a point in the $d$-dimensional unit ball up to error $\\epsilon$, or to minimize $1$-Lipschitz convex functions over the unit ball up to error $\\epsilon$.\nThey provide a family of algorithms parametrised by $p \\in [d]$ that solve the problem using $O(d^2 \\log (1/\\epsilon) / p)$ bits of memory and make $(C d \\log (1/\\epsilon)/p)^p$ oracle calls, where $C$ is some absolute constant.\n\nMore precisely, the first result (the case $p=1$) is the proof that a memory-constrained Vaidya’s method has (optimal) oracle complexity $O(d\\log(1/\\epsilon))$ and memory complexity $O(d^2\\log(1/\\epsilon))$, that is a $\\log(1/\\epsilon)$-factor improvement over the state-of-the-art. For $p=d$, their algorithm has oracle complexity $(C\\log (1/\\epsilon))^d$ and (optimal) memory complexity $O(d\\log(1/\\epsilon))$, that improves over state-of-the art oracle complexity $O(1/\\epsilon^2)$ if $\\log(1/\\epsilon) \\gtrsim d\\log d$.", "questions": "I have a question related to non-efficient algorithms: Since to match the optimal memory complexity your algorithm requires $p=d$ (and so the running time is exponential in $d$), it makes sense to compare your algorithms with inefficient approaches. Naive brute force for the feasibility problem (that only uses a weaker oracle for an indicator of the set, not a separation oracle) seems to require $(C/\\epsilon)^d$ oracle calls, which is too large, but maybe there exists some other simple brute force algorithm that uses the separation oracle and has comparable guarantees to your algorithm. Did you by chance think about such an algorithm?", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper provides new algorithms with better memory vs oracle calls trade-off than the state-of-the art. The paper is well-written, and the contribution is clear. The algorithms are non-trivial and their analyses are sophisticated.", "weaknesses": "My main concern is that the results only slightly improve over the state-of-the-art. \n\nThe first result improves over the state-of-the-art only by a $\\log(1/\\epsilon)$-factor. It is not surprising, since there are lower bounds that (for the feasibility problem) imply that $d^{2-\\Omega(1)}$ memory complexity can only be achieved with $> d^{1+\\Omega(1)}$ queries, but I am not sure if this result itself is strong and/or interesting enough to justify acceptance in NeurIPS.\n\nThe importance of the second result (with $p>1$) is not very clear to me. Let memory complexity of memory-constrained Vaidya’s method be $M$. In order to achieve memory complexity $o(M)$ (even $M/\\log \\log M$), one needs to increase the oracle complexity by a factor that is super-polynomial in $M$. I can hardly imagine settings when it might be reasonable. For comparison, there are some problems for which information-computation trade-offs are known (e.g. planted clique), and for those problems even a minor improvement over the state-of-the-art might be important, since there are basically only two options: Either we solve the problem (and perhaps spend a lot of computational resources), or do not solve it at all. Here it is not the case: the algorithm designer can always choose to use the memory-constrained Vaidya’s method, or to slightly decrease memory complexity and significantly increase the number of oracle calls (and hence the running time), and it seems to me that the huge price of memory complexity is not adequate here.  \n\nOne could argue that the trade-off that is not useful in practice can be interesting if it clarifies memory vs oracle complexity picture of the problem. But the upper bounds from the paper are very far from the currently known lower bounds, and it does not improve a high-level understanding of the complexity picture. For example, it is not clear if super-polynomial oracle complexity is necessary for sub-quadratic memory complexity.\n\nConsidering these strengths and weaknesses, I recommend borderline reject.\n\nUPDATE: After reading the rebuttal I decided to increase the score from 4 to 6. Please see the comments below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comprehensive summary and your positive view of our algorithms and analysis. We are very happy to provide some answers to the concerns you raised.\n\n1. We believe that this work provides some important clarifications to the memory/oracle complexity landscape. We emphasize that to the best of our knowledge, prior to this work, no positive results nor algorithms were known to improve in any way over two most foundational algorithms for optimization: gradient descent (GD) and cutting-planes (CP) (including ellipsoid methods). The specific question of whether it is possible to improve these algorithms in the memory/oracle complexity picture was also present in the literature and stated in its strong form as a COLT 2019 open problem [1]. Although our work does not provide a full understanding of the picture:\n\n- We show that in super-polynomial regimes, it is indeed possible to improve over these algorithms (dark green region in Figure 1). To the best of our knowledge this is the first result making some progress on the algorithmic side as opposed to lower bounds for which the literature is better established [2,3,4]. We further provide a class of algorithms giving a positive trade-off between memory and oracle complexity. This enables an optimizer to specify a desired memory usage (at the price of oracle complexity), through the parameter $p$, instead of restricting the choice to either linear or full (quadratic) memory.\n- A major question was whether one can Pareto-improve over GD and/or CP. Lower bounds [3,4] have already shown that one cannot improve over CP, but in this work, we show somewhat surprisingly that GD does not Pareto-dominates in some regime (exponential accuracy).\n\nAdditionally, our algorithms work in the face of a stronger form of memory constraint than described in the literature: they are limited in memory between iterations, but also for within-iteration computations.\n\n2. To answer your question, we are not aware of any brute-force (or other) algorithms that have comparable guarantees to our algorithms (say for $p=d$) for non-smooth convex optimization. Closest to brute-force methods are some works that consider smooth optimization in low-dimensional settings.\n\n- Vavasis [5] showed that thanks to smoothness, combining brute-force search with gradient approaches one can achieve $1/\\epsilon^{\\frac{2d}{d+2}}$ oracle complexity. This slightly improves over what gradient descent would achieve in our setting, only if $\\log \\frac{1}{\\epsilon} \\gg d$. However, in that regime $\\log \\frac{1}{\\epsilon} \\gtrsim d\\ln d$, the oracle complexity $(C\\log\\frac{1}{\\epsilon})^d$ from our method with $p=d$ is much lower than a polynomial in $\\frac{1}{\\epsilon}$, and does not require smoothness.\n- The polynomial exponent for the oracle complexity from [5] was then improved in dimensions 2 and 3 by Bubeck and Mikulincer [6] with clever ideas to side-step brute-force approaches. In high-dimensions, their algorithms achieve $(\\frac{\\log 1/\\epsilon}{\\epsilon})^{\\frac{d-1}{2}}$, which exhibits a strong curse of dimensionality (at least $\\epsilon^{-d/4}$).\n\nThese two works considered harder non-convex problems but heavily used the smoothness assumption. It is worth noting that using smoothness, Monte-Carlo approaches may outperform optimization in terms of oracle complexity (e.g [7], but the suboptimality measure considered is somewhat different), which always shows some form of dimensionality curse [7].\n\nThe above-mentioned approaches do not seem to give successful results for our non-smooth convex optimization setup and other ideas seemed to be required compared to the literature to possibly improve over gradient descent. Instead, we use different techniques based on a recursive reduction to lower-dimensional subproblems, which we believe are novel.\n\n3. Last, the study of super-polynomial accuracies is not uncommon in optimization. Following the seminal paper [5], there has been a growing literature that considered optimization in low-dimensional (or even constant as in [6]) settings---for instance, in dimension $d$, the improvement from [5] in smooth-nonconvex optimization over $\\frac{1}{\\epsilon^2}$ is significant when $\\log\\frac{1}{\\epsilon}\\gg d$. In that asymptotic in $\\epsilon$ perspective, our bounds in the exponential accuracy regime are (a high-degree) polynomial in $\\log\\frac{1}{\\epsilon}$ instead of $\\frac{1}{\\epsilon^2}$. Also, in the specific literature for memory/oracle-complexity tradeoffs, some papers specifically study super-polynomial accuracy regimes, e.g. [4] which consider accuracies $\\epsilon\\leq \\exp(-\\log^4 d)$ (to appear at FOCS 2023 according to the author's website).\n\n\n[1] Woodworth, Blake, and Nathan Srebro. \"Open problem: The oracle complexity of convex optimization with limited memory.\" Conference on Learning Theory. PMLR, 2019.\n\n[2] Marsden, Annie, et al. \"Efficient convex optimization requires superlinear memory.\" Conference on Learning Theory. PMLR, 2022.\n\n[3] Blanchard, Moïse, Junhui Zhang, and Patrick Jaillet. \"Quadratic memory is necessary for optimal query complexity in convex optimization: Center-of-mass is Pareto-optimal.\" Conference on Learning Theory. PMLR, 2023.\n\n[4] Chen, Xi, and Binghui Peng. \"Memory-Query Tradeoffs for Randomized Convex Optimization.\" arXiv preprint arXiv:2306.12534 (2023).\n\n[5] Vavasis, Stephen A. \"Black-box complexity of local minimization.\" SIAM Journal on Optimization 3.1 (1993): 60-80.\n\n[6] Bubeck, Sébastien, and Dan Mikulincer. \"How to trap a gradient flow.\" Conference on Learning Theory. PMLR, 2020.\n\n[7] Ma, Yi-An, et al. \"Sampling can be faster than optimization.\" Proceedings of the National Academy of Sciences 116.42 (2019): 20881-20885."}, {"review_id": "a5oV31RwOY", "reviewer": "Reviewer_LsGk", "summary": "The paper discusses a parameterized family of memory-constrained algorithms for convex optimization and compares the memory and oracle call complexity of this family with existing algorithms. The authors show that with this parameterized family, one can trade between oracle call and memory complexity, and they claim that this is the first work in this direction.", "questions": "- In Def. 2.2, you write that the \"the contents of $Q$ and $N$ are $q$ and $n$, respectively\" and that \"$R$ must contain at least $n$ bits\". Is the latter the same $n$ as the former?\n- What is the meaning of the notation $\\vee$ and $\\wedge$ in Corollary 3.1?", "limitations": "I do not see any immediate negative societal impacts, hence it is fine that the authors did not mention any. The limitations of the study are clearly discussed in Section 5.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and accessible even to readers slightly unfamiliar with the topic (but see also below for some comments). The clarity is particularly facilitated by the excellent setup in Section 2, and also the overview of related work in Section 2.1 is exemplary. The paper seems theoretically quite strong (although I admittedly did not check the proofs in the supplementary material) and the algorithms are easy to understand. Figure 1 excellently summarizes the significance of the paper in the sense that the known upper and lower bounds are non-trivially improved upon.", "weaknesses": "One weakness of the paper is the introduction, which requires (in my opinion) more prior knowledge than what may be available from a non-expert. For example, the concept of a separation oracle in line 33 did not become clear to me until line 99, and similarly for the feasibility problem in line 42. In line 36 it is said that center-of-mass methods are \"quadratic\" in memory, from which I deduced quadratic in $d$ (but not in $-\\log\\epsilon$); then the statement that the algorithm improves upon center-of-mass for $p=1$ in line 54 is confusing. This is not a critical weakness, though, as the rest of the paper is quite accessible.\n\nAnother concern is whether the content of the paper fits well the scope of the venue. This is not immediately clear to me and shall be discussed in the discussion phase.\n\n## Minor:\n- line 115: \"can also be carried OUT\"?\n- line 122: \"all known lower boundS\"\n- line 139: \"one needs to store $O(d)$ cuts instead OF $O(...$\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive view of our paper and its contributions, and for your useful remarks. We will take care to solve all minor issues in the revised manuscript. We will also make sure to clarify parts of the exposition mentioned. With respect to the conference, NeurIPS has a tradition of publishing optimization papers that provide theoretical insights. This paper contributes to the overall goal of understanding resource constraints for optimization algorithms and designing efficient algorithms for these tasks, which we believe is of interest to the NeurIPS community in general, and its optimization sub-community in particular.\n\nIn Def 2.2, the two $n$ are indeed the same: roughly speaking, before making a query to the oracle, the algorithm first needs to specify a bit precision for the response. That precision $n$ is stored in the placement $N$ which is read by the oracle. The oracle then writes the subgradient rounded to a precision of $n$ bits within the response placement $R$, which should therefore contain at least $n$ bits.\n\nThank you for noting that we did not define the notations $\\land$ and $\\lor$, which act as minimum and maximum operators. We will add a formal definition in the revised manuscript. For clarity, Corollary 3.1 states that using $p\\leq \\mathcal O(\\min(d,\\frac{\\ln\\frac{1}{\\epsilon}}{\\ln d}))$, this provides a tradeoff between cutting planes and having memory $\\mathcal O(\\max(d^2\\ln d,d\\ln\\frac{1}{\\epsilon}))$ (we recall that $d\\ln\\frac{1}{\\epsilon}$ memory is necessary) and oracle complexity $\\mathcal O(\\min(\\frac{1}{\\epsilon^2},(C\\ln \\frac{1}{\\epsilon})^d))$."}, {"review_id": "ItD8lpKv7q", "reviewer": "Reviewer_6ZsG", "summary": "The authors propose an algorithm to solve a feasibility problem with constrained memory while minimizing the number of calls in separation oracle. The memory complexity and the calls to separation oracle is parametetrized by a parameter $p$.  They get $O(d^2/p \\log 1/\\epsilon)$ bits of memory with $O(d/p\\log(1/\\epsilon))^p$ calls to separation oracle. Their result basically improves the case where $\\epsilon$ is much smaller than $1/d$. They also provide a lower bound of that shows the dependences on $\\log(1/\\epsilon)$ for several settings. The algorithm is based on the Vaidya's cutting plane algorithm.", "questions": "-", "limitations": "no limitations.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Contains new contributions for the regime where $\\epsilon$ is much smaller than $1/d$.  The lower bound is also an interesting and a new contribution and potentially of independent interest. Overall, the paper is well written.", "weaknesses": "For me, the only weakness is that as you improve the memory, you increase the number of calls exponentially, which does not sound so intuitive to me. But still, the results are interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive view of the paper. The number of oracle class indeed grows exponentially with the parameter $p$, due to the recursive nature of the algorithm. We emphasize however that these are the first class of algorithms providing a positive result to trade-off memory and oracle-complexity in convex optimization, while the question of understanding the memory/oracle-complexity trade-off was well-identified in the literature (in its strong form, this was formulated in a COLT 2019 open problem [1]). Our results do not fully describe the memory/oracle-complexity landscape but provide significant clarifications. We first show that it is in fact possible to improve in some regime over the two fundamental algorithms in optimization: gradient descent and cutting-planes. Second, while it was known that cutting-planes are Pareto-optimal, we show somewhat surprisingly that in some exponential regime, gradient descent is not. Our algorithms allow an optimizer to specify a memory usage (at the cost of oracle complexity) instead of being restricted to either linear or full (quadratic) memory. Prior to this work, results were only obtained for lower-bounds, i.e., impossibility results [2,3,4], and novel ideas seemed to be required to make progress on the algorithmic side. In particular, to the best of our knowledge, previous approaches for optimization in low dimensions always showed significantly stronger curse of dimensionality [5] than say our $(d/p\\ln\\frac{1}{\\epsilon})^d$ oracle dependence. Here we propose a recursive approach to solve low-dimensional sub-problems together with a careful analysis, which we believe are novel.\n\n\n[1] Woodworth, Blake, and Nathan Srebro. \"Open problem: The oracle complexity of convex optimization with limited memory.\" Conference on Learning Theory. PMLR, 2019.\n\n[2] Marsden, Annie, et al. \"Efficient convex optimization requires superlinear memory.\" Conference on Learning Theory. PMLR, 2022.\n\n[3] Blanchard, Moïse, Junhui Zhang, and Patrick Jaillet. \"Quadratic memory is necessary for optimal query complexity in convex optimization: Center-of-mass is Pareto-optimal.\" Conference on Learning Theory. PMLR, 2023.\n\n[4] Chen, Xi, and Binghui Peng. \"Memory-Query Tradeoffs for Randomized Convex Optimization.\" arXiv preprint arXiv:2306.12534 (2023).\n\n[5] Ma, Yi-An, et al. \"Sampling can be faster than optimization.\" Proceedings of the National Academy of Sciences 116.42 (2019): 20881-20885."}, {"review_id": "7b40bdUGkg", "reviewer": "Reviewer_U1uo", "summary": "This paper studies solving feasibility problems, and hence optimization problems, and focusing on the trade-offs between the number of oracle calls and use of memory. The precise problem is to find a point in a convex set inside the unit cube, given access to a separation oracle, which reports if a query point is in the convex set, or otherwise returns a hyperplane separating the input query point and the convex set.\n\nBy segmenting the variables/dimensions and working on them sequentially, and using the variant of Vaidya’s cutting-plane method by Lee, Sidford, and Wong, this paper presents a new recursive algorithm with better trade-offs between the number of oracle calls and use of memory. In particular, this algorithm uses the same optimal memory but makes less oracle queries than gradient descent for low error regime $\\epsilon \\le \\frac1{\\sqrt d}$.\n\nIn addition to algorithms, this paper slightly improves on existing lower-bounds for the trade-offs between accuracy $\\epsilon$ and dimension $d$ with a more careful analysis.", "questions": "Are there geometric intuition (better than the repeated convexity argument applied to blocks of variables) to the recursive application of cutting plane method? Arguably, breaking up variables into blocks, while improving bounds, does not give new geometric understanding.", "limitations": "This theoretical paper does not have broader societal impacts.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper adapts an existing algorithm with a recursive decomposition to improve the trade-offs between number of oracle calls and memory usage, beating gradient descent for very low error regime.", "weaknesses": "The improvement appears incremental, and does not give new insights or understanding for solving feasibility or optimization problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive view and the questions! Regarding the weakness, although our work does not provide a full understanding of the memory-query landscape, we emphasize the following three contributions. \n\n- To the best of our knowledge, prior to this work, no positive results nor algorithms were known to improve (in the memory-query landscape) over two most foundational algorithms for optimization: gradient descent (GD) and cutting-planes (CP). Our results demonstrate that in super-polynomial accuracy regimes, it is indeed possible to improve over these algorithms (dark green region in Figure 1). This is the first result making some progress on the algorithmic side as opposed to lower bounds for which the literature is better established [1,2,3]. \n- We further provide a class of algorithms giving a positive trade-off between memory and oracle complexity. This enables an optimizer to specify a desired memory usage (at the price of oracle complexity), through the parameter $p$, instead of restricting the choice to either linear or full (quadratic) memory.\n- A major question was whether one can Pareto-improve over GD and/or CP. Lower bounds [2,3] have already shown that one cannot improve over CP, but in this work, we show somewhat surprisingly that GD does not Pareto-dominates in some regime (exponential accuracy).\n\nAdditionally, our algorithms work in the face of a stronger form of memory constraint than described in the literature: they are limited in memory between iterations, but also for within-iteration computations.\n\n\nFor your question about the geometric intuition, we agree that the description of the algorithms and their performance is a bit abstract, and we will provide more explanations in the paper. We give in Figure 1 from the rebuttal pdf a geometric illustration in dimension 2 of the recursive step, where an approximate separating hyperplane to the problem ``projected'' to the $x$-axis is constructed using a separating oracle for the $2$-dimensional problem. To be precise, the target is $\\boldsymbol p^* = (p_x^*,p_y^*)$, and we use two blocks (i.e. $p=2$). Suppose at a step of the algorithm, the current value of the $x$ coordinate is $c$. We then aim to find an approximate separating hyperplane between $x = p_x^*$ and $x = c$ for some $c$, Algorithm 2 first runs Algorithm 1 (i.e. the memory-constrained Vaidya) to find two separating hyperplanes (the two blue hyperplanes). Lemma 4.1 then guarantees the existence of a convex combination of the 2 blue hyperplanes -- the red hyperplane-- which is approximately parallel to the $y$-axis and thus can serve as an approximate separating hyperplane between $x = p_x^*$ and $x = c$. \n\n[1] Marsden, Annie, et al. \"Efficient convex optimization requires superlinear memory.\" Conference on Learning Theory. PMLR, 2022.\n\n[2] Blanchard, Moïse, Junhui Zhang, and Patrick Jaillet. \"Quadratic memory is necessary for optimal query complexity in convex optimization: Center-of-mass is Pareto-optimal.\" Conference on Learning Theory. PMLR, 2023.\n\n[3] Chen, Xi, and Binghui Peng. \"Memory-Query Tradeoffs for Randomized Convex Optimization.\" arXiv preprint arXiv:2306.12534 (2023)."}, {"review_id": "BSF5UY0rF5", "reviewer": "Reviewer_H4w2", "summary": "The paper studies the problem of memory constrained convex optimization. In this setting, the algorithm is given oracle access to the gradients of an unknown convex function and is tasked with finding an approximate minimizer. The additional constraint is that the algorithm is constrained to use as few bits of memory as possible. Though convex programming is a classical area, understanding the memory requirements of algorithms has only recently been considered and has become an active area of research. When considering memory, two standard algorithms witness a tradeoff between memory and oracle complexity: gradient descent makes $1/\\epsilon^2$ queries and uses $d \\log(1/\\epsilon)$ bits of memory while the center of gravity method makes $d \\log(1/\\epsilon) $ queries and uses $d^2 \nlog^2(1/ \\epsilon)$ bits of memory. A recent line of study has been trying to understand the tradeoff between these complexities. The paper presents a recursive implementation of a cutting plane method which uses $O( d^2 / p \\log (1/ \\epsilon)$ memory while making $O( (d/p \\log (1/ \\epsilon))^p$ queries. Here $p \\in [d]$ is a parameter of the algorithm. In particular, the paper shows that for $\\epsilon = d^{-d}$ the algorithm presented has improved query complexity than gradient descent while using the same amount of memory. ", "questions": "- More thorough description of the algorithm along with the intuition for why it works would be very helpful. ", "limitations": "Yes ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The question considered by the paper is very interesting as memory constraints are a very natural \"simplicity\" condition on algorithms. To the best of my knowledge this is the first algorithm that improves on the memory complexity over the two benchmark algorithms. Furthermore the framework of recursive partitioning seems very interesting and could lead to improvements to other optimization algorithms, ", "weaknesses": "The regime of parameters that the algorithms improves over gradient descent is rather quant. In this regime both the algorithms make $d^O(d)$ calls to the oracle and the current algorithm improves the constant in $O(d)$ in the exponent. While this is of mathematical interest and does show the non Pareto optimality of gradient descent, justifying the interestingness of this range of parameters seems difficult. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive view and we really appreciate your suggestions! We agree that our algorithm improves over gradient descent only in the regime $\\epsilon\\leq \\frac{1}{d^{\\mathcal O(d)}}$, which might be smaller than regimes considered in some previous works on oracle complexity of convex optimization/feasibility problem. To justify studying this regime, we would like to point out here that optimization problems in the low-dimension regimes have a growing literature [1][2]; also, in the specific literature for memory/oracle-complexity tradeoffs, some papers specifically study super-polynomial accuracy regimes, e.g. [3] considers accuracies $\\epsilon\\leq \\exp(-\\log^4 d)$ (to appear at FOCS 2023 according to the author's website). In addition, we emphasize that our algorithm shows a non-trivial memory-query trade-off in the regime $\\log(\\frac{1}{\\epsilon})\\gg\\log(d)$, and outperforms the center-of-mass in the standard regime $\\epsilon\\leq\\frac{1}{\\sqrt{d}}$, which are novel results that might help understand the memory-query landscape better. \n\nFollowing your suggestions, we will provide more detailed description of and intuition behind the algorithm. Here in Figure 1 (in the rebuttal pdf), we use a $2$-dimensional feasibility problem to illustrate the geometry of the recursive step, where an approximate separating hyperplane to the problem ``projected'' to the $x$-axis is constructed using a separating oracle for the $2$-dimensional problem. To be precise, the target is $\\boldsymbol p^* = (p_x^*,p_y^*)$, and we use two blocks (i.e. $p=2$). Suppose at a step of the algorithm, the current value of the $x$ coordinate is $c$. We then aim to find an approximate separating hyperplane between $x = p_x^*$ and $x = c$ for some $c$, Algorithm 2 first runs Algorithm 1 (i.e. the memory-constrained Vaidya) to find two separating hyperplanes (the two blue hyperplanes). Lemma 4.1 then guarantees the existence of a convex combination of the 2 blue hyperplanes -- the red hyperplane-- which is approximately parallel to the $y$-axis and thus can serve as an approximate separating hyperplane between $x = p_x^*$ and $x = c$. \n\n\n\n[1] Vavasis, Stephen A. \"Black-box complexity of local minimization.\" SIAM Journal on Optimization 3.1 (1993): 60-80.\n\n[2] Bubeck, Sébastien, and Dan Mikulincer. \"How to trap a gradient flow.\" Conference on Learning Theory. PMLR, 2020.\n\n[3] Chen, Xi, and Binghui Peng. \"Memory-Query Tradeoffs for Randomized Convex Optimization.\" arXiv preprint arXiv:2306.12534 (2023)."}, {"review_id": "CTsAiyey73", "reviewer": "Reviewer_MixU", "summary": "The main result of the paper is a theorem that establishes a trade-off between oracle-complexity and memory-usage for convex optimization problems. More specifically they show that given a convex optimization problem in R^d, then for any p between 1 and d there is a deterministic first-order algorithm tha solves the feasibility problem for accuracy \\epsilon <=1/sqrt{d} using O(d^2/p ln 1 \\epsilon) bits of memory with O((C (d/p) (ln 1/epsilon))^p) calls to the separation oracle.  In other words, by decreasing the number of bits of memory by a factor of p, one needs to call the oracle a number of times that is exponential in p. The basis of the exponential function is roughly (d/p)* ln(1/epsilon). ", "questions": "1) Please make theorem 3.2 more self contained by briefly describing two parameters before the statement of the theorem: d and omega. \n\nIt should not be necessary to read a big portion of the paper to be able to understand the meaning of the main statement (Theorem 3.2). For instance, you could add a line before the theorem stating that you are dealing with optimization problems in R^d. Same thing for omega. I only see it defined in the footnote of page 4. Although the notation is standard, it took some time to find the precise meaning of omega. So it would be good to write its meaning either in the theorem or in the text just before it.  \n\n2) What are the differences between your method and Vaidya's method? Is it the case that the only difference relies in a recursive application of Vaidya's method? Do you modify the method somehow? This should be better discussed in the introduction. ", "limitations": "In my opinion the paper discusses the limitations of the techniques in a fair way. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The papers seems to make relevant advances in the understanding of tradeoffs between memory and number of oracle calls in convex optimization algorithms. ", "weaknesses": "The technique is heavily based on the Vaidya's cutting-plane method. It is not entirely clear what are really the advancements with respect to the original technique. \n\nThere are some minor presentation issues, such as statements of results with undefined parameters or parameters that are defined very far away. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our paper carefully and for the positive views! For your first point, we agree that our algorithm relies heavily on Vaidya's cutting-plane method [1] and its variant proposed in [2]. We will provide more detailed comparisons between our algorithm and (the variant of) Vaidya's methods in the introduction. Here, we would like to emphasize advancements from the following two perspectives.\n\n- We use Vaidya's methods as dimension reduction techniques. In particular, our algorithm divides the variables into blocks and applies Vaidya's methods recursively to construct approximate separation or subgradient oracles for problems with reduced dimensions. We believe that there is some novelty in this recursive dimension reduction step. \n- An important and novel technical step in the convergence analysis is to ensure that the precision of the computed approximate separation oracles is sufficient, which is primordial given the recursive nature of our algorithms (the errors accumulate at each layer of recursion). A natural approach to having a separation oracle for a father problem is to ensure that Vaidya's method of the sub-problem converges to the ``minimizer'' of the sub-problem. In fact with this approach, the precision required is multiplicative in the depth of the recursion and in the end, the required memory to store such high-precision sub-gradients (for low-level sub-problems) blows up and does not yield improvements over standard cutting-plane methods. Instead, Algorithm 2 performs Vaidya's method to high accuracy on all sub-problems (even though the sub-gradients used are of lower quality): on the sub-problem, the iterates effectively do not converge to the true minimizer of the sub-problem, but the analysis shows that the corresponding aggregated subgradient at the higher-level is still of sufficient quality (the deterioration becomes additive in the number of recursive levels). We did not emphasize this in the main body for the sake of simplicity, but this is the reason the proof requires estimating approximation errors along the complete computation path, instead of using a level-by-level recursive approach.\n- We take into account memory throughout computations. To be precise, for the original Vaidya's method in [1], only the weaker notion of memory constraint (Definition 2.1) applies. By adopting the variant of Vaidya's method in [2] (which has more penalty terms in the potential function), our algorithm is proven to satisfy the stronger notion of memory constraint (Definition 2.2), i.e. the memory is constrained not just between oracle calls but also throughout computations. \n\nThank you for pointing out the presentation issues, we apologize for any confusion! We will clarify $d$ (the dimension of the problem) and $\\omega$ (the exponent of matrix multiplication, $\\omega<2.373$) in Theorem 3.2.\n\n\n \n\n\n[1] Kurt M Anstreicher. “Towards a practical volumetric cutting plane method for convex pro- gramming”. In: SIAM Journal on Optimization 9.1 (1998), pp. 190–206.\n\n[2] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. “A faster cutting plane method and its implications for combinatorial and convex optimization”. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 1049–1065.\n"}]

Author rebuttal:
In this document, we provide in Figure 1, a geometric illustration of the recursive step of our algorithm, where an approximate separating hyperplane to the father problem (in the recursive hierarchy) is computed (Reviewers U1uo and H4w2). 

Meta-review: This paper proposes a parametrized class of algorithms for convex optimization that allow to trade-off memory and oracle calls via the choice of the parameter (p). For a certain range of parameters (depending also on the target accuracy epsilon) the method attains an improved memory/oracle call trade-off than previously known schemes. The paper also shows that the attained trade-off cannot significantly be improved in the high accuracy (low epsilon) regime.

The question on the optimal memory/oracle call trade-off was originally raised in (Woodworth and Srebro, 2019, "Open problem: The oracle complexity of convex optimization with limited memory"). This paper makes advances to understand this trade-off better (in the deterministic case), and complements other works on this open problem that focused don lower-bound impossibility results.

Please add the comments/discussion regarding the super-polynomial accuracy regime (as below) to the final version of the paper.
Decision: Accept (poster)