Robust Regression Revisited: Acceleration and Improved Estimation Rates
Authors: Arun Jambulapati
Jerry Li
Tselil Schramm
Kevin Tian
Venue: NeurIPS 2021 Poster (2021)
Keywords: robust statistics
stochastic optimization
linear regression
acceleration

Abstract: We study fast algorithms for statistical regression problems under the strong contamination model, where the goal is to approximately optimize a generalized linear model (GLM) given adversarially corrupted samples. Prior works in this line of research were based on the \emph{robust gradient descent} framework of \cite{PrasadSBR20}, a first-order method using biased gradient queries, or the \emph{Sever} framework of \cite{DiakonikolasKK019}, an iterative outlier-removal method calling a stationary point finder. 

We present nearly-linear time algorithms for robust regression problems with improved runtime or estimation guarantees compared to the state-of-the-art. For the general case of smooth GLMs (e.g.\ logistic regression), we show that the robust gradient descent framework of \cite{PrasadSBR20} can be \emph{accelerated}, and show our algorithm extends to optimizing the Moreau envelopes of Lipschitz GLMs (e.g.\ support vector machines), answering several open questions in the literature. 

For the well-studied case of robust linear regression, we present an alternative approach obtaining improved estimation rates over prior nearly-linear time algorithms. Interestingly, our algorithm starts with an identifiability proof introduced in the context of the sum-of-squares algorithm of \cite{BakshiP21}, which achieved optimal error rates while requiring large polynomial runtime and sample complexity. We reinterpret their proof within the Sever framework and obtain a dramatically faster and more sample-efficient algorithm under fewer distributional assumptions.

Robust Regression Revisited: Acceleration and Improved Estimation Rates
Arun Jambulapati Stanford University jublpati@staan ord. edu
Jerry Li Microsoft Research jerr1@mi www.emmmccoott.oommm com
Tselil Schramm Stanford University tselil drelil@stanfor ord. edu
Kevin Tian
Stanford University kjtian@stanford.edh
Abstract
We study fast algorithms for statistical regression problems under the strong con- tamination model, where the goal is to approximately optimize generalized linear model (GLM) given adversarially corrupted samples. Prior works this line research were based the robust gradient descent framework of (PSBR20), first- order method using biased gradient queries, or the Sever framework of [DKK* 19)
iterative outlier-remova method calling stationary point finder.
We present nearly-linear time algorithms for robust regression problems with improved runtime or estimation guarantees compared to the state-of-the-art. For the general case of smooth GLMs (c.g. logistic regression), we show that the robust gradient descent framework of [PSBR20] can be accelerated, and show our algorithm extends to optimizing the Moreau envelopes Lipschitz GLMs (e.g. support vector machines), answering several open questions in the literature.
present an alternative For the well-studied case of robust linear regression, approach obtaining improved estimation rates over prior nearly-linear time algo- rithms. Interestingly, our algorithm starts with an identifiability proof introduced in the context of the sum-of-square algorithm of [BP21]. which achieved optimal error rates while requiring large polynomial runtime and sample complexity. We reinterpret their proof within the Sever framework and obtain dramatically faster and more sample-efficient algorithm under fewer distributional assumptions.
Introduction
Parameter estimation in generalized linear models (GLMs), such as linear and logistic regression problems, is among the most fundamental and well-studied statistical optimization problems. serves the primary workhorse in statistical studies arising from variety of disciplines, ranging from economics 1mi12), biology [VGSM05), and the social sciences [Gorl0]. Formally, given link function 7 2 R and dataset of covariates and labels {(X,, (:)) [e(]))]]]] Rd x IR drawn from an underlying distribution Dx the problem of statistical (generalized linear) regression asks to
estimate 8* argminggas
E ((x,))>Dx hn x).e
For example, when 7(,,)) v) (w- corresponds (statistical) linear regression. The problem ①1) also has an interpretation as computing a maximum likelihood estimate for a parameterized distributional model for data generation, and indeed is only tractable under certain distributional
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

