We study the problem of high-dimensional robust mean estimation in the
presence of a constant fraction of adversarial outliers. A recent line of work
has provided sophisticated polynomial-time algorithms for this problem with
dimension-independent error guarantees for a range of natural distribution
families.
In this work, we show that a natural non-convex formulation of the problem
can be solved directly by gradient descent. Our approach leverages a novel
structural lemma, roughly showing that any approximate stationary point of our
non-convex objective gives a near-optimal solution to the underlying robust
estimation task. Our work establishes an intriguing connection between
algorithmic high-dimensional robust statistics and non-convex optimization,
which may have broader applications to other robust estimation tasks.

研究高维度的强健均值估计问题，在存在恒定比例的对抗性离群值的情况下，我们显示出这个问题的自然非凸公式可以直接通过梯度下降来解决。

通过梯度下降实现高维度鲁棒均值估计

High-Dimensional Robust Mean Estimation via Gradient Descent

We consider the non-square matrix sensing problem, under restricted isometry
property (RIP) assumptions. We focus on the non-convex formulation, where any
rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ is represented as $UV^\top$,
where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. In
this paper, we complement recent findings on the non-convex geometry of the
analogous PSD setting [5], and show that matrix factorization does not
introduce any spurious local minima, under RIP.

本文探讨了基于受限等距性质（RIP）假设的非方阵矩阵感知问题，并关注了非凸形式化的矩阵分解，证明了矩阵分解不会在 RIP 下引入任何虚假的局部最小值。

应用 Burer-Monteiro 方法消除虚假局部最小值的非方阵矩阵感知

Non-square matrix sensing without spurious local minima via the  Burer-Monteiro approach

We study the problem of recovering the phase from magnitude measurements;
specifically, we wish to reconstruct a complex-valued signal x of C^n about
which we have phaseless samples of the form y_r = |< a_r,x >|^2, r = 1,2,...,m
(knowledge of the phase of these samples would yield a linear system). This
paper develops a non-convex formulation of the phase retrieval problem as well
as a concrete solution algorithm. In a nutshell, this algorithm starts with a
careful initialization obtained by means of a spectral method, and then refines
this initial estimate by iteratively applying novel update rules, which have
low computational complexity, much like in a gradient descent scheme. The main
contribution is that this algorithm is shown to rigorously allow the exact
retrieval of phase information from a nearly minimal number of random
measurements. Indeed, the sequence of successive iterates provably converges to
the solution at a geometric rate so that the proposed scheme is efficient both
in terms of computational and data resources. In theory, a variation on this
scheme leads to a near-linear time algorithm for a physically realizable model
based on coded diffraction patterns. We illustrate the effectiveness of our
methods with various experiments on image data. Underlying our analysis are
insights for the analysis of non-convex optimization schemes that may have
implications for computational problems beyond phase retrieval.

本文提出一种非凸公式的相位恢复方法，通过随机数迭代更新的规则精确地重建了信号的相位信息。此算法具有低计算复杂性并在计算和数据资源方面都非常有效。

通过 Wirtinger Flow 进行相位恢复：理论和算法

Phase Retrieval via Wirtinger Flow: Theory and Algorithms

Multi-task sparse feature learning aims to improve the generalization
performance by exploiting the shared features among tasks. It has been
successfully applied to many applications including computer vision and
biomedical informatics. Most of the existing multi-task sparse feature learning
algorithms are formulated as a convex sparse regularization problem, which is
usually suboptimal, due to its looseness for approximating an $\ell_0$-type
regularizer. In this paper, we propose a non-convex formulation for multi-task
sparse feature learning based on a novel non-convex regularizer. To solve the
non-convex optimization problem, we propose a Multi-Stage Multi-Task Feature
Learning (MSMTFL) algorithm; we also provide intuitive interpretations,
detailed convergence and reproducibility analysis for the proposed algorithm.
Moreover, we present a detailed theoretical analysis showing that MSMTFL
achieves a better parameter estimation error bound than the convex formulation.
Empirical studies on both synthetic and real-world data sets demonstrate the
effectiveness of MSMTFL in comparison with the state of the art multi-task
sparse feature learning algorithms.

本文提出了一种基于新颖非凸正则化器的多任务稀疏特征学习的非凸公式，并提供了多阶段多任务特征学习算法的详细收敛和可重复性分析，理论分析指出该方法与现有凸公式相比较为优越，在合成和真实数据集上，实证研究表明 MSMTFL 比现有多任务稀疏特征学习算法更为有效。