Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
Authors: Shuyao Li
Yu Cheng
Ilias Diakonikolas
Jelena Diakonikolas
Rong Ge
Stephen Wright
Venue: NeurIPS 2023 poster (2023)
Keywords: low rank matrix sensing
non-convex optimization
high-dimensional robust statistics
second-order optimization
statistical query model

Abstract: Finding an approximate second-order stationary point (SOSP) 
is a well-studied and fundamental problem in stochastic nonconvex optimization with many applications in machine learning.
However, this problem is poorly understood in the presence of outliers, limiting the use of existing nonconvex algorithms in adversarial settings.

In this paper, we study the problem of finding SOSPs in the strong contamination model, 
where a constant fraction of datapoints are arbitrarily corrupted.
We introduce a general framework for efficiently finding an approximate SOSP with \emph{dimension-independent} accuracy guarantees, using $\widetilde{O}({D^2}/{\epsilon})$ samples where $D$ is the ambient dimension and $\epsilon$ is the fraction of corrupted datapoints.

As a concrete application of our framework, we apply it to the problem of low rank matrix sensing, developing efficient and provably robust algorithms that can tolerate corruptions in both the sensing matrices and the measurements.
In addition, we establish a Statistical Query lower bound providing evidence that the quadratic dependence on $D$ in the sample complexity is necessary for computationally efficient algorithms.

Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
Shuyao Li
Yu Cheng
University of Wisconsin-Madison shuyao li@wisc. edu
Brown University yu_ ru_cheng@brown. edu
las Diakonikolas University of Wisconsin- Wisconsin-Madison ilias@cs edu
Jelena Diakonikolas
Madison
University of Wisconsin-Madiss jelenaEcs. visc.edu
Rong Ge
Stephen Wright
Duke University ronggeucs. tuke.edu
University of Wisconsin-Madison swright&cs. wisc.
Abstract
Finding an approximate second-order stationary point (SOSP) is well-studied and fundamental problem in stochastic nonconvex optimization with many applications in machine learning. However, this problem is poorly understood in the presence of outliers, limiting the use of existing nonconvex algorithms in adversarial settings.
In this paper, we study the problem of finding SOSPs in the strong contamination model. where constant fraction of datapoints are arbitrarily corrupted. We introduce a general framework for efficiently finding an approximate SOSP with dimensionninndepennennt accuracy guarantees, using ( /e) samples where is the ambient dimension and is the fraction of corrupted datapoints.
As a concrete application of our framework, we apply it to the problem of low rank matrix sensing, developing efficient and provably robust algorithms that tolerate corruptions in both the sensing matrices and the measurements. In addition, establish a Statistical Query lower bound providing evidence that the quadratic dependence on D in the sample complexity is necessary for computationally efficient algorithms.
Introduction
Learning in the presence of corrupted data is significant challenge in machine learning (ML) with many applications, including ML security [Bar+ 10, BNLI2 SKLI7 Dia+19) and exploratory
Li+08 Dia+17) The goal in such scenarios is to design efficient learning algorithms that can tolerate small constant fraction of outliers and achieve erro guarantees independent of the dimensionality of the data. Early work in robust statistics [Ham+86] [R09 gave sample-efficient robust estimators for various tasks (e.g., the Tukey median Tuk75] for robust mean estimation), alas with runtimes exponential the dimension. A recent line of work in computer science, starting with (Dia+ 16 LRV16), developed the first computationally efficient robust algorithms for several fundamental high- high-dimensional tasks. Since these early works, there has been significant progress in algorithmic aspects of robust high- dimensional statistics (see DK19 and DK23 for a comprehensive overview).
data analysis of real datasets, e-g., in biological settings [Ros+02] Pas+10
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we study the general problem of smooth (with Lipschitz gradient and Hessian) stochastic nonconvex optimization min,, f(x the outlier-robust setting. where f(x) := E faz A) and G is possibly unknown distribution of the random parameter A. We will focus on the following standard adversarial contamination model (see, e.g., [Dia+16)).
(Strong Contamination Model). Given a parameter 0 <<< < 1/2 and an inlier distribution g, an algorithm receives samples from 9 with c-contamination as follows: The algorithm first specifies the number of samples n, and n samples are drawn independently from G. An adversary is then allowed inspect these samples, and replace an e-fraction of the samples with arbitrary points. This modified set of n points is said to be e-corrupted, which is then given to the algorithm.
Definition 1.1
The stochastic optimization problem we consider is computationally intractable in full generality - even without corruption if the goal is to obtain globally optimal solutions. At a high level, an achievable goal is to design sample and computationally efficient robust algorithms for finding locally optimal solutions. Prior work (Pra+20) Dia+ 19] studied outlie--rouust stochastic optimization and obtained efficient algorithms for finding approximate first-order stationary points. While first-order guarantees suffice for convex problems, it is known that in many tractable non-convex problems, first-order stationary points may be bad solutions, but all second-order stationary points (SOSPs) are globally optimal. This motivates us to study the following questions:
Can we develop a general framework for finding second-order stationary points in outlier-robust stochastic optimization?
Can we obtain sample and computationally efficient algorithms for oullier-robust versions of tractable nonconvex problems using this framework?
In this work, we answer both questions affirmatively. We introduce a framework for efficiently finding an approximate SOSP when c-fraction of the functions are corrupted and then use our framework to solve the problem of outlier-robust low rank matrix sensing.
In addition to the gradient being zero, a SOSP requires the Hessian matrix to not have negative cigenvalues. The second-order optimality condition is important because it rules out suboptimal solutions such as strict saddle points. is known that all SOSPs are globally optimal in nonconvex formulations of many important machine learning problems, such as matrix completion GLM16). matrix sensing (BNS16), phase retrieval (SQW16). phase synchronization (BBVI6), dictionary learning (SQW17) 17J. and tensor decomposition [Ge+13] (see also [WM22, Chapter 7D.. However, the properties of SOSPs are highly sensitive perturbation in the input data. For example, it is possible to create spurious SOSPs for nonconvex formulations of low rank matrix recovery problems, even for a semi-random adversary that can add additional sensing matrices but cannot corrupt the measurements in matrix sensing [GC23 or an adversary who can only reveal more entries of the ground-truth matrix in matrix completion [CGT8). Those spurious SOSPs correspond to highly suboptimal solutions.
Finding SOSPs in stochastic nonconvex optimization problems in the presence of arbitrary outliers was largely unaddressed prior to our work. Prior works (Pra+20] Dia+19 obtained efficient and robust algorithms for finding ordsr stationary points with dimension-indepes independent accuracy guarantees. These works relied on the following simple idea: Under certain smoothness assumptions, projected gradient descent with an approximate gradient oracle efficiently converges to an approximate first- order stationary point. Moreover, in the outlier-robust setting, approximating the gradient at specific point amounts to robust mean estimation problem (for the underlying distribution of the gradients), which can be solved by leveraging existing algorithms for robust mean estimation.
Our work is the first to find approximate SOSPs with cuinension-inepenndee settings. Note that in standard non-robust settings. approximate SOSPs can be computed using first-order methods such as perturbed gradient descent [Jin+17 [in+21]. This strategy might seem extendable to outlier- robust settings through perturbed approximate gradient descent, utilizing robust mean estimation algorithms to approximate gradients. The approach in [Yin+19) follows this idea, but unfortunately their second-order guarantees scale polynomially with dimension, even under very strong distributional assumptions (e.g., subgaussianity). Our lower bound result provides evidence that approximating SOSPs with dimension-indeeeedden error is as hard as approximating full Hessian, suggesting that solely approximating the gradients not sufficient. On a different note, [TP1233 recently employed robust estimators for both gradient and Hessian in solving certain convex stochastic
errors in outlier-robust

---

optimization problems, which has a different focus than ours and does not provide SOSPs with the guarantees that we achieve.
1.1 Our Results and Contributions
The notation we use in this section defined in Section To state our results, we first formally define our generic nonconvex optimization problem. Suppose there is true distribution over functions f x A + R, where f(x, A) takes an argument x E IR D and is parameterized by a random variable A E A drawn from distribution G. Our goal is find an (fg> ( -approximate SOSP of the function f(x) BA-g (s, A).
Definition 1.2 (e-Corrupted Stochastic Optimization), The algorithm has access to n functions (f1)==1 generated as follows. First n random variables (A,) are drawn independently from G. Then an adversary arbitrarily corrupts an fraction of the A,'s. Finally, the e-corrupted version of f(() = f(- A,) is sent to the algorithm as input. The task is find an approximate SOSP of the ground-truth average function f(-) Ea~g A).
Definition 1.3 (Approximate SOSPs). point x is an (Cgs ( aapproximate second-order stationary point (SOSP) of f if [[)(] & cy and Amin (V²f(x) 2 -H-
We make the following additional assumptions on and g. Assumption 1.4. There exists a bounded region B such that the following conditions hold:
(i) There exists lower bound f -00 such that for all x E B. f(z, A) 2 f with probability 1. (ii) There exist parameters LDD, Lpg. BD, and BDy such that, with high probability over the randomness in A A~G G. letting g(z) f(x,A), A), we have that g(z) is -gagddie Lipschitz and LDD--Hssiaa Lipschitz over B, and [V](())] S BD, and [| S BD for all æ E B.
(iii There exist parameters g. 0 > 0 such that for all x E BB
||CovAng( f A))loop S o and A-glvce (fZ, A))) ((x((1))))|... Sozz
Note that the radius of B and the parameters LD,, LD BDG BDn all allowed to depend polynomially on D and e (but not on x and A).
Our main algorithmic result for e-corrupted stochastic optimization is summarized in the following theorem. A formal version of this theorem is stated as Theorem 3.1 in Section
Theorem 1.5 (Finding an Outlier Robust SOSP, informal). Suppose f satisfies Assumption I.4 in
region B with parameters og and он- Given an arbitrary initial point za E B and an e-corrupted set of (D2 /e) functions where D is the ambient dimension, there exists a polynomial-time algorithm that with high probability outputs (O(ggV)) (((aa)) ((ll://))-ppproximmme SOSP of f.
provided that all iterates of the algorithm stay inside B.
Although the bounded iterate condition in Theorem 1.5 appears restrictive, this assumption holds if the objective function satisfies a "dissipativity" property, which is a fairly general phenomenon (Hal10] Moreover, adding an & fz-regularization arization term enables any Lipschitz function satisfy the dissipativity property [RRT17] Section 4J. As an illustrating example, simple problem-specific analysis shows that this bounded iterate condition holds for outlier-robust matrix sensing by exploiting the fact that the matrix sensing objective satisfies the dissipativity property.
In this paper, consider the problem of outlier-robust symmetric low rank matrix sensing, which we formally define below. We focus on the setting with Gaussian design.
Definition 1.6 (Outlier-Rouust Matrix Sensing). There is an unknown rank-r ground-truth matrix M E Rddd that can be factored into U* where U d The (clean) sensing matrices (Athieja have i.idd. standard Gaussian entries. The (clean) measurements are obtained as = (A, MM)++ Ç. where the noise Ç ~ (O, a²) is independent from all other randomness. We denote the (clean) data generation process by (A,, y:) ~ G,. When a 0, we have Ç; = and we write G = Go for this noiseless (measurement) setting. In outlier robust matrix sensing, an adversary can arbitrarily change any e-fraction of the sensing matrices and the corresponding measurements. This corrupted set of (As, ).)'s is then given to the algorithm input, where the goal is to recover M*.
3

---

We highlight that in our setting, both the sensing matrices A, Rxdd and the measurements y E IR can be corrupted, presenting a substantially more challenging problem compared to prior works (e.g., 20b Li+20a that only allow corruption in y/-
Let of and or denote the largest and the smallest nonzero singular value of M respectively. We assume of and the rank r are given to the algorithm, and we assume that the algorithm knows multiplicative upper bound I' of oj such that 360j (a standard assumption in matrix sensing even for non-robust settings GJZZ7 Jin+17]. Let K =
Our main algorithmic result for the low rank matrix sensing problem is summarized in the following theorem. For a more detailed statement, see Theorems 3.2 and B.3 in Section S
Theorem 1.7 (Our Algorithm for Outlier-Rouust Matrix Sensing). Let M E Rddd be the rank ground-truth truth matrix with smallest nonzero singular value o,, Ler ž 36 || and let is = T/o There exists an algorithm for outlier-robust matrix sensing, where an ((1((x(r)) fraction of samples from Go as in Definition 1.6 gets arbitrarily corrupted, that can oulput rank-r matrix M such that || - = I with probability at least 1 - -E. where v > 0 is the error parameter:
1) Ifa 2 rI, then ((ovE))
2) o - rI, then = (noooo)))))
3) If a = 0 (noiseless), then can be made arbitrarily small, achieving exact recovery.
The algorithm uses = & (
samples and runs in time poly(n, K. log(o"/()).
Finally, we complement our algorithmic results for outlier-robust matrix sensing with a Statistical Query (SQ) lower bound, which provides strong evidence that quadratic dependence on d in the sample complexity is unavoidable for efficient algorithms. A detailed statement of this result is provided in Section 4
1.2 Our Techniques
Outlier-rouust nonconvex optimization. To obtain our algorithmic result in the general nonconvex setting, we leverage existing results on robust mean estimation (DKP20), which we use as a black box to robustly estimate the gradient and the (vectorized) Hessian. We use these robust estimates as a subroutine in a randomized nonconvex optimization algorithm (described in Appendix (A.2)) which can tolerate inexactness in both the gradient and the Hessian. With high probability, this algorithm outputs an (eg. é ) Jaappoximmaee SOSP, where Eg and εµ depend on the inexactness of the gradient and Hessian oracles.
We remark that robust estimation of the Hessian is crucial to obtaining our dimension- dimension-indepeune independent approximation error result and what causes D2 dependence in the sample complexity (which is unavoidable for SQ algorithms as discussed below). Notably, the only prior work on approximating SOSPs the outlier-robust setting (Yn+199 used robust mean estimation only on the gradients and had sample complexity scaling linearly with D: however, they only output an order (vC, 2/5) SOSP, which is uninformative for many problems of interest, including the matrix sensing problem considered in this paper, due to the dimensional dependence in the approximation error.
Application to low rank matrix sensing. Our main contribution on the algorithmic side is showing that our outlier-robust nonconvex optimization framework can be applied to solve outlier-robust matrix sensing with dimension -nndpiionnndeeeeddenn approximation error, even achieving exact recovery when the measurements the problem: We show that the norm of the covariance of the gradient and the Hessian can both be upper bounded by the sum of o² and function of the distance to the closest optimal solution. We further prove that all iterates stay inside nice region using a "dissipativity" property (Hal10), which says that the iterate aligns with the direction of the gradient when the iterate's norm is large. This allows us to invoke Theorem 1.5 to obtain an approximate SOSP of the ground-truth objective function.
noiseless. We obtain this result using the following geometric insights about
We show that this approximate SOSP must be close to a global optimal solution. Additionally, we establish local regularity condition in small region around globally optimal solutions (which is

---

similar to strong convexity but holds only locally). This local regularity condition bounds below measure of stationarity, which allows us to prove that gradient descent-type updates contract the distance to the closest global optimum under appropriate stepsize. We leverage this local regularity condition to prove that the iterates of the algorithm stay near a global optimum, so that the regularity condition continues to hold, and moreover, the distance between the current solution and the closest global optimum contracts, as long as it is larger than a function of a. Consequently, the distance- dependent component of the gradient and Hessian covariance bound contracts as well, which allows us to obtain more accurate gradient and Hessian estimates. While such a statement may seem evident to readers familiar with linear convergence arguments, we note that proving it is quite challenging, due to the circular dependence between the distance from the current solution to global optima, the inexactness in the gradient and Hessian estimates, and the progress made by our algorithm.
The described cinttacc- argument allows us to control the covariance of the gradient and Hessian, which we utilize to recover M exactly when o = 0, and recover M with error roughly Ola when 0 * S rT. We note that the a a/c appears unavoidable in the a o 0 case, due to known limits of robust mean estimation algorithms [DKS17]
SQ lower bound. We exhibit hard instance of low rank matrix sensing problem to show that quadratic dependence on the dimension in sample complexity is unavoidable for computationally efficient algorithms. Our SQ lower bound proceeds by constructing family of distributions, corre- sponding to corruptions of low rank matrix sensing, that are nearly uncorrelated a well-defined technical sense [Fll+17. To achieve this, we follow the framework of [DKS17] which considered a family of distributions that are rotations of a carefully constructed one-dimensional distribution. The proof builds on (DKST9] Dia+2[]. using a new univariate noment-matchiin construction which yields family of corrupted conditional distributions. These induce a family of joint distributions that are SQ-hard to learn.
1.3 Roadmap
Section 2 defines the necessary notation and discusses relevant building blocks of our algorithm and analysis. Section 3 introduces our framework for finding SOSPs in the outlier-robust setting. Section presents how extend and apply our framework to solve outlier-robust low rank matrix sensing. Section proves that our sample complexity has optimal dimensional dependence for SQ algorithms. Most proof' are deferred to the supplementary material due to space limitations.
2 Preliminaries
For an integer n, we use [n] to denote the ordered set f1. nn. matrix whose columns vectors a, where I is ordered set. We use 1 [xx) to denote the indicator function that equal if x E E and 0 otherwise. For two functions f and g, we say f Ö(g)
We use [aikez to denote the
f f= 0g (g)) for some constant k, and we similarly define 52
For vectors x and y,, we let (z. y) denote the inner product x y and ||=||| denote the l norm of For d E Z4. we use Id to denote the identity matrix of size d x d. For matrices A and B, we use ||Allop and || to denote the spectral norm and Frobenius norm of A respectively. We use (m))(() and Xmiin to denote the maximum and minimum eigenvalue of A respectively. We use tr( to denote the trace of matrix A. We use (A, B) tr(AA B) to denote the entry-wise inner product of two matrices of the same dimension. We vec(A) flattening of A into a vector, where 61, 02,.... Og are columns of A.
[a] 0g ....,......... ..........
. denote the canonical
Definition 2.1 (Lipschitz Continuity). Let X' and y be normed vector spaces. A function h X' + y f-Lipschitz if (z11) h (x2))ly I f || x2ll x 12..222
In this paper, when y is space of matrices, take Il-lly: to be the spectral norm I1-Ilop When X' is space of matrices, we take I| be the Frobenius norm ||-Ilp: this essentially views the function h as operating on the vectorized matrices endowed with the usual & norm. When X' or y is the Euclidean space, we take the corresponding norm be the lg norm.
Randomized Algorithm with Inexact Gradients and Hessians. We now discuss how to solve the unconstrained nonconvex optimization problem min f(z), where f()) is a smooth function
5

---

with Lipschitz gradients and Lipschitz Hessians. The goal of this section is to find an approximate SOSP as defined in Definition L.
Proposition 2.2 ([LW33). Suppose a function f is bounded below by f- -00, has L--Lipschitz gradient and -.p-hiiscchtz Hessian, and its inexact gradient and Hessian computations and He
satisfy l1 V V (xx)ll 3 and || (xx))lop S zCH- Then there exists algorithm
(Algorithm with the following guarantees:
1. (Correctness) If Algorithm SOSP.
A.1
terminates and outputs 2ns then In is a (3 JEH) approximmate
2 2 61, 21
2. (Runtime) Algorithm probability at least
A
terminates with probability 1. Let C. := min
With
o, Algorithm
A.7 terminates after l iterations for
f ro)
S
I log
k = 0
Ce
cH
The constants 1/3 and 2/9 are chosen for ease of presentation. For all constructions of Hessian oracles in this paper, we take the straightforward relaxation ||, - f2z))lo S - and upper bound Hessian inexactness using Frobenius norm. Proof of simplified version of Proposition 2.2 with weaker high probability bound that is sufficient for our purposes is provided in Appendix for completeness.
Robust Mean Estimation. Recent algorithms robust mean estimation give dimension- independent error in the presence of outliers under strong contamination model.
We use the following results, see, e.g.. [KP200] where the upper bound on the spectral norm of covariance matrix is unknown to the algorithm.
Proposition 2.3 (Robust Mean Estimation). Fix any O < É 1. Let S be multiset of n O(k log + log(1/E))/ i..d samples from a distribution on IR with mean ps and covariance E. Let RR be an e-corrupted version of as in Definition 1.1 There exists an algorithm (Algorithm A.2 such that, with probability at least 1 - -5, input and T (but not [| returns
vector ço in polynomial time so that I|us - x
e).
Algorithm A.2 is given in Appendix A.3 Proposition 2.3 states that for Algorithm A.2 to succeed
with high probability, Ō(k/c) i.i.d. samples need to be drawn from a k-dimensional distribution of bounded covariance. State of the art algorithms for robust mean estimation in near-linear time, requiring only a logarithmic number of passes on the data, see, e.g. DDa+222 CDG19 I Any of these faster algorithms could be used for our purposes.
be implemented
With the above results, the remaining technical component for applying the robust estimation subroutine (Algorithm A.2) in this paper is handling the dependence across iterations.
Because we will run RobustMeanEstimation in each iteration of our optimization algorithm, the gradients (x++)) and Hessians (xx){ can no longer be considered as independently drawn from a distribution after the first iteration. Although they are i.i.d. for fixed x, the dependence on previous iterations through will break the independence assumption. Therefore, we will need a union bound over all x, to handle dependence across different iterations t. We deal with this
technicality in Appendix B
3 General Robust Nonconvex Optimization
In this section, establish general result that uses Algorithm A. to obtain approximate SOSPs in the presence of outliers under strong contamination. The inexact gradient and inexact Hessian oracles constructed with the robust mean estimation subroutine (Algorithm A.2). We consider stochastic
optimization tasks in Definition 1.2 satisfying Assumption [.4 We construct the inexact gradient and
Hessian oracle required by Algorithm A.I as follows:
gt <- Robusttaannssiintttoo (V[(i)aattii((((==)))))>>>)
H, + RobustMean (V")

---

Then we have the following guarantee:
Theorem 3.1. Suppose we are given e-corrupted of functions [f sample size n, generated
according to Definition 1.2 Suppose Assumption 1.4 holds in bounded region B C RD of diameter y with gradient and Hessian covariance bound og and о respectively, and we have an arbitrary initialization v0 B. Algorithm A./ initialized at xo ouiputs an (fy. < -approximmae SOSP for sufficiently large sample with probability at least - if if following conditions hold:
(I) All iterates 24 in Algorithum 1.1 stay inside the bounded region B.
(II) For an absolute constant > 0, holds that 0g 0gve= S (Cgg and o S cCH-
The algorithm uses
((D))e) samples, where Ö(-) hides logarithmic dependence on D e,e, LD,; LD,,BD, "/op>//o,,/// and 1/5. The algorithm runs in time polynomial in the above parameters.
Note that we are able to obtain dimension-inndepedeee errors Cy and 6xs provided that dg and are dimension-indee inneepednnn
3.1 Low Rank Matrix Sensing Problems
In this section, we study the problem outler-robust low rank matrix sensing as formally defined in Definition 1.6 We first apply the above framework to obtain approximate SOSP in Section B.1.2 Then we make use of the approximate SOSP to obtain a solution that is close to the ground-truth matrix M in Section
3.1.3 this demonstrates the usefulness of approximate SOSPs.
3.1.1 Main results for Robust Low Rank Matrix Sensing
The following are the main results that we obtain this section:
Theorem 3.2 (Main Theorem Under Noiseless Measurements). Consider the noiseless setting as in O. For some sample size Ō(dd,² + dr log(L//E)//e and with probability at least 1 - 5. there exists an algorithm that outputs a solution that is t-close to M Frobenius norm in O(1 log(1/E) + log(o,, (osso//// /t) calls to the robust mean estimation subroutine (Algorithm A.2
Theorem w.th with
This result achieves exact recovery of M despite the strong contamination of samples. Each iteration involves a subroutine call to robust mean estimation. Algorithm A.2 presented here is one simple example of robust mean estimation; there are refinements [Dia+22] DHL that run in nearly linear time, so the total computation utilizing those more efficient algorithms indeed requires (12x²) passes of data (computed gradients and Hessians).
Theorem 3.3 (Main Theorem Under Noisy Measurements). Consider the same setting as in Theo- rem 1.7 with a of There exists a sample size n. (dpp2 dr log(T/E))/o such that
a S SrT, then with probability at least E, there exists an algorithm that outputs a solution M in Ō(r2k3) calls to robust mean estimation routine A.2 with error || M
1| = O(RO /c);
o 2 rI, then with probability at least 1- &, there exists a (different) algorithm that outputs a solution M in one call to robust mean estimation routine A.2 with ervor || - M = O
We prove Theorem 3.3 in Appendix C.4 and instead focus on the noiseless measurements with = 0 when we develop our algorithms in this section; the two share many common techniques. In the remaining part of Section 3.1 We now describe how we obtain the solution via nonconvex optimization. Consider the following objective function for (uncorrupted) matrix sensing:
we use Go in Definition I.6 for the data generation process.
min M Me (Arik)~GG rank(M) M)r
E
((M, Ar) =
We can write M = U for some U Rddxr to reparameterize the objective function. Let
1 f((0) = (LUUT.A) .A.) =v)²
(3)
7

---

We can compute
f(U) =
E (A.
((U))
1
Var(UUT M A.) | - M
1
We seek to solve the following optimization problem under the corruption model in Definition 1.2 f(U).
min
UERAXT
The gradient Lipschitz constant and Hessian Lipschitz constant of are given by the following result. Fact 3.4 (1in+17), Lemma 6). For any 1 > oi. f(U) has gradient Lipschitz constant Lg 16T and Hessian Lipschitz constant Lg 24r's inside the region {U : :1[Ulppp F).
3.1.2 Global Convergence to an Approximate SOSP
In this section, apply framework Theorem 3.1 obtain global convergence from arbitrary initialization to an approximate SOSP, by providing problem-specific analysis to guarantee that both Assumption 1.4 algorithmic assumptions (I) and (II) required by Theorem 3.1 are satisfied.
Theorem 3.5 (Global Convergence to SOSP). Consider the noiseless setting as in Theorem 1.7 with
0 and e O11/(x²r))) Assume have arbitrary initialization Uo inside {U | op r}.
There exists sample size n Ô ((d2,² + dr log (o))(/)))/e)) such that with probability at least
1 - 5, Algorithm A.1 initialized at Uo outputs a a 3/2 3 -approximate SOSP using at most Orp" R² log(1/E)) calls to robust mean estimation subroutine (Algorithm A.2
Proof of Theorem
3.5 To apply Theorem 3.1 we verify Assumption first. To verify (i), for all
so f 0 is uniform lower bound. We verify (ii) in Appendix C.2 conceptually, by Fact 3.4 f is gradient and Hessian Lipschitz; both gradient and Hessian of Ji are sub-exponential and concentrate around those of ʃ. To check (iii), we calculate the gradients and Hessians of ft in Appendix C.I.I and bound their covariances from above in
and A., f((U) (UUUT, (A)) - y
Appendix C.1.2 and C.I.3 The result summarized the following lemma. Note that the domain of the target function in Algorithm A.J and Theorem 3.1 is the Euclidean space R,,, so we vectorize U and let D dr. The gradient becomes vector in a and the Hessian becomes matrix in dddxxdr
Lemma 3.6 (Gradient and Hessian Covariance Bounds). For all U Rdxr with || S I and fa defined in Equation it holds
(ooo(vec(Vfi(U))) S - - M 1= |1l1 S 3
(6)
|[Cov(vecHH))llop I 16r - - M 1| + 128 | < 19
(7)
We proceed to verify the algorithmic assumptions in Theorem For the assumption (I), we prove the following Lemma in Appendix C.2 to show that all iterates stay inside the bounded region in which we compute the covariance bounds.
Lemma 3.7. All iterates of Algorithm A.l
stay inside the region UU ||Ul S 1'}.
To verify Theorem 3.1 (II), we let cg =
32 o. 3/2 CH = 10 and 0g 1.1 oH = 16r So
we assume e = (11 3 3, ))), then for the absolute constant e Theorem 3.1 it holds that
ogve S ceg
anvE CEH.
Hence, Theorem 3.1 applies and Algorithm A.1 outputs an
SOSP with high
probability in polynomial time. To bound the runtime, since f(U,) 1/2 UOUJ -M 12 0()212) for an arbitrary initialization Uo with [|Ubl < I, the initial distance can be bounded by (1r2))) Setting Lg = 16I, LH = 1/2 f(U)) = 21) f = 0 and thus C. = O /T). Proposition 2.2 implies that Algorithm A.1 outputs of 3/2 stationary point UsOSP in 2r log( ( steps with high probability.
3 f approximate second order

---

3.1.3 Local Linear Convergence
In this section, we describe a local search algorithm that takes ( order stationary point as its initialization and achieves exact recovery in the presence of outliers.
3/2 - second-
Algorithm 3.1: Local Inexact Gradient Descent
Data: The initialization USoSp is (2 3/3 - -aprooxitt SOSP, corruption fraction is c, corrupted samples are ((4, y:Jr== target distance to optima is L
Result: U that is i-close in Frobenius norm some global minimum 1/T, Ug = USOSP for = 0, ... do
== BobuutMMeaastiimttooooWWW/oC
U11 U₁ 19tt
Theorem 3.8 (Local Linear Convergence). Consider the same noiseless setting in Theorem 1.7 Assume we already found a 0,,07 ) apprrxxmaae SOSP UsOSP of Then there exists sample size n n (dr log(1/E)/c) such that with probability at least 1 E. Algorithm 3.1 initialized USOSP outputs a solution that is t-close some globul minimum in Frobenius norm after
(K log(o;;1)) calls to robust mean estimation subroutine (Algorithm A.2 2 Moreover, all iterates Ug are o 1/2 -close to some global minimum in Frobenius norm.
Proof Sketch. First we use known properties of ( fi from the literature [Jin+17 | to show approximate SOSPs of f - in particular our initialization UsOSP are in a small neighbor- hood of the global minima of f. In that neighborhood. it was also known that f satisfies some local regularity conditions that enable gradient descent's ' linear convergence.
However, the algorithm only has access the inexact gradient from the robust mean estimation subroutine (line Sl in Algorithm 3.T and, therefore, we need to establish linear convergence of inexact gradient descent. We achieve this with the following iterative argument: As the iterate gets closer to global optima, the covariance bound of sample gradient in Equation (6) gets closer to 0. Because the accuracy of the robust mean estimation scales with the covariance bound (see Proposition 2.3 more accurate estimate of population gradient V can be obtained via the robust estimation subroutine (Algorithm A.2). This, in turn, allows for an improved inexact gradient descent step. driving the algorithm towards an iterate that is even closer to global optima.
See Appendix for the complete proof.
4 Statistical Query Lower Bound for Low Rank Matrix Sensing
Our general algorithm (Theorem 3.1 leads to efficient algorithm for robust low rank matrix sensing with sample complexity Old (Theorem 3.3). Interestingly, the sample complexity of the underlying robust estimation problem ignoring computational considerations is (dr/cc. The information -thooretic upper bound of (dr /e) can achieved by an exponential (in the dimension) time algorithm (generalizing the Tukey median to regression setting); see, e.g., Theorem 3.5
in (Gaa22).
Given this discrepancy, it is natural to ask whether the sample complexity achieved by our algorithm can be improved via a different computationally efficient method. In this section, we provide evidence that this may not be possible. In more detail, we establish near-optimal information-computtiio tradeoff for the problem, within the class of Statistical Query (SQ) algorithms. To formally state our lower bound, we require basic background on SQ algorithms.
Basics on SQ Model. SQ algorithms are a class of algorithms that, instead of access to samples from some distribution P, are allowed query expectations of bounded functions over P.
Definition 4.1 (SQ Algorithms and STAT Oracle [Kaa9)]) Let P be a distribution on 1d+++1 A Statistical Query (SQ) is bounded function [g [-1, 1]. For 7 0, the STAT(T) oracle

---

responds to the query with a value such that - -x-Exxpleee Ex=pla(X)]] S T. An SQ algorithm is an algorithm whose objective is to learn some information about an unknown distribution P by making adaptive calls to the corresponding STAT (T) oracle.
In this section, we consider P as the unknown corrupted distribution where (A,, 34) are drawn. The SQ algorithm tries to learn the ground truth matrix M from this corrupted distribution; the goal of the lower bound result is to show that this is hard.
The SQ model has the capability to implement diverse set of algorithmic techniques in machine learning such as spectral techniques, moment and tensor methods, local search (e.g.. Expectation Maximization). and several others [Fel+17]. A lower bound on the SQ complexity of problem provides evidence of hardness for the problem. [Bre+2I] established that (under certain assumptions) an SQ lower bound also implies a qualitatively similar lower bound in the low-degree polynomial testing model. This connection can used show a similar lower bound for low-degree polynomials.
Our main result here is near-optimal SQ lower bound for robust low rank matrix sensing that applies even for rank rank r = yields the strongest possible lower bound in our setting because it is the easiest parameter regime: Recall that the sample complexity of our algorithm is ()d)r²) as in Theorems 3.2 and 3.3 and the main message of our SQ lower bound is to provide evidence that the d2 factor is necessary for computationally efficient algorithms even if r 1.
1, i.c., when the ground truth matrix M uuu for some u Rd. The choice of
Theorem 4.2 (SQ Lower Bound for Robust Rank- Matrix Sensing). Let e E (0,1/2) be the fraction of corruptions and let с E (0, 1/2). Assume the dimension d E is sufficiently large. Consider the e-corrupted rank-one matrix sensing problem with ground-truth matrix M uu
and noise o² = O()). Any SQ algorithm that outputs ã with ji ull =(e either requires 20(d") /d2 queries or makes at least one query to STAT (1/V)) /0 (0(d-20))
In other words, we show that, when provided with SQ access an e-corrupted distribution, ap- proximating u is impossible unless employing a statistical query of higher precision than what can be achieved with a strictly sub-quadratic number (e.g., d'-99) of samples. Note that the SQ oracle STAT(( ((1/E)) (Od)-20) can be simulated with ( (e0L/e) samples, and this bound is tight in general. Informally speaking. this thcorem implics that improving the sample complexity from d to d² 4c requires exponentially many queries. This result can be viewed near-optimal information computation tradeoff for the problem, within the class of SQ algorithms.
The proof follows a similar analysis as in DKS19 Dia+21) using one- one-dimensional moment matching to construct a family of corrupted conditional distributions, which induce family of corrupted joint distributions that are SQ-hard to learn. We provide the details of the proof in Appendix D Apart from the formal proof, Appendix [ we also informally discuss the intuition for why some simple algorithms that require (dd) samples do not provide dimension-independeee error guarantees.
Acknowledgements
Shuyao Li was supported in part by NSF Awards DMS- NMMS2003239, NSF Award CCF-2007757 and the U. S. Office of Naval Research under award number N00014-22- 1-1-2-----2348 Yu Cheng supported in part by NSF Award CCF-2307 106. Ilias Diakonikolas was supported in part by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER), Sloan Research Fellowship, and DARPA Learning with Less Labels (LwLL.) grant. Jelena Diakonikolas was supported part by NSF Award
CCF-2007757 and by the U.S. S. Office of Naval Research under award number N00014-22-1 1-2448. Rong Ge was supported in part by NSF Award DMS-2031 1849, CCF-184517 (CAREER) and a
Sloan Research Fellowship. Stephen Wright was supported in part by NSF Awards DMS-2023239 and CCF-2224213 and AFOSR via subcontract UTA20-00122 from UT-Austin.
10

---

References
[Bar+10]
M. Barreno, B. Nelson, A. D. Joseph, and J. D. Tygar. "The security of machine learning". In: Machine Learning 81.2 (2010), pp. 121-148.
[BBV16] A. S. Bandeira, N. Boumal, and V. Voroninski. "On the low-rank approach for semidefi- nite programs arising in synchronization and community detection".. In: Conference on learning theory. PMLR. 2016, pp. 361-382.
[Ber+22] E. H. Bergou, Y. Diouane, V. Kunc, V. Kungurtsev, and C. W. Royer. "A subsampling line-search method with second-order results". In: INFORMS Journal on Optimization
4.4 (2022), pp. 403-425.
[BNL12] B. Biggio, B. Nelson, and P. Laskov. "Poisoning Attacks against Support Vector Ma- chines".. In: Proceedings of the 29th International Coference International Conference on Machine Learning. Omnipress, 2012, pp. 1467-1474.
[BNS16]
S. Bhojanapalli, B. Neyshabur, and N. Srebro. "Global optimality of local search for low rank matrix recovery". In: Advances in Neural Information Processing Systems. 2016,
pp. 3873-3881.
[Bre+21]
M. S. Brennan, G. Bresler, S. Hopkins, J. Li, and T. Schramm. "Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent". In: Proceedings of Thirty Learning Theory. Ed. by M. Belkin and S. Kpotufe. Vol. 134.
Fourth Conference Proceedings of Machine Learning Research. PMLR, 15-19 Aug 2021, pp. 774-774.
[CDG19]
Y. Cheng, I. Diakonikolas, and R. Ge. "High-Dimensions" Robust Mean Estimation in Nearly-Linear Time". In: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2019, pp. 2755-2771.
(CG18)
Y. Cheng and R. Ge. "Non-convex matrix completion against semi-random adversary".
In: Conference On Learning Theory. PMLR. 2018, pp. 1362-1394.
[DHL19]
Y. Dong, S. Hopkins, and Li. "Quantum entropy scoring for fast robust mean estimation and improved outlier detection".. In: Advances in Neural Information Processing Systems 32 (2019).
[Di++16]
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. "Robust estimators in high dimensions without the computational intractabilitt".. In: 57th Anmual IEEE Symposium on Foundations of Computer Science-FOCe 2016. IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 655-664.
[Dia+17]
I. Diakonikolas, G. Kamath, D. M. Kane, Li, A. Moitra, and A. Stewart. "Being Robust (in High Dimensions) Can Be Practical". In: Proceedings of the 34th International Conference on Machine Learning. Ed. by D. Precup and Y. W. Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, June 2017, pp. 999-1008.
[Dia+19]
I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart. "Sever: Robust Meta-Algoritha for Stochastic Optimization". In: Proceedings of the 36th Inter- national Conference on Machine Learning. Ed. by K. Chaudhuri and R. Salakhutdinov. Vol. 97. Proceedings of Machine Learning Research. PMLR, Sept. 2019, pp. 1596-1606.
[Dia+21]
I. Diakonikolas, D. Kane, A. Pensia. T. Pittas, and A. Stewart. "Statistical Query Lower Bounds for List- Dist-Decodable Linear Regression". " In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and
J. W. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 3191-3204.
[Di++22]
I. Diakonikolas, D. M. Kane, A. Pensia, and T. Pittas. "Streaming Algorithms for High- Dimensional Robust Statistics". In: Proceedings of the 39th International Conference on Machine Learning. Ed. by K. Chaudhuri, S. Jegelka, L. Song. C. Szepesvari, G. Niu, and S. Sabato. Vol. 162. Proceedings of Machine Learning Research. PMLR, July 2022. pp. 5061-5117.
[DK19]
I. Diakonikolas and D. M. Kane. "Recent advances in algorithmic high-dimensional robust statistics". In: arXiv preprint 1rXiv:191L.0S3 (2019).
[DK23]
I. Diakonikolas and D. M. Kane. Algorithmic High Digh-DDimesional Robust Statistics. Cambridge University Press, 2023.
[DKP20]
I. Diakonikolas, M. Kane, and A. Pensia. "Outlier Robust Mean Estimation with Sub- gaussian Rates via Stability". In: Advances in Neural Information Processing Systems. Ed. by H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin. Vol. 33. Curran Associates, Inc., 2020, pp. 1830-1840.

---

[DKS17]
I. Diakonikolas, D. M. Kane, and A. Stewart. "Statistical Query Lower Bounds for Robust Estimation of High-Dimensiona Gaussians and Gaussian Mixtures". In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 2017, pp. 73-84.
[DKS19]
I. Diakonikolas, Kong, and A. Stewart. "Efficient algorithms and lower bounds for robust linear regression". In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 2019, pp. 2745-2754.
[Dur19]
R. Durrett. Probability-theory and examples. Vol. 49. Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019. V. Feldman, Grigorescu, L. Reyzin, S. Vempala, and Xiao. "Statistical Algorithms and Lower Bound for Detecting Planted Cliques". In: J. ACM 64.2 (2017), 8:1-8:37. C. Gao. "Robust regression via mutivariate regression depth". In: Bernoulli 26.2 (2020),
[Fel+17]
[Gao20]
pp. 1139-1170.
[GC23]
X. Gao and Y. Cheng. "Robust Matrix Sensing in the Mani-Random Model". In: Pro- ceedings of the 37th Conference on Neural Information Processing Systems (NeurlPS) (2023).
[Ge+15]
R. Ge, F. Huang, C. Jin, and Y. Yuan. "Escaping from saddle points-online stochastic gradient for tensor decomposition", In: Conference on Learning Theory. 2015, pp. 797- 842.
[GJZ17] R. Ge, C. Jin, and Y. Zheng. "No Spurious Local Minima in Nonconvex Low Rank Problems: Unified Geometric Analysis". In: Proceedings of the 34th International Conference Machine Learning. Ed. by D. Precup and Y. W. Teh. Vol. 70. Proceedings Machine Learning Research. PMLR, June 2017, pp. 1233-1242.
[GLM16]
R. Ge, J. D. Lee, and Ma. "Matrix completion has no spurious local minimum". In: Advances in Neural Information Processing Systems. 2016, pp. 2973-2981.
[Hal10]
J. K. Hale. Asymptotic behavior of dissipative systems. 25, American Mathematical Soc.,
2010.
[Ham+86]
F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust statistics. The approach based on influence functions. Wiley New York, 1986.
[HR09]
P. J. Huber and E. M. Ronchetti. Robust statistics. Wiley New York, 2009.
[Hub64]
P. J. Huber. "Robust estimation of a location parameter". In: Annals of Mathematical Statisties 35 (1964), pp. 70-101. E. Ioannou, M. S. Pydi, and P.-L. Loh. "Robust empirical risk minimization via Newton's method". In: arXiv preprint 3rXiv:2300.13199 (2023).
[IPL23]
[Jin+17]
C. Jin, R. Ge. P. Netrapalli, S. M. Kakade, and M. I. Jordan. "How to Escape Saddle Points Efficiently". In: Proceedings of the 34th International Conference on Machine Learning. Ed. by D. Precup and Y. W. Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, June 2017, pp. 1724-1732.
[Jin+21]
Jin, P. Netrapalli, R. Ge. S. M. Kakade, and M. Jordan. "On nonconvex optimization for machine learning: gradients, stochasticity, and saddle points". In: Journal of the ACM 68.2 (2021), Art. 11, 19.
[Kea98]
M. J. Kearns. "Efficient noise-tolerant Learning from Statistical Queries". In: Journal of the ACM 45.6 (1998), pp. 983-1006.
[Li+08]
J. Li, D. Absher, H. Tang, Southwick, A. Casto, Ramachandran, Cann, G. Barsh,
M. Feldman, L. Cavalli-Sforzz and R. Myers. "Worldwide human relationships inferred from genome-wine wide patterns of variation" In: Science 319 (2008), pp. 1100-1104.
[Li+20a]
X. Li, Z. Zhu, A. Man-Cho So, and R. Vidal. "Nonconvex robust low-rank matrix recovery". In: SIAM Journal on Optimization 30.1 (2020), pp. 660-686.
[Li+20b]
Y. Li, Y. Chi, H. Zhang, and Y. Liang. "Non-convex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent". In: Information and Inference:
A Journal of the IMA 9.2 (2020), pp. 289-325.
[LRV16]
K. Lai, A. B. Rao, and S. Vempala. "Agnostic Estimation of Mean and Covariance".
In: focs2016. 2016, pp. 665-674.
[LW23]
S. Li and S. J. Wright, "A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees". In: arXiv preprint arXiv:2310. 1884 (2023).
12

---

[Pas+10]
P. Paschou, J. Lewis, A. Javed, and P. Drineas. "Ancestry Informative Markers for Fine-Scale Individual Assignment Worldwide Populations". In: Journal of Medical Genetics 47 (2010), pp. 835-847.
[Pra+20]
A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. "Robust estimation via robust gradient estimation". In: Journal of the Royal Statistical Society. Series Statistical Methodology 82.3 (2020), pp. 601-62)
[Ros+02]
N. Rosenberg, Pritchard. Weber, H. Cann, K. Kidd, L. Zhivotovsky, and M. Feldman. "Genetic structure of human populations" In: Science 298 (2002), pp. 2381-2385,
[RRT17]
M. Raginsky, A. Rakhlin, and M. Telgarsky. "Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis". In: Proceedings of the 2017 Conference on Learning Theory. Ed. by S. Kale and O. Shamir. Vol. 65. Proceedings of Machine Learning Research. PMLR, July 2017, pp. 1674-1703.
[SKLI7] J. Steinhardt, P. W. Koh, and P. S. Liang. "Certified Defenses for Data Poisoning Attacks". In: Advances in Neural Information Processing Systems 30. 2017, pp. 3520-3532.
[SQW16] J. Sun, Q. Qu, and Wright. "A geometric analysis of phase retrieval", Information Theory (ISIT), 2016 IEEE International Symposium on. IEEE. 2016, pp. 2379-2383.
[SQW17] J. Sun, Q. Qu, and J. Wright. "Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture". In: IEEE Trans. Inf. Theor. 63.2 (Feb. 2017), pp. 853-884.
[Tuk75]
J. Tukey. "Mathematics and picturing of data". In: Proceedings of ICM. Vol. 6. 1975, pp. 523-531.
[WM22]
J. Wright and Y. Ma. High-dimensional data analysis with low-dimensional models: Principles, computation, and applications. Cambridge University Press, 2022.
[Yin+19]
D. Yin, Y. Chen, R. Kannan, and P. Bartlett. "Defending against saddle point attack in Byzantine-robust distributed learning". In: International Conference Machine Learning. PMLR. 2019, pp. 7074-7084.
13


Reviews:
[{"review_id": "il0lvPQIfP", "reviewer": "Reviewer_kWga", "summary": "This paper studies the problem of finding approximate second-order stationary point when a constant fraction of datapoints are corrupted by outliers. It proposes an algorithm with provable guarantees which matches the statistical query lower bound established in the paper. The general result is applied to study low-rank matrix sensing with outliers.", "questions": "1. This paper considers symmetric case. What if the matrix $M^{\\star}$ is asymmetric?\n\n2. A closely related problem is matrix completion. Is it possible to extend the analysis to matrix completion? \n\n3. It is assumed that the algorithm requires knowledge of a multiplicative upper bound $\\Gamma$ of $\\sigma_1^{\\star}$. How can this parameter be estimated in practice?", "limitations": "This paper does not have potential negative social impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper first proposes a general result in finding approximate SOSP and then applies it to study the widely applicable problem of low-rank matrix sensing. The newly proposed algorithm is proved to be able to find an approximate SOSP in polynomial time even when a constant proportion of samples are corrupted. It also provides a lower bound on the sample complexity for rank-one matrix sensing which matches the required sample size of the algorithm, confirming the efficacy of the algorithm.", "weaknesses": "1. The results obtained in Theorem 1.7 and 3.3 suggest that increasing the sample size $n$ (while fixing the noise level $\\sigma$ and outlier fraction $\\epsilon$) does not enhance the algorithm's performance, as the estimation error does not depend on the sample size. This observation seems counterintuitive and calls for additional clarification in order to better understand this phenomenon.\n\n2. In Section 4, the paper presents a lower bound for low-rank matrix sensing specifically for the case where the rank is one (i.e., $r=1$). The statement \"Our main result in this section is a near-optimal SQ lower bound for robust low-rank matrix sensing that applies even for rank $r=1$\" suggests that the rank-one scenario poses additional challenges than the general low-rank case, which doesn't sound reasonable. Further clarification is needed to better understand this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weaknesses 1 & 2 and Question 2 were addressed in the global response.\n\nFor Question 1, we intended to present our robust low-rank symmetric matrix sensing algorithm as a simple application of our general robust nonconvex optimization framework. The techniques are generalizable to asymmetric ground truth matrix $M^*$: [GJZ17, Section 5] discussed how to reduce asymmetric $M^*$ to the symmetric case, i.e. when $M = U V^\\top$ for some tall matrices $U$ and $V$, we have $[UU^\\top, M; M^\\top, VV^\\top] = [U; V] [U; V]^\\top$ (which is symmetric) and one can add an additional regularizer in the objective function so that $UU^\\top \\approx VV^\\top$. We leave the details to future work.\n\nFor Questions 3 & 4, knowing an upper bound of the norm of the ground-truth matrix is a standard assumption in matrix sensing, even for non-robust settings. See, e.g., [GJZ17] and [Jin+17]. Its estimation is an interesting question but beyond the scope of our paper. One potential technique is to double the upper bound until a solution is found; the estimation procedure can certify a solution by robustly estimating the value of the objective function and checking whether the error bound in Theorem 1.7 is satisfied. We will clarify this.\n"}, {"review_id": "re1jZBcrW9", "reviewer": "Reviewer_emkc", "summary": "In this work, the authors proposed a new algorithm to find approximate second-order stationary points for stochastic optimization problems under the strong contamination model. The general algorithm is applied to the robust matrix sensing problem and the convergence results are proved for the robust matrix sensing problem.", "questions": "(1) Line 48: \"newdiscussed\" is a typo.\n\n(2) Line 69: it would be better to (briefly) discuss the counterexample in the appendix.\n\n(3) Line 85: it seems that both \"second-order stationary point\" and the abbreviation \"SOSP\" are used throughout the paper. It would be better to be consistent in using the abbreviation.\n\n(4) Line 93: I think B_D_g and B_D_H should be the bound on the norm of the gradient and the Hessian matrix, respectively?\n\n(5) Theorem 1.5: maybe the authors can briefly discuss the reason why the sample complexity is inversely proportional to the corruption rate \\epsilon?\n\n(6) Line 148: it may be better to use D to denote the dimension.\n\n(7) Line 157: I wonder if the region is the same as the region B in Assumption 1.4? In addition, is the information about region B provided to the algorithm as an input parameter? It will be helpful if the authors can clarify it in the paper.\n\n(8) It seems that the statements on Lines 163 and 166 are the same.\n\n(9) Line 169: it would be better if the authors can be more specific on the circular dependence. Does it refer to the rotational invariance of the objective function?\n\n(10) Line 176: I think the results in the following paper also concerns the noiseless and Gaussian measurement case. It will be better if the results in the following paper can be discussed and compared.\n\nLi, Xiao, Zhihui Zhu, Anthony Man-Cho So, and Rene Vidal. \"Nonconvex robust low-rank matrix recovery.\" SIAM Journal on Optimization 30, no. 1 (2020): 660-686.\n\n(11) In Equation (1), the computational complexity is proportional to \\epsilon_g^2. This is a little counter-intuitive, since the upper bound of the running time is not changed is we shrink \\epsilon_g and \\epsilon_H together (at different rates). It would be better if the authors can include an explanation to this relation.\n\n(12) Line 231: \"exists\"\n\n(13) Theorem 3.5: It would be better to mention the condition \\epsilon = O(1/k^2/r^2).\n\n(14) Line 320: \"Theorem 3.1 applies\"\n\n(15) Line 367: it would be better to explain why the results are more significant or important for the rank-1 case.\n\n(16) Line 378: it will be helpful if the authors can briefly explain how to generate the SQ oracle.", "limitations": "See my comments in the previous section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The results in this work are novel and should be interesting to audiences in optimization and machine learning fields.", "weaknesses": "It is unclear how the results of this work differ with those in literature; see my comment (10) in the next section. The presentation of the results and the sketch of proofs can be improved. Currently, many important technical details are omitted in the main manuscript. For example, Algorithms A.1-2 and the construction of distributions for the SQ lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing out the typos in Questions (1)(6)(12)(14) and suggestions for our presentation Questions (3)(13). Question (15) was addressed in the global response. As for the weakness about our presentation, we provided a sketch of the proof in the main body and deferred algorithms introduced in other papers and technical details to the appendix due to page limitations. \n\nAbout Question (10) and the main weakness about our novelty: Thank you for pointing out this improvement over [Li+20] and we will add it to the references. This paper, as well as the cited [Li+20], discussed the setting where outliers only exist in the measurements $y_i$. Our paper, in contrast, considers the more challenging scenario where both sensing matrices $A_i$ and measurements $y_i$ can be corrupted. Since the sensing matrices are high-dimensional objects, allowing their corruptions results in a much more difficult problem: while both [Li+20] and [Li+20a] can solve their problem with $\\widetilde O(d r)$ samples, our setup requires $\\widetilde \\Omega (d^2)$ samples as evidenced by our SQ lower bound. \n\n[Li+20a] Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Rene Vidal. \"Nonconvex robust low-rank matrix recovery.\" SIAM Journal on Optimization 30, no. 1 (2020): 660-686. \n\nAbout Question (5): See the global response for the derivation of the sample complexity. Our algorithm uses robust mean estimation discussed in the global response as a subroutine, which is why we have the same dependence on $\\epsilon$.\n\nAbout Question (7): Yes, the region in Theorem 1.5 is the same as in Assumption 1.4. Our algorithm does not explicitly check whether the iterates move outside the region. This is a fairly standard assumption in robust nonconvex optimization (see the global response where we argue this assumption is not restrictive). In the application to low-rank matrix sensing, we proved that this assumption is indeed satisfied. Note that information about region $\\mathcal{B}$, though not explicitly required and checked, might be implicitly passed to the algorithm because it can be related to the Lipschitz constant of the gradient or Hessian of the objective function. \n\nAbout Questions (8) & (9): The circular dependency in Line 169 refers to the following dependencies of three quantities: the gradient inexactness estimate depends on the covariance bound of gradients (which depends on the covariance bound of the gradients, see Proposition 2.3), the distance between current solution and global optima (which depends on the gradient inexactness, see Equation (32)), and the covariance bound of the gradients (which depends on the distance to global optima, see Equation (17) when we computed the covariance of the gradients). We intended to use this paragraph to sketch and help readers understand the proof of Theorem 3.8 and its difficulties. The repetition of similar wordings in Lines 163-166 happens when we are trying to sketch how we overcame such circular dependence.\n\nAbout Question (2): There is a counterexample from our low-rank matrix sensing application where the adversary can trick the algorithm into believing that a saddle point with dimension-dependent negative curvature appears to be a local minimum solution. We will include this counterexample in the appendix. \n\nAbout Question (4): When we discuss the general robust nonconvex optimization result, we consider the gradient to be a vector and Hessian to be a matrix. When we apply this result to robust low-rank matrix sensing, we vectorize the matrix variable $U$ when we invoke Algorithm A.1 to fit into the general framework.\n\nAbout Question (11): Equation (1) consists of two terms. The first term is the expected computational complexity that scales with $\\max(\\epsilon_g^{-2}, \\epsilon_H^{-3})$, which is standard for vanilla gradient descent algorithms with negative curvature detection. The second term is the correction when we extend the expected computational complexity to the high probability bound, which involves some more complicated interplay between the gradient step ($\\epsilon_g$ dependence) and negative curvature steps ($\\epsilon_H$ dependence). If we shrink $\\epsilon_g$ and $\\epsilon_H$ together, the first term will increase.\n\nAbout Question (16): A statistical query with accuracy \\tau can be implemented with error probability $\\delta$ by taking $O(\\log(1/\\delta)/\\tau^2)$ samples and evaluating the empirical mean of the query function $q(\\cdot)$ evaluated at those samples. It is usually possible to reuse samples across different queries. See the paragraph “SQ Algorithms versus Traditional Algorithms” in [DK23, Chapter 8.2.1] for a more detailed discussion.\n"}, {"review_id": "zT91ON9TtY", "reviewer": "Reviewer_jUUi", "summary": "This paper considers the problem of finding a second-order stationary point in corrupted settings. In particular, it considers the adversarial settings, where a fraction of the observations are arbitrarily corrupted after they are observed. In this setting, under certain assumptions on the cost functions, the authors give an algorithm that yields a second-order stationary point with $n=O(D^2/\\epsilon)$ samples. This result is applied to problem of robust matrix sensing.", "questions": "- I wonder when one would want to apply such a method over first-order methods. In particular, this method requires computing estimates of the Hessian, which is quite expensive in high-dimensional settings. Can the authors motivate a bit more why the second-order stationarity is important, for example, in the application they discuss (low-rank matrix sensing)? Experiments on some real data settings could show why one might be interested in second order stationarity.", "limitations": "- While an interesting and complete work, I am left unsure of what is new in this work, or if this is just applying already developed techniques to a new setting (finding a second-order stationary point) -- i.e., just combining the results of DKP20 and Aut23.\n- No experiments are given showing the practicality of the method, which could help to motivate the usefulness of finding SOSPs. \n- This is a limitation of the setting, but many more samples are needed than the information-theoretic threshold.\n- It is not clear why it is useful to find second-order stationary points in general.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This work yields the strongest guarantees of finding a second-order stationary point in this setting.\n- This is the first work to use both robust mean and robust Hessian approximation to solve the second-order approximation problem.\n- The work provides a statistical query lower bounds for rank one matrix sensing that shows that exponentially many queries would be needed to go beyond the $O(d^2)$ bound.", "weaknesses": "- One of the assumptions - that the iterates of the algorithms stay in a bounded region $\\mathcal B$, is hard to check or guarantee in general.\n- The work is a combination of two past works: the robust mean estimation algorithm of DKP20 and an anonymous work Aut23. It is not clear what new theoretical techniques are employed, or if this work is just a combination of the previous.\n- The statistical query result also follows the theorems in past works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "For Weaknesses, we responded to the restrictiveness of the bounded region assumption in the global response. We provided details of our novel theoretical techniques in Section 1.2, starting Line 152. Our main conceptual contribution is to propose a unified framework for designing provably robust learning algorithms by robustly finding second-order stationary points (SOSPs), which is important because for many nonconvex problems, first-order stationarity is not sufficient but second-order stationarity implies global optimality. We then showcase our framework by applying it to solve robust matrix sensing in the strong contamination model with dimension-independent error, even achieving exact recovery when the measurements are noiseless. On a technical level, showing that all iterates stay inside the region using the dissipativity condition is a useful demonstration and technically challenging.\n\nOn the lower bound side, although the generic techniques for our SQ lower bound construction exist in the literature, it is highly non-trivial to establish the moment-matching construction required to prove our lower bound. Moreover, it is by no means clear that such a lower bound should hold — there exist efficient algorithms that can estimate the largest eigenvalue (and an associated eigenvector) of a real symmetric positive semidefinite matrix with a sample size proportional to the dimension $d$, and one might think estimating the smallest eigenvector of a symmetric matrix is equally simple. Our SQ lower bound rules out this possibility, because otherwise both gradient directions and negative curvature directions can be estimated with $O(d)$ samples, contradicting the lower bound.\n\nFor Questions, Lines 36–57 in Section 1 discussed why we need approximate second-order stationary points. In summary, for a number of nonconvex problems, second-order stationarity implies global optimality, while first-order stationarity is known to be lacking [CG18]. In particular, this statement holds for low-rank matrix sensing problems.\n\nFor Limitations about the large sample size, while there may be a gap between the sample size required by our algorithm and the information-theoretic lower bound of the outlier robust low-rank matrix sensing problem, we provided an SQ lower bound that justifies such a gap and shows that our dependence on the matrix dimension $d$ is tight.\n"}, {"review_id": "Ii3XsNyhE6", "reviewer": "Reviewer_d53A", "summary": "The authors focus on the problem to find approximate second-order stationary points (SOSPs) in the strong contamination model, where they propose an efficient algorithm with an approximate SOSP as an output. The algorithm is proved to have dimension-independent accuracy guarantees. In particular, the proposed algorithm can solve the low rank matrix sensing problem robustly. They first introduce the formulation of generic nonconvex optimization problem and the low rank matrix sensing and the assumptions for the main theorem where the outputs of the algorithm for the corrupted Stochastic optimization problem can achieve approximate SOSP with high probability. For general cases, the algorithm can obtain approximate SOSPs under strong contamination. At last the authors provide the theoretical guarantees for robust low rank matrix sensing problem.\n", "questions": "See weakness.", "limitations": "I have not found the part explicit addressing the limitations of the algorithm. Maybe authors can elaborate more on these.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and clear, the approach is well supported by the theoretical analysis. The application on robust low rank matrix sensing problem seems strong and nice. ", "weaknesses": "- It might be good to include some simulations or real data applications on the robust low rank matrix sensing problem to address its computational efficiency. Or maybe some comparisons to first order method such as  projected gradient descent for robust stochastic optimization problem will be better.\n\n- The authors present theorem showing the results for general robust nonconvex optimization, like Theorem 1.5 and Theorem 3.1. As the authors say below Theorem 1.5, the assumptions appear restrictive and are satisfied for the matrix sensing. My question is whether the general results can hold for other nonconvex optimization problems such as matrix completion, phase retrieval, etc. Or what assumptions might be violated in these cases?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "About Weakness 1: We addressed simulations and experiments in the global response. To the best of our knowledge, the only first-order method that can robustly find approximate second-order stationary points is [Yin+19]; note that projected gradient descent can only find approximate first-order stationary points, which are not sufficient for a number of nonconvex optimization problems (see Lines 36–57 in Section 1 for the detailed reason). However, the error guarantee in [Yin+19] scales with the dimension, which is very unfavorable and usually uninformative for high-dimensional problems.\n\nAbout Weakness 2: We addressed why the assumption that the iterates stay in a bounded region $\\mathcal{B}$ is fairly general in the global response. For example, none of the mentioned nonconvex optimization problems violate those assumptions of Theorem 1.5. Regarding extensions to other nonconvex problems:\n- For matrix completion, see the global response as to why it may not be interesting in the strong contamination model.\n- For phase retrieval, our techniques should apply and this is an exciting avenue for future work.\n\nAbout Limitations: As a theory submission to NeurIPS, we stated all assumptions in a precise way. Our algorithms will succeed under those assumptions. As the “Limitations” section is not compulsory in NeurIPS 2023, we did not go into depth to discuss them because all our assumptions are fairly standard.\n"}]

Author rebuttal:
We thank the reviewers for their careful consideration of our work and the positive feedback. Below we address some common concerns raised by the reviewers. We hope that the provided clarifications will help clear possible misunderstandings and elevate the reviewer’s assessment of our contributions. 

**On the restrictiveness of the assumption that all iterates stay inside a bounded region $\mathcal{B}$ in Theorem 1.5**: As demonstrated in our low-rank matrix sensing example, this assumption is easy to satisfy if the objective function satisfies a dissipativity condition. The dissipativity condition says that the gradient aligns with the iterate when its norm exceeds some threshold; this threshold determines the radius of $\mathcal{B}$, which is allowed to depend polynomially on the dimension (see Line 97). Dissipativity is a fairly general phenomenon [Hal10]. See also [RRT17, Section 4] for a discussion of how adding a $\ell_2$-regularization term enables a Lipschitz function to satisfy the dissipativity condition. 

[RRT17] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. "Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis." In Conference on Learning Theory, pp. 1674-1703. PMLR, 2017. 

**On the choice of rank r = 1 in the construction of SQ lower bound**: The case where the rank $r = 1$ is in fact the easiest parameter regime, hence leading to a stronger lower bound. Recall that the sample complexity of our algorithm is $\widetilde O(d^2 r^2)$ as in Theorems 3.2 and 3.3, and the main point of our SQ lower bound shows that the $d^2$ factor is necessary *even if* $r = 1$.

**On the sample size in Theorems 1.7 and 3.3**: The error rate under the strong contamination model (Definition 1.1) usually takes the form of $\widetilde O(f(\epsilon) + g(d/n))$, where $f$ and $g$ are some nondecreasing functions, $n$ is the number of samples, and $d$ is the dimension of the samples. Even with infinite samples, the contribution of the error rate from $\widetilde O(f(\epsilon))$ does not go to 0. For example, any robust estimator for the mean of a $d$-dimensional identity covariance Gaussian must incur $\ell_2$-error $\Omega{\epsilon}$ in the strong contamination model [DK23, Chapter 1.2]. We choose the sample size $n$ so that the contribution from $\widetilde O(g(d/n))$ is comparable to $\widetilde O(f(\epsilon)$, as is the standard practice in algorithmic robust statistics. For the robust mean estimation subroutine used in our paper, Proposition 1.5 in [DKP20] showed that $\epsilon$-corruption of $d$-dimensional samples from a distribution with covariance bounded by  $\sigma^2 Identity$ gives error rate of $\widetilde O(\sqrt{d\sigma/n} + \sqrt{\sigma \epsilon})$. Matching the contribution from the first term with the second term gives the sample size $n = \widetilde O(d / \epsilon)$. 

**On the robust matrix completion problem**: The general robust nonconvex optimization framework and the techniques developed in this paper extend to the robust matrix completion problem (where both values and locations of a fraction of observed entries are corrupted). However, under our problem setup and with our current results, matrix completion where the target matrix has a total of $d^2$ entries requires a sample size bound of $O(d^2)$ (which is potentially optimal if our lower bound for matrix sensing extends to matrix completion). This does not seem to be a particularly interesting result, because this sample complexity allows the algorithm to inspect all entries multiple times. For some other contamination models (different from Definition 1.1), only $\widetilde O(d \operatorname{poly}(r))$ samples are needed (see, e.g., [CG18] and [CGJ17]). Those would be more reasonable sample sizes but their settings are drastically different from ours. 

[CGJ17] Yeshwanth Cherapanamjeri, Kartik Gupta, and Prateek Jain. "Nearly optimal robust matrix completion." In International Conference on Machine Learning, pp. 797-805. PMLR, 2017.

**On lacking simulations and experiments**: Our work is a learning and optimization theory submission that is well within the scope of NeurIPS (based on the Call for Papers). The sample/computational efficiency and error guarantees of our methods are analyzed in a precise way. We believe that our technical results are theoretically interesting and request that our work be judged based on its merits. That said, we acknowledge that experimental evaluation is important and a fruitful direction for future work.


Meta-review: The reviewers generally find that the paper has good theoretical contributions on the problem of finding approximate second-order stationary points of outlier-robust stochastic optimization problems. However, they also point out the insufficiency of the numerical evaluation. When preparing the camera-ready version, please incorporate the reviewers' suggestions and address their comments carefully.
Decision: Accept (poster)