We provide efficient replicable algorithms for the problem of learning
large-margin halfspaces. Our results improve upon the algorithms provided by
Impagliazzo, Lei, Pitassi, and Sorrell [STOC, 2022]. We design the first
dimension-independent replicable algorithms for this task which runs in
polynomial time, is proper, and has strictly improved sample complexity
compared to the one achieved by Impagliazzo et al. [2022] with respect to all
the relevant parameters. Moreover, our first algorithm has sample complexity
that is optimal with respect to the accuracy parameter $\epsilon$. We also
design an SGD-based replicable algorithm that, in some parameters' regimes,
achieves better sample and time complexity than our first algorithm.
Departing from the requirement of polynomial time algorithms, using the
DP-to-Replicability reduction of Bun, Gaboardi, Hopkins, Impagliazzo, Lei,
Pitassi, Sorrell, and Sivakumar [STOC, 2023], we show how to obtain a
replicable algorithm for large-margin halfspaces with improved sample
complexity with respect to the margin parameter $\tau$, but running time doubly
exponential in $1/\tau^2$ and worse sample complexity dependence on $\epsilon$
than one of our previous algorithms. We then design an improved algorithm with
better sample complexity than all three of our previous algorithms and running
time exponential in $1/\tau^{2}$.

我们提供了学习大间隔半空间问题的高效可复制算法，改进了 Impagliazzo 等人提供的算法。我们首次设计了这个任务的无维度依赖的可复制算法，其在多项式时间内运行，是合适的，并且在所有相关参数方面与 Impagliazzo 等人取得的结果相比，样本复杂度有明显提高。此外，我们的第一个算法在精度参数 ε 上具有最优的样本复杂度。我们还设计了一种基于 SGD 的可复制算法，在某些参数区间内，比我们第一个算法具有更好的样本和时间复杂度。最后，我们设计了一种改进的算法，其在样本复杂度上优于我们以前的三种算法，并且运行时间呈指数关系于 1/τ^2。

可复制的学习大边界半空间

Replicable Learning of Large-Margin Halfspaces

Robust mean estimation is the problem of estimating the mean $\mu \in
\mathbb{R}^d$ of a $d$-dimensional distribution $D$ from a list of independent
samples, an $\epsilon$-fraction of which have been arbitrarily corrupted by a
malicious adversary. Recent algorithmic progress has resulted in the first
polynomial-time algorithms which achieve \emph{dimension-independent} rates of
error: for instance, if $D$ has covariance $I$, in polynomial-time one may find
$\hat{\mu}$ with $\|\mu - \hat{\mu}\| \leq O(\sqrt{\epsilon})$. However, error
rates achieved by current polynomial-time algorithms, while
dimension-independent, are sub-optimal in many natural settings, such as when
$D$ is sub-Gaussian, or has bounded $4$-th moments.
In this work we give worst-case complexity-theoretic evidence that improving
on the error rates of current polynomial-time algorithms for robust mean
estimation may be computationally intractable in natural settings. We show that
several natural approaches to improving error rates of current polynomial-time
robust mean estimation algorithms would imply efficient algorithms for the
small-set expansion problem, refuting Raghavendra and Steurer's small-set
expansion hypothesis (so long as $P \neq NP$). We also give the first direct
reduction to the robust mean estimation problem, starting from a plausible but
nonstandard variant of the small-set expansion problem.

该论文阐述了在自然情况下改善多项式算法稳健均值估计误差率在计算上可能是不可行的，并探索了改善现有算法的错误率的自然方法，并证明了这将意味着小集合扩展问题的有效算法。

鲁棒均值估计有多难？

How Hard Is Robust Mean Estimation?

We derive exponential bounds on probabilities of large deviations for "light
tail" martingales taking values in finite-dimensional normed spaces. Our
primary emphasis is on the case where the bounds are dimension-independent or
nearly so. We demonstrate that this is the case when the norm on the space can
be approximated, within an absolute constant factor, by a norm which is
differentiable on the unit sphere with a Lipschitz continuous gradient. We also
present various examples of spaces possessing the latter property.

本文研究在有限维度的规范空间中，取值为 “轻尾” 鞅的大偏差概率的指数界，其中主要关注的是界与维度无关或接近无关的情况；论文还演示了当空间中的范数可被具有 Lipschitz 连续梯度的单位球上可微的范数以绝对常数因子逼近时，上述情况得以实现，并给出了几个具有该性质的空间的例子。