利用平滑和强凸条件改善风险上界,建立了新的凸优化式 的有限样本错误分析方法。
Feb, 2017
我们分析了非光滑随机凸优化中全批量梯度下降(GD)的样本复杂性,表明 GD 的泛化误差与最优超参数选择的样本复杂性匹配,可以表示为 Θ(d/m + 1/√m),其中 d 为维度,m 为样本大小,这与最坏情况下的经验风险最小化器相符,这意味着与其他算法相比,GD 没有优势。我们的界限来自一个新的泛化界限,它取决于维度、学习速率和迭代次数。对于一般的超参数,当维度严格大于样本数量时,需要 Ω(1/ε^4) 次迭代才能避免过拟合,这解决了 schliserman2024dimension 和 amir2021sgd 提出的一个开放问题,并改进了先前的下界,前者证明了样本大小至少必须为维度的平方根。
Apr, 2024
本文研究了凸聚合问题,通过考虑经验风险最小化过程,证明了一种风险近似最小风险程序,在概率上具有误差较小的优点,同时给出了最优凸聚合率的详细定义。
Dec, 2013
经验风险最小化算法(ERM)在已知数据集且平滑的情况下,能够实现次线性误差,并且具有统计复杂性的概念。
Feb, 2024
本文首次表征凸形 ERM 在高维广义线性模型推断中的基本统计精度界限,推导出任意损失函数和正则化参数值的紧凑下界,并精确评价了损失函数和正则化参数值的优化调整。
Jun, 2020
本文研究高维度的鲁棒线性回归,包括离群值和使用标准损失函数的经验风险最小化(ERMs)方法。结果显示,在相似数据集上,经过最优正则化的 ERM 在大样本复杂性极限下是渐近一致的,但在评估误差方面,由于规范标定的失配,估计器的一致性要求完美计算最优规范的预估值或存在未受离群值污染的交叉验证集。不同的损失函数在最优性能的使用情况下提供了有关使用情况的见解。
May, 2023
本文研究不同设置下差分隐私经验风险最小化问题,提出了比以前更少的梯度复杂度的算法,并从凸损失函数推广到满足 Polyak-Lojasiewicz 条件的非凸函数,给出比传统算法更紧的上界。
Feb, 2018
关于随机设计回归模型的统计学习研究,我们提出了一种聚合经验最小值的方法,并建立了其风险的尖锐 Oracle 不等式,进一步证明了在良好规定的模型下,统计估计和在错误规定的模型下的统计后悔的速率等价的结论。
Aug, 2013
本文研究了在非交互式局部差分隐私(LDP)模型下经验风险最小化(ERM)问题,利用 Bernstein 多项式逼近方法和内积多项式逼近技术提出了两种解决高维数据下样本复杂度指数级上升的方法,最终提出了用于学习 k 维边际查询和平滑查询的(高效的)非交互式局部差分隐私算法。
Nov, 2020
本文介绍了隐私保护数据集下 Empirical Risk Minimization(ERM)的改进算法 —— 不同 ially private ERM Algorithm。该算法通过利用限制条件的几何特性,在 Lipschitz、强凸和光滑函数等情况下,提供了更严格的误差上界,并针对稀疏线性回归(LASSO)提出了新的下界。
Nov, 2014