Approximate optimization of convex functions with outlier noise
Authors: Anindya De
Sanjeev Khanna
Huan Li
Hesam Nikpey
Venue: NeurIPS 2021 Poster (2021)
Keywords: gradient descent
convex optimization
optimization with noise
convex interpolation

Abstract: We study the problem of minimizing a convex function given by a zeroth order oracle that is possibly corrupted by {\em outlier noise}. Specifically, we assume the function values at some points of the domain are corrupted arbitrarily by an adversary, with the only restriction being that the total volume of corrupted points is bounded. The goal then is to find a point close to the function's minimizer using access to the corrupted oracle.

We first prove a lower bound result showing that, somewhat surprisingly, one cannot hope to approximate the minimizer {\em nearly as well} as one might expect, even if one is allowed {\em an unbounded number} of queries to the oracle. Complementing this negative result, we then develop an efficient algorithm that outputs a point close to the minimizer of the convex function, where the specific distance matches {\em exactly}, up to constant factors, the distance bound shown in our lower bound result.

Approximate optimization of convex functions with outlier noise
Anindya De University of Pennsylvania anindyad@cis upenn edu
Sanjeev Khanna University of Pennsylvania sanjee sanjeevOcis. upenn edu
Huan Li University of Pennsylvania huanli@cis upenn edu
Hesam Nikpey University of Pennsylvania hesam0cis upenn. edu
Abstract
We study the problem of minimizing a convex function given by a zeroth order ora- cle that is possibly corrupted by outlier noise. Specifically, we assume the function values at some points of the domain are corrupted arbitrarily by an adversary, with the only restriction being that the total volume of corrupted points is bounded. The goal then is to find a point close to the function's 's minimizer using access to the corrupted oracle.
We first prove a lower bound result showing that, somewhat surprisingly, one cannot hope to approximate the minimizer nearly as well as one might expect, even if one allowed an unbounded number of queries the oracle. Complementing this negative result, we then develop an efficient algorithm that outputs point close to the minimizer the convex function, where the specific distance matches exactly, up constant factors, the distance bound shown in our lower bound result.
1 Introduction
Unconstrained convex optimization is among the most well-studied problems in mathematical optimization and has extensive applications in machine learning [7]. In the classic unconstrained convex minimization problem, we are given oracle access to a convex function f IRd - R, and seek to efficiently find point ž that is close to the minimizer of f (call it xt)!" ! To obtain meaningful guarantees for approximating the minimizer xx, one needs to make certain assumptions on the convexity and smoothness of f- In partieular, f is commonly assumed to be a-strongly convex and 8-smooth for some 3 > a > 0. This means that, when f is twice differentiable, its second derivative in any direction between and B. For of presentation, we will say convex function is (o,,3) -nice if it satisfies these two conditions.
It is well known that the minimizer of (a, 3)-nice function can be approximated arbitrarily well in polynomial time by the classic gradient descent algorithm, or its accelerated version due to Nesterov [18]. To formally state the performance of these two algorithms, let us suppose (a, -ice function f Rd - is given to us as a zeroth order oracle, which returns the function value f(x) on any input point æ E Rd. Then we have:
Theorem 1.1 ((7)). Given any initial point Do E Rd and > O, the classic gradient descent algorithm outputs point s.f. || x" ll2 < using ((d(8/a) log I|50 |==l=="|| oracle queries.
Sometimes, instead of finding a point close to x, the goal is to find a point whose function value is close to f(x"), However, as point out later, it is more natural study approximations in the domain in setting.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Theorem 1.2 ((18)). Given any initial point E B and e > 0, the accelerated gradient descent
algorithm outputs a point T' s.f. || x" 20112 using O(d B/a log [[ oracle queries.
We note that the quantity 3/0 is called the condition number of the function f. The efficiency of a convex minimization algorithm is usually measured with respect to such a quantity.
Given that the complexity of convex minimization with exact oracles has been well understood, a natural question is "can we still minimize a convex function efficiently if the oracle is some extent inaccurate?" There has in fact been a rich body of work in efforts to answer this question. Roughly, they can be divided into two categories based on their assumptions on the oracle's 's inaccuracy.
The first category studies the case when the oracle is corrupted by stochastic noise" - namely, the errors of the oracle are assumed to be random and independently drawn from some distribution [10, 20, 19J. Notice that as the oracle is correct in expectation, one can obtain good estimates to the true values efficiently by averaging over sufficiently many points in small neighborhood. As result, it is still possible to approximate the minimizer x" to within arbitrarily small distance in polynomial time. The main focus of these results is thus to obtain optimal algorithm efficiency, ideally matching that of Nesterov's ss accelerated gradient descent.
The second category, on the other hand, considers the adversarial noise. That is, the errors are no longer drawn from certain distributions, but rather are added udversarially, while obeying certain constraints. A representative such model is what we call peintwise-boundee noise model [22, 5], in which the only assumption on the noise is that it is pointwise bounded in magnitude; other than that, the specific perturbation oracle to return, on an input point x, a value in the range [f(x) c, f()) + <] (absolute errors) or (f (1 + (x)) (relative errors), for some > O. [5] shows that when the errors absolute and e is on the order of 1 1/d, there is polynomial time algorithm that can find a point with function value arbitrarily close f(==). Whereas [22] shows that, in sharp contrast, when e is about 1/vd or larger, no polynomial-time algorithm is able to find point with function value within some constant error of (x*), for both absolute and relative errors.
each point can be arbitrary. Formally, it is allowed for the
Our model. Following the second line of research above, in this paper we study another type of adversarial noise model, called outlier noise model, which can be seen as natural variant of the nointwise-bounder noise model in [22, 5]. In this model, the only assumption we make is a bound on the "number" of points corrupted by the noise; apart from that, we do not assume any bounds on the magnitude of the errors on the corrupted points. Formally, we are given access to an exact zeroth order oracle of a function f that differs from the true convex function ff only on a set C C Rd with the guarantee that the volume of C is at most that of a d-dimensional ball of radius K, for some K > O. Notice that although is bounded in volume, for any x E C, f(x) and f(x) can differ arbitrarily.
Though variants of each other, both the pointwise- pointwise-boundd noise model in [22, 5] and our model may be considered as special cases of more general type of adversarial noise model, namely the by-bounded noise model. To see this, let us write the noise as function 17 Rd - I, such that the noisy zeroth order oracle given to us corresponds to the function f f 17. Then, in the (absolute) pointwise-bounded noise model, is bounded in -oom (they assume || I c). whereas in the outlier noise model, 17 is bounded in fnrmr (we assume ||7/|aa I vol (radius- K ball)). will certainly be an interesting future direction to explore what can be achieved for minimizing convex functions with general boubddde noise.
We would also like to point out that in our noise model, it is more natural to consider getting as close as possible to x as opposed to finding point with function value close to f fx*). This is because our only ussumption on the noise is that the corrupted region C, which is in the domain of the function f. bounded in volume, and in particular, it may be located around x". Therefore, we believe makes the most sense to measure the quality of the solution of minimization algorithm by its distance to the optimal in the domain (specifically, how the distance compares with the corruption radius K).
Our results. Let first consider what one might expect achieve in the outlier noise model. By the observation made above, it is not hard to see that we cannot hope to always find a point that is within distance K of the minimizer x", as an adversary could potentially corrupt some radius- K ball
2 This model more often deals with the first order oracle, which gives the (noisy) gradient V Vf(x) at point
2

---

around x², making it impossible for us to know where the true minimizer lies. However, is it possible to obtain distance bound that is close to K (e.g. O(K))
Our first result in this paper is a lower bound showing that, somewhat surprisingly, this goal is in general impossible achieve, even for algorithms that are allowed an unbounded number of queries to the oracle. In fact, our lower bound indicates that the best distance bound one can hope for is at least ( /3/a). where we recall that a., are the "niceness" of the function. This result is a consequence of the existence of two (a, - functions that only differ in a small region of the domain. but whose minimizers are sufficiently far apart. We then develop, as our second result, an efficient algorithm that finds point within distance O(K /B/a) of the minimizer x", thus matching our lower bound up to constant factors. Roughly, our algorithm performs two stages of gradient descent, using approximate gradients computed from the noisy zeroth order oracle.
We state our results formally in the theorems below. For simplicity, let say zeroth order oracle of a function f is K- K-corrupted if it is perturbed by an outlier noise of corruption radius K.
Theorem 1.3 (Lower bound; formal version appears as Theorem 3.1). For a, B, K > 0 and suffi- ciently large d, there exist two (a, 3)-nice functions fo- fi R - R which satisfy the following conditions: (i) The E--distance between the minimizers of for fi is 9K( /3//3//a), (ii) The total volume of points where fo and f1 differ is at most that of a d-dimensional ball of radius K.
To see the implication of this theorem, consider an adversary that randomly picks an index i E {0, 1} and lets f; be the true convex function, but always uses fo as the K K-corrupted oracle. Then no matter which point our algorithm outputs, with probability at least 1/2 over the randomness of i, it is Q(K V 3Baa) away from the minimizer of the true convex function fi-
Theorem 1.4 (Algorithm; formal version appears as Theorems 5.1). Let az, 3, K > 0 and d be sufficiently large. There is an algorithm that, given access to a K-corrupted oracle of an (a,, 3)-ncce function f Rd + R. and an initial point xn Rd, makes Ö (8 /a²) log I1:00 - xx 1I3 queries to the oracle and outputs a point 't s.l. | - x=1 S O(K v B/ox). Here x² is the minimizer of s-
We note that in both our results, our conditions d are roughly that d 2 22log B/a). In other words, we require the function's 's condition number 3/a a to be most 20(4), quantity exponential in d.
Our techniques. We now briefly describe our techniques used to obtain the above results.
Our lower bound proceeds by proving the existence of two (a, -icce functions fo and fi s.t. (i) they differ only in an ellipsoid with volume at most that of a ball of radius K; (ii) their minimizers are at f2-distance 2((K' K /3/a)-aau -away from each other. As mentioned above, this implies that even with infinitely many queries, one cannot approximate the minimizer x= to within distance o(K / B/aa).
More concretely, we start by letting fu be a simple (a, 3) -nice quadratic function whose minimizer is at the origin. Then the existence of our desired function fi will follow by two steps: first we show that there exists another function f' with certain good properties, then we obtain f1 by taking a piecewise combination of fo and f'. Specifically, the properties that we need f' to satisfy is as follows: (i) f' (a. 3)-niee: (ii) both the function values and the gradients of fo and f' agree on all points on the periphery of an ellipsoid & that is centered at the origin and has bounded volume; (iii) the minimizer of f' has coordinate of the form (Ω(K) v 3/ ..,,... 0). We show that this essentially boils down to a convex function interpolation task where the function values and gradients at some infinitely many points are given. To this end, we adapt an interpolation result from [23], which was proposed to accommodate interpolation from finitely many points, to prove the existence of f'. Finally, we construct the function fi by letting f1 f inside the ellipsoid E, but fi = fo outside of E.
For the upper bound, our algorithm proceeds in two stages. In the first stage, we come to within distance ((K(B/a) of the minimizer x* and in the subsequent stage, we improve to /B/a).)).
The first algorithm essentially follows a gradient descent, but using an approximate gradient at each point x, we set up system of linear equations, where
step. In order estimate the gradient each equation adds a constraint on the derivative at x along uniformly random direction. There are however two types of noise in these equations, one from using a zeroth order oracle compute first
Here and throughout the paper, we write Ō(f) denote O(f ploy f)).
3

---

order information, and the other from the outlier noise added to the oracle. While we can solve this noisy linear system with good enough accuracy via an exhaustive search, we show that using an LP decoding routine in [12], we can solve it more efficiently in polynomial time. We note that using the latter is only to improve the running time, as both approaches result the same query complexity.
However, the one bottleneck in this approach that at any point, the ball of radius < K around could potentially be (nearly) completely corrupted. Thus, get a meaningful estimate of the gradient, we have to sample points which are more than distance K ffr apart. This tradeoff eventually allows us get ((((3a)))
to the minimizer.
To get to the optimal closeness of O(K //aa), we start point which is guaranteed to be OK (3/ (8/a²) -close
the true minimizer. We now consider the function which is defined as the average of f in a ball of radius (say) 2K. It is not hard to verify that I continues to be (a, - Moreover, the minimizers of f and f can be shown to be O(K / /Boooe to each other. Thus, it suffices to get close to the minimizer of f. We will do so by simulating a gradient descent on f. It therefore boils down to how we can efficiently approximate the gradients of f.
By the definition f. the gradient V f(x) is also equal to the average the gradients Vf(y) over all points y within distance 2K of æ. This suggests that we can approximate vf(x>) by averaging the gradients Vz(y) at sufficiently many randomly sampled y and bounding the error using concentration inequalities for sums of random vectors. Now key observation is that, since these y's are sampled randomly from radius 2K -bal,, it is highly likely that each sampled sits in a mostly uncorrupted neighborhood, as long as the dimension is sufficiently high. Consequently, we can use the LP decoding approach above to obtain an accurate estimate of the gradient at each of these points.
Prior work on noisy convex optimization. Other than the works mentioned above, noisy convex optimization has also been investigated in the context of multi-armed bandits and regret minimiza- tion [2, I]. In the direction of convex optimization under adversarial noise, the early results fact date back to the 90s by [3]. Specifically for the pointwise-bounded noise model, there are subsequent works such as [21, 24, 17] that have improved on the guarantees of [5].
Due to space limitation, we include some other related work in Appendix A.
Organization. In Section 2, up few notations and give some basic definitions and technical preliminaries. In Section 3, we prove our lower bound result. In Section 4, we give first algorithm that gets to within distance ((K(3/a) of x². In Section 5, we give second algorithm that gets us to within distance O(K / B/a) ( of xx. Section 6, we propose several future directions.
Preliminaries
Note that due to space limitation, we defer some of the preliminaries to Appendix B.
While there are many known equivalent definitions of strong convexity and smoothness of a function, the specific ones that we use in this paper are as follows.
Definition 2.1. A function f Rd + IR is 3-smooth if it is differentiable and for all pairs v, E Rd we have V ( < B | y/l
Definition 2.2. A function f IRd + R is a-strongly convex if f(x) - || is comex
We next set up notations of a ball and the uniform distribution over
Definition 2.3. Let r(x, def {y lyy - I|| S r) denote the ball of radius r centered at x. Let all points in the ball B(z,r).
U(xrr) denote the uniform distribution
As result, the fraction of corrupted volume in ball B(z, r) is Pigre(ee))) f(v)), where we recall that f denotes the corrupted version of f-
For second algorithm in Section 5, will need to consider the "average" function, whose value at a point x is the average of f(y)'s 's where y is within some distance of x.
' 'eere and going forward, all norms are lz- no-mo unless stated otherwise

---

Definition 2.4. For any 0, define the function Fr as fx(x) def By-e((z.)) [f(v)].
is not hard to verify the strong convexity and smoothness of fr: Lemma 2.5. If f is a-strongly convex and B-smooth, fo is also a-strongly convex and 3-smooth.
As result of a--ttrong convexity and mmsootthssss, we can upper bound the distance between the minimizers of f and fr by O(r/B/aa).
Lemma 2.6. Let x", Be the minimizers of I and Jr respectively. Then ||=* - F. S 2r 2 B/oo. A proof of this lemma is included in Appendix B.
3 An O(K V 3/a) lower bound
In this section we show that getting D(K/B/o -close to x² is the best we can hope for even if we are allowed query the function value every point of the domain. We will prove this by showing that when the dimension is sufficiently high in terms of 3/a, there exist two a-strongly convex, 3-smooth functions that differ only in ellipsoid of volume equal ball of radius K, but whose minimizers are QKK / 3/aa)-)00 -apart.
Theorem 3.1. Given 0 < S 8 with 1 log < d where d is the dimension, and a K > O, there exist two a-strongly convex, B-smooth functions whose values differ only an ellipsoid of volume equal to radius-K K ball, but whose minimizers are R(V / K)-far from each other.
In order to prove Theorem 3.1, we shall prove several intermediate lemmas first, which are built on the interpolation results from [23]. We remark that the main results in [23] are stated for interpolating a set of finitely many points, while for our purpose we need to interpolate infinitely many. Therefore we cannot use their results directly black-box manner, but instead have to make certain adaptations.
3.1 Some interpolation results from [23]
First let us define the notion of (a, 3). -)-ieetrpollaiiitty
Definition 3.2 ((a, 3) -iittrrpllabbiliyy. Suppose we are given a set of (possibly infinitely many) tuples ((a,, 9v. fi) where each vi, St E TR fi E TR. Let R2o, E (+20U(+)o) where a 33 We say this set is (a. -ntteerrpoll there is proper and closed convex function f Rd + [U that is a-strongly convex and 8-smooth such that for all E gi E af(r;) and f(x:)) = St. where 0f(x,) denotes the set of subgradients of at di.
Note here that when be smooth and thus f is not necessarily differentiable; when 3 < oc, the condition 9: e 0f((;;) is equivalent to 9:
0, we only require be convex. When xc, do not require f to
(2,) as the gradient is unique at any point when is differentiable.
The following two lemmas are proved in [23]. The first lemma enables us to reduce the (a, B)- interpolation of some tuple
the (0, -intteerrpolannonn of another tuple set, while the second lemma allows us to further reduce it to the (a', oc) -o)-interpolation of some other tuple set. We note that although [23] only states these lemmas for sets containing finitely many tuples, their proofs work for sets containing infinitely many tuples as well.
Lemma 3.3. Given a set of (possibly infinitely many) tuples {(x gin ft) where Fi, E Rd. ft E IR and < < B < too. The following two statements are equivalent:
1. filres is (a, i)-tterrpple
2. { (1r.. oxr, Sa | (22) J is (0, 3 oi-inttrpollable.
Lemma 3.4. Given set of (possibly infinitely many) tuples {(x; gr. Ji) where Ti. ga E Rdd fe E IR and < < S +00. The following two statements are equivalent:
1. [( 9t, filler is (0, interppllle
5

---

2. I1, 9: fi))ser is (eft,,,o)iiterpolabba
Then as in [23], by alternately applying Lemmas 3.3 and 3.4 twice each, we are able to reduce any (a, intterrpoolatoon problem (0, -nteerrpolaannnn problem. where we only want interpolate some points with a proper and closed comvex function. Formally, we have the following lemma, whose proof is deferred to Appendix C.
Lemma 3.5. Given set of (possibly infinitely many) tuples { 9h. fi) where Rt.gt E R4 ft E IR and & a < S too. The following two statements are equivalent:
1. {( fillerr is (a, 9)-interpolable.
2.
{
B-aa
Sm: 9t B-a 9: - azii, B-a
oz d:
+ fa
Bal|z1l1
)} 2(3-a) 2(3-a)
11 1
is (0, iinterllltee.llla
igr
3.2 Our lower bound
We first show that there exists an 52(1) -Str)--tro convex, -mmo-oho function whose minimizer 1 f-2r from the origin, but whose function values and gradients agree with the quadratic function || all points the surface of unit ball. Formally, have the following lemma. For ease def
of presentation, let us define X-1 {a: || 1} and similarly X>1
{x ||=||| 2 1}. We also
write 61 (1, ..., 0)² to denote the first standard basis vector.
Lemma 3.6. Let f(x) def ||=||² which is 2-strongly convex and 2-smooth. There exists --strongly convex, 16-smooth function such that
1. f's minimizer is fee.
2. For all X=1 we have f(x) f(x) and vf(x)= Vz))).
The proof of this lemma is deferred to Appendix C. Roughly, the proof consists of three steps: (i) formulate proving the existence of as (5. 16)-interpolation problem; (ii) use Lemma 3.5 to reduce it the (0, oo) -ntterrrpootto of some infinitely many points; (iii) explicitly construct proper and closed convex function that does interpolate these points.
Now by taking a piecewise combination the functioon f in Lemma 3.6 and the quadratic function || we can show that there exists an (())-strongly convex, O(1)-smooth function ff whose minimizer is 1/2-far from the origin, but whose function values and gradients agree with ||==|] on every point with 22-norm greater than or equal to
Lemma 3.7. Let fxx def | which is 2-strongly convex and 2-smooth. Define f such that f(x) = f(x) [| < and f(x) f(x) otherwise [||=|| > 1). Then we have
1. f --strongly convex and 16-smooth.
2. f's minimizer is fee.
3. For all X21 we have f(x) = f(x) and vf(x)= Vs(x).
The proof of this lemma is included in Appendix C.
Then by scaling the domains of f. f in Lemma 3.7, we prove that for any 2 1, when the dimension sufficiently high in terms of K,, there exist two 12(1/k)) (1//:)-strongly convex, ((1)-s((oo))))) functions whose function values and gradients agree on every point outside of an ellipsoid of volume equal to unit ball, whose minimizers are /k/2-apart. Here x. shall thought of as 3/aa where 3 (
Lemma 3.8. Given K 2 1 with log x & where the dimension. Let def (1/x)=4 [1/2, 1]. Let Saxd DIAG(K, ...... Define s(x) = T S z. which (2/n))-stronll) convex and (2/7)- smooth. Let X = (x: s(x) 2 1). Also define 3(x) = f(S-1/2 Then we have
1. & is
convex and (16/7)-smoonl

---

Lx
2. 8's minimizer is 2 61.
3. For all E Xs21 we have $(x) = s(x) and V$(x) = (s(
Finally, by further scaling (the domain and the function values of) 8, 8 in Lemma 3.8, we can prove Theorem 3.1. The proof' of Lemma 3.8 and Theorem 3.1 are both included in Appendix C.
4 An ((((((()))))))))
algorithm
In this section we give an algorithm GDSTAGEI that finds a point ((K( to the minimizer of f. GDSTAGEI essentially implements gradient descent algorithm, but uses approximate gradient computed from the noisy oracle at each step. To begin with, we present a subroutine GR GRADIENTCOMP for computing the gradient point where small neighborhood is mostly uncorrupted.
Algorithm 1: GRADDENTCOMP(C,RR. B,T,)
Input :Rd IR, IR > 0, and 0.
Output: g E IRd.
Randomly choose 1000d pairs of points a1, b1 .... 1000d. 1100 in the ball B(x, r).
2 Query the function values f(a,). f(b)) for all j = 1, ...... 1000d.
3
Let g E Rd be any vector such that, for at least 800d of the j's, the following holds:
TT aa) (f(b)) -(as)
S BT.
(1)
|bb -
ajll
If such g exists, set y be arbitrary vector.
We summarize the performance of GRaDIENTCOmP below, with the proof deferred to Appendix D. Essentially, the error in the gradient computed by GRadiENtCOmp tends to zero as T -
Lemma 4.1. Fix d > O and O. There exists a function err(r) satisfying lim,- err(r) such that the following holds. Fix any TRd and such that the radius-T ball centered is mostly uncorrupted:
Prymu((ar)) (s()) /(m)
100
Then we have that with probability 2-33, the vector returned by GRADIENTCOMP satisfies
lgg vf(x)) S err(r).
(3)
The number of queries made by GRADIENTCOMP is Odd)
We now describe GDSTAGEI Algorithm 2. Its performance is characterized Theorem 4.2.
Algorithm G.GSTAGEII.... a, 3, xo, Ro, 8)
Input : -> RR, 0 < < B, 2o E Rd. Ro 2 ||10 x² Output: à E Rd.
and & (0, 1).
Ro Let the iteration count be T + 100 log [3/ajK
for t= 0,..0,,.....
do
Let the sample count be + 200 ())
Sample random points 91, .2.... Us in the ball B(x,, 99K).
5 Compute gradients 9, <- GRADIENTCOMP(f y4 T)
-) for some sufficiently small > 0.
Find vector I E Idd such that at least (2s) of the are within euclidean distance 99.5,3K of g: if such exists, set 9 to be an arbitrary vector.
Perform descent step: Ft+1 < Fz 3
8
return Zz-

---

Theorem 4.2. Let d 2 2. Given an initial point zo with I|20 -xx1 || - Ro and a Ó E (0, 1). the algo-
rithu GDSTAGEI returns point &t with - S 10000(8/a) with probability 1 ò. where x* the minimizer of f. The number of queries made by GDSTAGEI is ((d(B/a) log [B/a)R log(1 (16)).
Ro
Crucial to proving this theorem is to show that the gradients used by GDSTAGEI are accurate enough:
Lemma 4.3. Let d 2 The 9 computed at Line 6 of GDSTAGEI satisfies with probability 1 T that || f=(x)) & 200
Full proof's of Theorem 4.2 and Lemma 4.3 are presented in Appendix D.
A note on the running time of our algorithms. While we are mainly concerned about the query complexity, we remark that both of our algorithms above can be implemented in polynomial time.
For GRADIENTCOMP, all steps except Line 3 are easily seen to be implementable in polynomial time (in particular, linear time). Therefore it suffices to show that Line 3 can be done efficiently.
Claim 4.4. A vector satisfying the condition at Line of GRADIENTCOMP, if it exists, can be found in time polynomial in d.
Our proof of this claim proceeds by presenting a poly(d)-time algorithm based on an L.eddcoo routine in [12]. Therefore let us first introduce the specific result that we need from [12].
Let A E Raxd be a matrix and z E 12d be a vector. Consider the linear system Ar Az, which x = z is clearly solution. If n 2 d and A has full rank, then we can retrieve the vector given A and Az by solving the linear system Ar Az in polynomial time using, c.g., Gaussian elimination.
Now suppose the RHS of the linear system is corrupted by some noise e E RR", and we are only given A and the corrupted RHS Az e, then can we still retrieve the vector efficiently? [12] showed that under certain assumptions, we can obtain good estimates of z in poly-time by linear programming.
Theorem 4.5 ([12)). There exist constants p² 0.239 and y 2 1 such that the following holds. Suppose n 2 7dd and Anxd's 's entries are drawn independently from a standard Gaussian distribution. Suppose also the noise e can be written as e G1 + C2 where ||eq llo S p''.. Then given and A + e, we can find in polynomial time a vector z! s.t. || 2 ll1 S O(1ee2llax) for any 2 RR..
Basically, this theorem assumes that the noise can be decomposed into the sum of two parts, one with small nonzero support, and the other with small entry-wise magnitude. Then the eg-error of the solution is on the order of the largest entry-wise magnitude of the second part of the noise.
Proof of Claim 4.4. Let us define a matrix B E R 1000dxd whose 7th row is equal to (b.-a,) [b [bb-- where
a, by's are the sampled points at Line I of GRADIENTCOMP. We also define vectors b, d R 1000d with b(i) [(==) and i(i) f(b:)-((a.) where is the input point of GRADIENTCOMP.
[|b.-a. Notice that each b(i) is the inner product of the 7th row of B and V V (z), and therefore we have fV b. Consequently, given B and we can retrieve V (xx) by solving the linear system By = b (y are the variables). Thus our goal becomes solving this linear system when only B and i (a.k.a. a corrupted version of b) are given. While this looks like the task in Theorem 4.5, note that the entries of B are not drawn from independent Gaussian distributions, so we will need go step further.
[|b,-a.1l
-o As the a, b,'s 's are sampled uniformly at random from ball, each row (b-aa)" of B is unit vector
with uniformly random direction. It is well known that a vector with independent standard Gaussian entries also points to uniformly random direction. In fact, we can sample a d-dimensional such vector by a three-step process: (i) sample a unit vector with a random direction; (ii) sample a length l from the x2 di-tiiiibttionn with d degrees of freedom (i.e., the sum of the squares of d independent standard Gaussians); (iii) scale the unit vector by vt. In light of this, let us generate diagonal matrix D E Re 10000x 1000d such that each D(i, i) is independently sampled as in step (ii). Then we consider the linear system 11/ By- = / to which y = V f=) a solution. Notice that we now have that each entry of D1/2 B follows a standard Gaussian.
By thinking of D as corrupted version of Db, we then need to show that the noise def Db/2(6 b) can be written as ei +e2 such that ||e llo I p² (1000d) and ||e2lloo is small. To this end,
8

---

we notice that for each i such that both a; b; are uncorrupted, we have by 8-smoothness that
b(0) b(0) (z())² (b; ai) |b - all
f(b:) f(a;) S (((r),
(4)
l|6 -0-aa aill
where 7 is the radius of the ball B(a,, 7) from which a,, b, are sampled. Thus, if B(x,, r) is mostly (say 99%) uncorrupted, with probability exp(-I(dd), (4) holds for most (say 90%) of the i's.
Also, by standard Markov's inequality and Chernoff bounds, with probability 1 - ---xe-((S(())) for most (say 99%) of the i's we have (ii, I (dd). Combining this with (4), have for 80% of the i's that VD(i, i) b(t) b(i) ((vd3r). implying the existence of C12 62
61 C2 and lle I 0.2(1000d), ||ez cl - d(v))r). This means that by Theorem 4.5 we can use linear programming to find g with llg V=(())l - O( ((vāBr), matching the guarantee in Lemma 4.1.
Finally, to address technicality about the constant y in Theorem 4.5, note that increase the number of sampled a; b, pairs to max {1000d, yd), and the rest of the analysis still follows.
Then consider the running time of GDSTAGEL. By Claim 4.4 and straightforward observations, all steps other than Line 6 run in polynomial time. Thus we focus on the efficiency of Line 6.
Claim 4.6. A vector 9 satisfying the condition at Line 6 of GDSTAGEL, if it exists, can be found in nearly-linear time s, at the cost of an extra constant factor in the radius of the ball.
We note that an extra constant factor in the radius of the ball will not affect the final distance to x by more than a constant factor. The proof of this claim is deferred to Appendix D. Roughly, the proof proceeds by sampling (11) points from 91..... and checking for each sampled if at least 2/3 fraction of the total points are within euclidean distance 200 of gy. Note that the radius now becomes 2003K as opposed to 1003K at Line 6 of GDSTAGEL.
An (3/)k///))cllll algorithm
In this section we give an algorithm GDSTAGEII that, when given an initial point which is (((/)/)))cooose to the minimizer x² of f. finds a point that O(K /BK))//)-lloss to x². GDSTAGELI basically performs a gradient descent on the average function fex (Definition 2.4).
Algorithmm 3: GDSTAGEEI() a. 3,)))
Input fR + RR, 0 < < <,, and xp E Ied with ||:0 - x"1| 10000(3/a)K.
Output: 2 Rdd
Let the iteration count be + 1 log( 1).
2 for (. = 1,
do
Let the sample count be s - 400 log(dT).
Sample random points y/, ...... ys in the ball B(x,, 2K).
Compute gradients 9j <- GRADIRNTCOMP(C Vi. 3, () for sufficiently small r > 0, and their average 9 - Di-
Perform descent step: T++1 Ft 239-
return Zt-
The performance of GDSTAGEII is characterized in Theorem 5.1, with the proof in Appendix Note that while the success probability in Theorem 5.1 is not arbitrarily large, any 8 by repeating the algorithm O(log(1/6) times, as we show in Corollary E.2.
amplify it to
Theorem 5.1. Suppose that d 2 100 log(8//= 1). Then given an initial point zo that satisfies ||z0- -1 S 10000(3/a)KK, GDSTAGEII returns a point à with || -iæ=="ll S 1000 /B/aK with probability at least 2- 2-4/8, where x" is the minimizer of f. The number of queries made by GDSTAGELl is ((d(3/a)²). 2)). Moreover, the algorithu runs in polynomial time.

---

The proof of Theorem 5.1 builds on lemma showing that the gradients that GDSTAGEII uses are sufficiently precise. The lemma relies on an co-cennennontion imquuality for the sum of random vectors (i.c., the Vector Bernstein Inequality in Theorem E.1). Its proof also appears in Appendix E. Lemma 5.2. Let d 2 100 log(3/// + 1). The vector g computed at Line 5 of GDSTAGEIl satisfies the following with probability at least 2 d/8 (T: || 52 (a,) S 16/a8K.
Future directions
We obtained asymptotically matching upper and lower bounds how well the minimizer of convex function can be identified in presence outlier noise. There are several natural directions for future work. First, while our algorithm's query complexity has essentially the same dependence on d and ||000 - x=I| as Nesterov's accelerated gradient descent, is still off by a factor of (8/a)1.5. It will thus be interesting understand if this remaining performance gap can be eliminated. Also, we note that both our results require the dimension to be sufficiently high. While we believe the high dimension regime of the most interest, will be an interesting exercise to understand how these bounds change in the low-dimenn wwwdiimesioonll setting. Finally, as pointed out in the introduction, appealing future direction is to study convex minimization with the more general lp ép-bounded noise.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their valuable feedback. This work was supported in part by NSF awards CCF-1763514, CCF-1934876, CCF-2008305, CCF-1910534, CCF-1926872, and CCF-2045128.
References
[1] A. Agarwal, O. Dekel, and L. Xiao. Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. In COLT, pages 28 28-40, 2010.
[2] Alekh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. SIAM Journal on Optimization, 23(1):213-240, 2013.
[3] David Applegate and Ravi Kannan. Sampling and integration near log-concave functions. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages
156 163, 1991.
[4] Sanjeev Arora and Subhash Khot, Fitting algebraic curves to noisy data. Journal of Computer and System Sciences, 67(2):325 320, 2003.
[5) Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Conference Learning Theory, pages 240-265 PMLR, 2015.
[6] Elwyn R Berlekamp. Algebraic coding theory (revised edition). World Scientific, 2015.
[7] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[8] Sébastien Bubeck, Nicolò Cesa-Bianchi, et al. Regret Analysis of Stochastic and Nonstochastic Multi-amen armed Bandit Problems. Foundations and Trends( Machine Learning, 5(1):1-122, 2012.
[9] Xue Chen and Anindya De. Reconstruction under Outliers for Fourier-Sparse Functions. In Proceedings of the Thirty-Frrst Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 200 page 2010-2029, 2020.
[10] Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia. On acceleration with noise- corrupted gradients. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässon Stockholm, Sweden, July 10-15, 2018, pages 1018-1022 2018
10

---

[11] Anindya De, Sanjeev Khanna, Huan Li, and Hesam Nikpey. Nearly tight bounds for discrete search under outlier noise. To appear in SOSA 2022.
[12] Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price privacy and the limits LP decoding. In Proceedings of the 39th Annual ACM Symposium Theory of Computing, San Diego, California, USA, June 1 11-13, 2007, pages 85-94, 2007.
[13] Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 25-32, 1989.
[14] Venkatesan Guruswami and David Zuckerman. Robust fourier and polynomial curve fitting. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 751-759. IEEE, 2016.
[15] Daniel Kane, Sushrut Karmalkar, and Eric Price. Robust polynomial regression up to the information theoretic limit. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 391-402 IEEE, 2017.
[16] Jonas Moritz Kohler and Aurélien Lucchi. Sub-sampled cubic regularization for non-convex optimization. Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 1895-1904, 2017.
[17] Oren Mangoubi and Nisheeth K. Vishnoi. Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing. In Proceedings of the 31 Conference On Learning Theory, pages 1086-1124. 2018.
[18] Yurii Nesterov. Introductory lectures on convex programming volume Basic course. Lecture notes, 3(4):5, 1998.
[19] Aaditya Ramdas, Barnabas Poczos, Aarti Singh, and Larry Wasserman. An analysis of active learning with uniform feature noise. Artificial Intelligence and Statistics, pages 805-813. PMLR, 2014.
[20] Aaditya Ramdas and Aarti Singh. Optimal rates for stochastic convex optimization under tsybakov noise condition. In International Conference on Machine Learning, pages 365-373. PMLR, 2013.
[21] Andrej Risteski and Yuanzhi Li. Algorithms and matching lower bounds for approximately- convex optimization. Advances in Neural Information Processing Systems, 29:4745-4753, 2016.
[22] Yaron Singer and Jan Vondrák. Information- -hhoortion-theoretiic lower bounds for convex optimization with erroneous oracles. In Advances in Neural Information Processing Systems, pages 3204-3212, 2015.
[23] Adrien B Taylor, Julien M Hendrickx, and François Glineur. Smooth strongly convex interpo- lation and exact worst-case performance of first-order methods. Mathematical Programming, 16:01-2) 2017.
[24] Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient Langevin dynamics. In Conference on Learning Theory, pages 1980-2022 PMLR, 2017.


Reviews:
[{"review_id": "tzabXqr0_2Q", "reviewer": "Reviewer_CLVB", "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.", "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": "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.\n\nI have only a few minor comments : \n- 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.\n\n- 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? \n\n- 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.\n\n-----------------------------------------\nUpdate after author responses : \n\nI read the other reviews and the authors' responses. \nGenerally, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "nyyQtHkR3l4", "reviewer": "Reviewer_jGRm", "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.\n\nThe 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. \n\nClearly, 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. \n\nThe model and results are nice. One drawback though is that the results only apply to high dimensional scenarios. ", "questions": "", "limitations": "", "rating": 6, "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": "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.\n\nUpper 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XhsJkWN6-z8", "reviewer": "Reviewer_E9DP", "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "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 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?\n\n\nI 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.\n\nAlso, 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.\n\nAfter 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.\n\nI 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.\n\nAlso 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)