本文研究机器学习中的经验风险最小化方法在核支持向量机、核岭回归和神经网络训练等问题上的计算复杂性,并基于复杂理论假设如强指数时间假设,证明了这些问题的条件难度结果。同时,对于许多非凸学习任务中的主要计算负担 —— 经验损失的梯度计算,也给出了类似的难度结果。
Apr, 2017
本文提出了一种通过求解对偶问题的分布式经验风险最小化训练框架,可以用于各种机器学习问题,具有全局线性收敛和更快的实证性能。
Sep, 2017
为了解决联邦学习框架下传统 ERM 问题所面临的隐私保障、低带宽、动态客户端等挑战,我们开发了最优通信 - efficient 私密方案,可以使客户端参与到 ERM 的优化中,同时保证通信和隐私效果,并利用数据和客户端抽样实现隐私扩大,验证了我们的解决方案既能够获得相同的隐私、优化 - 性能操作点,又能大幅降低通信成本。
Aug, 2020
研究网络数据在机器学习中的应用,通过一种通用的风险边界得到一个优化问题,使用带权重的 ERM 可以求解这个优化问题,再通过一种新的全多项式时间近似方案来在非凸情况下解决这个问题。
Nov, 2017
本文研究不同设置下差分隐私经验风险最小化问题,提出了比以前更少的梯度复杂度的算法,并从凸损失函数推广到满足 Polyak-Lojasiewicz 条件的非凸函数,给出比传统算法更紧的上界。
Feb, 2018
本文介绍了隐私保护数据集下 Empirical Risk Minimization(ERM)的改进算法 —— 不同 ially private ERM Algorithm。该算法通过利用限制条件的几何特性,在 Lipschitz、强凸和光滑函数等情况下,提供了更严格的误差上界,并针对稀疏线性回归(LASSO)提出了新的下界。
Nov, 2014
本文首次表征凸形 ERM 在高维广义线性模型推断中的基本统计精度界限,推导出任意损失函数和正则化参数值的紧凑下界,并精确评价了损失函数和正则化参数值的优化调整。
Jun, 2020
本研究提出了一个隐私保护的机器学习算法,基于差分隐私定义,首先将 Dwork 等人的输出扰动思想应用于 ERM 分类,然后通过扰动目标函数来设计一个新的 objective perturbation 方法,对于满足某些凸性和可微性条件的损失函数和正则化方法,我们证明了我们的算法可以保护隐私,并提供线性和非线性核的泛化界,同时我们提供了一种隐私保护的技术来调整通用机器学习算法的参数,从而为训练过程提供了端到端的隐私保证。实验结果表明,与输出扰动方法相比,我们的 objective perturbation 方法在处理隐私保护和学习性能间的固有权衡方面更加卓越。
Dec, 2009
经验风险最小化算法(ERM)在已知数据集且平滑的情况下,能够实现次线性误差,并且具有统计复杂性的概念。
Feb, 2024
本文提出了一种流式算法,可以在一次样本遍历中,线性时间内实现并且使用的空间仅为每个样本大小的线性。算法能够在每个问题上达到与 $ERM$ 相同的统计收敛速率,甚至考虑常数因素,而且算法性能随初始误差下降的超多项式速率,算法易于并行。此外,本文量化了算法与 $ERM$ 竞争的(有限样本)速度。
Dec, 2014