We revisit the well-studied problem of learning a linear combination of $k$
ReLU activations given labeled examples drawn from the standard $d$-dimensional
Gaussian measure. Chen et al. [CDG+23] recently gave the first algorithm for
this problem to run in $\text{poly}(d,1/\varepsilon)$ time when $k = O(1)$,
where $\varepsilon$ is the target error. More precisely, their algorithm runs
in time $(d/\varepsilon)^{\mathrm{quasipoly}(k)}$ and learns over multiple
stages. Here we show that a much simpler one-stage version of their algorithm
suffices, and moreover its runtime is only $(d/\varepsilon)^{O(k^2)}$.

我们研究了学习从标准的 d 维高斯度量中绘制的带有标签的示例的 k 个 ReLU 激活的线性组合的问题。我们发现了一个简化的一阶段版本的算法，其运行时间只有 (d/ε)^O (k^2)。

学习浅层网络的更快更简单算法

A faster and simpler algorithm for learning shallow networks

We study sampling as optimization in the space of measures. We focus on
gradient flow-based optimization with the Langevin dynamics as a case study. We
investigate the source of the bias of the unadjusted Langevin algorithm (ULA)
in discrete time, and consider how to remove or reduce the bias. We point out
the difficulty is that the heat flow is exactly solvable, but neither its
forward nor backward method is implementable in general, except for Gaussian
data. We propose the symmetrized Langevin algorithm (SLA), which should have a
smaller bias than ULA, at the price of implementing a proximal gradient step in
space. We show SLA is in fact consistent for Gaussian target measure, whereas
ULA is not. We also illustrate various algorithms explicitly for Gaussian
target measure, including gradient descent, proximal gradient, and
Forward-Backward, and show they are all consistent.

该研究以 Langevin 动力学为例，探究基于梯度流的优化过程中的采样问题，提出了一种降低偏差的新算法 SLA，并证明了在高斯目标测度下它具有一致性。

在测度空间中的优化抽样：Langevin 动力学作为一个复合优化问题

Sampling as optimization in the space of measures: The Langevin dynamics  as a composite optimization problem

We present randomized algorithms for sampling the standard Gaussian
distribution restricted to a convex set and for estimating the Gaussian measure
of a convex set, in the general membership oracle model. The complexity of
integration is $O^*(n^3)$ while the complexity of sampling is $O^*(n^3)$ for
the first sample and $O^*(n^2)$ for every subsequent sample. These bounds
improve on the corresponding state-of-the-art by a factor of $n$. Our
improvement comes from several aspects: better isoperimetry, smoother
annealing, avoiding transformation to isotropic position and the use of the
"speedy walk" in the analysis.

本研究提出了应用于凸集内标准高斯分布抽样及高斯度量估计的随机算法，并证明它们在一般性成员查询模型下的可行性，其采样的时间复杂度为每个样本均摊 $O^*(n^2)$，比现有最先进算法快 $n$ 倍。在等周问题、平滑退火、避免变换到各向同性和快速随机行走等方面实现了改进。