Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing

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.

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. - 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?

Questions

See weakness.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I have not found the part explicit addressing the limitations of the algorithm. Maybe authors can elaborate more on these.

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.

Strengths

- This work yields the strongest guarantees of finding a second-order stationary point in this setting. - This is the first work to use both robust mean and robust Hessian approximation to solve the second-order approximation problem. - 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. - 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. - The statistical query result also follows the theorems in past works.

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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

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. - No experiments are given showing the practicality of the method, which could help to motivate the usefulness of finding SOSPs. - This is a limitation of the setting, but many more samples are needed than the information-theoretic threshold. - It is not clear why it is useful to find second-order stationary points in general.

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.

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.

Questions

(1) Line 48: "newdiscussed" is a typo. (2) Line 69: it would be better to (briefly) discuss the counterexample in the appendix. (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. (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? (5) Theorem 1.5: maybe the authors can briefly discuss the reason why the sample complexity is inversely proportional to the corruption rate \epsilon? (6) Line 148: it may be better to use D to denote the dimension. (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. (8) It seems that the statements on Lines 163 and 166 are the same. (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? (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. Li, 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. (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. (12) Line 231: "exists" (13) Theorem 3.5: It would be better to mention the condition \epsilon = O(1/k^2/r^2). (14) Line 320: "Theorem 3.1 applies" (15) Line 367: it would be better to explain why the results are more significant or important for the rank-1 case. (16) Line 378: it will be helpful if the authors can briefly explain how to generate the SQ oracle.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

See my comments in the previous section.

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.

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. 2. 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.

Questions

1. This paper considers symmetric case. What if the matrix $M^{\star}$ is asymmetric? 2. A closely related problem is matrix completion. Is it possible to extend the analysis to matrix completion? 3. 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This paper does not have potential negative social impact.