assumptions, since we only have access to samples from Dxy rather than the underlying distribution itself (see e.g. [BP2T] for tractability results in the linear regression setting).
However, in many modern settings these strong distributional assumptions fail to hold. In practically relevant settings, regression is often performed on massive datasets, where the data come from poorly-understood distribution and have not been thoroughly vetted or cleaned of outliers. This has prompted the study of robust regression, i.e. regression under weak distributional or corruption assumptions. In this work, we study T in the strong contamination model. In this model, we assume the data points we receive are independently drawn from Dxy- but that an arbitrary c-fraction of the samples are then adversarially contaminated or replaced. The strong contamination model has garnered significant recent interest in the algorithmic statistics and learning communities for several reasons. Firstly, it is a flexbbe model of corruption and can be used to study both truly adversarial data poisoning attacks (where e.g. part of the dataset is sourced from malicious respondents), as well as model misspecification, where the generative Dxy does not exactly satisfy our distributional assumptions, but close in total variation to a distribution that does. Furthermore, a line of work building upon [DKK 16, 6 (discussed in our survey of prior work in Section 1.2) has achieved remarkable positive results for mean estimation and related problems under strong contamination, with statistical guarantees scaling independently of the dimension d. This dimension-free error promise is important in modern high nigh-dimensional settings.
1.1
Our results
We give multiple nearly-linear time algorithms for problem ① under the strong contamination model, with improved statistical or runtime guarantees compared the state-of-the-art. Prior algorithms for (1) under the strong contamination model in the literature typically followed one of two frameworks. The first, which we refer to as robust gradient descent, was pioneered by [PSR200) and is based on reframing (1) as a problem where we have noisy gradient access to an unknown function we wish to optimize, coupled with the design of a noisy gradient oracle based on a robust mean estimation primitive. The second, which we refer to as Sever, originated in work of [DKK+19 19), and uses the guarantees of stationary point finders such as stochastic gradient descent to repeatedly perform outlier removal. Interestingly, show that both approaches can be dramatically sped up. and give two complementary types of algorithms within these frameworks.
Robust acceleration. We demonstrate that under the noisy gradient estimation framework for solving well-conditioned regression problems (T), an accelerated rate of optimization can be achieved, answering an open question of [PSBR20] We give the following result for smooth statistical regression, where we assume the uncorrupted data drawn from Dxg with marginals Dx and Dy: throughout, Ô hides polylogarithmic factors in problem parameters and failure probabilities. Finally, we remove x dependences in sample complexity statements, as they are subsumed by dependences due to assumed bounds on ek or ck.
Theorem (informal, cf. Theorem 7, supplement). Suppose 7 TR.2 - TR is such that (v) == TV, y) is convex and has (absolute) first and second derivatives at most for all in the support of Dy, and Dx has second moment matrix Σ' + LI. For some μ 2 0, let := max(1, 1, 1) and let
0 argmingeR*
E ((Xy))>Xx,
(7 x) v)
1011 1 2
be the solution to the true regularized statistical regression problem? There is an algorithm that given (( e-corrupted samples from Dx for ex² at most an absolute constant, obtains 0 with high probability in time (k).
with |0 1lg 112
KE
A canonical example of link function satisfying assumptions of Theorem iis the logit function 7(, y) = log(1 + ex)(-oy)) when the labels y are + To contextualize Theorem PSER20
'Throughout, we reserve the description "nearly-linear" for runtimes scaling linearly in the dataset size nd, and polynomially in c and the condition number, up a polylogarithmic overhead in problem parameters. "To simplify bounds and avoid estimation error for non- strongly convex statistical regression problems scaling with the initial search radius (which may be dimension -eeenniinnddeedeeut) we focus on regularized problems. There a substantial line of work on reductions between rates for strongly convex and convex smooth optimization in the non-roue mon-robust setting, e.g. (ZH16), and we defer an analogous exploration in the robust setting to future work.

---

obtains a similar statistical guarantee in its setting, using (k)) calls to noisy gradient oracle, implemented via subroutine based on robust mean estimation. Since then, [CAT showed that for the case of linear regression (see Theorem 3 for the formal setup, as the linear regression link function is not Lipschitz), the framework was amenable to nearly-linear time mean estimation
techniques of [CDG19], and gave an algorithm with runtime O(ndree -0). Theorem | represents an improvement to these results on two fronts: we apply tools from [DHLI9] remove the poly(e"i) runtime dependence for a general class of regression problems, and we achieve an iteration count of O D(VR), R), matching the accelerated runtime of [Ne883] for (non-robust) smooth optimization. We remark that the application of tools inspired by [DHL19 is fairly straightforward, and not a primary contribution of our work compared to the accelerated dependence on Ki
We demonstrate the generality of our acceleration framework by applying it optimizing the Moreau envelope for Lipschitz, but possibly non-smooth, link functions 7; a canonical example is the hinge loss 7 y) max(0, uy) with 1:1 labels, used in training support vector machines. The Moreau envelope is an extremely well-studied smooth approximation, and is an everywhere additive approximation if the original function is Lipschitz (see c.g. [Sho97]) In the non-robust setting many statc-of-the-art rates for Lipschitz optimization are attainable by accelerated optimization of an appropriate Moreau envelope [TJNO20] We show that even without explicit access the Moreau envelope, we can approximately minimize it with our robust acceleration framework.
Theorem 2 (informal, cf. Theorem 8, supplement). Suppose 7 II22 + IR is such that 7y(UV) == y(, y) convex and has (absolute) first derivative at most for all y in the support of Dy. and Dx has bounded second moment matrix. For some Ht, X 2 0, let K- max(1, xp) and let
Oem == argmingERd { (X) + 11018 where (T) == inf O' { F (0'0") + 10 - 0'112
1
2A
is the Moreau envelope of F* (0)
E (Xa))~Du
{o (0, x))))
There is an algorithm that given n == Ō e-corrupted samples from Dxy. for EK2 at most an with high probability in time Ö mdd/K)
absolute constant, obtains 0 with |00 0 2 = 0
Kc
To obtain this result, we give a nearly-linear time construction of a noisy gradient oracle for the Moreau envelope, which may be of independent interest; we note similar gradient oracle constructions in different settings have been developed in the optimization literature (see e.g. (CJS21
Robust linear regression. Perhaps the most ubiquitous example of statistical regression, the specific problem of robust linear regression has received substantial attention in the literature (cf. Section [.2]. Amongst the algorithms developed for the variant of this problem that we study, the only nearly- linear time algorithm is the recent work of [ 20 For a robust linear regression problem with noise variance bounded by a² and covariate second moment matrix Σ' := Ex=Dx [XXT]. [DKK 19 PSBR20 CAT 20) attain distance to the true regression minimizer 6* scaling as O the E norm (the "Mahalanobis distance" I Jnder bounded 4th moment assumption. We give one result (Theorem 3) which improves the runtime of [DKK 19 [SSR20 CAT 20) under the noisy gradient descent framework, and one result (Theorem 4) which improves its estimation rate, under the Sever framework.
We first demonstrate that applying our robust acceleration framework leads similar estimation guarantee as [DKK + 19 PSBR20 CAT+20 under the same assumptions, but with improved runtime.
Theorem 3 (informal, ef. Theorem 6, supplement). Suppose Dx is 2-1o-4 hypercontractive with second moment matrix Σ Ex=Dx [XXT] satisfying μI < Σ* LI, and y Dr, generated as x)* + 6, for d ~ D3 with variance at most o² independent of X. Let K == L. There is an algorithm that given n == Ō(4) e-corrupted samples from y for ex² at most an absolute constant, obtains 0 with ||0 8* 1| = (( with high probability in time (k).
Another algorithm was recently given by under different assumptions, most notably known second moment matrix.
WWe measure error in the V norm as it is scale invariant and the natural norm to measure the underlying (quadratic) statistical regression problem under; some prior works gave & norm guarantees, which convert.
3

---

We give a formal definition of 2-to-4 hypercontractivity in Section 2 We remark that attaining estimation rates for robust linear regression scaling polynomially in e known to be impossible under only bounded second moments ([BP2]); the 4th moment bound we require is the minimal assumption known in the literature under which such robust estimation is possible Theorem matches the distribution assumptions and error of 2CA while obtaining an accelerated runtime.
Interestingly, under the 4th moment bound used in Theorem 3 [P21 showed that the information- theoretically optimal rate of estimation in the Σ- norm is independent of K, and presented a matching upper bound under an analogous, but more stringent, distributional assumption (6) However, thus far robust linear regression algorithms have broadly fallen under two categories. The first family (e.g. [KMI88 ZIS20 BP2T), based on the sum-of- -quares paradigm for algorithm design, sacrifices practicality to obtain improved error rates by paying a large runtime and sample complexity overhead (as well as requiring stronger distributional assumptions). The second (e.g. DKK+19 PSBR20 (A]))0)), which opts for more practical approaches to algorithm design, has been bottlenecked at Mahalanobis distance ((an/c) and the requirement that ex² = 0(1).
We present a nearly-linear time method for robust linear regression overcoming this bottleneck for the first time amongst -o--uum-of-squarss algorithms, attaining improved statistical rates compared to Theorem 3 while only requiring ek = O(1).
Theorem 4 (informal, ef. Theorem 5, supplement), Suppose Dx is 2-10-4 hypercontractive with second moment matrix E* = xxx [X x satisfying pl 3 E* 3 LI, and y ~ Dy is generated as 10", X) + foror 8 ~ Ds. 2-to-4 hypercontractive distribution with variance at most 0² independent of X. Let K == ". There is an algorithm that given n = Ō(( + =) samples from D for ek at most an absolute constant, uses (2)) calls to an empirical risk minimization algorithm F and Õ (ad additional runtime, and obtains 0 with ||0 - 11 (RC) with probability at least 9 T0-
This second algorithm does require more resources than that of Theorem 3 the sample complexity scales quadratically in d, and the runtime is never faster. Further, we make the slightly stronger assumption of hypercontractive noise for the uncorrupted samples. On the other hand, the improved dependence on the condition number in the error can be significant for distributions in practice, which presents an intermediate tradeoff inheriting some statistical gains of the sum-of-squares approach (albeit still depending on α) without sacrificing a nearly-lineat runtime. Interestingly, we obtain Theorem 4 by reinterpreting an identifiability proof used in the algorithm of [BP21], and combining with tools inspired by the Sever robust estimation framework. We note that our sample complexity dramatically improves that of [DKK 17''s original linear regression algorithm in the Sever framework in terms of the dependence on d (but not E), which requires Ō(5) d ( samples (in addition to beating their weaker error guarantee). We elaborate on these points further in Section 4 we believe it is an interesting open problem understand if the worse sample complexity of Theorem is truly necessary for the improved statistical guarantees.
may be far from isotropic. All told, Theorem 4
1.2
Prior work
We give a general overview contextualizing our work in this section, and defer the comparison of technical components we develop in this work to the relevant sections. Specifically, in Section 3 we discuss prior work on acceleration with noisy gradients, and how it compares to our results.
The study of learning in the presence of adversarial noise is known as robust statistics, with a long history dating back over 60 years [Ans6)) Tuk60) Hub64 75k75 [ubb44. Despite this, the first efficient algorithms with near-optimal error for many fundamental high dimensional robust statistics problems were only recently developed [DKK* + 16 LRVI6 DKK + 17). Since these works, efficient robust estimators have been developed for variety of more complex problems; a comprehensive overview may be found in [K19 Li8 Ste18.
'This is true not only for efficient algorithms but even information- information-thhoortiiallly in the case of Dx. 'The algorithm of [B221] requires Dx be certifibly hypercomtracttvve, an algebraic condition frequently required by the sum-of-squares algorithmic paradigm to apply to robust statistical estimation problems. 'The empirical risk minimization algorithm used up to the practitioner; its runtime will never scale worse than (ndd/k) by applying (non-robust) accelerated gradient descent, but can be substantially better if recent advances in stochastic gradient methods are used, e.g. [Zhul7].
4

---

Table 1: Robust linear regression results in the > 1 regime. All listed results assume 2-to-4 hypercontractivity and independent noise (although some also give rates for non-independent noise). Error guarantees are Mahalanobis distance. We omit polylogarithmie factors for simplicity.
Reference
Runtime
Error guarantee
Range of
Comments
KKM18
poly(d)
oct oe
N/A
Certifiable hypercontractivity
[ZSS00]
poly(d)
N/A
Certifiable hypercontractivity
[BP21]
poly(d)
oci
N/A
Certifiable hypercontractivity
[DKK 19
poly(d)
oke
((x-3)
Linear sample size
ICAT*20 20
ndk poly(c
oked
O(x=²)
Linear sample size
Theorem
nd
aket
O(x-²)
Linear sample size
Theorem
nd -polycc"
o(KE)å
O(w²))
Quadratic sample size
Our results sit within the line of work in this field on robust stochastic optimization. The first works which achieved dimension-independden error rates with efficient algorithms for the problems we consider in this paper are the aforementioned works of [PSBR20 DKK*19). Similar problems were previously considered in [CSVV77l BDLS17]. In [CSV17a], the authors consider a setting where a majority of the data is corrupted, and the goal is output short list of hypotheses so that at least one is close to the true regressor. However, because most of their data is corrupted, they achieve weaker statistical rates; particular, their techniques not achieve vanishing error as the fraction of error goes to zero. In (BDLS17) the authors consider somewhat different model with stronger assumptions on the structure of the functions. In particular, they assume that the uncorrupted covariates are Gaussian with identity covariance, and are primarily concerned with the case where the regressors are sparse. Their main goal is to achieve sublinear sample complexities by leveraging sparsity. We also remark that the algorithms in [CSV17a BDLS17] are also much more cumbersome, requiring heavy-duty machinery such as black-box box SDP solvers and cutting plane methods, and as a result are more computationally intensive than those considered in [PSBR20 DKK 17).
There has been large body of subsequent work on the special case of robust linear regres- sion [KKMI8 KKK19 DKS19 ZSS2 CAT+20 [P21]; however, the majority of this line of work focuses on achieving improved error rates under additional distributional assumptions by using the sum-of-squares hierachy. As result, their algorithms are likely impractical in high dimensions, and require large (albeit polynomial) sample complexity and runtime. Of particular interest to us is 1CA++20) 20), who combine the framework of [PSBR20) with the robust mean estimation algorithm of [CGT19 to achieve nearly-linear runtimes in the problem dimension and the number of samples. Our Theorem 3 can be thought of as the natural accelerated version of |CAT 20), with additional runtime overhead removed using more sophisticated mean estimation techniques.
After the initial submission of this paper, we were made aware of another recent work [P]L20 preventing different approach to robust regression based on covariate filtering. Their work focuses on the highly well-conditioned setting, where the true second moment matrix has constant condition
number, whereas our work primarily aims to improve various rates in terms of dependence on the condition number k in the ill-conditioned regime (i.e. K >> 1).
2 Preliminaries
Notation. For d e N we let
jj d]. The lp norm of a vector is Il.I,p The all-ones vector (of appropriate dimension from context) is 1, and the identity matrix I. The (solid) probability simplex is A : {w E Ry ||w|], < 13. For E R² and S C [m]. we let us E R zero out coordinates [n] \ S. We call S1, S2 a bipartition of S if n 0 and S U S2 = S. For symmetric x A, B we write A < B to mean B A is positive semidefinite. For positive definite M, we define the induced norm ||u||> := Vu Me. We use |1-llop to mean the lz-l2 operator norm.
F Functions. We say differentiable f I -> IR is X-Lisschitz in Il if [ : S A for all 0 E Rd, and that twice-differentiable f RRd + IR is L-smooth and u-strongly convex in Il-llm if M 3 f() LM, for all 0 Rd. When M is not specified, we assume M I.
5

---

Distributions. For E A" and set of vectors X = (Xi)eetu) the empirical second moment matrix is denoted Cov (X) Eiend " X We say distribution D supported on E is 2-to-4 Tiill hypercontractive if for all u E R. Ex=D (X, o) Ex~D u3
Corruption model. We provide provable guarantees for statistical problems captured by the follow- ing standard statistical model (the "strong contamination model"): given link function Y IR? - R and "truc" underlying distribution Dxy on R x R with marginals Dx. Dy dataset {[X,,, 21.) ingin] is independently sampled from Dxy. and an arbitrary (unknown) subset B C [n]] is replaced by arbitrary points (Dy)( For i E B, we observe the corrupted (Xi: and otherwise we observe (6) + (X,. ūz)- When [B] = en, we say the dataset is 6-corrupted. We define [0(0) = ((X,, 0) v.). (0) (0), and for A", (0) == EiE(n) (.).
Filtering. Our algorithms make frequent of algorithmic primitive call "filtering" [ABL14 DKK* 17 SCVIS8 Here, we have an index set [n]] with fixed unknown bipartition GU intuitively, Gs "good" set of indices wish to keep. and B is a "bad" set we would like to remove. Naively, one would expect that we would choose G' to be the set of remaining uncorrupted points. For technical reasons, will often have choose (large) subsets of the set of remaining uncorrupted points.
The filtering algorithm maintains weights w E A Th iteratively downweights using "scores" E R2 with the goal of producing weights close to the uniform distribution on G. We call w E A" c-saturated | + c. The following lemma (implicit in DKK 17 CSV17b Li18 Ste18) is representative of this technique. Lemma 1. Suppose G J B is bipartition of [n], and (wa.T) I (WB, T) for e-saturated E A
(or saturated for short if = 0) if I 11 entrywise and | w|cll S |[ - w/ e|],
T E 20 Then w', + (1 Timx
=)),; Vi E [m]] and Tmax == max4e[m]] w.#0 Tg. w/ is also e-saturated.
keep weights saturated (retaining most of the weight G) by repeatedly identifying scores whose empirical average is large due to B. We use a variety of different scores; one subroutine which follows consequence of this paradigm, which is implicit in [DLLI9], is way to rapidly decrease the operator norm of an empirical second moment matrix whose restriction to "good" majority set is bounded. Many of our algorithms use this subroutine, stated here.
In other words,
Lemma 2 (ef. Proposition 5, supplement). There is an algorithm, FastCovFilter, taking inputs V {Ue hein) E IRnxd, saturated w E A" with respect to [n] GU B with |B] en, and R 2 0 with the promise that | Σieg Uad llop S R. Then, FastCovFilter returns saturated w' A such that Eve(n) w/yn,, To 1lap = (R)) with high probability time Ö(nd).
Organization. In Section 3 we describe general framework for attaining accelerated optimization rates under a "noisy gradient oracle" model, which we use to obtain Theorems D 2 and 3 by efficiently constructing appropriate oracles. In Section 4 overview techniques used in designing the nearly-linear time linear regression algorithm of Theorem Due to space constraints, we defer proofs, a precise statement of our statistical models and assumptions, and an extended exposition of our techniques to the unabridged version of this paper in the supplementary material.
3 Acceleration under noisy gradient oracle access
Our robust acceleration framework, which we use to prove Theorems and 3 addresses the following problem formulation: there is an unknown function F* with minimizer 0* which is L- smooth and p-strongly convex, and we wish to estimate 6*, but our only mode of accessing F* is through a noisy gradient orucle Ong- Namely, for some a, e, we can query Ong with some E Bd and an upper bound R 2 |10 0* 00112 and receive estimate G(O) such that
||G(0) V (0)12 - - + LVER)
In other words, we receive gradients perturbed by both fixed additive noise, and multiplicative noise depending (a known upper bound on) distance to 0*. Prior works observed that by using tools from robust mean estimation, appropriate noisy gradient oracles could be constructed for the "mean" functions E(x,g)>Dx, [x((X, 0) v)] arising from the distributional assumptions in Theorems and
Efficient Ong construction. Our first contribution is speeding up the implementation of Ong to run in nearly- -ineer time ((d)), leveraging recent advances by [DLL19 for robust mean estimation. This

---

improves a similar construction by 20), running in time Ö(d c -00) in the linear regression setting. To obtain this construction, we use the following lemma implicit in (DLL19.
Lemma (Lemma 11, supplement), Let w E A be saturated with respect to hipartition [x] = GUB, and let w == c 1 l. ih == w 1
Then,
F ()) V wa 1012-0000 (I/Covig (em 3/2 + a (o:())
By demonstrating that our "uncorrupted" dataset has function gradients which are appropriately bounded under our distributional assumptions, can apply FastCovFilter (Lemma in conjunction with the above lemma to produce an weighting vi E A whose empirical gradient satisfies (2) in time (nd). We give Ong construction for linear regression in the distributional model of Theorem 3 and a radiusless Ong construction for smooth GLMs (satisfying (2) with no dependence on and in the distributional model of Theorem I in Corollaries and 2 of the supplement. Finally, in the setting of Theorem 2 (Lipschitz GLMs), we give a reduction from constructing a noisy gradient oracle for Moreau envelopes to ( queries of noisy gradient oracle (cf. Corollary 3, supplement) solution regularized objective.
1)
using a characterization of the Moreau gradient
Noisy proximal oracle construction. For the remainder of this section, we assume access to Ong satisfying (2) Our second, and much more technically involved, contribution is demonstrating that acceleration is achievable under the noise model 2 Designing accelerated algorithms under noisy gradient access is extremely well-studied, and there are both strong positive results d A'8 MS13
6GT6 CDOTS MRJ19 [JJ, 19] as well as negative results [DGN44] showing under certain noise assumptions, accelerated gradient descent may be outperformed by unaccelerated methods. Motivated by these negative results, [PSBR20] posed the question of whether acceleration was possible under We demonstrate the accelerated proximal point framework of [MS13] is amenable to such noise.
In the noiseless setting, accelerated proximal point algorithms (introduced by Gu192) are a reduction from optimization of a function F* to iteratively solving proximal subproblems of the form
- { (mr(0) + 2X 110 013
0g argmingexd
(3)
for some Ō E Rdd By tuning À we can trade off how efficiently we can solve the subproblem with how many times we need to solve them. In our accelerated algorithm, we will always set
A 1. in proximal subproblems. We first use the (unaccelerated) robust gradient descent analysis
of (PSBR20 CAT+20) show that given a current upper bound It ||0 0*1|2 we can solve the proximal subproblems (3) to appropriate accuracy, yielding a "noisy proximal oracle."
Lemma 4 (Definition 5, Proposition 7, supplement). There is an algorithm, NoisyProximalrracle
which given 0 E R.d, R ||0 8" llz. and Ong giving noisy gradient estimates satisfying 2 returns
i satisfying |10 0ill = O(o VF. + VeR), where Oz is the minimizer to The complexity of the
algorithm is dominated by Õ(1) calls to a noisy gradient oracle Ong-
In other words, NoisyProximalOracle runs in Ö(n)) time (as expected, since 33) with L-1 has condition number < 2). We now discuss how to use NoisyP PoxiyProximalOracle in our main subroutine.
Our accelerated algorithm runs in logarithmically many phases, each halving an upper bound on the distance to the optimizer (while above a certain noise floor, M( ) }²), due to the additive error in (2). We state one phase of our accelerated algorithm below as HalfRadiusAccel, assuming access to oracle Oup with the guarantees of Lemma 4
Halving the radius with NoisyProximalOrace
In Line 5, scalars {ar, A are parameters used by acceleration potential analyses, defined by recursions Ao 0, A, Laf, Ar+1 A, + dr+1- We remark HalfRadiusAccel is simply the proximal framework of [MS13), where we call NoisyProximalOrach in place of a (classical) proximal oracle in Line 6, and constrain Line Our main technical innovation to show the analysis of [MS13 is robust to guarantees of rioxiiaalalaa by carefully balancing accumulated errors.
'Though our algorithm is randomized, we omit discussion of failure here for brevity. Our algorithm succeeds with high probability (with sample sizes and runtimes depending polylogarihmmially on failure probabilities).
7

---

Algorithm 1 HalfRadiussAcel(A. R, Oup)
Input: E ||0 0- 2| with R l( ( ) Oap satisfying guarantees Lemma
2: Output: E IRd with 110 - 0*1 S fR
3: T <- (VKR) for a sufficiently large constant, <- 0g <- 0. uo
4: while f < T do
5: y/ - A 0
d1+1 Ut
A++1
Ar-
6: 0,+1 + Oup (yt. 3R)
7: Ur411 f- argmin (a++1 (w Oc+1, ZI 1|u- Us (2)) where : {0l ||0 11-00,
-0l, s R}
8: 1+1+1
9:
end while
10: return 0g
To make the analysis more modular, first observe via characterizing proximal minimizers f (following (3)) that though iterates of Algorithm may drift more than I away from 0* (due to error in Op)) they never drift too far. Formally, Lemma 13 of the supplement shows all y/ satisfy l1ye - 0* 12 I 3R, validating calls to Onp- We then give our main noisy potential bound.
Lemma 5 (main potential bound, Lemma 14, supplement). For all S S T, define E. = (0,) -
(0,)-F((01) (0*), D; := ||e 011 and 4, == A,E, + Dr. Then for all 0 st
Φ Φ; 50 to RR+WER + 2 =
The potential 4, defined in Lemma
is typical acceleration analyses, and indeed the (non-robust) analysis of [MS13] shows 4++1 4, under an exact proximal oracle. Since the coefficient of function error in the potential, Ar, grows 32 s2( {
it straightforward (via strong convexity) to show HalfRadiuAAccel halves the radius in ( iterations classically. We demonstrate the analysis still goes through under the potential increase of Lemma the same number of iterations (up to constant factors), concluding analysis of HalfRadiusAcoel. Our final algorithm iterates HalfRadiusAccel until reaching the noise floor, requiring (VK) iterations dominated by calls Ong-
Discussion. Our result builds upon recent studies of the noise tolerance of proximal point methods, e.g. 19]. who used model with fixed additive gradient error, and (US22 who used noisy solutions to (3) with fixed additive error. Our model crucially tolerates both additive and multiplicative guarantees for both gradient and proximal solution estimates. An interesting open question whether a similar result is obtainable without proximal point abstraction, c.g. by extending [CDO18]. We view our result as proof-of-concepl that acceleration is possible under ( We believe unified study of acceleration under models encompassing ( warrants further exploration, and defer it to interesting future work.
Improved statistical rates for robust linear regression
We now overview the algorithm that achieves Theorem 4 and describe its correctness proof. We define the following, strong deterministic condition on the uncorrupted points.
Assumption (deterministic regularity for linear regression). Let be sufficiently small, and let r E (0, 2)). Assume {(X,, wi) hej.) C Rdd x R is (e, r)odg for linear regression (or (e. r)ogo context is clear), which means there a partition [n] = G B with |G] > (1 e)n which satisfies:
1. For any E A with | ||, 2 1 4c, Σ - Cov wa
2. There a constant Cest such that for all 0 E Rd and all e-saturated w E A", there exists a G' G satisfying [G'| 2 G so that if we let == T Ili
Wer
IV (6) - (F)12) S Cos Te (a + 1
)
(4)
Cov (la((0))ea))
|g S C (110 - 0-13- + o²)
(5)

---

1 Eieo ((X,, yy:) S Cubo?. 3. There is constant Cub such that Eieo | f(())) = 2
1
The following claim establishes that Assumption probability under the statistical model in Theorem 4 We give the proof in the supplement.
I (up constants in definitions) holds with good
Proposition (Proposition 2, supplement), Let a 2 and > 0 be sufficiently small. Let {(X,, 3)) Ne(()) C. R x R be e-corrupted samples from Dxy as in Theorem 4 Then, if
dlagd n = ( da² logd d' doolog(//e))
2
the set (XX;,i)) is (2c, ) I-good for linear regression with probability at least 10.
Through this section, we will assume that our set of points is (2e, )gooo,, where we choose a = O (max (1, log (n)) Here, Ro is an initial distance bound on ||0, 8"11 This assumption inflates the sample complexity of Proposition T by a factor depending on a.
Filtering under goodness. Enforcing Assumption I and in particular, Assumption I holds inductively introduces some additional technical difficulties for our algorithm. However, our choice of a ensures that we never remove more than 3e mass from G. and that our weights are always e-saturated with respect G U "U allowing for inductive application of Assumption [ This holds because we show that our algorithm uses at most 2e distinct subsets of G for filtering. Each distinct
set satisfies Lemma up to a
2e additive discrepancy, whose accumulation loses an additive e.
Algorithms through identifiability. We now describe our algorithm, assuming Assumption hholds throughout. We begin with the following (slight) reinterpretation of an identifiability proof in [B211] Proposition 2 (Proposition 6, supplement). Let A be e-saturated with respect to bipartition [m] = GUU B, and let A E Red. Assuming on is sufficiently small,
||0 - 10 =0 (ve (oVR+ vllcor (1o1(0)iees))
) + -
+[VE((0))
This shows if V Fin (0)( and (1a((()))))))))))) wn) op are simultaneously bounded, then obtain distance bound to 6*. We can bound the former at fixed by setting 0 to minimize Fi. and the latter at fixed 0 by filtering via FastCovFilter. This introduces a chicken-and-egs problem of obtaining both bounds at once; we accomplish this via an alternating approach, and argue fast termination using third potential monotone under both subroutines, the function value (f).
Halving the radius. We design a procedure, HalfRadiusLin with the following guarantee. Suppose の E A is esaturrated and E IRd, and we know R = (2(a) with the promise 1/00--11 S
R. HalfRadiusLinReg then returns new 0 with ||0 0'11s- S fR. We do so by using saturated weights to guide a potential analysis via Proposition 2 subroutines achieving
Before stating HalfRadiusLinReg, we give earlier stated goals. The first is approximate optimizer.
Definition 1. We call OERM 7-approximate ERM oracle if on input F Rd + R it returns point i such that F(O) F(0)) S 7, for 0j- == argmin F(0).
The second controls the initial error, which we use to yield distance bounds via strong convexity. Lemma 6 (Lemma 6, supplement). FunctionFilter takes inpul e-saturated A", 0 E Rd, and R 1 0* and produces e-saturated w/ e A with (0) < 20,b(a22 + RR), in time Ö(nd).
FunctionFilter is a straightforward implementation of the filtering paradigm using Assumption I and we formally define it in the supplementary material. We can now state (a simplified version of) HinfR,, which iteratively filters weights initially set to uniform. It calls FunctionFilter to preprocess, and then alternates calls to OERM and FastCovFilter, which respectively decrease the gradient norm and operator norm in Proposition [ It finally terminates when the function value decrease between consecutive iterations is small, whence we conclude an OERM call was not actually necessary for Proposition 2 to imply progress.
Lemma 7 (Lemma 7, supplement). HalfRadiusLinReg correctly returns (w, 0) such that w E A is e-saturated and 0 0- 1| < 3R R in calls OERM and Ö(ndk) additional time.

---

Algorithm 2 Hale X, y, w, 0, R. OERM)
I: Input: Dataset X {Xitke]m) E Raxd = tus E R", satisfying Assumption
saturated E A with respect to bipartition [n] = GU with X diag (w) 3 8T1, 0
Rd
with ||0 1-00 0011= S R for R = Q(a), ( )-ppprxximat ERM oracle ORRM
2: Output: Saturated with respect to G U B, and with 10 0* 0- S R. 3: 6 0, w0()) +- FunctionFilter(w,, 0, R),, Do <- 0c
4: while A, = 52( /t² do
5: 0(9) &- (F...)
6:
w((++) FastCovFilter((ge (8(1) hee(n), w(t), O(LR))
7: A+ Farte11) (0(0)) Fw(e 1) (B(++))
8: I +-t+1
9:
end while
10: return 0(t-1))
We prove Lemma by using the proof strategy outlined earlier: first, strong convexity, our initial function error bound, and monotonicity of function error ensure that |((t)) - 0-1| s- ( through- out. Next, if A, is ever too small, the gradient norm in Proposition 2 was small even before we ran the loop, so we could have terminated with the prior ( Finally, the whole algorithm runs (x)) times, since each loop decreases function error (initially at O(R²)) substantially.
Putting it all together. We iteratively apply Lemma 7 Olog Ro times, at which point we are within distance (a) in the Σ" norm. To achieve distance /Ke), the natural bottleneck of Proposition 2 we define LastPhase, variant of Algorithm 2 with more stringent termination condition in Line and use similar argument to show it iterates ( times before concluding. Finally, we verify that
throughout only filtered against most Os log Ra + 2) distinct sets, where the summands due to calls to HalfRadiusLinRes and LastPhase respectively. This fulfills the premise of using 2
distinct sets for the defined at the beginning of the section, and concludes our analysis.
Acknowledgments
KT supported by NSF Grant CCF-1955039 and the Alfred Sloan Foundation.
10

---

References
[ABL14] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 449-458, 2014.
[Ans60] Frank Anscombe. Rejection of outliers. Technometrics, 2(2): 1960.
[BDLS17] Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory, pages 169-212, 2017.
[BJL*19] 19] Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non- non-smooth convex optimization. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13900- 13909, 2019.
[BP21] Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, 2021.
[CAT*20) Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael I. Jordan, Nicolas Flammarion, and Peter I.. Bartlett. Optimal robust linear regression in nearly linear time. CoRR, abs/2007.081 2020.
[CDG19] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2755-2771, 2019.
[CDO18] Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia. On acceleration with noise- corrupted gradients. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pages 1018-1027, 2018.
[CJJS21] Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. CoRR, abs/2105.01178. 2021.
[CSV17a] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47-60, 2017.
[CSV17b] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 47-60, 2017.
[d' [08] Alexandre d' A'pprmmon. Smooth optimization with approximate gradient. SIAM J. Optim., (13):1171-1183, 2008
[DG16] Pavel E. Dvurechensky and Alexander Gasnikov. Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. J. Optim. Theory Appl., 171(1):121-145, 2016.
[DGN14] Olivier Devolder, François Glineur, and Yurii E. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Math. Program.. 146(1 (66112))37775, 2014.
[DHL19] Yihe Dong, Samuel B. Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 14, 2019, Vancouver, BC, Canada, pages 6065-6075. 2019.

---

[DK19] Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911, 2019.
[DKK 16] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 655 2016.
[7KK*17] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 999-1008, 2017.
[9KK*19] Ilass Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 1596-1606, 2019.
[DKS19] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages
2019.
[Gor10] Rachel A. Gordon. Regression Analysis for the Social Sciences. Routledge, 2010.
[Gu192] Osman Güler. New proximal point algorithms for convex minimization. SIAM J. Optim., 2(4):649-664, 1992.
[Hub64] Peter Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1);33-01, 1964.
[Hub04] Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
[KKK19] Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari. List-decodable linear regres- sion. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 7423-7432, 2019.
[KММ88] Adam Klivans, Pravesh K. Kothari, and Raghu Meka. Efficient algorithms for outlier- robust regression. In Conference On Learning Theory, COLT 2018, Stockhoim, Sweden, 6-9 July 2018, pages 1420-1430, 2018
[Li18] Jerry Zheng Li. Principled approaches to robust machine learning and beyond. PhD thesis, Massachusetts Institute of Technology, Cambridge, USA, 2018
[LRV16] Kevin A. Lai, Anup B. Rao, and Santosh S. Vempala. Agnostic estimation of mean and covariance. In JEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyutt Regency, New Brunswick, New Jersey, USA, pages 665-674, 2016.
[MRJ19] Hesameddin Mohammadi, Meisam Razaviyayn, and Mihailo R. Jovanovic. Performance of noisy nesterov's accelerated method for strongly convex optimization problems. In 2019 American Control Conference, ACC 2019, Philadelphia, PA, USA, July 10-12, 2019, pages 3426-3431, 2019.
[MS13] Renato D. C. Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extra- gradient method for convex optimization and its implications second-order methods. SIAM J. Optim., 23(2):1092-1122 2013.
[Nes83] Yurii Nesterov. A method for solving convex programming problem with convergence rate o(1/k?). Doklady AN SSSR, 269:543-547, 1983.
12

---

[PJL20] Ankit Pensia, Varun Jog, and Po-Ling Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. CoRR, abs/2009. 12976, 2020.
[PSBR20] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society, Series B (Methodological), 82(3):601-62) 2020.
[SCV18] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstull-eeibnizzZZetruu fuer Informatik, 2018.
[Sho97] Ralph E. Showalter. Monotone operators in banach space and nonlinear partial differen- tial equations. Mathematical Surveys and Monographs, 49:162- 12-1163,, 1997.
[Smi12] Gary Smith. Essential Statistics, Regression, and Econometrics. Academic Press, 2012.
[Ste18] Jacob Steinhardt. Robust learning: information theory and algorithms. PhD thesis, Stanford University, Stanford, USA, 2018.
[TJN020] Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Projection efficient subgradient method and optimal nonsmooth frank-wolfe method. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[Tuk60] John W Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statisties, pages 448 485, 1960.
[Tuk75] John Tukey, Mathematics and the picturing of data. Proceedings of the Inter- national Congress of Mathematicians, Vancouver, 1975, volume 2, pages 523-531, 1975.
[VGSM05] Eric Vittinghoff, David V. Glidden, Stephen C. Shiboski, and Charles E. McCulloch. Regression Methods in Biostatistics: Linear, Logistic, Survival, and Repeated Measures Models. Springer, 2005.
[ZH16] Zeyuan Allen Zhu and Elad Hazan. Optimal black-box reductions between optimization objectives. In Advances in Neural Information Processing Systems 29: Annual Confer- ence on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1606-1614, 2016.
[7hu17] Zeyuan Allen Zhu. Katyusha: the first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1200-1205, 2017.
[ZJS20] Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. Robust estimation via generalized quasi-gradients. CoRR, abs/2005. 14073, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] For robust linear regression tasks,
we describe lower bounds and technical bottlenecks our algorithms encounter which prevent attaining optimal statistical rates.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work does not present any direct foreseeable societal consequence, as a result primarily of theoretical interest to the community. Moreover, because results concern robustness of models to arbitrarily corrupted data, we believe our methods may have practical implications for downstream tasks where protection against malicious adversary is warranted.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 'e using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "r2McGEyR6G8", "reviewer": "Reviewer_Xq7Q", "summary": "This paper resolves an open question of the recent work [PSBR 20], which uses robust gradient descent for robust estimation tasks, to achieve faster accelerated convergence rate and better statistical accuracy. This is done via a clever modification to the accelerated proximal point framework of [MS13] with the gradient step replaced by noisy gradient. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper extends the recent work [PSBR 20], which uses robust gradient descent for robust estimation tasks, to achieve faster accelerated convergence rate and better statistical accuracy. This is done via a clever modification to the accelerated proximal point framework of [MS13] with the gradient step replaced by noisy gradient. \n\nThe authors proposed a clean formulation of robust gradient estimators as an oracle, and showed how to implement this oracle in near linear time which improves from prior works. Next, the author showed that the algorithm of [MS13], is \"stable\" to the noise in the gradient oracle and can achieve a smaller statistical error via a iterating halving argument. Finally, the author showed how the proposed methodology can be applied to robust linear regression with strong statistical guarantee and practical computational complexity, without resorting to the costly Sum-of-square estimators.\n\nOverall, this paper is well-written and it solved an important open question elegantly. I recommend a clear accept.\n\nThe only minor drawback of this approach, is that it requires a larger number of samples comparing to the SoS-based estimators (and other slightly stronger assumptions) - there is a d^2 factor in the O(1/eps) term. I am curious about the necessity about this - is there some fundamental limit of the robust GD-based approach that strictly separates it from SoS?   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_ywFdzY2a33", "reviewer": "Reviewer_KSqf", "summary": "This paper consider the robust regression problem with adversarial corruption, including linear regression, generalized linear models (GLMs) and Moreau envelopes of Lipschitz GLMs. Leveraging recent advances in robust mean estimation and proximal point methods, they provide improved algorithms in terms of optimization convergence rates and statistical error rates.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper consider the robust regression problem with adversarial corruption, including linear regression, generalized linear models (GLMs) and Moreau envelopes of Lipschitz GLMs. Leveraging recent advances in robust mean estimation and proximal point methods, they provide improved algorithms in terms of optimization convergence rates and statistical error rates.\n\nSpecifically, their contributions include:\n\n1) Following the noisy gradient oracle framework in [PSBR20], they use tools from [DHL19] to show that such an oracle can be implemented in near-linear time. Furthermore, they show that the accelerated proximal point algorithm in [MS13] is robust to the noise in the above oracle. Combining these results allows them to develop accelerated algorithms whose convergence rates feature better dependence on the condition number without sacrificing the statistical error rates.\n\n2) In the context of robust linear regression, they leverage the identifiability proof in [BP21] to develop a non-SOS algorithm that achieves better statistical error rates.\n\nThis paper is a solid contribution to the problem of robust estimation/regression, improving upon existing work in several aspects and in particular answering the question left open in [PSBR20] on whether robust gradient descent can be accelerated.\n\nOther comments:\n\n- In the statement of all theoretical results, the authors should clearly speak out the dependence on all relevant problem parameters including the condition number $\\kappa$, the dimension $d$ and the error $\\epsilon$.\n- The authors may consider providing a summary (say as a table) of their quantitative results and those from prior work for ease of comparison. \n- Line 64: should be $\\gamma: \\mathbb{R}^2 \\times \\mathbb{R} \\to \\mathbb{R}$\n\n\n===================\n\nI acknowledge that I have read the rebuttal and other comments. I maintain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical oriented.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "XLRz_9Km6z", "reviewer": "Reviewer_jG4X", "summary": "The proposed new algorithms for robust regression problems with improved runtime and estimation guarantees. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think it is important to have fast algorithms that optimize a generalized linear model (GLM) given corrupted samples. The new algorithm in the paper has improved the running time and estimation error comparing to prior work. However,  I am not familiar with the related work and it is unclear to me how significant the contribution is. One suggestion is that the authors can present a table that summarizes the error estimation bound and running time of prior works and the work in this paper so that we have a better understanding of how much improvements have been made. In addition, as a paper aiming to improve running time, it would be great to have some experiments to show that the improvements do exist.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is mainly a theoretical paper while I would prefer some simulations or experiments to show the improvements of the new algorithm do exist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6ZugU_l4JFG", "reviewer": "Reviewer_56zo", "summary": "The paper develops fast algorithms for robust stochastic optimization in the presence of strong contamination model, where the objective function belongs to one of the following: linear regression, (regularized) generalized linear models, and (regularized) Moureau Envelope. The main contributions of the paper are as follows:\n1. Building on the gradient descent framework of [PSBR20], the paper develops accelerated gradient descent method using a noisy gradient oracle. This allows them to get better dependence on the condition number in the all of the mentioned models (with similar statistical rate as existing works).\n2. Inspired by the identifiability proof of [BP21], the paper gives a practical algorithm for linear regression that has better statistical rates than existing works (at the cost of additional sample complexity). This is the first work that achieves this rate without certifiable hypercontractivity. \n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe the paper is a good contribution to the field of robust stochastic optimization, showing that proximal accelerated methods are amenable to noisy gradient oracles. Thus I recommend \"accept\" for the paper with the following changes.\n\n**Main Comments**\n\n1. As $\\kappa$, the condition number, is an important parameter in this project, the dependence on $\\kappa$ must be mentioned in the sample complexities in main theorems. (For example, value of $\\alpha$ from Line 316 + Proposition 1 suggests that there is a quadratic dependence on $\\kappa$ in Theorem 4).\n\n2. Independence of noise: It must be mentioned in the main paper that the noise distribution is independent of the covariates  in Theorem 3 and 4 (Model 3 and Model 4 in the supplementary material). This is a critical modeling assumption.\n\n3. The paper should clearly state the contributions of their work. In particular, while comparing with [CAT+20], the focus should be on the number of calls to robust mean estimation. Removing $O(\\epsilon^{-6})$ in runtime from [CAT+20] is a blackbox benefit from [DHL19] or [DL19]. It is not obvious from reading the paper.\n\n4. Paper claims multiple times that there are only two approaches for robust linear regression: (i) sum-of-squares based approaches and (ii) Gradient based approaches. The paper is missing the \"covariate filtering\" approach of [PJL20].\n\n5. Theorem 3 and 4 have different upper bounds on $\\epsilon$ in terms of $\\kappa$. What is the main reason behind this?\n\n**Other Comments**\n\n1. Line 144: Dependence on $d$ is improved but is worse on $\\epsilon$.\n\n2. Line 36: What is \"highly robust regression\"?\n\n3. Line 99: [Dep20] also provides a near linear time algorithm.\n\n4. Line 64: Typo in defining the domain and range of $\\gamma$.\n\n5. Line 165: In [BDLS17], apart from Gaussianity, the identity covariance assumption is critical too.\n\n6. Line 206: what is $c$ here? \n\n7. Footnote 7: What depends polylogarithmically on failure probability? Time complexity.\n\n8. Line 363: The last expression should be $2\\alpha/\\epsilon^2$ instead of $\\epsilon^2/2 \\alpha$.\n\n**References**\n\n[Dep20] J. Depersin. A spectral algorithm for robust regression with subgaussian rates. CoRR abs/2007.06072. (2020)\n\n[DL19] J. Depersin & G. Lecué. Robust subgaussian estimation of a mean vector in nearly linear time. CoRR abs/1906.03058, (2019)\n\n[PJL20] A. Pensia, V. Jog, & P. Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. CoRR abs/2009.12976, (2020)\n\n===============UPDATE After Author Response====================\n\nI thank the authors for their thoughtful response, and answering my questions. I maintain my score and recommend 'acceptance'. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agree that this paper makes solid contributions to the robust estimation problem and improves upon existing work in several aspects. The authors should incorporate the reviewers' suggestions into the final version of the paper.
Decision: Accept (Poster)