Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the question of optimizing a strongly convex function f given a zeroth' order oracle for the function. This is one of the most studied problems in optimization and there is a wealth of literature on the problem.

The twist considered here is that the zeroth-order oracle has outlier noise: on some points in the domain, the oracle can output an arbitrary value (completely corrupted). The fraction of the domain that is corrupted is assumed to have a volume equal to that of a ball of radius K. 

Clearly, since we are allowed to completely corrupt a ball of radius K, one cannot expect to get more than K close to the true minimizer even with an unbounded number of queries. Interestingly, the authors also show that if the function f is alpha-strongly convex and beta-smooth, one, in fact, cannot even get better than $K \sqrt{\beta/\alpha}$ close with an unbounded number of queries. The paper also shows that one can get relatively close: If the function f is alpha-strongly convex and beta-smooth, then one can get to a point that is $O(K \sqrt{\beta/\alpha})$ close and this with $\approx O(d (\beta/\alpha)^2)$ queries. 

The model and results are nice. One drawback though is that the results only apply to high dimensional scenarios. 
main_review: Lower bound: The lower bound that one cannot get better than $O(K \sqrt{\beta/\alpha})$ is obtained by explicitly constructing two functions whose minima are $K\sqrt{\beta/\alpha}$ apart but differ from each other only on a ball of radius $K$. This critically relies on the space being high-dimensional.

Upper bound: The authors first use plain gradient descent to argue that one can indeed get $O(K \beta/\alpha)$ close relatively easily. The authors then bootstrap by a clever argument of averaging the gradients in a ball of radius $2K$. Once again, as we are in high dimensions, the fractional volume covered by a ball of radius $K$ in a ball of radius $2K$ is exponentially small and as such most points will give the correct answer.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider a convex minimization problem with a certain noisy oracle. Specifically, the function to be minimized is assumed to be alpha-strongly convex, and beta-Lipschitz (referred to as alpha-beta nice). It is also assumed that we have access to the function values everywhere except for an ellipsoid with bounded volume. Within the mentioned ellipsoid, the oracle may select the values "adversarially" so as to confuse the minimization algorithm. In this setting, the authors first show the existence of two alpha-beta nice functions that differ on a bounded ball and such that their minimizers are a certain distance apart. This provides a bound on what one could possibly achieve. Next, they provide two algorithms that guarantee to produce approximate minimizers that are sufficiently close to the minimizer (within the bounds permitted by the first negative result), along with an upper bound on the number of queries that the algorithms make.
main_review: The paper is a purely theoretical paper that delivers what it promises. It is clearly written, and well-presented, with detailed proofs in an appendix. I think some of the intuition is hidden in the proofs, but that doesn't make the paper unreadable. There are no experiments to demonstrate how the framework could be useful in practice, and I think that's a weakness of the paper. While the authors place their noise model within the context of others' works, I think a stronger motivation is lacking -- especially since the whole framework (e.g., the selection of the family of functions to work with) relies on it. Overall, I think this paper would be of high interest to a few readers -- and I'd welcome authors' comments that may serve to broaden the readership.

I have only a few minor comments : 
- In presenting the model (starting line 54), the description reads as if there's no restriction on C, other than its volume. It becomes clear later that we also need C to be contained in an ellipsoid -- in fact, otherwise the oracle could have simply chosen to corrupt each query, adding up to a total of zero volume, since there are only a finite queries. Please clarify this part.

- About Thm 3.1 : While I don't have any objection to this statement, I found it a bit pessimistic. How about a statement in the following form : "Given an arbitrary (alpha-beta) nice f, there exists (alpha-beta) g such that f and g differ only on a set contained in a ball of radius R.". Does such a statement follow from your result? If not, is it possible that some functions are "harder" for the oracle to scramble? 

- In the appendix, Remark D.1 mentions that, for simplicity, the gradients will be assumed to be exact, with a certain probability. Does this really not affect any of the coming proofs? When you work with a bounded error in the gradient (again with the same small probability), if the proofs extend easily, why do you make this assumption? The appendix is already detailed, so you might as well drop this assumption. If there's a compelling reason to keep it, I'd suggest to make it part of the statements of the results.

