正则化经验风险最小化的分布式块对角逼近方法
提出了一种使用二阶信息进行通信和计算效率高的分布式优化算法来解决具有非平滑正则化项的 ERM 问题。该算法使用逐步二次逼近法,并描述了如何在分布式方式下有效地维护 Hessian 的逼近并解决子问题。该方法适用于广泛的非强凸问题,具有全局线性收敛性,需要更低的通信复杂度。同时,该方法可以收敛于非凸问题,因此具有在深度学习等应用中使用的潜力。初步的计算结果表明,该方法在凸问题上显著提高了通信成本和运行时间,超越了现有技术的方法。
Mar, 2018
本文提出了一种新的随机算法,通过将强凸函数的最小化转化为函数规则化的逼近最小化,从而优化了经验风险最小化过程中的性能,实践表明该算法具有稳定性和行之有效的优势
Jun, 2015
本文提出一种内点法(IPM),用于在联合学习设置下解决一般的经验风险最小化(ERM)问题,展示了每次迭代 IPM 的通信复杂度具有 O(d ^ {3/2})的上限。
May, 2023
本文首次表征凸形 ERM 在高维广义线性模型推断中的基本统计精度界限,推导出任意损失函数和正则化参数值的紧凑下界,并精确评价了损失函数和正则化参数值的优化调整。
Jun, 2020
本文研究机器学习中的经验风险最小化方法在核支持向量机、核岭回归和神经网络训练等问题上的计算复杂性,并基于复杂理论假设如强指数时间假设,证明了这些问题的条件难度结果。同时,对于许多非凸学习任务中的主要计算负担 —— 经验损失的梯度计算,也给出了类似的难度结果。
Apr, 2017
本文研究不同设置下差分隐私经验风险最小化问题,提出了比以前更少的梯度复杂度的算法,并从凸损失函数推广到满足 Polyak-Lojasiewicz 条件的非凸函数,给出比传统算法更紧的上界。
Feb, 2018
本文为凸经验风险最小化问题提供了一系列不同的差分隐私算法,并同时给出了相应的下界,且不同的隐私模型需要使用完全不同的算法,这些算法在多项式时间内运行,并且适用于很多简单光滑的函数家族。
May, 2014
本研究提出了一种双重随机算法,使用新的加速多动量技术来解决学习任务中的大规模经验风险最小化问题,各迭代只访问一小批样本和同时更新一小块变量坐标,从而在同时涉及海量样本大小和超高维度时显著减少了内存引用量,实证研究也说明了该方法在实践中的高效性。
Apr, 2023
本文提出异步 ProxSVRG 和异步 ProxSVRCD 算法,证明当训练数据为稀疏矩阵时,异步 ProxSVRG 可以达到近似线性加速,而异步 ProxSVRCD 无论稠密还是稀疏数据,只要区块数目适当,就可以实现近似线性加速。通过实验证实了异步随机近端算法与方差规约技术的实践效率。
Sep, 2016