论文标题
提高对$ L_2 $稳定的随机学习算法的概括的信心
Boosting the Confidence of Generalization for $L_2$-Stable Randomized Learning Algorithms
论文作者
论文摘要
最近已经建立了近似稳定的学习算法的指数概括范围。但是，统一稳定性的概念是严格的，因为它是数据生成分布不变的。在稳定性的较弱和分布依赖的概念下，例如假设稳定性和$ L_2 $ - 稳定性，文献表明，在一般情况下，只有多项式概括范围是可能的。本文解决了这两个结果方案之间的长期张力，并在富有信心的经典框架内取得了进步。为此，我们首先建立了一个针对具有$ L_2 $稳定性的潜在随机学习算法约束的概括的概括误差，然后基于该算法，我们然后表明，正确设计的subbagagging过程会导致近乎密度的指数概括性概括性限制数据和算法的随机性。我们将这些通用结果进一步验证到随机梯度下降（SGD），以提高凸的高概率概括性范围，用于凸或非convex优化问题，而自然时间衰减的学习率与现有的假设稳定性或基于统一的稳定性结果相关。
Exponential generalization bounds with near-tight rates have recently been established for uniformly stable learning algorithms. The notion of uniform stability, however, is stringent in the sense that it is invariant to the data-generating distribution. Under the weaker and distribution dependent notions of stability such as hypothesis stability and $L_2$-stability, the literature suggests that only polynomial generalization bounds are possible in general cases. The present paper addresses this long standing tension between these two regimes of results and makes progress towards relaxing it inside a classic framework of confidence-boosting. To this end, we first establish an in-expectation first moment generalization error bound for potentially randomized learning algorithms with $L_2$-stability, based on which we then show that a properly designed subbagging process leads to near-tight exponential generalization bounds over the randomness of both data and algorithm. We further substantialize these generic results to stochastic gradient descent (SGD) to derive improved high-probability generalization bounds for convex or non-convex optimization problems with natural time decaying learning rates, which have not been possible to prove with the existing hypothesis stability or uniform stability based results.
