First Order Stochastic Optimization with Oblivious Noise
Authors: Ilias Diakonikolas
Sushrut Karmalkar
Jongho Park
Christos Tzamos
Venue: NeurIPS 2023 poster (2023)
Keywords: Oblivious noise
Robust Statistics
Heavy-tailed Stochastic Optimization
Approximate Gradients
Inexact Gradients
TL;DR: We initiate the study of stochastic optimization with oblivious noise, a generalization of heavy-tailed noise.  We present an efficient list-decodable learner that recovers a small list of candidates one of which is close to the true solution.

Abstract: We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup.
In our setting, in addition to random observation noise, the stochastic gradient 
may be subject to independent \emph{oblivious noise}, 
which may not have bounded moments and is not necessarily centered. 
Specifically, we assume access to a noisy oracle for the stochastic gradient of $f$ 
at $x$,  which returns a vector $\nabla f(\gamma, x) + \xi$, where $\gamma$ is 
the  bounded variance observation noise 
and $\xi$ is the oblivious noise that is independent of $\gamma$ and $x$. 
The only assumption we make on the oblivious noise $\xi$ 
is that $\Pr[\xi = 0] \ge \alpha$, for some $\alpha \in (0, 1)$.
In this setting, it is not information-theoretically possible to recover a single solution 
close to the target when the fraction of inliers $\alpha$ is less than $1/2$. 
Our main result is an efficient {\em list-decodable} learner that recovers 
a small list of candidates at least one of which is close to the true solution. 
On the other hand, if $\alpha = 1-\epsilon$, where $0< \epsilon < 1/2$ is sufficiently small
constant, the algorithm recovers a single solution.

Along the way, we develop a rejection-sampling-based algorithm to perform noisy location estimation, 
which may be of independent interest.

