非平滑随机镜像下降的一般性尾部界
本研究讨论了使用第一阶梯度算法进行的非凸随机优化问题,其中梯度估计可能具有重尾特征,结果表明梯度剪裁,动量和归一化梯度下降的组合可以在高概率下收敛于关键点,特别适用于光滑损失的已知最佳速率,适用于任意光滑度规范,并针对克服该领域二阶光滑损失引发的问题进行讨论。
Jun, 2021
我们针对具有结构密度的重尾噪声的随机优化问题展开研究,证明在随机梯度具有有限阶矩(α ∈ (1, 2])时,可以获得比 Ο(K^(-2 (α - 1)/α)) 更快的收敛速率,而且噪声范数可以有无界期望。为实现这些结果,我们使用平滑的中值均值稳定随机梯度,并证明了所得估计具有可忽略的偏差和可控的方差,从而可以将其谨慎地纳入剪辑随机梯度下降(clipped-SGD)和剪辑随机次梯度均值(clipped-SSTM),并推导出所考虑情况下的新的高概率复杂度界限。
Nov, 2023
本文针对线性预测器的迭代定点方法(特别是随机和批量镜像下降法及随机时间差分学习),提供了测试误差界限。主要贡献包括:通过单一证明技巧对收敛和非收敛状态下具有高概率保证的拟合损失进行统一处理,以无需投影、正则化或任何等效手段,适用于具有二次界限的损失(如平方和逻辑损失),并基于低范数预测器的特性提供局部自适应率。证明技巧采用基本且多功能的耦合论证法,在多种设置中进行了演示。
Feb, 2022
该论文研究了随机镜像下降法在非凸优化中的非渐近稳态收敛性,特别关注了一类非凸非光滑的随机优化问题,其中目标函数可以分解为一个相对弱凸函数(可能是非 Lipschitz)和简单的非光滑凸规则化函数。论文证明,SMD 算法在收敛速率为 $O(1/√t)$ 的同时,无需使用小批量就能保证收敛到一个稳定点。
Jun, 2018
本文提出了一种新的加速随机一阶方法 clipped-SSTM,该方法通过剪辑随机梯度结合特殊变体的随机梯度下降法,用于解决具有重尾分布噪声的光滑凸随机优化问题,并推导出了该方法的第一个高概率复杂度界限,证明了其优于同类方法。
May, 2020
我们使用 Talagrand 通用串联方法修改,为随机过程的所有 p 阶矩获得上界。我们将此过程应用于改进和扩展一些已知的偏差不等式,以便获得至上极限的上尾估计,同时具有最佳的偏差参数,其中包括未限制的经验过程和混沌过程的极限值。作为实践,我们提供了约束等距性质的明显简化证明,该质将离散傅立叶变换的子采样用于稀疏信号恢复。
Sep, 2013
本文介绍了使用离散随机递归关系模拟随机优化算法,说明由于局部收敛速度方差的增加,会导致多项式噪声,从而得到具有重尾结构的参数固定点,其优化具有更高的容量,以更好地探索非凸损失面。
Jun, 2020
我们研究了具有重尾梯度的差分隐私随机凸优化(DP-SCO)问题,在这里我们假设样本函数的 Lipschitz 常数具有 k 次矩界而不是统一界。我们提出了一种新的基于约束的方法,使我们能够在重尾设置中获得首个最优速率(达到对数因子),在(ε,δ)- 近似差分隐私下,实现误差 G2⋅1/√n+Gk⋅(√d/nε)^(1-1/k),几乎匹配于 [Lowy and Razaviyayn 2023] 的下界。在额外假设下,我们进一步给出了一套重尾设置的私有算法,包括在已知 Lipschitz 常数假设下的最优算法,平滑函数的近线性时间算法以及平滑广义线性模型的最优线性时间算法。
Jun, 2024
利用 Luxemburg 范数的估计,本文针对非必然独立的随机变量中的二次形式给出其尾部概率上限,并给出了在相关观测中固定设计的线性回归中的超额损失估计。
Sep, 2018
通过研究一类广泛的非线性随机梯度下降方法在高概率下的收敛界限,我们证明了对于具有 Lipschitz 连续梯度的强凸损失函数,即使在噪声具有重尾分布的情况下,也能实现失败概率的对数依赖性,这对于任何具有有界(逐分量或联合)输出的非线性性质(如剪切、归一化和量化)都是成立的,与以往对于具有重尾噪声的研究相比,我们的研究结果在噪声的矩阶限制上得以松弛。
Oct, 2023