The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondr\'{a}k, 2018, 2019), (Bousquet, Klochkov, Zhivotovskiy, 2020) contain a generally inevitable sampling error term of order $\Theta(1/\sqrt{n})$. When applied to excess risk bounds, this leads to suboptimal results in several standard stochastic convex optimization problems. We show that if the so-called Bernstein condition is satisfied, the term $\Theta(1/\sqrt{n})$ can be avoided, and high probability excess risk bounds of order up to $O(1/n)$ are possible via uniform stability. Using this result, we show a high probability excess risk bound with the rate $O(\log n/n)$ for strongly convex and Lipschitz losses valid for \emph{any} empirical risk minimization method. This resolves a question of Shalev-Shwartz, Shamir, Srebro, and Sridharan (2009). We discuss how $O(\log n/n)$ high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.

研究证明，通过满足所谓的Bernstein条件，可以避免高概率广义化界限中的采样误差项，从而实现高概率过量风险边界，我们进而讨论了一些强凸和Lipschitz损失的方法。我们展示了任何经验风险最小化方法的$O(log n/n)$高概率过量风险边界，从而解决了Shalev-Shwartz，Shamir，Srebro和Sridharan（2009）的问题。

稳定性和偏差优化风险界的收敛速度为$O(1/n)$