First Order Stochastic Optimization with Oblivious Noise
Mai Diakonikolas
Sushrut Karmalkar Department of Computer Sciences University of Wisconsin-Maddson
Department of Computer Sciences University of Wisconsin-Madiisnn
ilias@cs siic..ddu
skarmalkar@vise. edu
Jongho Park KRAFTON
Christos Tzamos Department of Informatics University of Athens tzamos@wisc. edu
j jongho. park@rrafton.coo
Abstract
We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup. In our setting, addition to random observation noise, the stochastic gradient may be subject to independent oblivious noise, which may not have bounded moments and is not necessarily centered. Specifically,
assume access noisy oracle for the stochastic gradient of f at which returns a vector Vf(r, x) + where 7 is the bounded variance observation noise and is the oblivious noise that is independent r. The only assumption we make on the oblivious noise & is that Pr[g = 0] 2 a for some (0, 1). In this setting, is recover single solution close to the target when the fraction of inliers a is less than 1/2. Our main result is an efficient dist-decodable learner that recovers small list of candidates, at least one of which is close to the true solution. On the other hand, if recovers single solution. Along the way, we develop eejection-samplingg based algorithm to perform noisy location estimation, which may be of independent interest.
7 and
cearmation-thhortiical
possible
e, where <<< 6 < 1/2 sufficiently small constant, the algorithm
Introduction
major challenge in modern machine learning systems perform inference in the presence of outliers. Such problems appear in various contexts, such as analysis of real datasets with natural outliers, e-g., in biology [Rosenberg al., 2002, Paschou et al., 2010, Li et al., 2008], or neural network training, where heavy-tailed behavior arises from stochastic gradient descent when the batch size is small and when the step size large [Hodgkinson and Mahoney, 2021, Gurbuzbalaban et al., 2021]. In particular, when optimizing various neural networks, there exists strong empirical evidence indicating that gradient noise frequently displays heavy-tailed behavior, often showing characteristics of unbounded variance. This phenomenon has been observed for fully connected and convolutional neural networks [Simsekli et al., 2019, Gurbuzbalaban and Hu, 202 as well as attention models [Zhang et al., 2020]. Hence, it is imperative to develop robust optimization methods for machine learning in terms of both performance and security.
In this paper, we study robust first-order stochastic optimization under heavy-tailed noise, which may not have any bounded moments. Specifically, given access a noisy gradient oracle for f=)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(which we describe later), the goal is to find a stationary point of the objective function f R - R. f(z) := E, 2)], where y drawn with respect an arbitrary distribution on R
Previous work on p-heavy-tailed noise often considers the case where one has access to V a)) such that [7, = fzx) and [
(+)))]] oº for p 2 [Nazin et al., 2019, Gorbunov et al., 2020], and recently for (1, [Cutkosky and Mchta, 2021, Sadiev et al., 2023]. In contrast, Diakonikolas al. [2019] investigates a more challenging noise model in which small proportion of the sampled functions f(7, x) are arbitrary adversarial outliers. In their scenario, they have full access to the specific functions being sampled and can eventually eliminate all but the least harmful outlier functions. Their algorithm employs robust mean estimation techniques to estimate the gradient and filter out the outlier functions. Note that their adversarial noise model requires that at least half of the samples are inliers.
This work aims to relax the distributional assumption of heavy-tailed noise such that the fraction of outliers can approach one, and do not have any bounded moment constraints while keeping optimization still computationally tractable. Thus, we ask the following natural question:
What is the weakest noise model for optimization in which efficient learning is possible, while allowing for strong corruption of almost all samples?
In turn, we move beyond prior heavy-taile -aiile noise models with bounded moments and define new noise model for first-order optimization, inspired by the oblivious noise model studied in the context of regression [Bhatia et al., 2015, d' O'Orii et al., 202 20].b]. We consider the setting in which the gradient oracle returns noisy gradients whose mean may not be V V f(x)), and in fact, may not even exist. The only condition on our additive noise distribution of is that with probability at least a, oblivious noise takes the value zero. Without this, the optimization problem would become intractable. Notably, oblivious noise can capture any tail behavior that arises from independent p-heavy- noise.
We now formally define the oblivious noise oracle below.
Definition 1.1 (Oblivious Noise Oracle). We say that oracle (a)),(()) is oblivious oracle, if. when queried on x. the oracle returns f x) + where 7 is drawn frawnfrrom some arbitrary distribution and& & is drawn from De independent of x and 7, satisfying Prę-De | 0] a. The distribution satisfies En,-oVV((,,a) (x)
and
V f(x) <
Unfortunately, providing an approximate stationary point 2 such that [ < for some small E >> 0, is information-thhoreticllll impossible when a < 1/2. To see this, consider the case where [r,[7 = 0] = 1 and the function f(0,z) = x². If & follows uniform distribution over the set 0,2,0,2, when we query the oracle for a gradient at xr we will observe a uniform distribution over (2z - 2, 2x. 2x + 2}. This scenario cannot be distinguished from a similar situation where the objective is to minimize f0, x) = (x 1)2, and & follows a uniform distribution over {0,2, 2, 4).
To address this challenge, we allow our algorithm to work in the list-decodable setting, implying that it may return small list of candidate solutions such that one of its elements 3 satisfies ||V (z) < We now define our main problem of interest.
Definition 1.2 (List- Distdaecod Stochastic Optimization). The problem of List-Decodable Stochastic
Optimization with oblivious noise is defined as follows: For f that is L-smooth and has global minimum, given access to O fa,a(())) as defined in Definition 1.1, the goal is to output a list L of size such that minzeel [ S
1.1 Our Contributions
As our main result, we demonstrate the equivalence between list-decodable stochastic optimization with oblivious noise and list-decodable mean estimation (LDME), which we define below.
Definition 1.3 Distt-ecoddble Mean Estimation). Algorithm A is an (a., B,, -DLMM algorithm for D (a set of candidate inlier distributions) if with probability 8,A. it returns a list L of size 8 such that mingeclli -E,-D [r]] < 3 for D E D when given m. samples {z, + A for 2; D and & ~ Dg where Pr 0) 2 a. If a is a sufficiently small constant less than 1/2, then =

---

We define Do to be the following set of distributions over R D. We also use (.) to hide all log factors in d, 1/a, 1/6, where ó denotes the failure probability and 1) is a multiplicative parameter we use in our algorithm.
:- (D Eolle-Ep|e|l - d²).
Our first theorem shows that if there exists an efficient algorithm for the problem of list-decodable mean estimation and an inexact learner (an optimization method using inexact gradients), there an efficient algorithm for list distdeccodabee stochastic optimization.
Theorem 1.4 (List- Decodable Stochastic Optimization - List-Decodable Mean Estimation). Sup- pose that for any having a global minimum and being L-smooth, the algorithm Ag, given access to In satisfying [| - V [ || S O(1a), recovers & salisfying [V))] S O(ng) + t in time TG. Let AME E be an (a, O(1g) 8Y-LMME algorithm for Do. Then, there exists an algorithm (Algorithm 2) which uses AME and Ag, makes m m. AME + +Ō(TG. (O(1)/a) fn/² queries to Oa runs in time Ta Ta.pa (oooyyy(d 1/1,, (O(1)/a))/) (oo)//))/,,oo log((1/rre))) and returns a list L of 8 candidates satisfying minzee/| [V]]a) S O(n)) + with probability 1 6
To achieve this reduction, we develop an algorithm capable of determining the translation between two instances of a distribution by utilizing samples that are subject to additive noise. It is important to note that the additive noise can differ for each set of samples. As far as we know, this is the first guarantee of its kind for estimating the location of distribution, considering the presence of noise, sample access, and the absence of density information.
Theorem 1.5 (Noisy Location Estimation). Let 1 E (0,1) and let De, Dz, De be distributions and Dz, D2 are possibly distinct mean zero distributions with
such that Prę~De Is 0] variance bounded by o², Then there an algorithm (Algorithm 5) which, for unknown I E IRd takes
samples {E. + 24 + +)/ and (E. + 2 where & and &. are drawn independently from De and 2i and 24 are drawn from D2 and De' respectively, runs in time poly(d, 1/n, (0(1)/a)1/) log(1/8na)). and with probability 1 - 5 recovers t' such that It 1t-t" -'1 S ((no).
(O(())
The fact that there exist algorithms for list-decodable mean estimation with the inliers coming from D, allows us to get concrete results for list-decodable stochastic optimization.
Conversely, we show that if we have an algorithm for list-decodable stochastic optimization, then we also get an algorithm for list-decodable mean-estimation. This turn implies, via Fact 2.1, that an exponential dependence on 1/n) is necessary in the list-size if we want to estimate the correct gradient up to an error of (1jor) when the inliers are drawn from some distribution in D,-
Theorem 1.6 (Lisd-Decddable Mean Estimation - List-Decodable Stochastic Optimization). Assume there is an algorithm for List-Decodable Stochastic Optimization with oblivious noise that rums in time T and makes m. queries to Oo f. and returns a list L of size s containing 3 satisfying lIf()) S e. Then, there is an (a, e, s) algorithm for 'D that runs in time T, queries m samples, and returns a list of size s.
If = e, where 0 < é < 1/2 is at most a sufficiently small constant, the above theorems hold for the same problems, but with the constraint that the list is singleton.
1.2 Related Work
Given the extensive robust optimization and estimation literature, we focus on the most relevant work.
Optimization with Htavy-tailed Noise There is a wealth of literature on both the theoretical and empirical convergence behavior of stochastic gradient descent (SGD) for both convex and non-convex problems, under various assumptions on the stochastic gradient (see, e.g., Hardt et al. [2016], Wang et al. []021] and references within). However, the noisy gradients have shown to be problematic when training ML models [Shen and Sanghavi, 2019, Zhang et al., 2020], hence necessitating robust optimization algorithms.
From a theoretical point of view, several noise models have been proposed to account for inexact gradients. A line of work [d' Aspremont, 2008, So, 2013, Devolder et al., 2014, Cohen et al., 2018) 8] studies the effects of inexact gradients to optimization methods in terms of error accumulation. For instance, Devolder et al. [2014] demonstrates that, given oracle that outputs arbitrary
3

---

perturbation of the true gradient, the noise can be determined adversarially to encode non-smooth problems, Alternatively, many recent works [Lan, 2012, Gorbunov et al., 2020, Cutkosky and Mchta, 2021, Mai and Johansson, 2021, Sadiev et al., 2023] have studied 1--heayy-tailes noise, an additive stochastic noise to the true gradient where one has access to V V .)) such that E, [ x)] = (xx) and f
V [ S o². For instance, Sadiev et al. [2023] propose and analyze a variant of clipped- SGD to provide convergence guarantees for when p E (1,2). However, these noisy oracles, whether deterministic
stochastic, assume bounded norm moments on the noise, an assumption that is not present in the oblivious noise oracle.
Robust Estimation Our oblivious noise oracle for optimization motivated by the recent work on regression under oblivious outliers. In the case of linear regression, the oblivious noise model can be seen as the weakest possible noise model that allows almost all points to be arbitrarily corrupted, while still allowing for recovery of the true function with vanishing error [Bhatia et al., 2015, Suggala et al., 2019]. This also captures heavy-tailed noise that may not have any moments. The setting has been studied for various problems, including online regression [Pesme and Flammarion, 2020], PCA [d' Orsi et al., 2021a], and sparse signal recovery [d' Orsi et al., 2022].
On the other hand, there has been a flurry of work on robust estimation in regards to worst-case adversarial outliers (see, e.g., Diakonikolas et al. [2016], Lai et al. [2016], Charikar et al. [2017], Diakonikolas et al. [2019]). Robust mean estimation aims to develop an efficient mean estimator when (1 - a) -facction of the samples arbitrary. In contrast, list-decodable mean estimation generates small list of candidates such that one of these candidates is a good estimator. While robust mean estimation becomes information-thhorreiially theoretically impossible when a S 1/2, the relaxation to output a list allows the problem to become tractable for any a E (0, 1J [Charikar et al., 2017, Diakonikolas et al., 2022]. See Diakonikolas and Kane [2019, 2023] for in-depth treatments of the subject.
In the past, robust mean estimators have been used to perform robust gradient estimation (see. c.g., Charikar et al. [2017]. Diakonikolas et al. [2019]). which is similar to what we do in our paper. However, these results assume access to the entire function set, which allows them to discard outlier functions. contrast, in our setting, we only have access to a noisy gradient oracle, so at each step, we get fresh sample set and, hence, a different set of outliers. This introduces further difficulties. which we resolve via location estimation.
We note a subtle difference in the standard list-decodable mean estimation setting and the setting considered in this work. The standard list-decodable mean estimation setting draws inlier with probability and an outlier with the remaining probability. In contrast, our model gets samples of the kind E -+2 where 2 is drawn from the inlier distribution, and Pr(g = 0] > a, and is arbitrary otherwise. The algorithms for the mixture setting continue to work in our setting as well. Another difference that the standard setting requires that the distribution have bounded variance in every direction. On the other hand, in the optimization literature, the assumption is that the stochastic gradient has bounded expected squared norm from the expectation.
Location estimation Location estimation has been extensively studied since the 1960s. Traditional approaches to location estimation have focused on achieving optimal estimators in the asymptotic regime. The asymptotic theory of location estimation is discussed in detail in [Van der Vaart, 2000].
Recent research has attempted to develop the finite-sample theory of location estimation. These efforts aim to estimate the location of a Gaussian- smoothed distribution with sample complexity that matches the optimal sample complexity up a constant (see [Gupta et al., 2022] and [Gupta et al., 2023)). However, these results assume prior knowledge of the likelihood function of the distribution up to translation.
Another closely related work initiates the study of robust location estimation for the case where the underlying high-dimensioonl distribution is symmetric and an 0 < e < 1/2 fraction of the samples are adversarially corrupted Novikov et al. [2023]. This follows the line of work robust mean estimation discussed above.
We present a finite-sample guarantee for the setting with noisy access to samples drawn from a distribution and its translation. Our assumption on the distribution is that places an a mass at some point, where a E (0. 1) and, for instance, could be small as 1/d for some constant c. The noise is constrained to have mean zero and bounded variance, but crucially the noise added to the samples coming from the distribution and its translation might be drawn from different distributions. To the

---

best of our knowledge, this is the first result that has noisy access, does not have prior knowledge of the probability density of the distribution and achieves a finite-sample guarantee.
1.3 Technical Overview
For ease of exposition, we will make the simplifying assumption that the observation noise is bounded between [-a, g.. Let y and y be two distinct mean-zero noise distributions, both bounded within the range [-a, o.. Define to be the oblivious noise drawn from Dg. satisfying Pr[s 0] Z Assume we have access to the distributions (i.e., we have infinite samples).
Stochastic Optimization reduces to Mean Estimation. In Theorem 1.4, we show how we can leverage a list-decodable mean estimator to address the challenge of list-decodable stochastic op- timization with oblivious noise (see Algorithm 2). The key idea is recognize that we generate list of gradient estimates, and update this list such that one of the elements always closely approximates the true gradient in &g norm at the desired point.
The algorithmic idea as follows: gradients 3o 0 to retrieve a list L consisting of s potential gradient candidates. This set of candidates contains at least one element which closely approximates f()).
First, run a list-decodable mean estimation algorithm on the noisy
One natural approach at this stage would be to perform a gradient descent step for each of the gradients, and run the list-decodable mean estimation algorithm again to explore all potential paths that arise from these gradients. However, this naive approach would accumulate an exponentially large number of candidate solutions. We use a location-estimation algorithm to tackle this issue.
We can express f(r, x) as f(x) + e(7, z) where E,,e(yy, .I] = 0 and x))]11(( < o². When we query (a. at x. we obtain samples of the form ff(z) + + Ve(y. i.e., samples from translated copy of the oblivious noise distribution convolved with the distribution of Ve(y,x)) We treat the distribution of Ve(r, x)) as observation noise. The translation between the distributions of our queries to (-) at x and O correspond to Vf(x)= - (()). To update the gradient, it is sufficient to recover this translation accurately. By doing so, we can adjust by translating each element while maintaining the accuracy of the estimate.
Finally, we run first-order learner for stochastic optimization using these gradient estimates. We select and explore s distinct paths, with each path corresponding to an element of L obtained earlier. Since one of the paths always has approximately correct gradients, this path will converge stationary point in the time that it takes for the first-order learner to converge.
The objective of noisy location estimation is to retrieve the translation between two instances of distribution by utilizing samples that are subject to additive mean-zero and bounded saadded-vriinnee variance noise.
Noisy Location Estimation in 1-D.
In Lemma 3.1, we establish that if Algorithm 1 is provided with a parameter 1) E (0, 1) and samples from the distributions of & + and Ç + y' + J, it can recover the value of ( within error of ( Here & and & are independent draws from the same distribution.
Observe that in the absence of additive noise y and y', can be estimated exactly by simply taking the median of sufficiently large number of pairwise differences between independent samples from Ç and E + l. This is because the distribution of { - & is symmetric at zero and Pr[g - 0] a². However, with unknown and y', this estimator is no longer consistent since the median of zero- mean and v-variance random variables can be as large as O(ar in magnitude. In fact, Claim 3.2 demonstrates that for the setting we consider the median of & + y can as far as O(a /a) far from the mean of &. However, it does recover rough estimate f. such that it f < Ola/
Consequently, our approach starts by using t, as the estimate for t. and then iteratively improving the estimate by mitigating the heavy-tail influence of &. Note that if did not have heavy tails, then we could try to directly compute = E[g + y + 1] - E(g + y]. Unfortunately, due to ('s completely unconstrained tail, & may not even possess well-defined mean. Nonetheless, if we are able to condition & to a bounded interval, we can essentially perform the same calculation described above. In what follows, we describe one step of an iterative process to improve estimate t.
5

---

Rejection Sampling, Suppose we have an initial rough estimate of t, given by t, such that | -t| < Ao. We can then re-center the distributions to get { + and { + z', where 2 and have means of magnitude at most Ao, and have variance that is O(r). Claim 3.4 then shows that we can refine our estimate of does so by identifying an interval 7 = [-ka, ko] around such that the addition of either or z' to & does not significantly alter the distribution's 's mass within or outside of J. We show that since 2, z', and & are independent, the that we choose satisfies Els + z' E+22 E - + 8 =+2 f] Eig + z' | E 1] Eig + 2 & E 1] = n E[z"| E + nA for some 77 1.
To see that such an interval I exists, we will show that for some i, there are pairs of intervals (Ari, (2 + Ao] and [- + Ao -iAo) which contain negligible mass with respect to &. Since and can move mass by at most (A + 1) with high probability, is sufficient to condition on the interval around 0 which is contained in this pair of intervals. Since we do not have access to Ç. we instead search for pairs of intervals of length O(Ao) which have negligible mass with respect to both Ç + and Ç + z', which suffices.
To do this, we will demonstrate an upper bound P(i) on the mass crossing the jth pair of intervals described above. This will satisfy Σ, P(i) = C" for some constant C".
To show that this implies there is interval of negligible mass, we aim demonstrate the existence of a k E N such that kP(k) I 17. We will do this through contradiction. Suppose this is not the case for all i E [0, k]. then 1 2 (lo0i.. If k 2 exp(10C" /n), we arrive at contradiction because the right-hand side is at least Etzo (1/1) 2 1) (log(exp(1OC/m) > 10C", while the left-hand side bounded above by C.
Claim C.4 demonstrates, via a more involved and finer analysis, that for the bounded -vriiance setting where intervals very far away contribute to mass crossing Ari, there exists an & such that (P)( < 17 Pr[lél Aork,, and that taking the conditional mean restricted to the interval [-kAA, Ao) allows to improve our estimate of l. Here P(k) denotes an upper bound the total probability mass that crosses intervals described above.
Extension to Higher Dimensions. In order to extend the algorithm to higher dimensions, we apply the one-dimensional algorithm coordinate-wise but in randomly chosen coordinate-basis. Lemma 3.5 uses the fact that representing the distributions in a randomly rotated basis ensures that, with high probability, the inlier distribution will project down to each coordinate with variance of Ol log(d)/ /d) to extend Lemma 3.1 to higher dimensions.
Mean Estimation reduces to Stochastic Optimization. In Theorem 1.6 we show that the problem of list-decodable mean estimation can be solved by using list-decodable stochastic optimization for the oblivious noise setting. This establishes the opposite direction of the reduction to show the equivalence of list-decodable mean estimation and list-decodable stochastic optimization.
The reduction uses samples from the list-decodable mean estimation problem to simulate responses from the oblivious oracle to queries x. Let the mean of the inlier distribution be μu. If the first-order stochastic learner queries we return + where is sample drawn from the list- decodable -ettmmestimation problem. These correspond to possible responses to the queries when f(x) = (1/2)][a: + ull?, where y is the true mean. The first-order stochastic learner learns a ğú from list L such that [[V(( = 11 + pll I c; then the final guarantee of the list-decodable mean estimator follows by returning - which contains -ğ..
2 Preliminaries
Basic Notation For random variable X, we use E[X] for its expectation and Pr[X E E] for the probability of the random variable belonging to the set E. We use N(H, distribution with mean μ and variance matrix o². When D is a distribution, we use X ~ D to denote that the random variable X distributed according to D. When S is set, we let Ex~s(1 [-] denote the expectation under the uniform distribution over S. When clear from context, we denote the empirical expectation and probability by É and Pr. We denote || || as the fo-norm and assume f Rd + R is differentiable and L-smooth, i.c., |[ ff(x')l < L|| x'll for all x, x' Rd.
denote the Gaussian

---

& will always denote the oblivious noise drawn from a distribution Q satisfying Prę-QlÉ = 0] 2 a. y, s/ will be used to denote mean-zero and variance at-most x² random variables. Also define e(7,,) = 27),)) f()) and the interval (a. b] == (oa, øbj.
Facts We use these algorithmic facts in the following sections. We use a list-decodable robust mean estimation subroutine black-box manner. The proof for list-decodable mean estimation can be found in Appendix D, while such algorithms can be found in prior work, see, e.g., Charikar et al. [2017], Diakonikolas et al. [2020a]. We also define a (3, e) e--inxxxct-learrer for f.
Fact 2.1 (List-decoding algorithm). There is an (a, on, )) J-LDME algorithm for the an inlier distribution belonging to Do which runs time (d((1/a) 1/²)))//²)) and succeeds with probability
1 - ò. Conversely, any algorithm which returns list, of which makes an error of at most (1j))
in l2 norm to the true mean, must have a list whose size grows exponentially in 1/1..
If is a sufficiently small constant less than half, then the list size is to get an error of O(v1 - a a).
We now define the notion of robust-learnet which is algorithm which, given access to approximate gradients is able to recover a point at which the gradient norm is small.
Definition 2.2 (Robust Inexact Learner). Let f be a smoohh function with a global minimum and O.f (.) be an oracle which when queried on x returns a vector Ix satisfying 1| -V(()) S 8. We say that an algorithm Ag is an (B, E) e--inexact-leame for f if, given access to 0 the algorithm Ag recovers î satisfying f+) & 3 + c. We will assume Ag runs in time TG-
Several algorithms for convex optimization amount to there being an existence of a robust learner in the convex setting. More recently, for smooth nonconvex optimization, the convergence result for SGD under inexact gradients due Ajalloeian and Stich [2020] doubles as a (5, (i.e)-iiexcct-leame
running in To (LFFFC /B3 + +)) iterations, where F f(xo)) min, fxx) and 20 is the initial point. This follows by an application of Theorem from Ajalloeian and Stich [2020) and by taking
the point in the set of iterates that minimizes the gradient norm.
3 Location Estimation
To estimate how the gradient changes between iterations, we will need estimate the shift between distribution and its translation. In this section, we give an algorithm which, given access to samples from distribution and its noisy translation returns estimate of accurate up to error of (1jo) in fo-morm. We show a proof sketch here, and a more detailed proof of all the claims involved in Appendix C.
Lemma 3.1 (One-dimensional location-estimation). There is algorithm (Algorithm 1) which, for = (1()))
(L/(6))))), given samples {E, + ys t) and {& + v' where &, and E, are both drawn from De, Ys and y drawn from distinct distributions with mean- zero with variance bounded above by a and t E I is an unknown translation, runs in time poly(1 /n, (O(1)/a)//, log(1 ())))))) and recovers t' such that |t. (') S O(1a).
Proof. We first identify up to error of (aa/Va)) with the following claim.
Claim 3.2 (Rough Estimate). There is algorithm which, for O((1/a²) log(1/5)) given samples {&A + ys f) and (E+ + mm where & and & are both drawn from Dş, ys and yf are drawn from distinct distributions with mean-zero with variance bounded above by and e R is an unknown translation, returns tt, -1 S -1/2).
We use t. to center the two distributions up to an error of 112 Let the centered distributions be given by & + z and & + z' where 2, 2 are independent, have means that are at most da 1/2 in magnitude and have variance that is bounded by 4
Let AAB B denote the symmetric difference of the two events A, B. To improve our estimate further, restrict our attention to an interval I o(-i,)) such that Pr[(E + 2 e I) A (E E [)] <
7

---

Algorithm I One-dimensional Location Estimation: ShiftID(S), S2, 1,,00,
Input: Sample sets S S2 C Rd of size o, (0, 1), 0
1. Let 7 = /n (1/a)) For E (1,2), partition Sj into 7 equal pieces, 500 for i E (T).
2. D = (a b a s( )
3. (1) == median(D).
4. Set A = O()/va).
Repeat steps 12, for going from 2 to T:
6. S =5 5 (1 - 1).
For (1,2)
P5(1) = 0(1 Pr
| Ao - 5,8+00 5)]
zm
+11
Σ (1/(1- 1)²) Pr zns(i)
||]] E Ajo + Aol -., 4.5)
Let P()) (1)++ P2(1).
Identify an integer E [(1/an), (C/a + 1/(an))))// such that
P(k) S 1 Σ
Pr
|||||||||
Aok) O(n/t).
JE(1,2} amsh
10. (1(1) t E
2~ [> |2|
Aok
E
|
Aok).
11. == -1AA
12. Return (T)
Pnp I]) and Pr[(E + e I) f)] < On I]), i.c., neither nor o' moves more than a negligible mass of & either into, or out of T.
To detect such an interval (if it exists), we control the total mass contained in, and moved across the intervals (-i --i-1,, 1, 1,) and (i, + when z' are added ç. We denote this mass by P"ii). Claim C.4 shows that there is a function P(-) which we can compute using our samples from the distributions of & + and & + z', which serves good upper bound on pd (i).
Claim 3.3. There exists a function P. N - RR which satisfies the following:
1. For all i N, P(t) 2 P(i, P(i, which can be computed using samples from & + and
{ + z/.
2. There is a lek [(1//m)) (C/a 1/(an))))) such that kP(kk) < <n
3. Σ P(k)= = O(Pr(e < Aok] + Prill + +11 S Aok)).
With probability 1 8, for all (0(1)/a)///1) P(i) can be estimated to an accuracy of
On/ii) (i)b by using (0(1)/a)2/1 2/n log(1 /m00)//8/////// //1² samples from the distributions of + z and & z'.
Claim 3.4 shows that if such a P(-) exists, then the difference of the conditional expectations suffices to get a good estimate. This is because conditioning on g5 + 2| < 10ko satisfying conditions (2) and (3) above almost the same as conditioning on [g| < 10ka.
Claim 3.4. Suppose > (1a)) and P(.) satisfies the conclusions of Claim C.4. If z, have Ao bounded means and 4o bounded variances for some A, then Elg | + I Aoi] ElC + z + < Aoil = E[z] - E[ OAno)
The conclusion of the one-dimensional location estimation theorem then follows by putting these together, and iterating the above steps after re-centering the means. The sample complexity is governed by the following considerations:

---

(I) We require the Blş + 15 + σa oa E + 15 + + S σa 1/2k| to concentrate
around its mean for some i < (/ (2) We require Pr(s + E a i + 1)] to
concentrate for all integer i of magnitude at most aCC/a + 1/(an)))\//.
An application of Hoeffding's inequality (Lemma A. and union bound over all the events prove that it suffices ensure sample complexity to be 2 poly(1/n, (O(1)/a)" log(1/ôna)).
The following Lemma 3.5 uses the algorithm for one dimension to derive a dimeerrnmmmesional guarantee. The idea is to perform random rotation, which, with high probability, ensures that the variance of the distribution O(a / /og(d)/ / /v)) along each basis and then apply the one-dimensional algorithm coordinate- wise according to the random bases. We defer the proof to Appendix C. The algorithm referenced this lemma named "ShiftHighD", which we use later.
Lemma 3.5 (Location Estimation). Let Dy, for E {1,2} be the distributions of & 2 for i E {1,2} where & is drawn from De and Prę LE = 0j 2 a and 2, ~ D; are distri- Rd be unknown butions over R& satisfying ED,(2] = 0 and ED, [1[=]]]] < a². Let
shift, and Du denote the distribution of y/ shifted by v. There an algorithm (Algorithm 5), which draws poly(1/n, ()(1)/))) log(1/8na))
samples each from Dy, and Dyr.v runs in time log(1/8roo) /dyaa) and returns v' satisfying [| -oll
poly(d, 1/n, (O(1)/a)))) log(1 1-8.
Il z O(no) with probability
4 Algorithmic Results for Stochastic Optimization
Our first main result demonstrates that if we have access an algorithm that recovers list of size such that one of the means Oclose which is able to recover è such that V f+)]] & O(no) + given access to gradients that are close to the true gradient up to an & error of O(no).
-close to the true mean in &2 norm, then there is an algorithm
4.1 Proof of Theorem 1.4: List-decodable Stochastic Optimization - L.MME
Algorithm 2 Noisy Gradient Optimization:
Input: a, 17, 5, (a, ((yo) 3)-LDME algorithm AME for D,, Oa,a,( (O(no), le-leer Ag.
Let m' mAre
2. Query (0, to get samples S" +- (V/(2) + + Let La = ( 9.) +- AME(S).
4. Initialize starting points x! := y: for i E [s].
For each E [s), run Ag with x as the initial point and InexactOracle(:: ()., fo):
(the i-th element of the list) as gradient access to output 2 final
6. Return (1r. (nrf i E [s]].
Proof. The key to our proof is to recognize that at every step, we effectively have an oracle for an inexact gradient of f in the sense of O(mm),f as defined in Definition 2.2.
Algorithm 3 Inexact Gradient Oracle: InexactOracle(z:; Oa, Lo)
input: v, oracle Oa,a,f error 7, list Co of candidates such that mingecllo - VS(0)] S O(1o).
1. Let := O/T and m' = ((11ma))) /3/))/)))))))))))))
Query O (0. get samples S +- [Vf(%, 0) + [m/]].
3. Query Oa.a, / to get samples S + (Vf(), + + [m']]-
4. = SSiftHHigDDSS S* n,
5. Return Lo + v.

---

Claim 4.1. Given an initial list Co := (g......99h such that there is some fixed E [sr which llg, f((o)l I (nj)), a point z, access on. (.), Algorithm returns list C .9....................... gs} such that 9 - V [(()) I ((no) ) for the same i.
Proof. O 0 (v) returns samples of the kind {E, + e((%2),, + ff())]= and {e, e(%, 0): Vf(0)) 1m for = I and y = O, with e(%, y); being drawn from a distribution with and variance bounded by o² and & and & being drawn from De where Prę-Dz (S 0] 2 a. Hence, one can interpret the samples drawn being in the setting of Lemma 3.5 with the shift Vf(0)- fxx).
Let S1 and S2 be drawn from o (1y) with y and y = æ. Running Algorithm 5 on S1, S2. we recover satisfying ||e (Vf(z) V(j)) S O(no). A triangle inequality now tells us that if we set gf := 9: + v, we get llo V llo! 9i + 9: V.( + Vf( - Vz(
(ne) + (11)) = (1)o).
of can be interpreted the output of Olno). (2z), since 1lo follows from the guarantees of Ac, since for at least one of the sequences of gradients, Algorithm replicates every step of Ag.
O
v - O1jo). The result then
Substituting the guarentees of Fact 2.1 for the list-decoding algorithm in the above theorem then gives us the following corollary, the proof of which we defer to Appendix E.
Corollary 4.2. Given access to oblivious noise oracle Oa,o,f, (O(mo), -i-ixxxcct-learrer Ag running in time Te, there exists an algorithm which takes poly poly((O(1)/a)) //) log(Ta/ōnj)) sam- ples. runs in time To poly(d, (O(1)/a))/* log(1//())), and with probability 1 - returns a list L of size (((1/a)\/n) such that ( S ((jor) + Additionally, the exponential dependence on 1/1 the size of the list is necessary.
4.2 Proof of Theorem 1.6: LDME + List-Decodable Stochastic Optimization
In this subsection, we show the converse of the results from the previous subsection, i.e. that list-decodable stochastic optimization can be used to perform list-decodable mean estimation.
Proof. Assume there exists an algorithm A that can recover a s-sized list containing & such that [+)]l S when given access to O o2 From the list-decodable mean estimation setting,
denote D to be the distribution of { + where E[z] = and E[ll nM| < o², and Pr(g = 0] 2 a.
The goal of LDME is to recover from samples from D. We will show that we can recover an s-sized list that contains a ğ satisfying ||
- ا|| S
We do this by simulating the oracle Oa,e. (12)a(1//)] for A. To do this, whenever A asks for a query at x, return p where we sample p D of the list-decodable setting. This effectively simulates the oracle for the objective function f(x) (1/2)]la + ,l|2 where the oblivious noise & is the same, and the observation noise is (=-H) μ4). Hence A will return list L size containing
satisfying | + [a]| < e. Finally, return -C. This is the solution to list-decodable mean estimation
because -L contains = E, which satisfies || AIl S
Conclusion
In this paper, have initiated the study of stochastic optimization in the presence of oblivious noise, which extends the traditional heavy-tailed noise framework. our setting, the stochastic gradient is additionally affected by independent oblivious noise that lacks bounded moments and may not be centered. We have also designed an algorithm for unite-sample noisy location estimation based on taking conditional expectations, which we believe is of independent interest. We note that while the exponential dependence on 1/m for the size of the list is unavoidable, but it is an open problem to show that this is the case for the problem of noisy location estimation.
10

---

References
A. Ajallocian and U. Stich. Analysis of sgd with biased gradient estimators. arXiv preprint arXiv:2088.00055 2020.
K. Bhatia, P. Jain, and Kar. Robust regression via hard thresholding. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 721-729, 2015.
M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. Proc. 49th Annual ACM Symposium Theory of Computing, pages 47-60, 2017.
M. Cohen, Diakonikolas, and L.. Orecchia. On acceleration with noise-corrupted gradients. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2018.
A. Cutkosky and H. Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883-4895, 2021.
A. d' Aspremont. Smooth optimization with approximate gradient. SIAM Journal on Optimization, 1711:1777- 2008
O. Devolder, F. Glineur, and Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
I. Diakonikolas and D. M. Kane. Recent advances in algorithmic nigh-dimensional robust statistics. CoRR, 0bb//1911.05911 2019. URI. URL.http:/arxxi org/ abs/aaasa///// 1911. 05911.
I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statisties. Cambridge university press, 2023. Full version available https://siiess.oogle.. wwt.o/ggw...oo/eee//a/a/bbbooooo
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. In Proc. 57th IEEE Symposium Foundations of Computer Science (FOCS), pages 655-664, 2016.
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart. SEVER: A robust meta-algorithm for stochastic optimization. Proc. 36th International Conference on Machine Learning (ICML), pages 1596-16600 16666166.6666 2019.
I. Diakonikolas, D. Kane, and D. Kongsgaard. List-decodable mean estimation via iterative multi- filtering. Advances in Neural Information Processing Systems, 33:9312-9323, 2020a.
I. Diakonikolas, D. M. Kane, and A. Pensia. Outlier robust mean estimation with subgaussian rates via stability, Advances in Neural Information Processing Systems, 33:1830-1840, 2020b.
Diakonikolas, D. Kane, S. Karmalkar, A. Pensia, and Pittas. List-decodable sparse mean estimation via difference-of-pairg filtering, Advances in Neural Information Processing Systems, 35:13947-13960, 2022.
T. d' Orsi, C. H. Liu, R. Nasser, G. Novikov, D. Steurer, and S. Tiegel. Consistent estimation for pea and sparse regression with oblivious outliers. Advances in Neural Information Processing Systems, 34:25427-25438, 2021a.
T. d'Orsi, G. Novikov, and D. Steurer. Consistent regression when oblivious outliers overwhelm. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 2297-2306. PMLR, 18-24 Jul 2021b. URL http:// httpp://pocceediggg. wttpinn..........es//ere. wwtppppwwse/eeeeeettttpp httpa///11//ddoorr1taaaaaaaaa
T. d' d'Orsi, R. Nasser, G. Novikov, and D. Steurer. Higher degree sum-of-squares relaxations robust against oblivious outliers. CoRR, abs/2211.07327, 2022. doi: 0044550Waxii.221...7722 URL
https://doi. org/ 10. 48550/ arxiv. 22217.77377
E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances Neural Information Processing Systems, 30:25042- 15053, 2020.
11

---

S. Gupta, J. Lee, E. Price, and P. Valiant. Finite-sample maximum likelihood estimation of location. Advances in Neural Information Processing Systems, 35:30139-30149 2022.
Gupta, C. Lee, and E. Price. High-dimensionall location estimation via norm concentration for subgamma vectors. arXiv preprini arXiv:2302.02299, 2023.
M. Gurbuzbalaban and Y. Hu. Fractional moment-preserving initialization schemes for training deep neural networks. International Conference on Artificial Intelligence and Statistics, pages 2233-2241. PMLR, 2021.
M. Gurbuzbalaban, U. Simsckli, and L. Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pages 3964-3975. PMLR, 2021.
M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference machine learning, pages 1225- 1234. PMLR, 2016.
L. Hodgkinson and M. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. In International Conference on Machine Learning. pages 4262-4274 4274.. PMLR, 2021.
K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proc. 57th IEEE Symposium Foundations of Computer Science (FOCS), pages 665-67 655-674, 2016.
G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133 (1-2):365-397) 2012.
J. Z. Li, D. M. Absher, H. Tang, A. M. Southwick, A. M. Casto, S. Ramachandran, H. M. Cann, G. S. Barsh, M. Feldman, L. Cavalli-Sforza and R. M. Myers. Worldwide human relationships inferred from genome-wide patterns of variation. Science, 319:1100-110 2008
V. V. Mai and M. Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pages 7335. PMLR, 2021.
A. V. Nazin, A. S. Nemirovsky, A. B. Tsybakov, and A. B. Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80:1607-1627, 2019.
G. Novikov, D. Steurer, and S. Tiegel. Robust mean estimation without mean: Dimension- independent error polynomial time for symmetric distributions, 2023.
Paschou, J. Lewis, A. Javed, and P. Drineas. Ancestry informative markers for fine-scale individual assignment to worldwide populations. Journal of Medical Genetics, 47:835-844 2010.
S. Pesme and N. Flammarion. Online robust regression via sgd on the 11 loss. Advances in Neural Information Processing Systems, 33:2540-2553 2020.
N. Rosenberg. J. Pritchard, J. Weber, H. Cann, K. Kidd, L. Zhivotovsky, and M. Feldman. Genetic structure of human populations. Science, 198:2381-2388 2002.
A. Sadiev, M. Danilova, E. Gorbunov, S. Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov, and P. Richtárik. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. arXiv preprint arXiv:2302. 230.000999 2023.
Y. Shen and Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning. pages 3739-5748. PMLR, 2019.
U. Simsekli, L. Sagun, and M. Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
A. M.-C. So. Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity, 2013.
A. S. Suggala, K. Bhatia, P. Ravikumar, and Jain. Adaptive hard thresholding for near-optimal consistent robust regression. In Conference Learning Theory, pages 2892-2897, PMLR, 2019.
12

---

A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
H. Wang, M. Gurbuzbalaban, L. Zhu, U. Simsekli, and M. A. Erdogdu. Convergence rates of stochas- tic gradient descent under infinite noise variance. Advances in Neural Information Processing Systems, 11188866-188777 2021.
J. Zhang. S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra. Why adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33: 15383-15393, 2020. 2020.
13

---

Supplementary Material
Organization In Appendix A, we state some elementary probabilistic facts. The next two sections focus on proving our lemma on noisy location estimation. In Appendix B, we prove some critical lemmas used in the proof, and in Appendix C, we present the complete version of our location estimation algorithm, while addressing some typos in the main text. We mention some typos in footnotes and correct other minor typos without mention.
Moving forward, in Appendix D. we introduce an algorithm and prove a hardness result for the specific version of list-decodable mean estimation we consider, which differs from prior work. Finally, in Appendix E, we state the final guarantees we can get for the problem of list-decodable stochastic optimization, incorporating our lemma from Appendix D.
A Elementary Probability Facts
In this section, we recall some elementary lemmas from probability theory. Lemma A.1 (Hoeffding). Let X1,. X,, be independent random variables such that X; [a,, by]. Let Sn = Di= Xú, then for all 0
2n²
Pr[[S, E[S,] 20 exp
Ei (b: a.)²
Lemma A.2 (Multivariate Chebyshev). Let XI,..., Xm be independent random variables drawn from D where D is distribution over IR such that Ex=D[X] = O and Ex=D |X|||| S 0². Let
S. E X1, then for all t
Pm[||m||| 2 S o² /mm2
Proof.
We first prove the following upper bound,
E Σ Eielm] X; x12
E|Ei, (X; () v)]
Pr
Yu
||a|||
1.
Σ
X
> 1
m² t2
m² t2
mm(ml
E,s [[ (X, .)]
Σ, E v)2 m2 f2
Σ. 1
m2 12
m2 t
mo² o²
m² t
m t2
Since the inequality holds for all unit v, also holds for the unit o in the direction of Sm. completing the proof.
Fact A.3 (Inflation via conditional probability). Let y be random variable with mean p and variance o² and let & be an arbitrary random variable independent of y. then
Pr[s E (a, b)] < (1 21+2/A²) Pr(g + y E + + + oA)
< (1 (1+2/49) Pr(g + E -a- b b 14| + +AA]
Proof. To do this, we inflate the intervals and use conditional probabilities.
y <oA Pr(g E (a, = + (a - - -
and ly - <oo
Pr|ly-w|<od <
AA) and by al <oA] < <1+2//4) Pr[ ty (a (a+ - (
< (1-1/44) Pr(g ty (a+ 0
The second inequality above follows from observing that we are simply lengthening the interval. We will often use the second version for ease of analysis.
14

---

B Useful Lemmas
In this section, present some helpful lemmas for the algorithm noisy one-dimensional location estimation.
To recap the setting: We can access samples from distributions + and + v' + L. Here, Pr(s = 0] > a, y and y' are distributions with zero mean and bounded variance, and E IR is an unknown translation. Our objective is to estimate the value of I.
B.1 Useful Lemma for Rough Estimation
Our algorithm for one-dimensional location estimation consists of two steps. the first step, we obtain initial estimate of the shift between the two distributions by computing pairwise differences of samples drawn from each distribution. This involves taking the median the distribution of x + y. where r is symmetric and y has mean 0 and bounded variance.
The following lemma demonstrates that the median of this distribution is at most O O(aa-112) where is the standard deviation of y. Furthermore, this guarantee cannot be improved.
Roonded-variiaeee Distribution). Let x be random variable symmetric around 0 such that (0, 1). Pr(z = 0] 2 a. Let be a random variable with mean and variance o², IfS is set of O11/a log(1/6)) samples drawn from the distribution of y. [median(S) S O 1/2). -1/3).
Fact B.1 (Median of Symmetric
This guarantee is tight in the sense that there exist distributions for a and y satisfying the above constraints, such that median(x + y) can be as large Moo 1/2).
Proof. We show that Pr(æ +y < -O((oVaa) < 0.5 and Pr(s+y > O(a/Va)) < 0.5, as result, [median(x + y)1 < O(a/Va) We will later transfer this guarantee to the uniform distribution over the samples.
Applying Fact A.3 to the first probability, we see that Pr(r + -Ola/Va) < (1 + Pr(z < -O(a/ V.)..
Since Pr(æ 0] 2 a, we see that Pr(r < < s 1/2- aa
and so Pr[z+y < -0la/v/aa < (0.5))) <1+))00 =
0.5.
The upper bound follows similarly.
Since Pr(z 0] 2 a and Pr[yv] < <((o/va) 21 a we see Pr[|æ + yl < 0 vox 2 a/2. Hoeffding's s inequality (Lemma A.1) now implies that the empirical median also satisfies the above upper bound as long as the number of samples is greater than ((1)/a" log(1/8).
To see that this is tight, consider the distribution centered at O, whose density function is 2/(1 + 2)3 in the range [L, oo), and is otherwise.
Call this Dy-a. Observe that PRo, ./2 < 0(1) J dyy
Let æ be a symmetric distribution whose distribution takes the value 0 with probability a and takes the values to -1221/11000 1/002// + 10 with probability 0.5(1 a).
We show that the median of the distribution of where y is drawn from Dy-3, is larger than a(a -1/2).
To see this, we show that the probability that x + y takes value smaller than -12 is less than half, implying that the median has to larger than this quantity.
takes three values. Note that y - (-o0, 100c, 1002000001///2 + 10j. So to estimate the probability that x + y takes value smaller than 100a -1/2 + 10, only need to consider contributions from the other two possible values. By
1/2 C1/2 12 places mass in the region
15

---

choosing a small enough, so that 100a 103 10, we see
Pr/z - 100a -
< 0.5(1 - a) Priy < 2000 20] + Prly < 100a - 1/2 + +10]
< 0.5(1 a1 C/(22000 +0))) + a(1 C/(100a -//0//// 3/11000-1/22//1 + 10)3)
0.5(1 a) - a//3 (400)) +
+a
< 0.5 + 0.5a - a a////8 (0002)))))))
We are done when 0.5a - a 1/12/8- 2/22/-((400) < O, this happens for a < 2/((8 (400²))
B.2 Useful Lemma for Finer Estimation
In the second step of our location-estimation lemma, we refine the estimate of f. To do this, we first re-center the distributions based on our rough estimate, so that the shift after re-centering is bounded. Then, we identify an interval I centered around such that, when conditioning on & + 2 falling within this interval, the expected value of 5 + 2 remains the same as when conditioning on & falling within the same interval. This expectation will help get an improved estimate, which we use to get an improved re-centering of our original distributions, and repeat the process.
To identify such an interval, we search for pair of bounded-lenge lenthh intervals equidistant from the origin (for e.g. (- 10a, -5a) and (5a, 10or) that contain very little probability mass. By doing so, when z is added to &. the amount of probability mass shifted into the interval (-5o, 50) remains small.
In this subsection, we prove Lemma B.2, which states that any positive sequence which has a finite sum must eventually have one small element. The lemma also gives concrete upper bound on which element of the sequence satisfies this property.
Lemma B.2. 04 2 0 for all and Li=oa < C for some constant C. Also, suppose we have E (0, 1) and L E R such that L 2 1. Then there is an integer i such that L < i S (C/ao + 1n) and ia, 17 E)= ag.
Consider partition of the reals into length L intervals. Here, L simply denotes the length of the intervals and the lower bound to i, not the smoothness parameter.
In our proof, we will use Lemma B.2 on the sequence a;, where a, corresponds to an upper bound on the mass of & contained in the i-th intervals equidistant from the origin on either side, and the mass that crosses them (i.e., the mass of that is moved either inside or out of the interval when 2 is added to it).
We need the following calculation to prove Lemma B.2.
Notation: For integer i > 1 and 17 (0, 1), define (i 1)) 11)=1(j -7).
Fact B.3. Let A 1 + Σ k-1 g(t-1) ()-) Then, for k 2 A (k- - 1)1/(k 1-n)
Proof. We prove this by induction. By definition, our hypothesis holds for Ag because A 1 + (1 - 1) = 1/(1 -1) (2 1))/(2//222222 - 17)!. Suppose it holds for all 2 < L S k. We then show that holds for k
1 1)!
n (k - 1)!
Ak+1
A
(t 7)!
(k: 77)
(k 1)!
17 (k: 1)!
(k 1)!
[+ k
(k 17)!
(k:
- n7)
(k - 1 - 7)!
(k - 1)!
k
k!
(k: - 1/)! k:
(I: 7))!
16

---

Proof of Lemma B.2 Let U (Cjas + L and suppose towards contradiction that there is such that satisfies the lemma. That means, will assume that ia; 1) Eラ= Oj for all integers i E [1,0], or equivalently, we assume 2 i-n Ej= aj- We then show that this implies i-- 2 odla for all in the range.
Consider the inductive hypothesis on t given by dt 2 ワ since 2 /1 ri) by our assumption. Suppose the inductive hypothesis holds for integers t E [1, - 1]. We show this for below. By starting with our assumption then applying the inductive hypothesis, we have that
dg- The base case when = 1 true
0g
t=0
1OT
n 1)!
1
k: -
(1 n))
(k 1)!
[]: - 17)
The final equality follows from Fact B.3 which states that (k- - 1)1/(k - = (t-n)]
k- sit-i
Simplifying this further, we see that since (i - 17) 2 exxp(-n/i) for all E [1,
(k: 1)!
2 Gu? (k: n7)!
(k: 1)!
2 dn7l k. exeppp- -n/k)
407 (1/k) (1/ //eex((-m) > 1/1))
2=11
N an7l (1/k) (1/ /exp(=1) (k))
N (un/2)n) (1/22-1/20)
Finally, observe that
C>
0 > ann Σ
i=L.
> an (1/x--0) dx
11
= -00 L*).
By definition, U = (C/ao + 1/ so the above inequality cannot be true and thus we have arrived at contradiction. Then it follows that there exists an i such that S L s is (C/au + L?) and ia; Ei=0 aj.
C Noisy Location Estimation
In this section, we state and prove the guarantees of our algorithms for noisy location estimation (Lemma 3.1 and Lemma 3.5).
C.1 One-dimensional Noisy Location Estimation
Throughout the technical summary and some parts of the proof, we make the assumption that the variables y and y were bounded. Extending this assumption to bounded-varians distributions requires significant effort.
17

---

Our algorithm for one mee-dmmesioonal noisy location estimation (Algorithm 1) can be thought of as two-step process. The first step involves a rough initial estimation algorithm, while the second step employs an iterative algorithm that progressively refines the estimate by factor of in each iteration.
Due to space limitations and for ease of exposition, the algorithm present in the main body is sketch of the refinement procedure.
In this Algorithm 1, we introduce the definition of P (the empirical estimate of P())), which is an upper bound on the probability mentioned earlier. This probability can be calculated using samples from { + and Ç + z'. Additionally, we incorporate the iterative refinement process within the algorithm.
Algorithm 4 One-dimensional Location Estimation: ShiftID(S1, S2, n,,
Input: Sample sets $1, S2 C Rd of size m, o, E (0, 1), 0
1. Let T = O (1 (1/a)). For j E {1,2), partition Sj into T equal pieces, S for E [T].
2. D = {a b | a E s(1) b )
(1) == mDdian(D).
4. Set A = O()/va).
12, for going from 2 T: 6. 5(0) = s( - (i 1).
Repeat steps
For j (1,
P,(1) = O(1) Pr
||| E Ao(i - 5, 5 5)
+01 Σ (1/(1- j)a) Pr
E Ajo + Aol 4, 5.))
Let P()) A
Identify integer [1/onn), (C/a 1/(an) such that
P(k) S 1 Σ
Pr |||| Aokk + O(n/t).
jEf1.2 wnis
10. (1(1 = f(-
ste |2 |&| S Aok!
E E 1 Aok].
11. == -1A
12. Return (T(
Lemma C.1 (One--imensiionn docation-estimattinn There an algorithm (Algorithm 1) which, given (O()))((())/))) log(1 nyo) samples {Es - Us t) and {É, + - where & and & are both drawn from Dę. Yt and y are drawn from distinct distributions with mean-zero with variance bounded above by and e R is unknown translation, runs in time poly(1/n, (O())/a) log(1/8na)) and recovers t' such that It 1--1l S O(1o).
Proof. Our proof based on the following claims:
Claim C.2 (Rough Estimate). There is an algorithm which, given m ((11/a²) log(1/8)) samples of the kind & + y +nd & + t,,,, where E R is an unknown translation, returns t,, satisfying 1r, - < 0 1/2).
Claim C.3 (Fine Estimate). Suppose z,z' have means bounded from above by Ao (0, and a E (0, Then in
and variances at most o² and suppose poly((O(1)/an)) 2/m) /o,gg// log(l/ samples and poly((O(1)/om)) Jog(1/ōn())) time, it is possible recover k E [1/na, (0(1)/ma) ((1/n)))) such that
Elg IE + 2| < Aok) - EIS + z' 1 IE 211 < Aak E|2] E + n (Ao).
18

---

Using Claim 3.2, we first identify a rough estimate t, satisfying |t, - < ( -12).. This allows us to re-center y' Let the re-centered distribution be denoted by z' 1/ and y + t, Then and z' are such that E and El [=2]] are both most O 1/2) in magnitude, and have variance at most o².
Claim 3.4 then allows us to estimate t'y such that (E El2') - 1
n 0
Setting t' t2 + t'y. see that our estimate t' is now 77 times closer f compared to t....
To refine this estimate further, we can obtain fresh samples and re-center using t' instead of f Repeating this process (( = O(log,,(a) times is sufficient to obtain an estimate that incurs an error of 17 lo (a", 1/3) ( (((3) I (ngr).
This results in a runtime and sample complexity that is only Oloog, (/,51/,((///) (1/a)) times the runtime and sample complexity required by Claim 3.4. This amounts to the final runtime and sample complexity being poly voly((())) ((O(1)/a)) (am) log(1/87())).
We now prove Claim 3.2 and Claim 3.4.
Claim 3.2 shows that the median of the distribution of pairwise differences of + y + and & + y estimates the mean up to error of aa 1/2
Proof of Claim 3.2 Let & be a random variable with the same distribution drawn. We have independent samples from the distributions of & + y+ + t and & + y'. Applying
and independently
Fact B.1 to these distributions, we see that if we have at least O(1/a*) log(1/8) samples from the distribution of (5 - E) + (y 3/) + these samples will have median of t O(a/Va).
O
Proof of Claim 3.4 To identify such the idea is to ensure that Elg 1 2| S Aokj
Elg + 2 [5] S Aork] + ((Anor) Elg [&] s Aokk + E[2] + O(An)) and similarly for 2'. The
theorem follows by taking the difference of these equations.
Before we proceed, we will need the following definitions: let P(i, 2) be defined as follows:
P(i,)) 2) = -Prlkl E Ao - 1, 1)]
Pr[kk] < Aío, I8 + 2 Aio] + Pr[[g] Aio, I5 + 2| Aio).
This will help bound the final error terms that arise in the calculation. We will need the following upper bound on P(i,z) + 2'),
Claim C.4. There exists a function P R-
satisfying:
1. For all i E N, P(i) 2(i,2) + P(i,z) z') which can be computed using samples from & + and + +
2. There is a E ((1/an), (C/a + 1/ 1/(an))))/n such that kP(kk <n P(k).
3. Σ P(k) O(rr + =| < Ark] Pr[le + 2'1 S Ark))
4. With probability 1- for all (0(1)/a)V//) /n, P(i) can be estimated an accuracy of On/i) by using (0(1)/o) 2/n log(1 ff1o))/fff samples from & + and z'.
We defer the proof of Claim C.4 to Appendix C.2, and continue with our proof showing that Elg + = +1 < Aork & Elg + |6| < Aork for k satisfying the conclusions of Claim C.4. To this end, observe the following for [(, =) being either or + +
Eif(E, 2) 1(5) < oi)] - (f , 2) 1(1 + + 2 oi)]l
2] 1 > αi) 1(kg < ot)] + 2)) 1(|s + 21 1({g) ot)]
By setting [(E,2) == and considering the case where k satisfies the conclusions of Claim C.4, we can bound the "error terms"
Pr[k + 2| < Aok and [|| Aokk and Pr[k + z| > Ask and | < Aok] in terms of P(k).
19

---

Furthermore, P(k) itself is upper bounded by (Prl)) + + - Aok) + Pr[ls + 2'1 S Aook) as per Item 2 and Item 3. Putting these facts together, we have that
Pr[|í & Aok] Pr[l + =| v A
= (Pr]( + 2| - Aok] + Pr[l + +21 S Aoki).
A similar claim holds for the distribution over z'. An application of the triangle inequality now implies
Pr + 21 S Aok] Prik + 2| < Aok]] (n//k) (Pr[k S Aok] + Pr[k 2'1 S Aok)).
If A- BI < <T(A + B) it follows that (1 (11)//(1)><< < A/B < (1+7)(11-7) For r E 1/.).
this means A @( Applying this our case,
conclude that Pr[le + ='1 S Aok
((r]I + 2| S Ark)). Substituting this equivalence back into the previous expression, we obtain:
Pr[k S Ark] Pr[k + =1 S Aokil = (n//k) (Prile + =1 - Aork))
(1)
Similarly, when [(E, =) == & + z, we need to control the error terms: E[(s + =) 1(5 + z| S
Ark) 1([5) > Ark) and E[(E + =) 1 + 2 > Ark) 1(E) < Aak)].
Observe that (5 + 2) 1 + 2| - Aok) 1({) > Aork has a nonzero value with probability at most
E[1(K + 2| I Aork 1({) > Aork)] < P(t)). Also, the magnitude of (5 + 2) in this event is at most
Ark. Putting these together, we get that
E| + 2) 1(K + 2| S Aok) 1(() > Aok)] < AokP(k) < ((An))
PÚ).
Unfortunately, we cannot use the same argument to bound (f++2) 1[{ Aok) 1( < Aok)], since [5 + 2| is no longer bounded by Aok in this event. However, we can break the sum & + 2 as
follows: { + { + =1 [2] > Aok) + 21 I Aok). This allows to get the following bound:
E[(5 + 2) 1 + x| > Aak) ( S Aok)]
< 2AokP((k) + E(= 1[ > Aok) 1 + 2| > Aak) 1(() & Ark)]
2AokP(k) + El= 1(1=| > Aok))
< <2AokP(k)) + AArk
k
< <O(Ano Σ P()) + (Anoa))
where the third inequality follows by an application of Chebyshev's inequality, and the final inequality follows by choosing k 2 1/(ma)
Putting everything together, we see
k
E[[E + =) 1( + = S Ark)] = EI[E + 2) 1(k) < Aak)] = O(ArTa + Aon Σ P()) (2)
1=1
To finally compute the conditional probability, we use Equation (1) and Equation (2) to get
E[(5 + 2) 1(55 + 2| < Aak) = O(Anaa + Aon Σ P(j))
E[(E + 2) | S Aok]
Pr[ S Aak]
BI(E - 2) 1 2| < Ark) - OAAna + Aon E/=1 P()))
(n/k)) Pr[ + 2| & Aok)
((nk())))) E[[E + =) | + z| S Aok]
+0( Aona + Aon Pr[l + 2| - Aok]
Pril + 2) $ Aok)
= =E((g + 2) 11 + 2| < Aok + O(An))
20

