Information-constrained optimization: can adaptive processing of gradients help?
Authors: Jayadev Acharya
Clement Louis Canonne
Prathamesh Mayekar
Himanshu Tyagi
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimization
convex optimization
adaptivity
information constraints
local privacy
communication constraints
lower bounds
random coordinate descent

Abstract: We revisit first-order optimization under local information constraints such as local privacy, gradient quantization, and computational constraints limiting access to a few coordinates of the gradient. In this setting, the optimization algorithm is not allowed to directly access the complete output of the gradient oracle, but only gets limited information about it subject to the local information constraints.   We study the role of adaptivity in processing the gradient output to obtain this limited information from it, and obtain tight or nearly tight bounds for both convex and strongly convex optimization when adaptive gradient processing is allowed.

Information-coontrraind optimization: can adaptive processing of gradients help?
Jayadev Acharya" Cornell University acharya@cornell.co edu
Clément Canonne University of Sydney
clement. canonn edu au
Prathamesh Mayekar Indian Institute of Science prathamesh@iisc.ad ac.
Himanshu Tyagi²
Indian Institute of Science htyagi @eeiiiisii.... aas.caac... ac. in
Abstract
We revisit first-order optimization under local information constraints such as local privacy, gradient quantization, and computational constraints limiting access to few coordinates of the gradient. this setting, the optimization algorithm not allowed to directly access the complete output of the gradient oracle, but only gets limited information about it subject to the local information constraints. We study the role of adaptivity in processing the gradient output to obtain this limited information from it, and obtain tight or nearly tight bounds for both convex and strongly convex optimization when adaptive gradient processing is allowed.
Introduction
Distributed optimization has emerged as a central tool in federated learning for building statistical and machine learning models for data distributed across users. In addition, large scale optimization is typically implemented in distributed fashion over multiple machines or multiple cores within the same machine. These distributed implementations fit naturally in the oracle framework of first-order optimization (see [22]) where in each iteration a user or machine computes the gradient oracle output. Due practical local constraints such communication bandwidth, privacy concerns, or computational issues, the entire gradient cannot be directly made available to the optimization algorithm. Instead, the gradients must be passed through a randomized mechanism which, respectively. ensures privacy of user data (local privacy constraints); or compresses them to small number of bits (communication constraints); or only computes few coordinates of the gradient (computational constraints). Motivated by these applications, we consider first-order optimization under such local information constraints placed on the gradient oracle.
When designing first-order optimization algorithm under local information constraints, one not only needs design the optimization algorithm itself, but also the algorithm for local processing of the gradient estimates. Many such algorithms have been proposed in recent years; see, for instance, [12), [1], [6]. [15], [29], [16]. and the references therein for privacy constraints [28]. [7], [30], [18].
'Supported by NSF-CCFF SCCF-18466 1846300 (CAREER), NSF-CCF- 18151181
i Part of this work was done while at IBM Research, supported by a Goldstine Postdoctoral Fellowship. 'Supported by Ph.D. fellowship from Wipro Ltd. Supported by grant from Robert Bosch Center for Cyber Physical Systems (RBCCPS), Indian Institute of
Science.
The full version of this paper [2] contains the proofs of all results discussed here, as well other additional details.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

[14], [25], [4], [11], [17], [20], [19], [27], and the references therein for communication constraints; [24, 26] for computational constraints. However, these algorithms primarily consider nonadaptive procedures for gradient processing (with the exception of [14]): that is, where the scheme used to process the gradients at any iteration cannot depend on information gleaned from previous iterations. As result, the following question remains largely open:
Can adaptively processing gradients improve convergence in information-coontrriieed optimization?
In this paper, we study this question for optimization over both convex and strongly convex function families and under the three different local constraints mentioned above: local privacy, communication, establish lower bounds convergence rates
and computational. For each of these constraints, which hold even when the gradients are adaptively processed. In the next sections, we cover prior related work, before elaborating on our results and techniques.
1.1
Prior work
The model studied here can be viewed as extension of the classical query complexity model in [22]. Without information constraints, [5] study this setting and provide a general recipe for proving convex optimization lower bounds for different function families. Specifically, they reduce the problem of optimization with a first-order oracle to a mean estimation problem whose probability of error is lower bounded using Fano's method (cf. [31]). While our work also relies on reduction to mean estimation, we deviate from their approach, using instead Assouad's s method to prove lower bounds for various function families. This different approach in turn enables us derive lower bounds for adaptive processing of gradients.
setting, motivated by privacy concerns, [12] consider the problem where the gradient estimates must pass through a locally differentially private (LDP) channel. How-
In the information-constrainn
ever, in their setting the LDP channels for all time steps are selected at the start of optimization algorithm - in other words, the channel selection strategy is nonadaptive. Similarly, [20] and [19] consider similar problem and impose the constraint that the gradient estimates be quantized to fixed number of bits. They, too, fix the quantization channels used at each time step at the start of optimization algorithm. In contrast, in this paper, we allow for adaptive channel selection strategies; as a result, the lower bounds established in these papers do not apply to our setting, and are more restrictive than bounds.
The results of Duchi and Rogers [13] for Bernoulli product distributions could be combined with our construction to obtain tight lower bounds for optimization in E [1,2] under LDP constraints, but would not extend to the entire range of p. The work of Braverman, Garg, Ma, Nguyen, and Woodruff [9] on communication constraints, also for E [1, 2). is relevant as well; however, their bounds on mutual information cannot be applied directly, as their setting (Gaussian distributions) would not satisfy almost sure gradient oracle assumption.
[14] provide adaptive quantization schemes for convex and &g Lipschitz function family. While the worst-case convergence guarantees for the quantizers in [14] are similar to those in [7] and [20], it shows some practical improvements over the state-of oftte-of-the-ar for some specific problem instances. This suggests that while adaptive quantization may not help in the worst case for non smothh convex optimization, it may be useful for a smaller subclass of convex optimization problems.
1.2 Our contributions
We consider a general formulation for first-order optimization under local information constraints where the output of the gradient oracle must be passed through a channel W selected from a fixed channel family W. This family W captures the information constraints; see Section 2.3 for description of the channel families corresponding to our constraints of interest. Specifically, the gradient is sent as input this channel W. and the algorithm receives the output. In each iteration of the algorithm, the channel to be used in that iteration can be selected adaptively based on previously received channel outputs by the algorithm or channels to be used throughout can be fixed upfront, nonadaptively. The detailed problem setup is given in Section 1. We obtain general lower bounds for optimization of convex and strongly convex functions using W. when adaptivity allowed. These bounds are then applied to the specific constraints of interest to obtain main results.

