In this paper, we provide tight deviation bounds for M-estimators, which are valid with a prescribed probability for every sample size. M-estimators are ubiquitous in machine learning and statistical learning theory. They are used both for defining prediction strategies and for evaluating their precision. Our deviation bounds can be seen as a non-asymptotic version of the law of iterated logarithm. They are established under general assumptions such as Lipschitz continuity of the loss function and (local) curvature of the population risk. These conditions are satisfied for most examples used in machine learning, including those that are known to be robust to outliers and to heavy tailed distributions. To further highlight the scope of applicability of the obtained results, a new algorithm, with provably optimal theoretical guarantees, for the best arm identification in a stochastic multi-arm bandit setting is presented. Numerical experiments illustrating the validity of the algorithm are reported.
翻译:在本文中,我们为测算器提供了严格的偏差界限,这些界限对每个样本大小都有一定的概率。 测算器在机器学习和统计学习理论中是无处不在的。 它们被用于界定预测战略和评估其精确度。 我们的偏差界限可以被视为迭代对数法的非非非无损版。 它们是根据Lipschitz损失功能连续性和(当地)人口风险曲线等一般假设建立的。 机器学习中所使用的大多数例子都符合这些条件, 包括那些已知对异端和重尾部分布十分强大的例子。 为了进一步突出所获得的结果的可适用性范围, 提出了一种新的算法, 并有可行的最佳理论保证, 以便在一个随机多臂强力的波段环境中进行最佳的手臂识别。 报告了说明算法有效性的数值实验。