We develop two methods for the following fundamental statistical task: given
an $\epsilon$-corrupted set of $n$ samples from a $d$-dimensional sub-Gaussian
distribution, return an approximate top eigenvector of the covariance matrix.
Our first robust PCA algorithm runs in polynomial time, returns a $1 -
O(\epsilon\log\epsilon^{-1})$-approximate top eigenvector, and is based on a
simple iterative filtering approach. Our second, which attains a slightly worse
approximation factor, runs in nearly-linear time and sample complexity under a
mild spectral gap assumption. These are the first polynomial-time algorithms
yielding non-trivial information about the covariance of a corrupted
sub-Gaussian distribution without requiring additional algebraic structure of
moments. As a key technical tool, we develop the first width-independent
solvers for Schatten-$p$ norm packing semidefinite programs, giving a $(1 +
\epsilon)$-approximate solution in
$O(p\log(\tfrac{nd}{\epsilon})\epsilon^{-1})$ input-sparsity time iterations
(where $n$, $d$ are problem dimensions).

研究开发了两种基于中心子高斯分布的降噪主成分分析算法，灵活应用于解决具有非代数结构矩的相关问题。同时定量地分析了算法的复杂性和置信度。

稳健的次高斯主成分分析与宽度独立的谱范数填充

Robust Sub-Gaussian Principal Component Analysis and Width-Independent  Schatten Packing

We use the Sum of Squares method to develop new efficient algorithms for
learning well-separated mixtures of Gaussians and robust mean estimation, both
in high dimensions, that substantially improve upon the statistical guarantees
achieved by previous efficient algorithms.
Firstly, we study mixtures of $k$ distributions in $d$ dimensions, where the
means of every pair of distributions are separated by at least
$k^{\varepsilon}$. In the special case of spherical Gaussian mixtures, we give
a $(dk)^{O(1/\varepsilon^2)}$-time algorithm that learns the means assuming
separation at least $k^{\varepsilon}$, for any $\varepsilon > 0$. This is the
first algorithm to improve on greedy ("single-linkage") and spectral
clustering, breaking a long-standing barrier for efficient algorithms at
separation $k^{1/4}$.
We also study robust estimation. When an unknown $(1-\varepsilon)$-fraction
of $X_1,\ldots,X_n$ are chosen from a sub-Gaussian distribution with mean $\mu$
but the remaining points are chosen adversarially, we give an algorithm
recovering $\mu$ to error $\varepsilon^{1-1/t}$ in time $d^{O(t^2)}$, so long
as sub-Gaussian-ness up to $O(t)$ moments can be certified by a Sum of Squares
proof. This is the first polynomial-time algorithm with guarantees approaching
the information-theoretic limit for non-Gaussian distributions. Previous
algorithms could not achieve error better than $\varepsilon^{1/2}$.
Both of these results are based on a unified technique. Inspired by recent
algorithms of Diakonikolas et al. in robust statistics, we devise an SDP based
on the Sum of Squares method for the following setting: given $X_1,\ldots,X_n
\in \mathbb{R}^d$ for large $d$ and $n = poly(d)$ with the promise that a
subset of $X_1,\ldots,X_n$ were sampled from a probability distribution with
bounded moments, recover some information about that distribution.

本文基于 Sum of Squares 方法，探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法，进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计，我们的方法多次突破优化算法的极限。

混合模型、鲁棒性和平方和证明

Mixture Models, Robustness, and Sum of Squares Proofs

We consider the problem of efficiently computing the maximum likelihood
estimator in Generalized Linear Models (GLMs) when the number of observations
is much larger than the number of coefficients ($n \gg p \gg 1$). In this
regime, optimization algorithms can immensely benefit from approximate second
order information. We propose an alternative way of constructing the curvature
information by formulating it as an estimation problem and applying a
Stein-type lemma, which allows further improvements through sub-sampling and
eigenvalue thresholding. Our algorithm enjoys fast convergence rates,
resembling that of second order methods, with modest per-iteration cost. We
provide its convergence analysis for the general case where the rows of the
design matrix are samples from a sub-gaussian distribution. We show that the
convergence has two phases, a quadratic phase followed by a linear phase.
Finally, we empirically demonstrate that our algorithm achieves the highest
performance compared to various algorithms on several datasets.

该论文提出了一种利用估计问题和 Stein 引理来构造曲率信息的算法，同时探讨了这种算法在广义线性模型中的应用和收敛性分析。实验证明，该算法在多个数据集上的表现都优于其他算法。

Newton-Stein 方法：通过 Stein 引理优化广义线性模型的方法

Newton-Stein Method: An optimization method for GLMs via Stein's Lemma

In one-bit compressed sensing, previous results state that sparse signals may
be robustly recovered when the measurements are taken using Gaussian random
vectors. In contrast to standard compressed sensing, these results are not
extendable to natural non-Gaussian distributions without further assumptions,
as can be demonstrated by simple counter-examples. We show that approximately
sparse signals that are not extremely sparse can be accurately reconstructed
from single-bit measurements sampled according to a sub-gaussian distribution,
and the reconstruction comes as the solution to a convex program.

本研究通过使用次高斯分布的单比特测量，结合凸程序解决方案，可以精确地重建几乎稀疏的信号。