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

Distributed adaptive stochastic gradient methods have been widely used for
large-scale nonconvex optimization, such as training deep learning models.
However, their communication complexity on finding $\varepsilon$-stationary
points has rarely been analyzed in the nonconvex setting. In this work, we
present a novel communication-efficient distributed Adam in the
parameter-server model for stochastic nonconvex optimization, dubbed {\em
Efficient-Adam}. Specifically, we incorporate a two-way quantization scheme
into Efficient-Adam to reduce the communication cost between the workers and
server. Simultaneously, we adopt a two-way error feedback strategy to reduce
the biases caused by the two-way quantization on both the server and workers,
respectively. In addition, we establish the iteration complexity for the
proposed Efficient-Adam with a class of quantization operators, and further
characterize its communication complexity between the server and workers when
an $\varepsilon$-stationary point is achieved. Finally, we apply Efficient-Adam
to solve a toy stochastic convex optimization problem and train deep learning
models on real-world vision and language tasks. Extensive experiments together
with a theoretical guarantee justify the merits of Efficient Adam.

本文提出了一种称为 Efficient-Adam 的新型通信高效的分布式优化算法，采用双向量化策略和双向误差反馈策略，在保证迭代收敛精度的同时有效减少了服务器与工作节点之间的通信成本，并应用于解决了一个随机凸优化问题，以及在实际视觉和语言任务中训练深度学习模型，同时进行了大量实验和理论分析以验证其优越性。

高效 Adam：具复杂度分析的通信高效分布式 Adam

Efficient-Adam: Communication-Efficient Distributed Adam with Complexity  Analysis

Principal component analysis (PCA) has been a prominent tool for
high-dimensional data analysis. Online algorithms that estimate the principal
component by processing streaming data are of tremendous practical and
theoretical interests. Despite its rich applications, theoretical convergence
analysis remains largely open. In this paper, we cast online PCA into a
stochastic nonconvex optimization problem, and we analyze the online PCA
algorithm as a stochastic approximation iteration. The stochastic approximation
iteration processes data points incrementally and maintains a running estimate
of the principal component. We prove for the first time a nearly optimal
finite-sample error bound for the online PCA algorithm. Under the subgaussian
assumption, we show that the finite-sample error bound closely matches the
minimax information lower bound.

本文将在线 PCA 转化为随机非凸优化问题，并将在线 PCA 算法分析为随机逼近迭代。在亚高斯假设下，我们证明了在线 PCA 算法的近乎最优有限样本误差界限，并且表明有限样本误差界限与极小信息下界紧密匹配。