- 去中心化随机极小极大优化算法是否能以线性收敛于有限和的非凸非凹问题?
本文针对分布式算法模型中面临的发散问题,提出了两种基于随机梯度下降的算法,并证明了其具有良好的收敛性能,这是首个针对分布式情况下的凸 - 非凸问题的线性收敛性的成果。
- 自然策略梯度法在对数线性策略参数化下的线性收敛
研究自然政策梯度算法在无限时间段折扣马尔可夫决策过程中的收敛速度,其中 Q-value 函数能够被已知特征函数的线性组合近似到偏差误差内,且算法具有相同的线性收敛保证,依赖于估计误差、偏差误差和特征协方差矩阵的条件数。
- 具有双线性耦合的平滑凸凹鞍点问题的加速原始 - 对偶梯度方法
本文提出了一种加速原始 - 对偶梯度方法 (APDG) 来解决凸 - 凹鞍点问题,该方法在强凸 - 强凹区间内实现了最佳线性收敛速率,匹配了复杂度下限,并在仅其中一个函数是强凸的情况下实现了加速线性收敛率,最终我们获得了一种针对一般凸 - - BROADCAST: 减少随机噪声和压缩噪声以增强通信效率的联邦学习
本文探讨了在大规模联邦学习中由于通信过载而引起的压缩问题,提出了一种可减少噪声并提高拜占庭攻击鲁棒性的压缩梯度差分方法,并提供了理论证明和数值实验结果。
- 自适应随机梯度下降的线性收敛
本文证明了自适应随机梯度方法的规范版本(AdaGrad-Norm)在强凸函数或满足 Polyak Lojasiewicz 不等式的非凸函数的子集中,达到的收敛速度是线性的。文中引入了梯度的限制均衡不等式(RUIG)的概念,用来描述函数的景观 - NIPS一种基于 Frank-Wolfe 的迹范数球线性收敛算法
本研究通过使用秩 -$k$ 变体的 Frank-Wolfe 算法对迹范数球上的凸优化问题进行求解,其将 Frank-Wolfe 中的 $1$-SVD 替换为 $top-k$ SVD 算法。实验表明,当目标函数是平滑的并且强凸的,且最优解的秩 - 分布式 SAGA:有限通信维持线性收敛速率
本研究提出了一种用于 SAGA 的分布式方案,该方案可以在节点间通信受限的情况下仍保持线性收敛速度,从而解决了大型数据集和集群推广时快速分布方法的需求。
- 用于非凸优化的随机递归梯度算法
本文研究分析了随机递归梯度算法 (StochAstic Recursive grAdient algoritHm, SARAH) 的 mini-batch 版本,用于解决非凸损失函数的经验损失最小化问题。我们提出了一种子线性收敛率 (对于一 - AAAI使用坐标轴下降算法训练带 L1 正则项的模型
本文提出了基于维度的被动下降算法(OPDA),它使用了随机变量减少梯度 (SVRG) 来初始化下降方向,并应用了一种新的对齐操作来促进每个元素在更新后保持相同的符号,从而参数保持在之前的正半轴。它还明确抑制了每个元素的大小,以强加稀疏性,演 - SARAH:一种使用随机递归梯度的机器学习问题新方法
本文提出了一种名为 SARAH 的随机递归梯度算法及其改进版 SARAH +,以优化有限累加和问题,并证明了该算法在强凸情况下具有线性收敛速率。
- 梯度和近端梯度法在 Polyak-Łojasiewicz 条件下的线性收敛
介绍了一种不需要强凸性条件的梯度下降算法,并针对机器学习中的各种问题提供了新的分析方法和收敛证明。
- 结构多面体的线性内存和分解不变线性收敛条件梯度算法
提出了一种改进的条件梯度方法来解决约束凸优化问题,针对多面体进行了相应的分析及优化,降低了每次迭代时的计算及内存开销,并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。
- 关于广义近端点算法的最优线性收敛速率
研究了泛化的 “Proximal Point Algorithm(PPA)” 在寻找 “Maximal Monotone Operator” 的零点上的线性收敛率问题,并证明 Rockafellar 提出的条件足以确保这种泛化的 PPA 的 - 随机梯度下降中方差与复杂度的权衡
CheapSVRG is proposed as a new stochastic variance-reduction optimization scheme which achieves a linear convergence rat - 一种线性收敛的随机 L-BFGS 算法
提出了一种新的随机 L-BFGS 算法,并证明了它对于强凸平滑函数具有线性收敛率。这种算法对于大规模的凸和非凸优化问题表现出色,具有快速求解高精度的线性收敛率,对于多种步幅表现良好。
- 线性反问题的尖锐时间 -- 数据折衷
本文论述了解决线性反问题的优化问题的尖锐时间 - 数据权衡,重点研究了一个最小化普通最小二乘目标的限制条件问题,我们提出了一个统一的收敛分析方法,针对各种随机测量阵列,依据所选择的惩罚函数所对应的结构复杂度,尖锐地表征了收敛速率。结果适用于 - 无对偶的 SDCA
本文介绍了一种 Stochastic Dual Coordinate Ascent 算法的变体,用于解决非凸损失函数的正则化损失最小化问题,并且证明了只要期望损失是凸的,就可以确保该算法具有线性收敛速度。
- 一种全局收敛的增量式牛顿法
本文提出了增量 Newton 方法和梯度增长条件,通过实例研究,发现增量 Newton 方法需要满足梯度增长条件才能达到线性收敛率,进而得到了分布式优化方法的线性收敛率结果。
- 无强凸性的方差缩减随机梯度线性收敛
本研究介绍了 Prox-SVRG 及其投影变体 VRPSG 算法,用于解决一类在机器学习中广泛使用的非强凸优化问题。通过 SSC 不等式的使用,本文证明了两种算法可以在无强凸性的情况下实现线性收敛率。
- 正交秩一矩阵追踪用于低秩矩阵补全
本文提出了一种高效和可扩展的低秩矩阵完成算法,使用正交匹配追踪方法将其从向量扩展到矩阵,并引入从推荐系统到电影 Lens 数据集的真实世界数据的新颖权重更新规则,表现出更好的预测性能。