Approximate optimization of convex functions with outlier noise
Year: 2021

Abstract:
We study the problem of minimizing a convex function given by a zeroth order oracle 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 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 is allowed 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 exactly, up to constant factors, the distance bound shown in our lower bound result.

heading: 1 Introduction
text: 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 : Rd → R, and seek to efficiently find a point x̃ that is close to the minimizer of f (call it x∗)1. To obtain meaningful guarantees for approximating the minimizer x∗, one needs to make certain assumptions on the convexity and smoothness of f . In particular, f is commonly assumed to be α-strongly convex and β-smooth for some β > α > 0. This means that, when f is twice differentiable, its second derivative in any direction is between α and β. For ease of presentation, we will say a convex function is (α, β)-nice if it satisfies these two conditions.
It is well known that the minimizer of an (α, β)-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 an (α, β)-nice function f : Rd → R is given to us as a zeroth order oracle, which returns the function value f(x) on any input point x ∈ Rd. Then we have: Theorem 1.1 ([7]). Given any initial point x0 ∈ Rd and > 0, the classic gradient descent algorithm outputs a point x̃ s.t. ‖x̃− x∗‖2 ≤ using O(d(β/α) log ‖x0−x∗‖ ) oracle queries.
1Sometimes, 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 we point out later, it is more natural to study approximations in the domain in our setting.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Theorem 1.2 ([18]). Given any initial point x0 ∈ Rd and > 0, the accelerated gradient descent algorithm outputs a point x̃ s.t. ‖x̃− x∗‖2 ≤ using O(d √ β/α log ‖x0−x ∗‖ ) oracle queries.
We note that the quantity β/α 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 to 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 inaccuracy.
The first category studies the case when the oracle is corrupted by stochastic noise2 — namely, the errors of the oracle are assumed to be random and independently drawn from some distribution [10, 20, 19]. 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 a small neighborhood. As a 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 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 adversarially, while obeying certain constraints. A representative such model is what we call pointwise-bounded 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 on each point can be arbitrary. Formally, it is allowed for the oracle to return, on an input point x, a value in the range [f(x)− , f(x) + ] (absolute errors) or [(1 − )f(x), (1 + )f(x)] (relative errors), for some > 0. [5] shows that when the errors are absolute and is on the order of 1/d, there is a polynomial-time algorithm that can find a point with function value arbitrarily close to f(x∗). Whereas [22] shows that, in sharp contrast, when is about 1/ √ d or larger, no polynomial-time algorithm is able to find a point with function value within some constant error of f(x∗), for both absolute and relative errors.
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 a natural variant of the pointwise-bounded 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 f only on a set 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 > 0. Notice that although C is bounded in volume, for any x ∈ C, f̂(x) and f(x) can differ arbitrarily. Though variants of each other, both the pointwise-bounded noise model in [22, 5] and our model may be considered as special cases of a more general type of adversarial noise model, namely the `p-bounded noise model. To see this, let us write the noise as a function η : Rd → R, such that the noisy zeroth order oracle given to us corresponds to the function f + η. Then, in the (absolute) pointwise-bounded noise model, η is bounded in `∞-norm (they assume ‖η‖∞ ≤ ), whereas in the outlier noise model, η is bounded in `0-norm (we assume ‖η‖0 ≤ vol(radius-K ball)). It will certainly be an interesting future direction to explore what can be achieved for minimizing convex functions with general `p-bounded 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 a point with function value close to f(x∗). This is because our only assumption on the noise is that the corrupted region C, which is in the domain of the function f , is bounded in volume, and in particular, it may be located around x∗. Therefore, we believe it makes the most sense to measure the quality of the solution of a minimization algorithm by its distance to the optimal in the domain (specifically, how the distance compares with the corruption radius K).
Our results. Let us first consider what one might expect to 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
2This model more often deals with the first order oracle, which gives the (noisy) gradient∇f(x) at a point x.
around x∗, making it impossible for us to know where the true minimizer lies. However, is it possible to obtain a 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 to 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 Ω(K √ β/α), where we recall that α,β are the “niceness” of the function. This result is a consequence of the existence of two (α, β)-nice 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 a point within distance O(K √ β/α) 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 us say a zeroth order oracle of a function f is 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 α, β,K > 0 and sufficiently large d, there exist two (α, β)-nice functions f0, f1 : Rd → R which satisfy the following conditions: (i) The `2-distance between the minimizers of f0, f1 is Ω(K √ β/α); (ii) The total volume of points where f0 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 ∈ {0, 1} and lets fi be the true convex function, but always uses f0 as the K-corrupted oracle. Then no matter which point our algorithm outputs, with probability at least 1/2 over the randomness of i, it is Ω(K √ β/α) away from the minimizer of the true convex function fi.
Theorem 1.4 (Algorithm; formal version appears as Theorems 4.2, 5.1). Let α, β,K > 0 and d be sufficiently large. There is an algorithm that, given access to a K-corrupted oracle of an (α, β)-nice function f : Rd → R and an initial point x0 ∈ Rd, makes Õ(d · (β2/α2) · log ‖x0 − x∗‖)3 queries to the oracle and outputs a point x̂ s.t. ‖x̂− x∗‖2 ≤ O(K √ β/α). Here x∗ is the minimizer of f .
We note that in both our results, our conditions on d are roughly that d ≥ Ω(log β/α). In other words, we require the function’s condition number β/α to be at most 2O(d), a 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 (α, β)-nice functions f0 and f1 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 `2-distance Ω(K √ β/α)-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 √ β/α).
More concretely, we start by letting f0 be a simple (α, β)-nice quadratic function whose minimizer is at the origin. Then the existence of our desired function f1 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 f0 and f ′. Specifically, the properties that we need f ′ to satisfy is as follows: (i) f ′ is (α, β)-nice; (ii) both the function values and the gradients of f0 and f ′ agree on all points on the periphery of an ellipsoid E that is centered at the origin and has bounded volume; (iii) the minimizer of f ′ has coordinate of the form (Ω(K √ β/α), 0, . . . , 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 f1 by letting f1 = f ′ inside the ellipsoid E , but f1 = f0 outside of E . For the upper bound, our algorithm proceeds in two stages. In the first stage, we come to within distance O(K(β/α)) of the minimizer x∗ and in the subsequent stage, we improve it to O(K √ β/α).
The first algorithm essentially follows a gradient descent, but using an approximate gradient at each step. In order to estimate the gradient at a point x, we set up a system of linear equations, where each equation adds a constraint on the derivative at x along a uniformly random direction. There are however two types of noise in these equations, one from using a zeroth order oracle to compute first
3Here and throughout the paper, we write Õ(f) to denote O(f · poly(log f)).
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 in the same query complexity.
However, the one bottleneck in this approach is that at any point, the ball of radius < K around it could potentially be (nearly) completely corrupted. Thus, to get a meaningful estimate of the gradient, we have to sample points which are more than distance K-far apart. This tradeoff eventually allows us to get O(K(β/α))-close to the minimizer. To get to the optimal closeness of O(K √ β/α), we next start at a point which is guaranteed to be
O(K(β/α))-close to the true minimizer. We now consider the function f̄ which is defined as the average of f in a ball of radius (say) 2K. It is not hard to verify that f̄ continues to be (α, β)-nice. Moreover, the minimizers of f̄ and f can be shown to be O(K √ β/α)-close 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 of f̄ , the gradient∇f̄(x) is also equal to the average of the gradients∇f(y) over all points y within distance 2K of x. This suggests that we can approximate ∇f̄(x) by averaging the gradients ∇f(y) at sufficiently many randomly sampled y’s, and bounding the error using concentration inequalities for sums of random vectors. Now a key observation is that, since these y’s are sampled randomly from a radius 2K-ball, it is highly likely that each sampled y 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 minimization [2, 8, 1]. In the direction of convex optimization under adversarial noise, the early results in 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, we set up a few notations and give some basic definitions and technical preliminaries. In Section 3, we prove our lower bound result. In Section 4, we give a first algorithm that gets us to within distance O(K(β/α)) of x∗. In Section 5, we give a second algorithm that gets us to within distance O(K √ β/α) of x∗. In Section 6, we propose several future directions.

heading: 2 Preliminaries
text: 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 → R is β-smooth if it is differentiable and for all pairs x, y ∈ Rd we have ‖∇f(x)−∇f(y)‖ ≤ β ‖x− y‖4. Definition 2.2. A function f : Rd → R is α-strongly convex if f(x)− α2 ‖x‖ 2 is convex.
We next set up notations of a ball and the uniform distribution over it.
Definition 2.3. Let B(x, r) def= {y : ‖y − x‖ ≤ r} denote the ball of radius r centered at x. Let U(x, r) denote the uniform distribution over all points in the ball B(x, r).
As a result, the fraction of corrupted volume in a ball B(x, r) is Pry∼U(x,r)[f(y) 6= f̂(y)], where we recall that f̂ denotes the corrupted version of f .
For our second algorithm in Section 5, we will need to consider the “average” function, whose value at a point x is the average of f(y)’s where y is within some distance of x.
4Here and going forward, all norms are `2-norms unless stated otherwise
Definition 2.4. For any r > 0, define the function f̄r as f̄r(x) def = Ey∼U(x,r) [f(y)].
It is not hard to verify the strong convexity and smoothness of f̄r: Lemma 2.5. If f is α-strongly convex and β-smooth, f̄r is also α-strongly convex and β-smooth.
As a result of α-strong convexity and β-smoothness, we can upper bound the distance between the minimizers of f and f̄r by O(r √ β/α). Lemma 2.6. Let x∗, x̄r be the minimizers of f and f̄r respectively. Then ‖x∗ − x̄r‖ ≤ 2r √ β/α.
A proof of this lemma is included in Appendix B.
3 An Ω(K √ β/α) lower bound
In this section we show that getting O(K √ β/α)-close to x∗ is the best we can hope for even if we are allowed to query the function value at every point of the domain. We will prove this by showing that when the dimension is sufficiently high in terms of β/α, there exist two α-strongly convex, β-smooth functions that differ only in an ellipsoid of volume equal to a ball of radius K, but whose minimizers are Ω(K √ β/α)-apart.
Theorem 3.1. Given 0 < α ≤ β with 1 + log βα ≤ d where d is the dimension, and a K > 0, there exist two α-strongly convex, β-smooth functions whose values differ only in an ellipsoid of volume equal to a radius-K ball, but whose minimizers are Ω( √
β α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 in a black-box manner, but instead have to make certain adaptations.

heading: 3.1 Some interpolation results from [23]
text: First let us define the notion of (α, β)-interpolability. Definition 3.2 ((α, β)-interpolability). Suppose we are given a set of (possibly infinitely many) tuples {(xi, gi, fi)}i∈I where each xi, gi ∈ Rd, fi ∈ R. Let α ∈ R≥0, β ∈ R≥0∪{+∞} where α < β. We say this set is (α, β)-interpolable if there is a proper and closed convex function f : Rd → R∪{+∞} that is α-strongly convex and β-smooth such that for all i ∈ I , gi ∈ ∂f(xi) and f(xi) = fi, where ∂f(xi) denotes the set of subgradients of f at xi.
Note here that when α = 0, we only require f to be convex. When β =∞, we do not require f to be smooth and thus f is not necessarily differentiable; when β <∞, the condition gi ∈ ∂f(xi) is equivalent to gi = ∇f(xi) as the gradient is unique at any point when f is differentiable. The following two lemmas are proved in [23]. The first lemma enables us to reduce the (α, β)interpolation of some tuple set to the (0, β′)-interpolation of another tuple set, while the second lemma allows us to further reduce it to the (α′,∞)-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 {(xi, gi, fi)}i∈I where xi, gi ∈ Rd, fi ∈ R and 0 ≤ α < β ≤ +∞. The following two statements are equivalent:
1. {(xi, gi, fi)}i∈I is (α, β)-interpolable. 2. {
(xi, gi − αxi, fi − α2 ‖xi‖ 2 ) } i∈I is (0, β − α)-interpolable.
Lemma 3.4. Given a set of (possibly infinitely many) tuples {(xi, gi, fi)}i∈I where xi, gi ∈ Rd, fi ∈ R and 0 < β ≤ +∞. The following two statements are equivalent:
1. {(xi, gi, fi)}i∈I is (0, β)-interpolable.
2. {
(gi, xi, x > i gi − fi) } i∈I is (1/β,∞)-interpolable.
Then as in [23], by alternately applying Lemmas 3.3 and 3.4 twice each, we are able to reduce any (α, β)-interpolation problem to a (0,∞)-interpolation problem, where we only want to interpolate some points with a proper and closed convex function. Formally, we have the following lemma, whose proof is deferred to Appendix C. Lemma 3.5. Given a set of (possibly infinitely many) tuples {(xi, gi, fi)}i∈I where xi, gi ∈ Rd, fi ∈ R and 0 ≤ α < β ≤ +∞. The following two statements are equivalent:
1. {(xi, gi, fi)}i∈I is (α, β)-interpolable. 2. {(
βxi β−α − gi β−α , gi − αxi, αx>i gi β−α + fi − βα‖xi‖2 2(β−α) − ‖gi‖2 2(β−α) )} i∈I is (0,∞)-interpolable.

heading: 3.2 Our lower bound
text: We first show that there exists an Ω(1)-strongly convex, O(1)-smooth function whose minimizer is 1/2-far from the origin, but whose function values and gradients agree with the quadratic function ‖x‖2 on all points on the surface of a unit ball. Formally, we have the following lemma. For ease of presentation, let us define X=1 def = {x : ‖x‖ = 1} and similarly X≥1 def= {x : ‖x‖ ≥ 1}. We also write e1 = (1, 0, . . . , 0)T to denote the first standard basis vector.
Lemma 3.6. Let f(x) def= ‖x‖2 which is 2-strongly convex and 2-smooth. There exists a 12 -strongly convex, 16-smooth function f̃ such that
1. f̃ ’s minimizer is 12e1.
2. For all x ∈ X=1 we have f̃(x) = f(x) and ∇f̃(x) = ∇f(x).
The proof of this lemma is deferred to Appendix C. Roughly, the proof consists of three steps: (i) formulate proving the existence of f̃ as a ( 12 , 16)-interpolation problem; (ii) use Lemma 3.5 to reduce it to the (0,∞)-interpolation of some infinitely many points; (iii) explicitly construct a proper and closed convex function that does interpolate these points.
Now by taking a piecewise combination of the function f̃ in Lemma 3.6 and the quadratic function ‖x‖2, we can show that there exists an Ω(1)-strongly convex, O(1)-smooth function f̂ whose minimizer is 1/2-far from the origin, but whose function values and gradients agree with ‖x‖2 on every point with `2-norm greater than or equal to 1.
Lemma 3.7. Let f(x) def= ‖x‖2 which is 2-strongly convex and 2-smooth. Define f̂ such that f̂(x) = f̃(x) if ‖x‖ ≤ 1 and f̂(x) = f(x) otherwise (‖x‖ > 1). Then we have
1. f̂ is 12 -strongly convex and 16-smooth.
2. f̂ ’s minimizer is 12e1.
3. For all x ∈ X≥1 we have f̂(x) = f(x) and ∇f̂(x) = ∇f(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 κ ≥ 1, when the dimension is sufficiently high in terms of κ, there exist two Ω(1/κ)-strongly convex, O(1)-smooth functions whose function values and gradients agree on every point outside of an ellipsoid of volume equal to a unit ball, but whose minimizers are √ κ/2-apart. Here κ shall be thought of as β/α where β = Θ(1).
Lemma 3.8. Given κ ≥ 1 with 1+log κ ≤ dwhere d is the dimension. Let γ def= (1/κ) 1d−1 ∈ [1/2, 1]. Let Sd×d = DIAG(κ, γ, . . . , γ). Define s(x) = x>S−1x, which is (2/κ)-strongly convex and (2/γ)smooth. Let Xs≥1 = {x : s(x) ≥ 1}. Also define ŝ(x) = f̂(S−1/2x). Then we have
1. ŝ is 1/(2κ)-strongly convex and (16/γ)-smooth.
2. ŝ’s minimizer is √ κ
2 e1.
3. For all x ∈ Xs≥1 we have ŝ(x) = s(x) and ∇ŝ(x) = ∇s(x).
Finally, by further scaling (the domain and the function values of) s, ŝ in Lemma 3.8, we can prove Theorem 3.1. The proofs of Lemma 3.8 and Theorem 3.1 are both included in Appendix C.

heading: 4 An O(K(β/α))-close algorithm
text: In this section we give an algorithm GDSTAGEI that finds a pointO(K(β/α))-close to the minimizer of f . GDSTAGEI essentially implements a gradient descent algorithm, but uses approximate gradient computed from the noisy oracle at each step. To begin with, we present a subroutine GRADIENTCOMP for computing the gradient at a point where a small neighborhood is mostly uncorrupted.
Algorithm 1: GRADIENTCOMP(f̂ , x, β, τ)
Input : f̂ : Rd → R, x ∈ Rd, β > 0, and τ > 0. Output : g ∈ Rd.
1 Randomly choose 1000d pairs of points a1, b1 . . . , a1000d, b1000d in the ball B(x, τ). 2 Query the function values f̂(aj), f̂(bj) for all j = 1, 2, . . . , 1000d. 3 Let g ∈ Rd be any vector such that, for at least 800d of the j’s, the following holds:
∣∣∣g>(bj − aj)− ( f̂(bj)− f̂(aj) )∣∣∣ ‖bj − aj‖ ≤ βτ. (1)
If no such g exists, set g to be an 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 τ → 0. Lemma 4.1. Fix d > 0 and β > 0. There exists a function err(τ) satisfying limτ→0+ err(τ) = 0 such that the following holds. Fix any x ∈ Rd and τ > 0 such that the radius-τ ball centered at x is mostly uncorrupted:
Pry∼U(x,τ) [ f(y) 6= f̂(y) ] ≤ 1
100 . (2)
Then we have that with probability 1− 2−3d, the vector g returned by GRADIENTCOMP satisfies ‖g −∇f(x)‖ ≤ err(τ). (3)
The number of queries made by GRADIENTCOMP is O(d).
We now describe GDSTAGEI in Algorithm 2. Its performance is characterized in Theorem 4.2.
Algorithm 2: GDSTAGEI(f̂ , α, β, x0, R0, δ)
Input : f̂ : Rd → R, 0 < α < β, x0 ∈ Rd, R0 ≥ ‖x0 − x∗‖, and δ ∈ (0, 1). Output : x̂ ∈ Rd.
1 Let the iteration count be T ← 100βα log R0(β/α)K . 2 for t = 0, 1, . . . , T − 1 do 3 Let the sample count be s← 200 log(T/δ). 4 Sample s random points y1, y2, . . . , ys in the ball B(xt, 99K). 5 Compute gradients gi ← GRADIENTCOMP(f̂ , yi, β, τ) for some sufficiently small τ > 0. 6 Find a vector ĝ ∈ Rd such that at least (2s)/3 of the gi’s are within euclidean distance 99.5βK of ĝ; if no such ĝ exists, set ĝ to be an arbitrary vector. 7 Perform a descent step: xt+1 ← xt − 12β ĝ. 8 return xt.
Theorem 4.2. Let d ≥ 2. Given an initial point x0 with ‖x0 − x∗‖ ≤ R0 and a δ ∈ (0, 1), the algorithm GDSTAGEI returns a point x̂ with ‖x̂− x∗‖ ≤ 10000(β/α)K with probability 1−δ, where x∗ is the minimizer of f . The number of queries made by GDSTAGEI is Õ(d(β/α) log R0(β/α)K log(1/δ)).
Crucial to proving this theorem is to show that the gradients used by GDSTAGEI are accurate enough:
Lemma 4.3. Let d ≥ 2. The ĝ computed at Line 6 of GDSTAGEI satisfies with probability 1− δT that ‖ĝ −∇f(xt)‖ ≤ 200βK.
Full proofs 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 g satisfying the condition at Line 3 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 LP-decoding routine in [12]. Therefore let us first introduce the specific result that we need from [12].
Let A ∈ Rn×d be a matrix and z ∈ Rd be a vector. Consider the linear system Ax = Az, to which x = z is clearly a solution. If n ≥ d and A has full rank, then we can retrieve the vector z given A and Az by solving the linear system Ax = Az in polynomial time using, e.g., Gaussian elimination.
Now suppose the RHS of the linear system is corrupted by some noise e ∈ Rn, and we are only given A and the corrupted RHS Az + e, then can we still retrieve the vector z 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 ρ∗ ≈ 0.239 and γ ≥ 1 such that the following holds. Suppose n ≥ γd and An×d’s entries are drawn independently from a standard Gaussian distribution. Suppose also the noise e can be written as e = e1 + e2 where ‖e1‖0 ≤ ρ∗n. Then given A and Az + e, we can find in polynomial time a vector z′ s.t. ‖z − z′‖2 ≤ O(‖e2‖∞), for any z ∈ Rd.
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 `2-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 ∈ R1000d×d whose ith row is equal to (bi−ai) T
‖bi−ai‖ , where
ai, bi’s are the sampled points at Line 1 of GRADIENTCOMP. We also define vectors b, b̂ ∈ R1000d with b(i) = ∇f(x)
T (bi−ai) ‖bi−ai‖ and b̂(i) = f̂(bi)−f̂(ai) ‖bi−ai‖ , where x is the input point of GRADIENTCOMP.
Notice that each b(i) is the inner product of the ith row of B and ∇f(x), and therefore we have B∇f(x) = b. Consequently, given B and b we can retrieve ∇f(x) by solving the linear system By = b (y are the variables). Thus our goal becomes solving this linear system when only B and b̂ (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 a step further.
As the ai, bi’s are sampled uniformly at random from a ball, each row (bi−ai)T ‖bi−ai‖ of B is a unit vector with a uniformly random direction. It is well known that a vector with independent standard Gaussian entries also points to a 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 ` from the χ2-distribution with d degrees of freedom (i.e., the sum of the squares of d independent standard Gaussians); (iii) scale the unit vector by √ `. In light of this, let us generate a diagonal matrix D ∈ R1000d×1000d such that each D(i, i) is independently sampled as in step (ii). Then we consider the linear system D1/2By = D1/2b to which y = ∇f(x) is a solution. Notice that we now have that each entry of D1/2B follows a standard Gaussian.
By thinking of D1/2b̂ as a corrupted version of Db, we then need to show that the noise e def= D1/2(b̂− b) can be written as e1 + e2 such that ‖e1‖0 ≤ ρ∗(1000d) and ‖e2‖∞ is small. To this end,
we notice that for each i such that both ai, bi are uncorrupted, we have by β-smoothness that
∣∣∣b(i)− b̂(i) ∣∣∣ = ∣∣∣∣∣ ∇f(x)T (bi − ai) ‖bi − ai‖ − f̂(bi)− f̂(ai)‖bi − ai‖ ∣∣∣∣∣ ≤ O(βτ), (4)
where τ is the radius of the ball B(x, τ) from which ai, bi’s are sampled. Thus, if B(x, τ) is mostly (say 99%) uncorrupted, with probability 1− exp(−Ω(d)), (4) holds for most (say 90%) of the i’s. Also, by standard Markov’s inequality and Chernoff bounds, with probability 1− exp(−Ω(d)), for most (say 99%) of the i’s we have D(i, i) ≤ O(d). Combining this with (4), we have for 80% of the i’s that √ D(i, i) ∣∣∣b̂(i)− b(i) ∣∣∣ ≤ O( √ dβτ), implying the existence of e1, e2 s.t. e = e1 + e2 and ‖e1‖0 ≤ 0.2(1000d), ‖e2‖∞ ≤ O( √ dβτ). This means that by Theorem 4.5 we can use linear
programming to find a g with ‖g −∇f(x)‖ ≤ O( √ dβτ), matching the guarantee in Lemma 4.1.
Finally, to address a technicality about the constant γ in Theorem 4.5, we note that we can increase the number of sampled ai, bi pairs to max {1000d, γd}, and the rest of the analysis still follows.
Then we consider the running time of GDSTAGEI. 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 ĝ satisfying the condition at Line 6 of GDSTAGEI, if it exists, can be found in nearly-linear time in 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 Õ(1) points from g1, . . . , gs and checking for each sampled gj if at least 2/3 fraction of the total points are within euclidean distance 200βK of gj . Note that the radius now becomes 200βK as opposed to 100βK at Line 6 of GDSTAGEI.
5 An O(K √ β/α)-close algorithm
In this section we give an algorithm GDSTAGEII that, when given an initial point which is O(K(β/α))-close to the minimizer x∗ of f , finds a point that is O(K √ β/α)-close to x∗.
GDSTAGEII basically performs a gradient descent on the average function f̄2K (Definition 2.4).
Algorithm 3: GDSTAGEII(f̂ , α, β, x0)
Input : f̂ : Rd → R, 0 < α < β, and x0 ∈ Rd with ‖x0 − x∗‖ ≤ 10000(β/α)K. Output : x̂ ∈ Rd.
1 Let the iteration count be T ← 100βα log( β α + 1). 2 for t = 0, 1, . . . , T − 1 do 3 Let the sample count be s← 400βα log(dT ). 4 Sample s random points y1, y2, . . . , ys in the ball B(xt, 2K). 5 Compute gradients gi ← GRADIENTCOMP(f̂ , yi, β, τ) for sufficiently small τ > 0, and
their average ḡ ← 1s ∑s i=1 gi.
6 Perform a descent step: xt+1 ← xt − 12β ḡ. 7 return xt.
The performance of GDSTAGEII is characterized in Theorem 5.1, with the proof in Appendix E. Note that while the success probability in Theorem 5.1 is not arbitrarily large, we can amplify it to any 1− δ by repeating the algorithm O(log(1/δ)) times, as we show in Corollary E.2. Theorem 5.1. Suppose that d ≥ 100 log(β/α + 1). Then given an initial point x0 that satisfies ‖x0 − x∗‖ ≤ 10000(β/α)K, GDSTAGEII returns a point x̂ with ‖x̂− x∗‖ ≤ 1000 √ β/αK with probability at least 1 − 2−d/8, where x∗ is the minimizer of f . The number of queries made by GDSTAGEII is Õ(d(β/α)2). Moreover, the algorithm runs in polynomial time.
The proof of Theorem 5.1 builds on a lemma showing that the gradients that GDSTAGEII uses are sufficiently precise. The lemma relies on an `2-concentration inequality for the sum of random vectors (i.e., the Vector Bernstein Inequality in Theorem E.1). Its proof also appears in Appendix E. Lemma 5.2. Let d ≥ 100 log(β/α+ 1). The vector ḡ computed at Line 5 of GDSTAGEII satisfies the following with probability at least 1− 2−d/8/T : ∥∥ḡ −∇f̄2K(xt) ∥∥ ≤ 16√αβK.

heading: 6 Future directions
text: We obtained asymptotically matching upper and lower bounds on how well the minimizer of a convex function can be identified in presence of 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 ‖x0 − x∗‖ as Nesterov’s accelerated gradient descent, it is still off by a factor of (β/α)1.5. It will thus be interesting to 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 is of the most interest, it will be an interesting exercise to understand how these bounds change in the low-dimensional setting. Finally, as pointed out in the introduction, an appealing future direction is to study convex minimization with the more general `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.

Review summaries:
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.

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.

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.