---

Our first contribution is in showing that adaptive gradient processing does not help for some of the most typical optimization problems. Namely, we prove that for most regimes of local privacy, communication, or computational constraints, adaptive gradient processing has nearly the same convergence rate as nonadaptive gradient processing for both convex and strongly convex function families. As a consequence, this shows that the nondaptive LDP algorithms from [12] and nonadap- tive compression protocols from [20]. [19] are optimal for private and optimization, respectively. In another direction, under computational constraints, where we allowed to compute only one gradient coordinate, we show that standard RCD (cf. [10, Section 6.4)), which employs uniform (nonadaptive) sampling of gradient coordinates, is optimal for convex and strongly convex function families. This proves that adaptive sampling of gradient coordinates does not improve over nonadaptive sampling strategies.
As previously discussed, prior work both the local privacy and communication-constraainn settings concerned itself with the family of convex functions, with no lower bounds known for the more restricted family of strongly convex functions, even for nonadaptive gradient processing protocols. The key obstacle is the fact that during the reduction from optimization to mean estimation, the known difficult case for the strongly convex family, even when analyzed for nonadaptive protocols, leads to an estimation problem using adaptive protocols, and the lack of known lower bounds for adaptive cooomationnconstraiiiii this difficult case has gradients that can depend the query point which in turn can be chosen based on previously observed channel outputs, an issue which does not arise in the case of the convex family, where the lower bounds are derived using affine functions for which the gradients do not depend on query point. We manage to circumvent this issue, by relying on a different reduction which lets us capitalize on recent lower bound for adaptive mean estimation. Crucially, this recent lower bound does apply to adaptive estimation algorithms as well, bringing the last missing piece to the puzzle. This lets derive lower bounds for both convex Lipschitz and strongly convex functions under adaptive gradient processing.
estimation prevented this approach from succeeding. Specifically,
For general function classes, the results discussed above show that adaptive processing of gradients does not help. This begs the question of whether there are natural function families where adaptive gradient processing can lead to significant savings. Our third contribution is to provide an example of such a family: specifically, we exhibit a natural optimization problem (entailing & minimization) under computational constraints for which adaptive gradient processing provides polynomial factor improvement in convergence rates compared to nonadaptive processing. The key feature of this optimization problem is that the resulting gradients have structured sparsity; adaptivity then allows for a two-phase optimization procedure, where the algorithm first "explores" to find the structure before, in second phase, "exploiting" it obtain more focused information about the function to minimize. However, nonadaptive gradient processing protocols cannot easily exploit this hidden structure, as finding it is now akin locating a needle in a haystack; and thus exhibit much slower convergence rates.
Notation:
Throughout the paper q denotes the Hölder conjugate of p (that is. 9 p 1)). V b and a A b denote... max (a, by and min (a, b). respectively. We denote by log the logarithm to the base 2 and by In the logarithm the base e. The informaatonn-hheortiiic quantities, such as mutual information and KL. divergence, are defined using In. In In"(a) denotes the number of times In must be iteratively applied to a before the result is at most 1. {ei,..., denotes the standard basis of Rdd
2 Setup and preliminaries
2.1 Optimization under information constraints
We consider the problem of minimizing unknown convex function f: X + R over its domain X using oracle access to noisy subgradients of the function (cf. [22]). In our setup, the gradient estimates supplied by the oracle must pass through channel W chosen from a fixed set of channels W. and the optimization algorithm π only has access to the output of this channel. The channel family W represents our information constraints.
A channel W with input alphabet X' and output alphabet V denoted W: X + V, represents the conditional distribution of the output of randomized function given its input. In particular, W (-|z) is the conditional distribution of the channel given that the input is x E X.
3

---

In detail, the framework is as follows:
1. At iteration the optimization algorithm makes a query for point Si the oracle O.
2. Upon receiving the point 2;, the oracle outputs ((zz), where I [ā(z)) æx. E a.))) and fz(z,) is the subgradient set of function f at zt.-
3. The subgradient estimate ((xx) is passed through channel W. E W. and the output of the channel W; along with outputs of channels {Wi )eett,,,,, where [M] = (l,...,70 n,., can be used by the first order optimization algorithm further update 24 2++1-
Denote by π the first-order optimization algorithm which is allowed T queries to the oracle O and, after the ith query, gets back the output Y, with distribution Wz(- (xx)). Denote the of all such optimization algorithms by II,
Our goal is to select channels Wis and an optimization algorithm to get small worst-case opti- mization error. Two classes of channel selection strategies are of interest: adaptive and nonadaptive.
Adaptive channel selection strategies can be described as follows. The channel W₁ selected at time t may depend on the previous outputs of channels [ [etttet- Specifically, denoting by Ye and Y respectively, the output alphabet and the output for the channel used at time t, the adaptive channel selection strategy S (S1. ................................ Sr) over T iterations comprises mappings S y²-1 W taking Y,,.. Y as input and yielding a channel in W as output. We write Sw.r for the collection of all such channel selection strategies.
For nonadaptive channel selection strategies, we fix the channels (We) E Wobi through which all the gradient estimates must pass at the start of the optimization algorithm." Denote the class of all nonadaptive strategies by SWi-
We measure the performance of an optimization protocol π and a channel selection strategy S for given function f and oracle O using the metric E(ʃ, O, n, S) defined as
n, = E f(xT) min f(x) zEX
(1)
where the expectation is over the randomness in TT-
For various function and oracle classes, denoted by O, the channel constraint family W, and the number of iteration I", we will characterize the adaptive minmax optimization error
Ex ExXX,
inf inf sup g(f.0,,,5
(2)
=Elly SESw.r (1,0)E0
and the corresponding nonadaptive minmax optimization error NA (X, *elly SES (FOOEE
inf inf sup
O(),
Since nonadaptive channel selection strategies are a subset of adaptive channel selection strategies, we have NA (ONAAAX,, (X,O,T, 2 8 (x,
2.2 Function classes
We define the function classes we consider, and structured optimization problem for which we show that adaptivity in the choice of channels helps.
Convex and ép Lipschitz function family, Our first set function families are parameterized by a
number p E [1, oo]. Throughout, we restrict ourselves to convex functions over domain X, i.e.,
f(Xu (1 A)y) (z)) (1 A)S(w), Ye, y E X, Aλ [0, 1).
(4)
Further, for a family parameterized by p. we assume that the subgradient estimates returned by the first-order oracle for a function f satisfy the following two assumptions:
E [Ø)()) E Of(x), (Unbiased estimates)
(5)
Pr (r(1lg(=)113 < B2 x) 1, (Bounded estimates)
(6)
'That is. W. is selected independently of the 1 gradient observations received by the optimization
algorithm step

---

where (x) is the set of subgradient for f at z and q : :=ppppp-a 1) is the Hölder conjugate of p. We denote by Oc.p the set of all pairs of functions and oracles satisfying assumptions (4), (5), and (6).
We note that (5) is standard in stochastic optimization literature (ef- [22], [21], [10], (5]). To prove convergence guarantees
first-order optimization in the classic setup (without any information constraints on the oracle), it is enough to assume E' [llĀ(>)]1? < B². We make slightly stronger assumption in this case since the more relaxed assumption leads technical difficulties in finding unbiased quantizers for gradients; see [20, 19J. Also, observe that assumption (6) imposes a restriction on the functions allowed in this class. Note that by (5) and (6) for every z E X there exists a vector E (f) such that وااوا < B. Further, since f is convex, f(x) f(y) S g" (x y) for every g E (x), whereby f((z) f(y) < B - yllp. Namely, f is B- B-Lipschitz continuous the ep norm."
Remark (Convergence rate for convex functions). Without any information constraints (when gradient estimates are directly observed), upper bounds of Sa B:Dg/l and o DDdd'/3-1/> on the error are achievable for & and l.p p E [2, so), convex family, respectively. Moreover, these rates are orderwise optimal. In particular, from [5, Appendix CJ we have the following result: For = 1, 2logd stochastic mirror descent algorithm with mirror map $a(x) = - I where a = dlo achieves the orderwise convergence rate; for p E 00], stochastic gradient descent achieves the orderwise optimal convergence rate.
/T
/T
Strongly convex and l2 Lipschitz function family. We now consider a special subset of the convex and Eg Lipschitz family described above, where the functions are strongly convex. For a >> 0, function f is a-stroogly convex on X' if the function h defined below is convex:
hxx) = f(x 1=l.
Va E.
We denote by Ose the set of all pairs of functions and oracles satisfying (4), (5), (6), and (7), where (6) is satisfied for q 2.
The strong convexity parameter a is related to the parameter B, the upper bound on the & norm of the gradient estimate. We state a relation between them when the domain X' contains an foo ball of radius D centered at the origin, as this will be of interest while proving lower bounds.
Lemma 1. For any X 2 {a: ||م| S D}. we have 2 D2
Remark 2 (Convergence rate for strongly convex functions). Without information constraints, 2B stochastic gradient descent achieves an upper bound of T+I ([21)) for the strongly convex family, and this rate is optimal; see [5].
Mean estimation
optimization problem. Our final optimization problem entails structured le minimization problem. We first define s-block sparsity which is needed for our function classes.
Definition 1. A vector E I2d is s-block sparse if (i) there exists an such that Vy 0 for all j & {is + I,..., minfi(s + 1), d}} and (ii) the non-zero coordinates have the same absolute value in [0, 1]. Let B, be the set of all s-block sparse vectors in d dimensions."
For B., we define function fo over X - [-1, 1]a as fe(x)- -lc--13,,0 X. Further, associate with each function f, an oracle O, as follows. Let X be a random variable over (-1, jd with E [X] = u (i.c., its mean is the s-block sparse vector V parameterizing fu). The gradient estimate output of the oracle O, at and at time is 2(x X,), where {2, are i.i.d. random variables with the same distribution as X. Note that the expected value of this gradient estimate is fz()).
Definition 2. Let Obisp,s denote the collection of pairs of functions and oracles described above.
Observe that the first-order optimization described above is the standard & mean estimation problem cast as an optimization problem, since the function fo minimized at x= = E [X]. Moreover, the essential information supplied by the oracle are the i.i.d. samples X, (since the optimization algorithm already knows the queries .:).
7 Thee same could he said under the weaker assumption E. [[]((T) [2] S B².
We assume throughout, for simplicity, that d/s is integer.
5

---

2.3 Information constraints
We describe three specific constraints of interest to us: local privacy, communication, and computation. The first two are well-studied; the third arises in procedures such as random coordinate descent.
Local differential privacy. To model local privacy, we define the e-locally differentially private (LDP) channel family Wprivee
Definition 3. A channel W: : Rd + R& is e-locally differentially private (s-LDP) ifr all a, E Rd.
W(Y E E x=
W(Y S s S
for all Borel measurable subsets S of Rd.
of We denote by Wpriv.e the set of all E-LDP channels.
When operating under local privacy constraints, oracle's subgradient estimates are passed through a e-LDP channel, and only the output available the optimization algorithm. Thus, the data of individual users, accessed in each oracle query, remains differentially private, a notion of privacy that now widely agreed upon.
Communication constraints. To model communication constraints, we define the Wean,r the r-bit communication constrained -onnsiiicctiiocccostraaneddd channel family, as follows.
Definition 4. A channel W: Bd > {0, 1)" constitutes an r-bit communication channel. We denote by Weon, the set of all r-bit communicatiorrcconstriieedd chunnels.
Computational constraints. For high-dimensional optimization, altogether computing the subgradi- ent estimates can be computationally expensive. Often in such cases, one resorts to computing only few coordinates of the gradient estimates and using only them for optimization ([24, 26]). This motivates the oblivious sampling channel family Wat., where the optimization algorithm gets to see only one randomly chosen coordinate of the gradient estimate.
Definition 5. An oblivious sampling channel W is channel W IR - Rd specified by a probability vector (pi)se(d) i.e., a vector p such that pi 2 0 for all i and Eieig P; 1. For an input g E IR. the output distribution of W is given by W (g(()e g) = Pi, Vi E [d]. We denote by Wobi the set of all oblivious sampling channels.
Therefore, at most one coordinate of the oracle's the gradient estimate can be used by the optimization algorithm. Further, this coordinate sampled obliviously to the input gradient estimate itself. We note that the special case of p 1. corresponds to sampling employed by standard Random Coordinate Descent (RCD) (cf. [10, Section 6.4)), where at each time step only one uniformly random coordinate of the gradient is used by the gradient descent algorithm.
3 Main results
For E [1, oo] and > 0, let (D) C Rd: of subsets of Rd whose Ep diameter is at most D. In stating our results, we will fix throughout the parameter B 0, the almost
maxz,vex || ullp I D} be the collection
bound on the gradient magnitude defined in (6), as well as the strong convexity parameter a defined in (7) (which, implicitly, is required to satisfy Lemma I). Throughout this section, our lower bounds minmax optimization error focus on tracking the convergence rate for large T, a standard regime of interest for the stochastic optimization setting.
3.1 Lower bounds on locally private optimization under adaptive gradient processing
Throughout, we consider E [0, 1). namely the high-privacy regime.
Convex function family. For the convex function family, we prove the following lower bounds. Theorem 1. Letp 1, [0, 1), and D 0. There exists constant co such that for T Rdd/e?),
Co
DB
sup O0,, W Woriv.e) (E)
VT
2

---

Theorem 2. Let E 12,00,, E [0, 11, and D > 0. There exists a constant such that for T 2id2///" )=²)
DDD2//221//p
sup (22 T, Wpriv.)) X)X,(D)
2
VT
2
Remark (Tightness bounds for convex functions and LDP constraints). [12, Theorem 4 and 5] provide nonadaptive LDP algorithms which show that Theorem I is tight up logarithmic factors for p 1 and Theorem 2 is tight up to constant factors for all 20]. Therefore, adaptive processing of gradients under LDP cannot significantly improve the convergence rate for convex function families.
Interestingly, for p 1, [12] also provide slightly stronger lower bound of 20 dlogg for /T
nonadaptive protocols, which matches the performance of their nonadaptive protocols up to constant factors. This points stronger lower bound for adaptive protocols to match the performance of the nonadaptive algorithm of [12], does there exist a better adaptive protocol? We believe that the latter option is correct, and conjecture that the Vd dependence is tight even for adaptive protocols.
minor gap in our understanding of adaptive protocols: Can establish
From Remark 1, the standard optimization error for l and lp- p [2, 00], convex family blows up by a factor v when the gradient estimates are passed through an e-LDP channel.
Remark 4. We note that techniques also yield lower bounds for p E (1,2), range that has been considered in prior works on information-coontruinneed knowledge. These bounds are given in the full version [2]. Deriving tight upper bounds for this range is an interesting open question, which we leave for future exploration.
constrained gradient processing to the best of our
Strongly convex family. We prove the following result for strongly convex functions.
Theorem 3. Let p = 2, E [0, and D > 0. There exists constant 0 such that for T
2
Ω
B2 d
D
20
B² d aT
sup (x Onc, T, Wpriv.e) XEX2(D)
>
62
Remark (Tightness of bounds for strongly convex functions and LDP constraints). One can use
stochastic gradient descent with the nonadaptive protocol from [12, Appendix C.2] to obtain
nonadaptive protocol with convergence rate matching the lower bound Theorem up to constant factors, establishing that adaptivity does not help for strongly convex functions.
From Remark 2, the standard optimization error for strongly convex functions blows up by a factor of 2 when the gradient estimates are passed through an E- s-LDP channel.
3.2 Lower bounds communication-oostrainne optimization
Convex function family. For convex functions we prove the following lower bounds.
Theorem Letp There exists a constant co > 0 such that for N, M(d/r), and D
Go DB
d
sup Oc,1, T. Wcmnr) (e),(D)
Z
VT
dAr
Theorem 5. Letp E (o). There exists constant co > such that for r E N, and T and >
= d² Ar
D2d///2211/
Co DB
d dAT
sup E*XX, T, Weo.,. XEX,(D)
VT
d
VT
Remark 6 (Tightness of bounds for convex functions and communication constraints). In the full version of the paper [2], we provide a scheme which matches the lower bound in Theorem 4 up to constant factors for any Since each coordinate of oracle output is bounded by B for p 1,

---

simply can use an unbiased 1-bit quantizer for each coordinate. The proposed scheme uses such quantizer for each coordinate and makes d/r repeated queries the oracle for the same point, but gets 1-bit information about v different coordinates in each query.
the quantizer SimQ from [19] with k = and appropriate mirror descent algorithms to get upper bounds that match the lower bounds in Theorem 5, up to an additional Ollo d) factor. For p we can use the quantizer RATQ from [20] to improve this match to an O(InIn d) factor.
For p [2, o0]. we
From Remark 1, the standard optimization errors for & and lp. p E [2, oc], convex family blow up
by a factor of V dhr and bits.
d
V
d#/r
där respectively, when the gradient estimates are compressed
d'2""
Remark 7. Finally, remark that techniques also extend lower bounds for communication- constrained optimization of l. E (1, convex family, which we prove the proofs section, but the known upper bounds in the previous works not tight for this family for S d.
Strongly convex family. We prove the following result for strongly convex functions.
Theorem 6. Let p = 2 and
There exists a constant Co > such that, for r E N and
T
B² a D
Co B
sup ("(X,Oec T, Weon.)) (xX)(D)
aT
dAr
Remark (Tightness bounds for strongly convex functions and communication constraints). We note that the nonadaptive scheme RATQ in [20] along with stochastic gradient descent matches the lower bound in Theorem up in In' d factor for 2(I In d).
From Remark 2, the standard optimization error for strongly convex functions blows up by factor of when the gradient estimates are compressed to r bits.
3.3 Lower bounds on
optimization
Our motivation for studying the oblivious sampling channel is to derive lower bounds for random coordinate descent methods. Since such optimization methods are natural to the & space, we restrict our attention to the convex family and &g Lipschitz family in this section.
Theorem 7 (Convex family). Lef p 2. There exists constant cn D > 0,
0 such that, for T ((d) and
/DVDDB
sup XEXx(D)
VT
The standard Random Coordinate Descent (RCD) (see for instance [10, Theorem 6.6]), which employs uniform sampling, matches this lower bound up to constant factors. The optimality of standard RCD reinforces the folklore approach of uniformly sampling coordinates for random coordinate descent unless there is an obvious structure to exploit (as in [23]). This establishes that adaptive sampling strategies do not improve over nonadaptive sampling strategies for the family Wob1 Also from Remark 1, the standard optimization error for l convex family blows by factor of / d when the gradients are sampled obliviously.
Theorem 8 (Strongly convex family). Let p = 2. There exists constant co >> such that for
= (dd B² and > 0
CpdB²
sup
XEX;(D)
aT
Once again, standard RCD algorithm matches this lower bound, which shows that adaptive sam- pling strategies do not improve over nonadaptive sampling strategies for strongly convex optimization. Further, from Remark 2, the standard optimization error for strongly convex family blows up by factor of /d when the gradients sampled obliviously.

---

3,4 An example where adaptivity helps
Until now we showed that for information-constriinndd constrained first-order optimization over the standard function and oracle classes using popular channel families, adaptive channel selection strategies offer no better convergence guarantees than nonadaptive strategies.
We will consider the function and oracle class as Osisp.s (Definition 2) using information constraint family as Wob1 (Definition 5) and show that adaptive channel selection strategies strictly outperform the nonadaptive ones. Towards that, we first derive a lower bound for nonadaptive strategies, and then we present an adaptive scheme which improves over this bound.
Recall that eN (X, Obtap.s, T, Wab1) 2 Ex (xt, Obisp.s, T, Won.). We will show strict separation between the two quantities: for s == dd, the error incurred by any nonadaptive strategy is at least ((d3/2/T) while there exists an adaptive strategy achieving error O(dlog d)/T).
Lower bound for nonadaptive channel selection strategies. We show the following.
Theorem 9. Let X |-1,1] 1|6. Then, there exists absolute constants co. Ct, C2 > 0, such that for any 2 6g and T 2 eıd, we have
sd T
EAA (X, Obisp,s; T, Wob1) 2 C2
An upper bound for adaptive channel selection strategies. We now prove a O(dlog/d/s) 3)) upper bound on the error for adaptive strategies, by exhibiting an adaptive channel selection strategy and optimization procedure term Adaptive Coordinate Descent (ACD), denoted AAC
First, note that the only new information that the oracles present at each iteration is about the random variable X with E [X] underlying the oracle associated with some function fo (z) || e/12 in our family Obiep.e. Thus, the problem at hand becomes that of estimating the mean v using independent copies of X. See the supplemental for detailed description.
Keeping this in mind, our adaptive channel selection strategy is divided in two phases, each making T/2 queries to the oracle: the exploration phase and the exploitation phase. In the exploration phase, we select each block's first coordinate as a representative coordinate for that block and query each representative coordinate (sd(2d) times. At the end of this phase, an estimate of the mean is formed for each representative coordinate. Next, we select the block whose representative coordinate has the sample mean with the highest absolute value. Then, in the exploitation phase each coordinate of the selected block is queried T/(2s) times. Our optimization algorithm estimates the means of coordinates in the selected block using the sample mean of the values received in the exploitation phase. For the rest of the coordinates, the mean estimate is zero. Finally, our algorithm returns the overall estimated mean vector as the estimated minimizer of the function.
Recall that in RCD, the oracle returns the gradient along randomly chosen coordinate. contrast, ACD gets gradient for particular coordinate in each round, and the choice of the coordinates used in the exploitation phase depends on the observations of the exploration phase. Also, we note that is possible to interpret our procedure as coordinate descent algorithm. However, for the ease of presentation, we simply retain the form above. The performance TACD is characterized below.
Theorem 10. Fix any S < d, and (f,O) E Orssp... 9 Let Ý E Id be the point returned by TCC after I oracle queries to O. Then,
36d In 2x²
T
4 Sketch of proof for our lower bounds
The proofs of all our lower bounds follow the same general template, summarized below.
Step 1. Relating optimality gap to average information: We consider family of functions
g (go : { 11,, 13d) satisfying suitable conditions and associate with it a "discrepancy metric"
9 That is, f(x) = (x) = ||æ ul for some with block sparsity structure and O gives independent copies of random variable X with [X]

---

(G) that allows us to relate the optimality gap of any algorithm to an average mutual information quantity. Specifically, for V distributed uniformly over {-1, 13 we show that the output or of any optimization algorithm satisfies
d()(5) 6
- 1
Eigv (xT) min gv (+)) xEx
Y is the channel output for the gradient in the fth iteration and Y == (V....., Yr). Heuristically, we have related the gap to optimality to the difficulty of inferring V by observing Y1, YY. We note that the bound above is similar to that of [5], but instead of mutual information T(V A AYT) we get average mutual information per coordinate. This latter quantity amenable to analysis for adaptive protocols.
Step 2. Average information bounds: To bound the average mutual information per coordinate,
+ (VV(i) YT), we take recourse recently proposed bounds from [3]. These bounds hold for Y which output of adaptively selected channels from fixed channel family W, with i.i.d. input X = (X1,.... Xr) generated from family of distributions {Pv. E { {- 1,, 1)d. We view the output of oracle as inputs X and derive the required bound. While results [3] provided bounds for Wpriv,e and Wcom.r. we extend the approach to handle Wos1. Specifically, under smoothness and symmetry condition on {Po, 2 E 11]1) which has parameter associated with it, we show the following. For |X| < oo and X; == {a(1)= E X3, E [d], we have
C Ty², $ 2
Σ (I(V(A
where the constant C > 0 depends only on (Pu, E (-1,+1)d) and, denoting, is given by C' = (max [x - 1) maXaex max,e (- max
P.o: (X(==2(0)
p. (X((=x()
Step Use appropriate difficult instances: To prove lower bounds for the convex family, we will use the class of functions Go = (x)( E 1 defined on the domain X' {o Rd || S b) comprising functions go given below:
go(x)= = a Σ (o( - vi)) b), Vr E E
-())
On the other hand, to prove lower bounds for the strongly convex family, we will use the class of functions Gec (g)(z)) E (-1, 1}43 on X fa E Rd || s bj given by
+ 20)(1)
[x) 1- 102((i) 1 (1))) U
(v(x)=
Σ iml
where,for i E [d]. fot (I) (1))
(x(i)+b) (z()))))) and f. (x) -1) -1' (x(() 2)
Step 4. Carefully combine everything: We obtain our desired bounds by applying Steps and 2 to difficult instances from Step Since the difficult instance for convex family comprises linear functions, the gradient does not depend on z. Thus, we can design oracles which give i.i.d. output with distribution independent of the query point 2t, whereby the bound in Step 2 can be applied. Interestingly, we construct different oracles for = 11 and p 2 2.
However, the situation is different for the strongly convex family. The gradients now depend on the query point Ft, whereby it is unclear if we can comply with the requirements in Step 2. Interestingly, for communication and local privacy constraints, we construct oracles that allow us view messages YT as output of adaptively selected channels applied to independent samples from a common distribution p... While it is unclear if the same can be done for computational constraints as well, we use an alternative approach and exhibit an oracle for which we can find an intermediate message vector Z,, ... Zr such that V and YT are conditionally independent give z" and the message ZT satisfies the requirements of Step 2.
For tuples of random variables X and Y. I(X A Y) denotes the mutual information between X and Y.
10

---

References
[1] Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. pages 308-318. ACM, 2016.
[2] Jayadev Acharya, Clément I. Canonne, Prathamesh Mayekar, and Himanshu Tyagi. Information- constrained optimization: can adaptive processing of gradients help? arXiv preprint arXiv:2104.00979, 2021.
[3] Jayadev Acharya, Clément I. Canonne, and Himanshu Tyagi. General lower bounds for interactive high-dimensional estimation under information constraints. arXiv preprint urXiv:2010.06562... 2020.
[4] Jayadev Acharya, Christopher De Sa, Dylan J Foster, and Karthik Sridharan. Distributed Learning with Sublinear Communication. drXiv:1902.1/259 2019.
[5] Alekh Agarwal, Peter Bartlett, Pradeep Ravikumar, and Martin Wainwright. Information- Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization. IEEE Transactions on Information Theory. 5(58):3235- 3249, 2012.
[6] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Bren- dan McMahan. cpSGD: Communication--ffiiiiiii and differentialll--rriaal distributed SGD, Advances in Neural Information Processing Systems, pages 7564-7575, 2018.
[7] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effiiii SGD via gradient quantization and encoding. Advances in Neural Information Processing Systems, pages 1709-1720, 2017.
[8] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):667-175, 2003.
[9] Mark Braverman, Ankit Garg, Tengyu Ma, Huy Nguyen, and David P. Woodruff. Com- munication lower bounds for statistical estimation problems via a distributed data processing inequality. Proceedings of ACM Symposium on the Theory of Computing (STOC' 16), pages 1011-1020, 2016.
[10] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4))231-357, 2015.
[11] Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. Breaking the cummuumicttoo--rivveeaauuuuuuu trilemma. arXiv preprint arXiv:2007.1 /707, 2020.
[12] John Duchi, Michael Jordan, and Martin Wainwright. Privacy aware learning. Journal of the ACM (JACM), 61(6):1-57. 2014.
[13] John C. Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1161-1191. PMLR, 2019.
[14] Fartash Faghri, Iman Tabrizian, Ili Markov, Dan Alistarh, Daniel Roy, and Ali Ramezani- Kebrya. Adaptive gradient quantization for data-parallel sgd. Advances Neural Information Processing Systems, 2020.
[15] Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. arXiv preprint arXiv: 1.07971, 2019.
[16] Antonious M Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of federated learning: Privacy, communication and accuracy trade-offs, arXiv preprint arXiv:2008.0711 07180, 2020.
[17] Zengfeng Huang, Ziyue Huang, Yilei Wang, and Ke Yi. Optimal sparsity-sensitive bounds for distributed mean estimation. Advances in Neural Information Processing Systems, pages 6371-6388 2019.
11

---

[18] Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. communication. Frontiers in Applied Mathematics and Statisties, 4:62, 2018.
[19] Prathamesh Mayekar and Himanshu Tyagi. Limits on gradient compression for stochastic optimization. Proceedings of the IEEE International Symposium of Information Theory (ISIT' 20), 2020.
[20] Prathamesh Mayekar and Himanshu Tyagi. RATQ: A universal fixed-length quantizer for stochastic optimization. Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS' 20), pages 1399-1409, 2020.
[21] Arkadi Nemirovsky. Information- complexity of convex programming. 1995. Available Online attp://www/h isye. .atecch. wdw/ne- http:/eemmirove/LL__BE..... pdf.
[22] Arkadi Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley series in Discrete Mathematics and Optimization, 1983.
[23] Yu Nesterov. Efficiency of coordinate descent methods huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-36) 2012.
[24] Yurii Nesterov. Introductory lectures on convex optimization: basic course. Springer Science and Business Media, 87, 2013.
[25] Ali Ramezani-Kebrye Fartash Faghri, and Daniel M Roy, Nuqsgd: Improved communication efficiency for data-parallel sgd via nonuniform quantization. arXiv preprint arXiv: 19Xv:1908,00077 2019.
[26] Peter Richtárik and M Takác. Parallel coordinate descent methods for big data optimization, 2012.
arxiv e-prints. arXiv preprint
[27] Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. arXiv preprint arXiv:2002.cm 08958, 2020.
(28) Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-paralled distributed training of speech dnns. Fifteenth Annual Conference of the International Speech Communication Association, 2014.
[29] Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private SGD via just-in-tine time compilation and vectorization. arXiv preprint arXiv:2010.09063, 2020.
[30] Ananda Theertha Suresh, Felix X Yu, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. Proceedings of the International Conference on Machine Learning (ICML' 17), 70:3329-3337, 2017.
[31] Bin Yu. Assouad, Fano, and Le Cam. In Festschrifi for Lucien Le Cam, pages 423-435. Springer, 1997.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We did our best to put our results in context, and ac- cuaretly describe our contributions and results (including assumptions and applicability of our results.
(b) Did you describe the limitations of your work? [Yes] Our theorem statements and the introduction describe the assumptions, and range of applicability, of our results.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our results are concerned with the theoretical foundations of distributed optimisation; while some applications may down the line have negative (or positive) socictal impacts, they are too far remote from our work for us to be able to assess them.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "iUbNoNaoWa", "reviewer": "Reviewer_3YxU", "summary": "In this paper, authors consider lower bounds for convex optimization where the stochastic gradient estimate is only partially observed. This sort of information constraint situation arises naturally when optimizing under local differential privacy, communication constraints, or randomized coordinate descent. The unique aspect of this paper is that they study *adaptive* information constraints, where the parts of the gradient that are revealed are chosen adaptively at each iteration by the algorithm, rather than fixed at the start of the algorithm. \n\nThe overall main result is that adaptively selecting gradient information does not provide any improvement on the worst case convergence rates, compared to non-adaptive selection. A proof sketch of this technique is provided at the end of the paper. An interesting positive result is a class of functions under which adaptively selecting gradient information does improve the convergence rate.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is extremely well written. My background is not in lower bounds, but I was able to understand the landscape of current work and the main contributions of the authors. Moreover, authors clearly described several technical aspects at a high level -- including obstructions for applying previously developed non-adaptive lower bound constructions to the adaptive setting. In this sense, the paper is extremely well written and a joy to read.\n\nBecause I do not work in the development of lower bounds, I cannot (with strong authority) comment on the relevance and novelty of the methods and results in the paper. However, based on the author’s description of the landscape of results, I believe that the results are timely and interesting. I was especially interested to see that the authors included a class of functions where adaptive selection of gradient information does provably improve over non-adaptive methods.\n\nI recommend this paper for acceptance at NeurIPS 2021. I have found only one typo: In line 344, the output is referred to as $x_T$ but the display equation uses $\\hat{x}$. I believe these should be the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "All ethical concerns are addressed.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "WJ4ZYPEj6EF", "reviewer": "Reviewer_bUwU", "summary": "\nThis paper concerns information theoretic lower bounds on \ninformation-constrained first order optimization: where\nthe access to gradients from the first order oracle\nis through a possibly adaptive noisy channel. As\nexamples of this model, they introduce privacy (via\ndifferentially private channels), communication (via\nr-bit channels) and computation (via coordinate-wise restricting\nchannels) constraints. For all of these cases, the paper\nproves lower bounds showing (for most parameters considered)\nthat non-adaptive algorithms are nearly tight. They also\ndemonstrate a simple group-sparse mean estimation problem\nwhere adaptively processing the gradients strictly\nimproves over the rate, in terms of dimension/sparsty dependence, \nnon-adaptive strategies.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper is overall well-written, the contributions are clearly laid\nout and the question is of traditional interest to the NeurIPS community.\nThe only potential weakness of the work is that its contributions are\nlargley lower bounds, and thereby not algorithmic. \nBased on this, I would recommend its acceptance to the program. \n\nMinor comments:\n1. L.168-170 do not strictly follow since the set of vectors\nE(hatg(x)) need not fully cover the subgradient. However, the\nlipschitzness argument does seem fine.\n2. Thms 1, 2 (and possibly later): why not include p \\in (1, 2)?\nThe bound is not harder or more complicated to state, it is the same as p=1 from the \nsupplement. \n3. Similar to point 2: why is this range for p not covered in the algorithmic\nliterature? Any particular reason this regime is not interesting for applications?\n4. Minor grammar errors in L.258 266\n5. The notation in the mutual information (\\vee) is possibly non-standard. Please\neither use I(X; Y) or explain this earlier in the text, particularly since you use\nthe same as \\min, \\max operators in the bounds. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper being theoretical in nature does not have currently foreseeable societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "M0yDWcsiYWu", "reviewer": "Reviewer_Z9A8", "summary": "Here, all the references are to the supplementary material section.\n\nThis work studies the problem of first-order optimization under local constraints, where at each step an agent computes a sub-gradient and the sub-gradient should pass through a channel. Then, output of the channel will be available for the optimization algorithm. The act of the channel is to constraint the information of the sub-gradient. Their idea is to construct an adaptive method, where at each step the computed sub-gradient depends on the previous outputs of the channel, in advance. They call this approach adaptive and the main goal of the authors is to investigate whether there is any gain in using adaptive methods compared to nonadaptive ones. \n\nAssumptions on the objective function: Denote the objective function as $f$, which is defined on a compact subset of $\\mathbb{R}^d$. They studied the above problem in the case that:\n1. $f$ is Lipschitz with respect to $\\ell_p$-norm, where $p \\geq 1$.\n2. $f$ is (strongly) convex.\n\nDifferent types of information constraints: Performance of an adaptive method has been studied in this paper over three different types of information constraints:\n1. Local differential privacy (defined in page 7)\n2. Communication constraints (defined in page 8)\n3. Computational constraints (defined in page 8)\n\nContributions: They used a novel technique for obtaining lower bounds by using Asoud's lemma (outlined in the lines 80 to 87, on page 3 and Section 4) for the adaptive methods. By comparing their derived lower bounds with the upper bounds for the non-adaptive scheme, they concluded that there is no gain in using adaptive methods, in general setting. \nAt the end, they studied adaptivity for the special case of structured $\\ell$_2 minimization (defined in Section 5.1, page 32.), for computational constraints (oblivious channels). First they derived a lower bound for non-adaptive setting, then they proposed an adaptive algorithm (Algorithm 1, page 28) and concluded that adaptive methods significantly outperform non-adaptive ones in this specific example.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. All the theoretical claims are well supported. \n2. The paper is well written. The proofs are mathematically clear. Also, the authors provide an adequate literature review and give enough comparison between their results and the prior works.\n3. I am not convinced of the motivation of the work. What is the motivation of the authors to study adaptive techniques in LDP and communication constraints? Are there important examples of functions for these constraints, where adaptive techniques outperform non-adaptive ones, which encouraged the authors to study the problem in a general case?\n4. They didn't provide enough justification why the example in Section 5 (structured $\\ell$_2 minimization with an oblivious channel)  is important in practice.\n5. Since the main novelty of the work is to derive lower bounds for adaptive algorithms, I encourage the authors to discuss this more in section 3. It would be nice if authors provided a technical comparison with Archarya et al. (2021), and outlined how their method distinguishes itself. \n\nI would like to thank the authors for their response. The authors addressed my concerns in the rebuttal. After reading other reviews and the authors' feedback, my assessment of the paper remains unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discuss the limitations of their work. I also pointed out some, along with suggestions to improve the paper in the Main Review section.\n\nSince the paper is quite technical, I except no direct social impact at this point.", "review_text": "", "extra_scores": {"ethical_concerns": "The authors briefly discuss the limitations of their work. I also pointed out some, along with suggestions to improve the paper in the Major Review section.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this generally a good paper although not entirely without (minor) flaws. Please take the reviewers comments in consideration when preparing a revision. The answers provided by the authors were given due consideration. 

Decision: Accept (Poster)