---

where the second inequality is consequence of Item 3, and the last is due to the fact that Prilç + S Aork] a whenever k > which follows from an application Fact A.3 while noting the fact that Pr(s = 0] 2 a.
Taking difference for the above calculations for and z',
that, E[(5+ =) 1E + z| S Aok] - E((E + z') 15 + 2'1 S Aakj = E(a] = ( Consider this final error, and let O < CAno for some constant C. Repeating the above argument initially setting 17 r// /C, where C' is the constant gives us the guarantee we need.
Finally, we estimate the runtime and sample complexity of our algorithm. The main bottleneck in our algorithm is the repeated estimation of ((i) and estimation of E + 2) ls + 2 S Aark.
According to Item 4, each time we estimate P(i) to the desired accuracy, we draw (oly))) 1//,, log(1/ōrj()) samples.
An application of Hoeffding's 's inequality (Lemmaa A.1) then allows us to estimate the con- ditional expectation E[(5 + 2) E + 2| I Aak] to an accuracy of nAo by drawing poly(1/n, (O(1)/a) log(1/ôna)) samples as well. The exponential dependence here comes from the exponential upper bound on k.
C.2 Proof of Claim C.4
In this section, we prove the existence of P(-) which is upper bound P(i,z) + P(i,=') which we can estimate using samples from & + 2 and ç +'.
Proof of Claim C.4
Proof of Item
Recall the definition of 2).
2(i,2) = Pr[1g] E Ao 1 1)]
Pr([k] < Aio, [ + =| Aia] + Pr[[c] Aio, I5 + 2| < Aig]
For Item to hold, we need to define P(i) to be an upper bound on P(i,z) + P(i. z/) which can be computed using samples from & + and - z'. To this end, we bound P(i, z) follows. First, note that we can adjust the endpoints of the intervals to get
P(i, 2) < 3 Pr[Kk] E Ao(i 1)]
Prik A(i 1)o, |5 + +| Aio] + Prliel A(i+ 15 Aio]
Then, we partition the ranges in the definition above into intervals of length Aa to get:
P(i,z) < 3 Pr[le| E Aoli - 1,;++1)
Prilel Ajo + [0, Ao), 2/ Aio]
+ Pr[lg| > A(i 1)o, + Ajo + 10, Ao)].
Next, an application of the triangle inequality to |g| E Ajo +0, Ao) and | + 2| > Aio implies that |z| 2 A(i - 1)a. Similarly, the same kind of argument when [gl A(i 1)a and -- - + - El 2 A(i j)a. We then use Fact A.3
K + =| E Ajo + [0, Aa) demonstrates that
move from | + =| to [gl in the third term.
P(i, 2) < 3 Pr[[c] E Ao 1,1 1)]
2-2
Σ
Prile E Ajo + AoI0, 12 2 (i-j- 1)
1-1
+ +0(1)
Σ
Pr[lg| E Ajo + Ao(-2,3), 2 (i Ao]
1=1
21

---

An application of Chebyshev's inequality to 2, using the independence of and &, gives that
P(i,z) < Pr[lk E Ao(i - 1, 1)]
+0(
11/(i 1 11) Ajo + Ao 1)]
i-1
+ +0()
Σ (1/(1 ()a) | e Ajo + 2o1-2,3))
Another application of Fact A.3 applied (E + 2) z then gives us
P(i,z) < 3 Pr( 2| E Ao 5, 5)]
i-2
+ +1
1)2) Pr[l 2/ E Ajo + Aol-2.3) (1/(i --1) Σ
+LL Σ (1/(1- Pr[le + z Ajo + Aol-4,
Finally, extending all intervals so that they match, and observing that Σ)= - 1)2) Pr[ls+ =| E Ajo Ao(-2,3)] " (1/(i j)8) Pr[se =| Ajo 4,)-, we get
P(i,z) < ((1) Pr + z| E Ar 5, 5)
i-1
+ 0(1)
Σ (1/(1i - p + 21 E Ajo 4o|-4.5) J=1
We now let P(i, z) denote the final upper bound on P(i,z). The value of having P(i, 2) is that it can be computed using samples from + z.
2(i,z) = 0(1) Prik + 2 E Ao - 5,i+5) 5)]
+ +01
Σ j +1 Ajo + Ao(-4,5)
A=1
We defined P(i) = P(i, + P(i,z').
Proof of Item 2:
First observe that > i=0 P(i) C for some constant C. It is clear that this is true of the first term, since every interval will get over-counted at most 10 times. To see that the second term can be bounded, observe that
Prile + 2/ Ajo + Ao[-4.5)]
1=
(1/(i-)))) 5) Pr[s 21 Ajo + Ao[-4,5)
Prilg 2| E Ajo
Σ (1/(1-)) -
The first inequality follows by extending the limits of summation.
The final inequality follows from the fact that the total probability is at most 1, every interval of size gets over-counted at most finitely many times, and the fact that Σx= 1/k2 (1))
Item 2 now follows from the fact that P(i), i 2 quantity, and (()) 2 az/2, since the interval P(0) upper bounds is contains least constant fraction of the mass of & at that is moved by z', and Pr(s 0] 2
non-negative sequence that sums to a finite
22

