Median-of-means (MOM) based procedures provide non-asymptotic and strong
deviation bounds even when data are heavy-tailed and/or corrupted. This work
proposes a new general way to bound the excess risk for MOM estimators. The
core technique is the use of VC-dimension (instead of Rademacher complexity) to
measure the statistical complexity. In particular, this allows to give the
first robust estimators for sparse estimation which achieves the so-called
subgaussian rate only assuming a finite second moment for the uncorrupted data.
By comparison, previous works using Rademacher complexities required a number
of finite moments that grows logarithmically with the dimension. With this
technique, we derive new robust sugaussian bounds for mean estimation in any
norm. We also derive a new robust estimator for covariance estimation that is
the first to achieve subgaussian bounds without $L_4-L_2$ norm equivalence.

该文提出了一种使用 VC-dimension 的方法来测量统计复杂性的新型通用方法，从而使得 MOM 估计值的超额风险得到限制，其中应用该方法得出的鲁棒稀疏估计器实现了所谓的次高斯速率并且最多只需要假设非污染数据拥有有限的二阶矩。同时，该技术还可用于导出多种新的鲁棒次高斯边界，包括任何范数下的均值估计和协方差估计中的使用。

具有 VC 维的鲁棒次高斯估计

Robust subgaussian estimation with VC-dimension

We propose a simple subsampling scheme for fast randomized approximate
computation of optimal transport distances. This scheme operates on a random
subset of the full data and can use any exact algorithm as a black-box
back-end, including state-of-the-art solvers and entropically penalized
versions. It is based on averaging the exact distances between empirical
measures generated from independent samples from the original measures and can
easily be tuned towards higher accuracy or shorter computation times. To this
end, we give non-asymptotic deviation bounds for its accuracy in the case of
discrete optimal transport problems. In particular, we show that in many
important instances, including images (2D-histograms), the approximation error
is independent of the size of the full problem. We present numerical
experiments that demonstrate that a very good approximation in typical
applications can be obtained in a computation time that is several orders of
magnitude smaller than what is required for exact computation of the full
problem.

本文提出了一个基于离散最优输运问题的简单子抽样方案，用于快速随机近似计算最优输运距离。该方案针对完全数据的随机子集操作，可使用任何精确算法作为黑盒后端，包括最先进的求解器和熵惩罚版本。我们给出了其非渐进偏差范围，以针对更高的精度或更短的计算时间进行简化。实验证明，该子抽样方案可以在计算时间大大降低的情况下，获得比精确方法更好的近似效果。

最优传输：带精确求解器的快速概率逼近

Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

We present deviation bounds for self-normalized averages and applications to
estimation with a random number of observations. The results rely on a peeling
argument in exponential martingale techniques that represents an alternative to
the method of mixture. The motivating examples of bandit problems and context
tree estimation are detailed.

本文介绍了自标准化平均值的偏差界限及其在具有随机观测数量的估计中的应用。结果基于指数鞅技术中的削减证明，为混合方法的替代提供了一种新的方法，并详细说明了赌徒问题和上下文树估计的动机示例。