We focus on the task of learning a single index model $\sigma(w^\star \cdot
x)$ with respect to the isotropic Gaussian distribution in $d$ dimensions.
Prior work has shown that the sample complexity of learning $w^\star$ is
governed by the information exponent $k^\star$ of the link function $\sigma$,
which is defined as the index of the first nonzero Hermite coefficient of
$\sigma$. Ben Arous et al. (2021) showed that $n \gtrsim d^{k^\star-1}$ samples
suffice for learning $w^\star$ and that this is tight for online SGD. However,
the CSQ lower bound for gradient based methods only shows that $n \gtrsim
d^{k^\star/2}$ samples are necessary. In this work, we close the gap between
the upper and lower bounds by showing that online SGD on a smoothed loss learns
$w^\star$ with $n \gtrsim d^{k^\star/2}$ samples. We also draw connections to
statistical analyses of tensor PCA and to the implicit regularization effects
of minibatch SGD on empirical losses.

本文研究在高斯分布下学习单指标模型 σ(w⁎・x)，以及学习该模型时信息指数 k * 的影响，论文提出了利用平滑误差函数与在线随机梯度下降等方法，减少样本数对模型的学习。

平滑景观增强了 SGD 的信号：学习单指数模型的最优样本复杂度

Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample  Complexity for Learning Single Index Models

We analyze Local SGD (aka parallel or federated SGD) and Minibatch SGD in the
heterogeneous distributed setting, where each machine has access to stochastic
gradient estimates for a different, machine-specific, convex objective; the
goal is to optimize w.r.t. the average objective; and machines can only
communicate intermittently. We argue that, (i) Minibatch SGD (even without
acceleration) dominates all existing analysis of Local SGD in this setting,
(ii) accelerated Minibatch SGD is optimal when the heterogeneity is high, and
(iii) present the first upper bound for Local SGD that improves over Minibatch
SGD in a non-homogeneous regime.

本文研究异构分布共享的随机梯度下降优化问题，通过对比 Local SGD 和 Minibatch SGD，得到加速的 Minibatch SGD 是解决高异质性问题的最优方法，并提出了第一个比 Minibatch SGD 更好的 Local SGD 的上界解。