论文标题
统计学习理论中的最佳问题依赖性概括误差界限
Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
论文作者
论文摘要
我们研究了问题依赖性率，即，在“最佳假设”中评估的方差，有效损失或梯度规范的范围近距离规模。我们引入了一个称为“统一局部收敛”的原则性框架，并描述了中央统计学习问题的尖锐问题依赖性率。从方法论角度来看，我们的框架解决了现有统一收敛和本地化分析方法的几个基本局限性。它还在研究局部复杂性，单侧均匀不平等和基于样本的迭代算法的研究中提供了改进和一定程度的统一。在所谓的“缓慢速率”制度中，我们提供了第一个（矩量化的）估计器，该估计器可实现一般“富”类别的最佳方差依赖性速率；我们还建立了提高的标准经验风险最小化损失依赖性率。在“快速率”制度中，我们建立了有限的问题依赖性界限，与精确的渐近学相媲美。此外，我们表明，诸如梯度下降和一阶期望最大化之类的迭代算法可以在非convex学习，随机优化和学习缺失数据的各个领域的几个代表性问题中实现最佳的泛化误差。
We study problem-dependent rates, i.e., generalization errors that scale near-optimally with the variance, the effective loss, or the gradient norms evaluated at the "best hypothesis." We introduce a principled framework dubbed "uniform localized convergence," and characterize sharp problem-dependent rates for central statistical learning problems. From a methodological viewpoint, our framework resolves several fundamental limitations of existing uniform convergence and localization analysis approaches. It also provides improvements and some level of unification in the study of localized complexities, one-sided uniform inequalities, and sample-based iterative algorithms. In the so-called "slow rate" regime, we provides the first (moment-penalized) estimator that achieves the optimal variance-dependent rate for general "rich" classes; we also establish improved loss-dependent rate for standard empirical risk minimization. In the "fast rate" regime, we establish finite-sample problem-dependent bounds that are comparable to precise asymptotics. In addition, we show that iterative algorithms like gradient descent and first-order Expectation-Maximization can achieve optimal generalization error in several representative problems across the areas of non-convex learning, stochastic optimization, and learning with missing data.