-----------------------------------------
Update after author responses : 

I read the other reviews and the authors' responses. 
Generally, I agree that the model considered is a bit unusual, but I think the manuscript is potentially interesting for a small community, and might spark a more useful discussion. I'm still somewhat positive, and will keep my score as is.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of convex optimization using a zeroth order oracle with adversarial noise.  In particular, the paper studies the setting where there is some convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ and the learner may interact with an oracle that returns the value of $f$ at a given point except the oracle is corrupted on some set of measure equal to $\textsf{Vol}(B(0,K))$ (where $B(0,K)$ is the ball of radius $K$) on which the oracle may return an arbitrary value.

The paper gives an algorithm that outputs a point that is within $K \sqrt{\beta/\alpha}$ of the minimizer of $f$ (where $\beta/\alpha$ is the condition number of $f$).  They also prove a matching information-theoretic lower bound that no algorithm can guarantee to get closer than $K \sqrt{\beta/\alpha}$.  At a high level, their algorithm is based on estimating the gradient at each point using the corrupted zeroth order oracle and then running gradient-descent.
main_review: The overall contributions are ok.  The presentation is also reasonable, but occasionally handwavy, which is understandable due to space constraints.  One point that was not clear to me was the following: in the algorithm description, what does it mean for a ball centered at $\widehat{g}$ to trap another vector $g_i$?  Does it just mean that the ball contains the vector?


I have some concerns about the overall significance of the result because of limitations in the problem setup.  My concern is that the authors rely on the dimension being sufficiently high so that failure probabilities from sampling are small.  But in high dimensions, a ball of radius $K$ only represents an exponentially small fraction of the entire domain so the result is really only able to deal with an exponentially small fraction of noise.

Also, one minor comment: it seems that with $\alpha$ and $\beta$, the only thing that actually matters is the ratio $\beta/\alpha$, which is just the condition number of the function.  This is a very standard concept in convex optimization but is never referenced.

After Author Response and Reviewer Discussion: Thanks for the clarifications!  I do believe that this paper could be important in driving further research and have updated my score accordingly.

I am a bit confused about a few points in the author response though. In terms of fraction of corruptions, the paper assumes that the learner is given a starting point within some radius $R_0$ of the optimum $x^*$ (which is of course a fine and standard assumption).  Thus, the learner is optimizing over a bounded set.  My point was that almost all of the points in this set are actually uncorrupted and even within any ball of radius $2K$, almost all of the points are uncorrupted.

Also in terms of the comment about $ \log (\beta/\alpha) \leq d$, I'm not sure I understand the comparison to gradient descent needing $\beta/\alpha \leq poly(d)$. The algorithm presented in this paper still needs $d poly( \beta/\alpha)$ runtime so it needs the stronger condition as well to run in polynomial time in high dimensions.  Moreover, gradient descent works in any dimension, even low dimensions such as $d = 1$, whereas the algorithm presented here actually needs the dimension to be high.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper studies the problem of minimizing a convex function given an evaluation oracle to it -- with the twist that the oracle has outlier-noise: for some parameter K, a volume equal to that of a ball of radius K can be corrupted adversarially (thus, when evaluated at any point inside this ball, the oracle can return an arbitrary, potentially adversarial noise). This immediately puts a lower bound of K on the distance to the optimum. The paper proves a non-trivial lower bound of K\sqrt{\beta/\alpha} on the best distance guarantees to the optimum for any \alpha-convex \beta-smooth function and shows that one can achieve this bound within a constant factor with poly(\beta/\alpha) queries. 

The idea of the algorithm is simple and natural (get somewhat close to the optimum by gradient descent and then do a clever bootstrapping by averaging gradients in a ball). But the paper studies and proves a clean result about a basic problem of interest to optimization and machine learning community broadly construed. We recommend acceptance.  
Decision: Accept (Poster)