Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
This paper concerns information theoretic lower bounds on 
information-constrained first order optimization: where
the access to gradients from the first order oracle
is through a possibly adaptive noisy channel. As
examples of this model, they introduce privacy (via
differentially private channels), communication (via
r-bit channels) and computation (via coordinate-wise restricting
channels) constraints. For all of these cases, the paper
proves lower bounds showing (for most parameters considered)
that non-adaptive algorithms are nearly tight. They also
demonstrate a simple group-sparse mean estimation problem
where adaptively processing the gradients strictly
improves over the rate, in terms of dimension/sparsty dependence, 
non-adaptive strategies.
main_review: 
The paper is overall well-written, the contributions are clearly laid
out and the question is of traditional interest to the NeurIPS community.
The only potential weakness of the work is that its contributions are
largley lower bounds, and thereby not algorithmic. 
Based on this, I would recommend its acceptance to the program. 

Minor comments:
1. L.168-170 do not strictly follow since the set of vectors
E(hatg(x)) need not fully cover the subgradient. However, the
lipschitzness argument does seem fine.
2. Thms 1, 2 (and possibly later): why not include p \in (1, 2)?
The bound is not harder or more complicated to state, it is the same as p=1 from the 
supplement. 
3. Similar to point 2: why is this range for p not covered in the algorithmic
literature? Any particular reason this regime is not interesting for applications?
4. Minor grammar errors in L.258 266
5. The notation in the mutual information (\vee) is possibly non-standard. Please
either use I(X; Y) or explain this earlier in the text, particularly since you use
the same as \min, \max operators in the bounds. 

limitations_and_societal_impact: The paper being theoretical in nature does not have currently foreseeable societal impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

The 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.
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.

Because 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.

I 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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Here, all the references are to the supplementary material section.

This 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. 

Assumptions 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:
1. $f$ is Lipschitz with respect to $\ell_p$-norm, where $p \geq 1$.
2. $f$ is (strongly) convex.

Different types of information constraints: Performance of an adaptive method has been studied in this paper over three different types of information constraints:
1. Local differential privacy (defined in page 7)
2. Communication constraints (defined in page 8)
3. Computational constraints (defined in page 8)

Contributions: 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. 
At 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.
main_review: 1. All the theoretical claims are well supported. 
2. 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.
3. 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?
4. They didn't provide enough justification why the example in Section 5 (structured $\ell$_2 minimization with an oblivious channel)  is important in practice.
5. 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. 

I 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. 
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.

Since the paper is quite technical, I except no direct social impact at this point.
review_title: null

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)