---

Applying Lemma B.2, we get our result.
Proof of Item 3:
Let & be such that Item holds, i.e. (P())) E
P(k), then the goal is to show Σÿ=1 P(k)
O(Pr(K + =| < Aok Pr[l ='1 Aaak)).
We first consider the sum over i, of P(t, 2). It is easy to see that this is
Σ =(i,z)= 0(1) Pr[ls & 2| s Ao + +5]
+ +11 ΣΣ =
( () + =1 E Ajo + Aol-4,5)]
The first term the RHS is almost what want. We now show how to bound the second term,
()((--))) Pr + 2/ E Ajo + Ao(-4,,5)
(4/(1-))²) Pr(ls + + E Ajo + Ao(-
0:0yf
Σ Pr[ls + =| E Ajo + Ao(-4,5))
E (1/(1-1)²)
:=0;ief
k-1
< <0(1) Pr((S + z| Ajo Ao[-4,5)]
1=1
0(1) Pril + < A(k + 5)
The first inequality holds since any pair of (i,j) that has nonzero term in the first sum will also occur in the second sum, and all terms are non-negative.
The second equality is just pulling the common j term out.
The third inequality follows from the fact that Σ 1/f 0(1)
The fourth inequality follows from the fact that each ø-length interval is overcounted at most constant number of times.
This allows us to bound Σ 2(),2) by O(PriK + 2| < Ao(k + 5)]) overall. Similarly for E P(i, 2'), can obtain a bound of O(Prl + 2'| < Ao(k + 5)]). Putting these together,
see Ei_ P(i) s O(Prl + 2| < Ao + 5)] + Prik + 2'1 < Ao(k + 5)]). Finally, to get the upper bound claimed in Item 3, observe that
Pr[k + 21 < Ao(k + + Pr|l6 + 2/1 < Ao(k: k + 5)]
Pr[k + 2| < - -o) 4 - 2 < (k - 4)]
+ +Prll + 2| E A 5)] + Pr[k + z'1 E Ao 4, k +5]
Pr[le + z| < Ao(k - + - 2 < Ao(k: - 4)]
+P(k)
< Pr[lg + 2| < Aockk - 4) + Priis + 2' < Ao(k: - 4)]
+ +O(nk + x| < Ao + 5) + Pr[l + +z'| < Ao + +)])
Rearranging the inequality and by scaling such that that (17/k) < 1/2, we see that Pr[lg + 2| <
(k 5)] +P < (k [1 Prrk O(Pr(1g + < Aak) + Pr[[ + 2'1 < Aak)). completing our proof of Item 3.
Aa (k-k-4)) ((44))
Proof of Item 4:
23

---

Finally, to see Item 4 holds, observe that 0 < P(t) < O(1). Let B (1/))(())))))) denote the find A such that PP()) I E, P(i). Now, To estimate P(i) empirically, we partition the interval (-BAo, BAa) into B intervals of length Ao each, and estimate the probability of + a falling in each interval. If we estimate each of these probabilities to an accuracy of 17(110) B), we can estimate P(t) to an accuracy of (nn/i).
maximum index before which
An application of Hoeffding's inequality (Lemma A.I) tells that each estimate will require O(B² /n/² log(1 (5)) samples. Taking a union bound over all these intervals, we see that we will require ( /1}² log( (B/6)) samples.
Finally, another union bound over each E [0, B] implies that we will need O(B² /nf log samples. Substituting the value of B back in, we see that this amounts to requiring (L/1") log(L/n0d) samples.
log(BB// /8))
Estimating P(t) will take time polynomial in the number of samples, and so we take time (oly((0(1)/a)))),, 1/1, log(//oo))))
C.3 High-dimensional Noisy Location Estimation
In this section, we explain how to use our one-dimensional location estimation algorithm to get an algorithm for noisy location estimation in d dimensions.
The algorithm performs one-dimensional location estimation coordinate-wise after random rotation.
We need to perform such rotation to ensure that every coordinate has a known variance bound of o/vd.
Algorithm 5 High-dimensional Location Estimation: SS V, 0, input: Sample sets S,, S22 C IR of size m, E (0,1). 0,
Sample Ra.j i.i.d. from the uniform distribution over (+1/Vd} for i,j E [d]
2. Represent S1 and S22 in the basis given by the rows of R: ri.-.-,'d.
3. for E [d] do
of ShiftID(S es, S2 es, (la/Va).a) end
4. Change the representation of v' back to the standard basis. Probability Amplification: Repeat steps 1-4, == (log(1/5)) times to get C == {u/,.... 777)
6. Find a ball of radius (()r) centered at one of the v containing > 90% of C. If such vector exists, set v' to be this vector. Otherwise set v to be an arbitrary element of C.
5. Return v'.
Lemma C.5 (Location Estimation). Let Dy for i {1,2} be the distributions of & + ze for i E (1,2} where & drawn from Dg and Pre [g 0] 2 a and z, D; are distri- butions over Rdd satisfying Ep, = O and [|=][11]]]) S o². Let u E Rd be an unknown shift, and Dyz,0 denote the distribution of y2 shifted by There is algorithm (Algorithm 5), which draws poly(1/n, (O(1)/a)) (aoi://///////////////l log(1/8na)) samples each from Dy, and D runs in time poly(d, 1/n. (O(1)/a) /og( log(1/ 1/8ja)) and returns s' satisfying - S O(no) with probability 1 5.
Proof. Consider matrix R whose entries R, are independently drawn from the uniform distribution over +l/Vd. and whose diagonals are 1 1/vd.
Our goal is to show that with probability at least 99%, the standard deviation of each coordinate of Rz is bounded by (aa/ //), i.., the standard deviation Rz e; is at most ( /d) for all integer i in [d].
We can then amplify this probability to ensure that the algorithm fails with a probability that is exponentially small.
24

---

that the To see this, observe that Re e4 = and so Eg(r; 2) = O.
El 2)
E
Ba Big Elāpžd!
pe pEld.nE(d
Σ E E
E
B Rs.g Elzp2yl
=
p.gEld).ps
$ (of +2
Σ
Rip Rig
E ElZp2yl.
p.qEld.p<q
We now bound the second term with probability 99% via applying Chebyshev's inequality. Observe that E| S V
S o². Since R., and Rigg are drawn independently and p * 9, we see that the variables Ri.p and R Ri pairwise independent for pairs (p. 9) # (I, m). this implies O(a)), dd-... By choosing T ( /d),
El E[
(ccd Re.p Rr.g 00 > 7]
right-hand side above is at most 0.001/d.
A union bound over all the coordinates then tells us that with probability 99%, the variance of each coordinate is at most ( /d).
Then, for each coordinate we can identify of i + O through an application of Lemma 3.1. Putting these together with probability at least 99%, we find o' satisfying |/ - vll < O(1)a²).
Changing between these basis representations maintains the quality our estimate since the new basis contains unit vectors nearly orthogonal to each other. With high probability, the inner products between these are around ((1vV for every pairwise comparison, R approximates random rotation.
Probability Amplification: The current guarantee ensures that we obtain good candidate with constant probability of success. However, for the final algorithmic guarantee, we need a higher probability of success. To achieve this, we modify the algorithm as follows:
1. Run the algorithm T times, each time returning candidate v/ that is, with probability 99%, within O(no) distance from the true solution.
2. Construct a list of candidates = fof..... ..
3. Identify a ball of radius ( centered at one of the of that contains at least 90% of the remaining points.
4. Return the corresponding vy as the final output.
5. If no such o exists, return any vector from C.
Let E denote the event that point is within O(1o) to the true solution.
This will succeed with probability - exp(-T). To see why, observe the chance that we re- cover (2/3)T vectors outside the event E is less than (0.01)2/3((, (2/S7) < (0.047)" (7Tp)
<
(0.047)T(22 /VT) < (0.095)7.
D List-Decodable Mean Estimation
This section presents algorithm for list-decodable mean estimation when the inlier distribution follows D., Here, D, represents a set of distributions over Id defined as D, = {D Ep[x--
Ep|ø] [2] - d²). In our setting, receive samples from & 2, where Prig = 0] a, where can be close to 0. Our objective is to estimate the mean with a high degree of precision.
Note that the guarantees provided by prior work do not directly apply our setting. Prior work examines more aggressive setting where arbitrary outliers are drawn with a probability of a. These outliers might not have the additive structure we have.
25

---

Recall the definition of an S)-LMME algorithm:
Definition D.1 (Algorithm for List-Decodable Mean Estimation). Algorithm A is an (a, 3, 3.s))-DME
algorithm for D (a set of candidate inlier distributions) with probability 6 returns a list L of size s such that minpec 10--E---- Eg [=>D[=]] S for D E 'D when given M. samples of the kind z + for z ~ and Pr(g 0 a. If a is sufficiently small constant less than 1/2, then s
We now prove Fact 2.1 which restate below for convenience.
Fact D.2 (List-decoding algorithm). There is an (a,, njo ((11/)))))))) LLLDMM algorithm for the
inlier distribution belonging Do which runs in time D(d(1/a)3/() and succeeds with probability
1 - 6. Conversely, any algorithm which returns list, one of which makes an error of at most (
in 2 norm to the true mean, must have a list whose size grows exponentially in 1/m..
If is a sufficiently small constant less than half, then the list size to get an error of O(v1 - a..
Proof. Algorithm: Consider the following algorithm:
If a < c and r > va: Run any stability- based robust mean estimation algorithm from Diakonikolas et al. [2020b] and return singleton list containing the output of the algorithm.
2. Otherwise, for integer each i [1, (0,1/((//)))// log(1/6)9 sample 1/n/ samples and let their mean be f0z-
3. Return the list L = {us [1, (001/a//))) log(1/8)3)
If the algorithm returns in the first step, then the guarantees follow from the guarantees of the algorithm for robust mean estimation from Diakonikolas et al. [2020b] (Proposition 1.5 on page 4),
Otherwise, observe that the probability that every one of 1/1/ samples drawn is an inlier, is !/n
Hence, with probability 1-6 we see that we draw 1/1/ samples (((1/a)²/1 log(1/8)2) times, there are at least Oloog( 1 sets of samples containing only inliers. Then, the mean of one of these concentrates to am eтror of O(nor) by an application of Lemma A.2. More precisely, Lemma A.2 ensures that with probability 99%, the mean of set of 1/1) inliers concentrates up an error of O(no). Repeating this log(1/8) times, we get our result.
Hardness: To see that the list size must be at least exp(1/n). consider the set of inlier distributions given by {D. E {=1]d} where each D. is defined as follows: D is a distribution over Bd such that each coordinate independently takes the value 8; with probability 1/d, and otherwise.
Each D. defined above belongs to V1 VI-1/d since Ez,D, [x] = s/d and
d
a²
E || - s/d| DnD
[( - (la-ss/df3 /d/
Dc((D,)
[1 (1- (1-1//)(1/a)211 (1/0((1 (1-1))
We will set the oblivious noise distribution for each D, to be D, Our objective is to demonstrate that the distribution D, D. the same for all and is independent of This means that we cannot identify by seeing samples from D. D..
Then, since the means of D, and D'2 for any distinct pair 8, E (+1]d differ by least 1/d, if set d 1/1 see that there 21/9 possible different values of the original mean, each pair being at least 77 far apart, which is larger than no² = 17(1 17).
We can assume, without loss of generality, that 1, where 1 represents the all-ones vector. Each coordinate of D, can be viewed as random coin flip, taking the value with probability 1/d and 1 with probability 1/d.
26

---

The probability of obtaining the all-zeros vector is given by (1 - 1/d)", which approaches constant value for sufficiently large and so, Pr.-D, [2. 2 0.001, the for the oblivious noise is at least a constant. In fact, it can be as large as e/e 0.35 for large enough d.
Let the oblivious noise be DD Now, consider the distribution of x + y. where follows the distribution D and follows the distribution - DD If we focus on the first coordinate, 21 + 91. we observe that it follows symmetric distribution over 1-1,0, 1} which does not depend on s1. Also, each coordinate exhibits the same distribution, and they are drawn independently of one another. Hence, the final distribution is independent of s, so we get our result.
E Proof of Corollary 4.2
Below, we restate Corollary 4.2 for convenience.
Corollary E.1. Given access to oblivious noise oracle Oo,o., f. a -neeexactteee Ag running in time TG, there exists an algorithm that takes poly ((1 /a)///" (0(1)/n)) log(Ta/Ena)) samples, runs in time Ta- poly(d, (1/a))/r², (O(1)/n))/n log Log (/)ja))), and with probability returns a list of size (((1/a))/²) such that min f=)] I ((1o) - Additionally, the exponential dependence on 1/n in the list size is necessary.
Proof. This follows by substituting the guarantees of Fact 2.1 for the algorithm AME in Theorem 1.4.
F
Varying Noise Assumptions
In this section, we demonstrate that changing some distributional assumptions of the oblivious noise & can yield better guarantees simpler algorithms.
F.1 Stronger Concentration on Yields Polynomial Dependence 1/n
We show that if the oblivious noise has bounded tails we can avoid the exponential dependence on 1/1, which we have shown in Appendix D to be necessary under standard assumptions.
For the sake of demonstration, we will assume the standard assumptions of heavy-tailed stochastic optimization where the mean of & is equal to zero and the variance of & is upper bounded by a, as is done in Gorbunov et al. [2020]. In this specific setting, our algorithm remains the same but our analysis becomes tighter in Item 2 of Claim C.4. Our original analysis yields an exponential dependence on 1/1 due to the upper bound on k. yet with concentration on the noise, we can show that k = (oly(1/a, 1/m).
Due to our specific construction of P(k) in the proof of Claim C.4 of Item 1, we have that kP(k) < 0(3-1/3) and a/2 < P(1) < Σ5= P(j). Thus, when k O ( the inequality of Item is satisfied. The fact that a/2 < P(1) is given, and thus, what remains is to show P(k) < 4/3 44/3,
which follows by splitting the summation in P(i, over j 1,..., k - 1 into E [1, 2// and j E (1.2/3 11. The sum over [1, k2233 is upper bounded by 0(k-1/3) and the sum over (1/// k O(ak- 4/3) using Chebyshev's inequality. Therefore, P(k) S
is upper bounded by 0(A-2k-4/3) 4-33 and k- p1ly(1/a, 1/n) in Claim 3.3.
Ultimately, it would be an interesting direction to identify conditions necessary and sufficient for polynomial dependence on 1/n.
F.2 Small Fraction of Adversarial Corruptions
If, on the other hand, at each point you have access to gradients v(z) such that with probability - you see fz 7), which concentrates around V fz, 7) and with probability you see an arbitrary point, then one can use robust mean estimation instead of location estimation algorithm and recover guarentees which are correct upto an error of ((Ve).
In this case, there is no need for list-decoding robust location estimation.
27


Reviews:
[{"review_id": "YUcfzvezlZ", "reviewer": "Reviewer_FMyo", "summary": "This paper introduces a new setup for stochastic optimization, where in addition to random observation noise, the stochastic gradient may be subject to independent oblivious noise. This noise might not have bounded moments and isn't necessarily centered. The authors propose a Noisy Location Estimation approach that estimates the gradient difference between two points, specifically \\nabla f(x_t)-\\nabla f(x_0). As such, they maintain robust estimations of the gradient at all points {x_t} as long as there is a reliable estimation of \\nabla f(x_0).", "questions": "1. In Line 227, it appears that [i- 4 · 12, i + 4 · 12) almost fully contains [i - 4 · 12, -i + 4 · 12)]. If that's the case, why is there a need for a \\cup operation?\n2. In Section 5, why is the exponential dependence on 1/\\eta for the size of the list unavoidable?\n3. Is it a requirement for the Noisy Location Estimation that alpha > 0? I didn't delve into the proof details, but it seems that if you're considering the conditional expectation, it might not require alpha > 0. Can you clarify this?", "limitations": "As discussed in Weakness.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The new setup for oblivious noise introduced in the work is plausible, and the authors effectively discuss its relation to existing research. The Noisy Location Estimation proposed by the authors provides an innovative way to estimate gradient differences accurately, reducing the stochastic optimization problem to a mean estimation problem, which seems simpler in the setting. Also, as shown by the authors, the reverse of the reduction holds by simple arguments.", "weaknesses": "The paper's presentation, particularly in the technical sections, lacks clarity.\n\n1. Definitions should be more precise and self-contained. For instance, the work seems to require that oblivious noise be independent of the noisy gradient, but Definition 1.1 doesn't explicitly state this. In Definition 1.3, phrases like \"sufficiently small constant\" are too vague.\n2. The methodology for mean estimation (Fact 2.1), isn't discussed in the main body. A brief discussion may be helpful.\n3. The \"Rejection Sampling\" discussion on page 5 is difficult to follow and potentially misleading. From my understanding, the core intuition is to identify a large enough domain of size $i$, such that $i$ times the conditional expectation is robust and stable upon shifting the domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first give a common response, and then addresses the specific concerns of the reviewer. \n\n**Common Response**\n\nTo summarize, our paper investigates a generalization of the heavy-tailed stochastic optimization problem. \nAs highlighted by reviewers M73n, NDsr, and 2f9g, our work addresses a challenging and well-motivated scenario with minimal noise assumptions. \nIt introduces a novel perspective on the connection between stochastic optimization and problems such as list-decodable mean estimation and location estimation, \nemploying an innovative efficient reduction (reviewer 2f9g and FMyo). \nA significant contribution of our work is the resolution of the noisy location estimation problem. The proof of our algorithm’s guarantee is novel and technically involved (reviewers 2f9g and NDsr). \nNotably, our method produces a single candidate for a sufficiently small constant fraction of outliers, allowing for a direct comparison with previous approaches in stochastic convex optimization.\n\nWe will fix the typos and address minor comments mentioned by the reviewers in the final version of the manuscript. \nWe now address more specific concerns of the reviewer. \n\n**Response to Reviewer FMyo**\n\nThank you for taking the time to review our paper and for appreciating the innovative reduction.\n\nWe address your concerns below, most of which have been addressed in the supplementary material:\n \n1. **“Sufficiently small constant”**:  \nThis is common terminology in the learning theory literature. It means “there is a sufficiently small universal constant”. In our case, a constant of $\\min{½, \\eta^2}$ suffices, where $\\eta$ is the final intended approximation error. Prior work in algorithmic robust statistics is able to perform efficient robust mean estimation tolerating up to half the samples being corrupted while achieving a guarantee of $\\sigma \\sqrt{\\epsilon/(1-2\\epsilon)}$, where $\\epsilon$ is the fraction of corrupted points (see, for e.g. exercise 2.10 in [2], or [1]). \n\n\n2. **Definition of oblivious noise**:  \nIndeed, the noise is independent of $x$ as well as $\\gamma$ as mentioned on lines L5-L8 of the abstract. \n\n\n3. **Methodology for list-decoding**:  \nWe use a list-decodable robust mean estimation subroutine in a black-box manner in the main body of our paper. (That is, one can use any efficient algorithm with this performance guarantee in our setting; prior work has developed such algorithms, see, e.g., [3, 4]). That said, please see the algorithm described on L821-L826 in the supplementary material. \n\n\n4. **Rejection sampling procedure hard to follow**:  \nThe reviewer’s understanding of the rejection sampling procedure is accurate. We will clarify any potentially confusing phrasing.  \n\n\n5. **Line 227**:  \nYes, this is a typo. The second interval is $[-i - 4 \\cdot 12\\sigma, -i+4 \\cdot 12\\sigma)$. The second term is “$-i$”.\n\n\n6. **Exponential dependence on $1/\\eta$**:  \nOn L835-L855 of the supplementary material, we provide an information-theoretic lower bound demonstrating that the exponential dependence is inherent. Specifically, we show the existence of $\\exp(1/\\eta)$ different pairs of inlier distributions and oblivious noise distributions, each inlier distribution having a different mean, such that the sum of the inlier distribution and the oblivious noise distribution is exactly the same in every case. \n\n\n7. **$\\alpha > 0$ requirement**:  \nThere must be some concentration that the oblivious noise satisfies, since for instance it is not possible to efficiently distinguish between $[-R, R]$ and $[-R+1, R+1]$ as $R \\rightarrow \\infty$. In our algorithm this appears in our noisy location estimation, which runs in two phases. The first step of this is a rough estimate, whose error goes as $O(\\sigma \\alpha^{-½})$ – and this is tight, as shown in the proof of the rough estimation –  the second step is to improve this to a much finer estimate (see L614-L617 of the supplementary material). For the rough estimation to work, we will require $\\alpha > 0$. \n\n[1] B. Zhu, J. Jiao, and J. Steinhardt. Robust estimation via generalized quasi-gradients. Information and Inference: A Journal of the IMA 11.2  2022.\n\n[2] I. Diakonikolas, and, D. Kane. Algorithmic High-dimensional Robust Statistics. \n\n[3] M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 2017.\n\n[4] I. Diakonikolas, D. Kane and D. Kongsgaard. List-Decodable Mean Estimation via Iterative Multi-Filtering. NeurIPS 2020\n\n"}, {"review_id": "Om29V3zxzA", "reviewer": "Reviewer_NDsr", "summary": "This paper studies robust first order optimization in a challenging setting where noise may be unbounded, a setting that arises often for real world optimization problems. Because this problem is intractable in general, one needs to make plausible assumptions on the noise, that are realistic on one hand but allow for efficient analysis.\n\nThe noise model proposed here allows for noise to be unbounded, and introduces two simple constraints:\n\n1. The unbounded noise when computing a gradient is *oblivious* in the following sense: there are two noise components, one that is well-behaved (zero mean and bounded variation), and one that is unbounded but oblivious/indpendent of both the location in which gradient is computed and the value of the well-behaved part of the noise.</li>\n\n2. We assume the unbounded noise has probability bounded away from 0 to be equal to zero (i.e., to not exist at all).\n\nIt turns out that these two relatively weak conditions allow for efficient robust first order optimization. Specifically, these conditions allow for list-decodable robust optimization, where the goal is to output a list of candidate outputs where at least one should be a good approximation of the correct optimization outcome. The main technical result shows how to solve this problem by reducing it to list-decodable mean estimation, a problem that enjoyed substantial progress in recent years. The authors also show a reduction in the opposite direction. A substantial component in the technical analysis is a procedure that the authors develop for location estimation in an appropriate noisy setting.", "questions": "Comment: my review is a low-confidence one (as a non expert in the field) and I may have missed central points in the paper, so may update the score after subsequent reviewers and authors discussions.", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Interesting and important goal, of better understanding the beyond worst case landscape for (first order) optimization.\n\n2. Writing is very clear and relatively easy to follow for me (a non-expert outsider). \n\n3. The assumptions required for the analysis are weak and seemingly realistic.", "weaknesses": "1. The technical novelty is perhaps somewhat limited, the work relies heavily on reductions to existing results in robust mean estimation.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first give a common response, and then addresses the specific concerns of the reviewer. \n\n**Common Response**\n\nTo summarize, our paper investigates a generalization of the heavy-tailed stochastic optimization problem. \nAs highlighted by reviewers M73n, NDsr, and 2f9g, our work addresses a challenging and well-motivated scenario with minimal noise assumptions. \nIt introduces a novel perspective on the connection between stochastic optimization and problems such as list-decodable mean estimation and location estimation, \nemploying an innovative efficient reduction (reviewer 2f9g and FMyo). \nA significant contribution of our work is the resolution of the noisy location estimation problem. The proof of our algorithm’s guarantee is novel and technically involved (reviewers 2f9g and NDsr). \nNotably, our method produces a single candidate for a sufficiently small constant fraction of outliers, allowing for a direct comparison with previous approaches in stochastic convex optimization.\n\nWe will fix the typos and address minor comments mentioned by the reviewers in the final version of the manuscript. \nWe now address more specific concerns of the reviewer. \n\n**Response to Reviewer NDsr**\n\nThank you for taking the time to review our paper. \n\nIndeed as you point out, a large part of our contribution is connecting the robust statistics literature to stochastic optimization, which involves developing novel efficient reductions between existing results in robust statistics and stochastic optimization for our setting.\n\nThat said, we would also like to emphasize that our location-estimation algorithm is novel and technically involved (algorithm 4, L608-609 in the supplementary material).\n\nPlease look at Section C of the supplementary material for more details. \n"}, {"review_id": "0zc9Wv88GC", "reviewer": "Reviewer_M73n", "summary": "The paper considers the problem of stochastic optimization with oblivious noise. Here, one receives noisy gradients of a non-convex function $f(x) = \\mathbb{E} [f(x, \\gamma)]$ (where $\\gamma$ is bounded variance observational noise) and the noisy gradient samples are generated as follows $\\nabla_x f(x, \\gamma) + \\xi$ where $\\xi$ is generated independently of $\\gamma$ and $x$ with the only restriction that $\\mathbb{P} (\\xi = 0) \\geq \\alpha$. The paper specifically focuses on the setting where $\\alpha \\ll 1 / 2$. Under such mild restrictions on $\\xi$, it is impossible to recover a single point which is guaranteed to be near-stationary. However, in line with recent results on list-decodable robust estimation, the paper shows that one can recover a list of estimates one of which is approximately stationary. \n\nTechnically, the paper builds on two recent results on robust estimation. The first is SEVER which is a robust stochastic estimation algorithm focusing on the setting when $\\alpha \\to 1$. In this setting, it is possible to leverage recent robust estimation algorithms to clean the observed gradients and recover a good approximation to the true gradient (up to the degree determined by $1 - \\alpha$) and then utilize this approximate gradient to find a stationary point. The second is a recent line of work on list-decodable mean estimation. Here, one receives corrupted samples from a high-dimensional distribution where $\\alpha$ fraction of points are from the true distribution and the goal is to estimate its mean. While producing a single estimate is impossible, these algorithms return a list of size $1 / \\alpha$, one of which is guaranteed to be accurate. In this paper, the authors essentially extend the SEVER framework to the list-decodable setting. However, this requires some novel technical contributions. A naive implementation would lead to exponential growth in the number of estimates (a list of size $l$ would have $l / \\alpha$ many elements in the next iteration if each of its elements were queried and updated with the $1 / \\alpha$ resulting gradients). Instead the authors introduce a novel technical tool that they term location estimation which when given samples from $z + \\xi$ and $z' + t + \\xi$ for some unknown $t$ (and $z$ and $z'$ have bounded covariance) can estimate $t$. With this tool, the algorithm starts by first generating $1/\\alpha$ gradients at $0$ and initializing $1 / \\alpha$ candidates each corresponding to one of the estimates. Then, each element of the list, $x$, is queried to produce gradient estimates. The location estimate procedure is then run on gradient estimates from $x$ and $0$ to essentially estimate $\\nabla f(x) - \\nabla f(0)$. Finally, from this each candidate is updated by estimating $\\nabla f(x)$ using the particular estimate of $\\nabla f(0)$ it corresponds to.\n\nOverall, this is a really nice paper studying an interesting problem. My one concern is in the assumptions made in the paper. For instance, the assumptions don't capture the canonical estimation problem of list-decodable mean estimation. Here, one assumes that the true distribution has covariance bounded in spectral norm whereas this paper essentially assumes a bound on the expected squared length of a data point which could be larger by a factor of $d$. It would be interesting to see if these results could be extended to setting with weaker assumptions. Can we obtain similar results with $\\mathbb{E} [(\\nabla f(x, \\gamma) - \\nabla f(x)) (\\nabla f(x, \\gamma) - \\nabla f(x))^\\top] \\prec \\sigma^2 I$ as opposed to the stronger assumption in this paper of $\\mathbb{E} [\\|\\nabla f(x, \\gamma) - \\nabla f(x)\\|^2] \\prec \\sigma^2$ used here.\n", "questions": "See main review", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See main review", "weaknesses": "See main review", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first give a common response, and then addresses the specific concerns of the reviewer. \n\n**Common Response**\n\nTo summarize, our paper investigates a generalization of the heavy-tailed stochastic optimization problem. \nAs highlighted by reviewers M73n, NDsr, and 2f9g, our work addresses a challenging and well-motivated scenario with minimal noise assumptions. \nIt introduces a novel perspective on the connection between stochastic optimization and problems such as list-decodable mean estimation and location estimation, \nemploying an innovative efficient reduction (reviewer 2f9g and FMyo). \nA significant contribution of our work is the resolution of the noisy location estimation problem. The proof of our algorithm’s guarantee is novel and technically involved (reviewers 2f9g and NDsr). \nNotably, our method produces a single candidate for a sufficiently small constant fraction of outliers, allowing for a direct comparison with previous approaches in stochastic convex optimization.\n\nWe will fix the typos and address minor comments mentioned by the reviewers in the final version of the manuscript. \nWe now address more specific concerns of the reviewer. \n\n**Response to Reviewer M73n**\n\nThank you for your insightful and detailed review. \n\nWith regard to your concern about the disconnect between the noise models in robust statistics and the noise in the paper, the assumption we make is common in the optimization literature (see, for e.g. [1,2]). In this setting, these works assume that the squared norm of the deviation satisfies bounded variance. \n\nIndeed, this setting is easier than the usual assumptions that are used in the robust statistics literature. However, even in this setting, we demonstrate a lower bound on the list size that is exponential in the approximation error (see L835 - L855 of the supplementary material). \n\nExtending this to the more general setting is an interesting future direction. \n\n[1] V. V. Mai and M. Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. International Conference on Machine Learning, 2021.\n\n[2] E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33: 15042–15053, 2020."}, {"review_id": "f0Bwsx6MLQ", "reviewer": "Reviewer_5dvc", "summary": "The paper presents an algorithm for first-order stochastic optimization where the algorithm has access to an oracle that returns a noisy version of the gradient of the objective function. The considered noise model includes two components: A bounded-variance observation noise (which is the typical well-studied type of noise), and oblivious outliers noise $\\xi$ satisfying $Pr[\\xi = 0] >= \\alpha$. Furthermore, the distribution of the oblivious noise \\xi does not need to be symmetric.\n\nIt is shown that if the fraction of inliers is below 1/2, it is information-theoretically impossible to give a unique solution. This is why the authors consider a list-decodable learner where the learner returns a list of solutions, one of which is guaranteed to be good. The authors show that if the fraction of inliers is sufficiently close to 1, then the algorithm can recover a single solution.", "questions": "- What are the properties of the function $f(\\gamma,x)$ which are needed for the main result to hold?\n- Page 4, line 203: Is $\\xi$ in $\\xi + y' + t$ the same as the $\\xi$ in $\\xi + y$, or is it an independent instance? It seems from the following discussion that the authors consider an independent instance. If this is the case, please write $\\xi' + y' + t$.\n- Page 7, line 309: What is $L$? Is it the same as the $L$ of Section 2? But in Section 3 we don't have a parameter $L$ for location estimation.\n- There doesn't seem to be a proof for Claim 3.3 (even in the appendices).", "limitations": "No concerns regarding potential societal impact of this work.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Designing learning algorithms which are robust against adversarial or semi-adversarial type of noise is very important. The setup that is considered in this paper is original (as far as I can tell).", "weaknesses": "I found the paper to be generally not very well written. The notation is a bit confusing in several places (e.g., check the question regarding line 203 below), and the writing style can be sometimes too informal.\n\nOne thing that I found crucially missing is the clear and formal statement of the problem and the clear statements of the assumptions. For example, what are the properties of the function $f(\\gamma,x)$? The only property that I found is that $f(x) = E_{\\gamma}[f(\\gamma,x)]$ must be $L$-smooth. However, this is clearly not enough to even guarantee the existence of a stationary point. For example, consider $x\\in \\mathbb{R}$ (i.e., one dimension) and define $f(\\gamma,x) = x$. In this case, we have $f(x) = x$ and hence $\\nabla f(x) = 1$ fo all $x$ and there is no stationary point.\n\nTypos:\n- Page 4, line 175: \"we can a generate list\" -> \"we can generate a list\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first give a common response, and then addresses the specific concerns of the reviewer.\n\n**Common Response**\n\nTo summarize, our paper investigates a generalization of the heavy-tailed stochastic optimization problem. As highlighted by reviewers M73n, NDsr, and 2f9g, our work addresses a challenging and well-motivated scenario with minimal noise assumptions. It introduces a novel perspective on the connection between stochastic optimization and problems such as list-decodable mean estimation and location estimation, employing an innovative efficient reduction (reviewer 2f9g and FMyo). A significant contribution of our work is the resolution of the noisy location estimation problem. The proof of our algorithm’s guarantee is novel and technically involved (reviewers 2f9g and NDsr). Notably, our method produces a single candidate for a sufficiently small constant fraction of outliers, allowing for a direct comparison with previous approaches in stochastic convex optimization.\n\nWe will fix the typos and address minor comments mentioned by the reviewers in the final version of the manuscript. We now address more specific concerns of the reviewer.\n\n**Response to Reviewer 5dvc**\n\nThank you for taking the time to review our paper and acknowledging our original setup. The main body of the paper attempts to communicate the ideas involved and hence sometimes is somewhat informal. \n\nHere are answers to your more specific questions:\n\n1. **Properties of $f(\\gamma, x)$**:  \nThank you for pointing this out. Our main contribution is a general method for de-biasing gradients (robust gradient estimator) which can be used along-side any standard stochastic optimization method that requires unbiased gradients. Our de-biasing method does not require any assumptions beyond those mentioned in Definition 1.1 (and the fact that the noise is independent). However, there may be additional assumptions that the black-box optimization algorithm requires.   \nAs stated on L282-L284 of the main body, if we use the algorithm from [1] for our underlying learner, in addition to the function being $L$-smooth, we would also need that a global minimum exists and that the initial function value has a bounded gap to reach a point with small average gradient. We will mention this assumption in the definition.\n\n\n2. **$\\xi + y’ + t$ and $\\xi + y$**:  \nWe think of $\\xi, y, y’$ as random variables. Indeed, it is an independent instance. \n\n\n3. **$L$ on Line 309**:  \nIt is not the same $L$ as in Section 2. One may think of $L$ as a free parameter here, this holds for any $L > 0$. It comes from Lemma B.2 in the supplementary which is a lemma used in Claim C.4 (more formal version of Claim 3.3). As can be seen in Claim C.4, $L = 1/\\eta \\alpha$ suffices for our case.\n\n\n4. **Proof of Claim 3.3**:  \nThis is claim C.4 in the appendix, the proof of which is in section C.2 (starting at L690 in the supplementary material). \n\n[1] A. Ajalloeian and S. U. Stich. Analysis of sgd with biased gradient estimators. arXiv preprint arXiv:2008.00051, 2020.\n\n\n"}, {"review_id": "484N9ZfTpM", "reviewer": "Reviewer_2f9g", "summary": "This paper initiates the study of stochastic optimization with oblivious noise that might be biased and have unbounded variance, which is a generalization of the heavy-tailed noise setup. The key assumption regarding the oblivious noise is that it assumes a value of $0$ with a probability within the range of $0 \\leq \\alpha \\leq 1$, which can be interpreted as the fraction of inliers. Notably, when $\\alpha \\leq 1/2$, it is proven to be information-theoretically impossible to find an approximate stationary point of the function. To address this challenge, the authors incorporate the concept of list-decoding into the framework of stochastic optimization, and focus instead on identifying a list of points where at least one of them is an approximate stationary point.\n\nTechnically, this paper presents an equivalence between list-decodable stochastic optimization with oblivious noise and list-decodable mean estimation problem leveraging a technique known as noisy location estimation. The analysis of list-decodable stochastic optimization with oblivious noise is conducted by examining the list-decodable mean estimation problem.", "questions": "Correspondingly, I have the following questions that could possibly make the results even stronger if addressed:\n1. Can the exponential dependence on $\\eta$ be mitigated by making slight adjustments to the original definition of list-decodable stochastic optimization? For instance, are there additional assumptions that can be incorporated or specific parameter regimes that can be adjusted to reduce this exponential dependency?\n\n2. Are there more concrete applications of list-decodable stochastic optimization methods? \n\n3. Minor comment: I saw the term \"convex\" in the caption of Algorithm 2. I assume this is a typo and convexity is not needed in the proof, right?", "limitations": "Not relevant in my opinion.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper investigates an important setting of stochastic optimization introduces a fresh perspective by introducing the concept of list-decodable stochastic optimization. The definition of this new framework is not only intuitive and well-motivated by practical problems but also exhibits elegance from a theoretical standpoint, given how weak the assumptions on the noise model are. The algorithms presented in the paper, along with their corresponding proofs, are intricate and highly nontrivial from a technical standpoint. Nevertheless, the authors have succeeded in presenting the analyses in a well-organized manner, ensuring that they are generally not hard to follow.", "weaknesses": "1. As pointed out in the paper, an exponential dependence on $1/\\eta$ is necessary in the list-size, which can mildly impact the overall appeal of the results. This dependency may introduce some considerations regarding scalability and practicality.\n\n2. The framework presented in this paper is inherently abstract, and there is a lack of clarity concerning the algorithm's performance in concrete examples, including scenarios with more specific theoretical settings that incorporate additional assumptions, as well as practical problem domains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first give a common response, and then addresses the specific concerns of the reviewer.\n\n**Common Response**\n\nTo summarize, our paper investigates a generalization of the heavy-tailed stochastic optimization problem. As highlighted by reviewers M73n, NDsr, and 2f9g, our work addresses a challenging and well-motivated scenario with minimal noise assumptions. It introduces a novel perspective on the connection between stochastic optimization and problems such as list-decodable mean estimation and location estimation, employing an innovative efficient reduction (reviewer 2f9g and FMyo). A significant contribution of our work is the resolution of the noisy location estimation problem. The proof of our algorithm’s guarantee is novel and technically involved (reviewers 2f9g and NDsr). Notably, our method produces a single candidate for a sufficiently small constant fraction of outliers, allowing for a direct comparison with previous approaches in stochastic convex optimization.\n\nWe will fix the typos and address minor comments mentioned by the reviewers in the final version of the manuscript. We now address more specific concerns of the reviewer.\n\n**Response to Reviewer 2f9g**\n\nThank you for your insightful and detailed review. We address your questions below. \n\n1. **Exponential dependence on $1/\\eta$ and concrete runtime in specific settings:**  \nIndeed, this is an interesting question, and we can mitigate the exponential dependence on $1/\\eta$ if we make additional assumptions on the oblivious noise $\\xi$.  \nFor the sake of demonstration, we will assume the standard assumptions of heavy-tailed stochastic optimization where the mean of $\\xi$ is equal to zero and the variance of $\\xi$ is upper bounded by $\\sigma$, as is done in [1]. In this specific setting, our algorithm remains the same but our analysis becomes tighter in Claim 3.3 (or Claim C.4) item 2. Our original analysis yields an exponential dependence on $1/eta$ due to the upper bound on $k$, yet with concentration on the noise, we can show that $k = poly(1/\\alpha, 1/\\eta)$.  \nDue to our specific construction of $\\tilde{P}(k)$ in L710, we have that $k\\tilde{P}(k) \\le O(k^{-1/3})$ and $\\alpha/2 \\le \\tilde{P}(1) \\le \\sum_{j=1}^k \\tilde{P}(j)$. Thus, when $k \\ge O(1/(\\alpha \\eta)^3)$, the inequality of item 2 is satisfied. The fact that $\\alpha/2 \\le \\tilde{P}(1)$ is given in L719 so what remains is to show $\\tilde{P}(k) \\le k^{-4/3}$, which follows by splitting the summation in $\\tilde{P}(i,z)$ over $j=1…k-1$ (defined in L709) into $j \\in [1, k^{2/3}]$ and $j \\in (k^{2/3}, k-1]$. The sum over $[1, k^{2/3}]$ is upper bounded by $O(k^{-4/3})$ and the sum over $(k^{2/3}, k-1]$ is upper bounded by $O(A^{-2}k^{-4/3}) = O(\\alpha k^{-4/3})$ using Chebyshev’s inequality. Therefore, $\\tilde{P}(k) \\le k^{-4/3}$ and $k = poly(1/\\alpha, 1/\\eta)$ in Claim 3.3.  \nUltimately, it would be an interesting direction to identify conditions necessary and sufficient for a polynomial dependence on $1/\\eta$.\n\n2. **More concrete application of list-decodable stochastic optimization:**  \nWe think of list-decoding as a natural consequence of having more than half the points being outliers. As mentioned in [2], there are practical settings where it is possible to get a very small set of verified samples which could be used to determine which of the multiple answers is the correct one (the \"semi-verified\" setting).\n\n3. **“Convex” in the caption of Algorithm 2:**  \nYes, this is a typo.\n\n[1] E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042–15053, 2020.\n\n[2] M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 2017.\n"}]

Author rebuttal:

Meta-review: The paper has received mostly favorable reviews, with reviewers appreciating the novelty of the setting and the proposed method. However, the reviewers have also noted several issues with the writing, and most notably a somewhat careless use of random variables to denote distributions, without clarifying whether repeated instances of the same greek letter indicated a fresh sample from the same distribution or not. (In addition to the instances of this issue pointed out by reviewers, I also noted that $\zeta_i$ in line 2 of Alg 3 is not the same as $zeta_i$ in line 3 of that algorithm.)

After additional consideration, in my opinion the paper passes the bar for acceptance to NeurIPS. For the camera-ready submission, please take care to clarify the issue outlined above as well as all the other points that came up during the review process.
Decision: Accept (poster)