文献中随机梯度方法的绝大多数收敛速率分析集中在预期中的收敛性,而轨迹的几乎确定的收敛对于确保随机算法的任何实例化都会与概率相关。在这里,我们为随机梯度下降(SGD),随机重球(SHB)和随机Nesterov的加速梯度(SNAG)方法提供了几乎确定的收敛速率分析。我们首次显示,这些随机梯度方法在强凸功能上获得的几乎确定的收敛速率已任意接近其最佳收敛速率。对于非凸目标函数,我们不仅表明平方梯度规范的加权平均值几乎可以肯定地收敛到零,而且是算法的最后一次迭代。与文献中的大多数现有结果相反,我们进一步为弱凸平平滑功能的随机梯度方法提供了最后的几乎确定的收敛速率分析,而文献中的大多数现有结果仅提供了对迭代率的加权平均值的预期。
translated by 谷歌翻译
最近,随机梯度下降(SGD)及其变体已成为机器学习(ML)问题大规模优化的主要方法。已经提出了各种策略来调整步骤尺寸,从自适应步骤大小到启发式方法,以更改每次迭代中的步骤大小。此外,动力已被广泛用于ML任务以加速训练过程。然而,我们对它们的理论理解存在差距。在这项工作中,我们开始通过为一些启发式优化方法提供正式保证并提出改进的算法来缩小这一差距。首先,我们分析了凸面和非凸口设置的Adagrad(延迟Adagrad)步骤大小的广义版本,这表明这些步骤尺寸允许算法自动适应随机梯度的噪声水平。我们首次显示延迟Adagrad的足够条件,以确保梯度几乎融合到零。此外,我们对延迟的Adagrad及其在非凸面设置中的动量变体进行了高概率分析。其次,我们用指数级和余弦的步骤分析了SGD,在经验上取得了成功,但缺乏理论支持。我们在平滑和非凸的设置中为它们提供了最初的收敛保证,有或没有polyak-{\ l} ojasiewicz(pl)条件。我们还显示了它们在PL条件下适应噪声的良好特性。第三,我们研究动量方法的最后迭代。我们证明了SGD的最后一个迭代的凸设置中的第一个下限,并以恒定的动量。此外,我们研究了一类跟随基于领先的领导者的动量算法,并随着动量和收缩的更新而增加。我们表明,他们的最后一个迭代具有最佳的收敛性,用于无约束的凸随机优化问题。
translated by 谷歌翻译
我们研究了具有有限和结构的平滑非凸化优化问题的随机重新洗脱(RR)方法。虽然该方法在诸如神经网络的训练之类的实践中广泛利用,但其会聚行为仅在几个有限的环境中被理解。在本文中,在众所周知的Kurdyka-LojasiewiCz(KL)不等式下,我们建立了具有适当递减步长尺寸的RR的强极限点收敛结果,即,RR产生的整个迭代序列是会聚并会聚到单个静止点几乎肯定的感觉。 In addition, we derive the corresponding rate of convergence, depending on the KL exponent and the suitably selected diminishing step sizes.当KL指数在$ [0,\ FRAC12] $以$ [0,\ FRAC12] $时,收敛率以$ \ mathcal {o}(t ^ { - 1})$的速率计算,以$ t $ counting迭代号。当KL指数属于$(\ FRAC12,1)$时,我们的派生收敛速率是FORM $ \ MATHCAL {O}(T ^ { - Q})$,$ Q \ IN(0,1)$取决于在KL指数上。基于标准的KL不等式的收敛分析框架仅适用于具有某种阶段性的算法。我们对基于KL不等式的步长尺寸减少的非下降RR方法进行了新的收敛性分析,这概括了标准KL框架。我们总结了我们在非正式分析框架中的主要步骤和核心思想,这些框架是独立的兴趣。作为本框架的直接应用,我们还建立了类似的强极限点收敛结果,为重组的近端点法。
translated by 谷歌翻译
在这项工作中,我们提供了一种基本的统一收敛定理,用于得出一系列随机优化方法的预期和几乎确定的收敛结果。我们的统一定理仅需要验证几种代表性条件,并且不适合任何特定算法。作为直接应用,我们在更一般的设置下恢复了随机梯度方法(SGD)和随机改组(RR)的预期收敛结果。此外,我们为非滑动非convex优化问题的随机近端梯度方法(Prox-SGD)和基于随机模型的方法(SMM)建立了新的预期和几乎确定的收敛结果。这些应用程序表明,我们的统一定理为广泛的随机优化方法提供了插件类型的收敛分析和强大的收敛保证。
translated by 谷歌翻译
我们的目标是使随机梯度$ \ sigma^2 $在随机梯度和(ii)问题依赖性常数中自适应(i)自适应。当最大程度地减少条件编号$ \ kappa $的平滑,强大的功能时,我们证明,$ t $ t $ toerations sgd的$ t $ toerations sgd具有指数降低的阶跃尺寸和对平滑度的知识可以实现$ \ tilde {o} \ left(\ exp) \ left(\ frac {-t} {\ kappa} \ right) + \ frac {\ sigma^2} {t} \ right)$ rate,而又不知道$ \ sigma^2 $。为了适应平滑度,我们使用随机线路搜索(SLS)并显示(通过上下距离),其SGD的SGD与SLS以所需的速率收敛,但仅针对溶液的邻域。另一方面,我们证明具有平滑度的离线估计值的SGD会收敛到最小化器。但是,其速率与估计误差成正比的速度减慢。接下来,我们证明具有Nesterov加速度和指数步骤尺寸(称为ASGD)的SGD可以实现接近最佳的$ \ tilde {o} \ left(\ exp \ left(\ frac {-t} {-t} {\ sqrt {\ sqrt {\ sqrt { \ kappa}}} \ right) + \ frac {\ sigma^2} {t} \ right)$ rate,而无需$ \ sigma^2 $。当与平滑度和强频率的离线估计值一起使用时,ASGD仍会收敛到溶液,尽管速度较慢。我们从经验上证明了指数级尺寸的有效性以及新型SLS的变体。
translated by 谷歌翻译
具有动量(SGDM)的SGD是一种广泛使用的算法系列,用于大规模优化机器学习问题。但是,当优化通用凸功能时,任何SGDM算法都不知道与普通SGD相比。此外,即使最近的结果也需要更改SGDM算法,例如平均迭代元素和对有限域的投影,这些域很少在实践中使用。在本文中,我们关注SGDM最后一次迭代的收敛速率。我们第一次证明,对于任何恒定的动量因素,都存在Lipschitz和凸功能,SGDM的最后一次迭代均具有$ \ omega的次优收敛速率(\ frac {\ ln t} {\ ln t} {\ sqrt {\ sqrt { $ t $迭代后的t}})$。基于这一事实,我们研究了一类(自适应和非自适应)遵循基于调查的领导者的SGDM算法,并随着动量的增加和缩小的更新而进行。对于这些算法,我们表明,最后一个迭代具有最佳收敛$ O(\ frac {1} {\ sqrt {t}})$,用于无约束的凸随机优化问题,而没有投影到有限域的域也没有$ t $的知识。此外,当与自适应步骤一起使用时,我们显示了基于FTRL的SGDM的各种结果。也显示了经验结果。
translated by 谷歌翻译
We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.
translated by 谷歌翻译
在本文中,我们提出了一种称为ANITA的新型加速梯度方法,用于解决基本的有限和优化问题。具体而言,我们同时考虑一般凸面和强烈凸面设置:i)对于一般凸有限的和有限的问题,Anita改善了Varag给定的先前最新结果(Lan等,2019)。特别是,对于大规模问题或收敛错误不是很小,即$ n \ geq \ frac {1} {\ epsilon^2} $,Anita获得\ emph {first} optimal restion $ o(n )$,匹配Woodworth and Srebro(2016)提供的下限$ \ Omega(N)$,而先前的结果为$ O(N \ log \ frac {1} {\ epsilon})$ 。 ii)对于强烈凸有限的问题,我们还表明,Anita可以实现最佳收敛速率$ o \ big(((n+\ sqrt {\ frac {\ frac {nl} {\ mu}} {\ mu}})\ log \ log \ frac {1} {1} {1} {1} { \ epsilon} \ big)$匹配下限$ \ omega \ big(((n+\ sqrt {\ frac {nl} {nl} {\ mu}})\ log \ frac {1} {\ epsilon} {\ epsilon} \ big) Lan and Zhou(2015)。此外,与以前的加速算法(如Varag(Lan等,2019)和Katyusha(Allen-Zhu,2017年),Anita享有更简单的无环算法结构。此外,我们提供了一种新颖的\ emph {动态多阶段收敛分析},这是将先前结果提高到最佳速率的关键技术。我们认为,针对基本有限和有限问题的新理论率和新颖的收敛分析将直接导致许多其他相关问题(例如分布式/联合/联合/分散的优化问题)的关键改进(例如,Li和Richt \'Arik,2021年,2021年)。最后,数值实验表明,Anita收敛的速度比以前的最先进的Varag(Lan等,2019)更快,从而验证了我们的理论结果并证实了Anita的实践优势。
translated by 谷歌翻译
我们认为随机梯度下降及其在繁殖内核希尔伯特空间中二进制分类问题的平均变体。在使用损失函数的一致性属性的传统分析中,众所周知,即使在条件标签概率上假设低噪声状态时,预期的分类误差也比预期风险更慢。因此,最终的速率为sublinear。因此,重要的是要考虑是否可以实现预期分类误差的更快收敛。在最近的研究中,随机梯度下降的指数收敛速率在强烈的低噪声条件下显示,但前提是理论分析仅限于平方损耗函数,这对于二元分类任务来说是不足的。在本文中,我们在随机梯度下降的最后阶段中显示了预期分类误差的指数收敛性,用于在相似的假设下进行一类宽类可区分的凸损失函数。至于平均的随机梯度下降,我们表明相同的收敛速率来自训练的早期阶段。在实验中,我们验证了对$ L_2 $调查的逻辑回归的分析。
translated by 谷歌翻译
我们考虑光滑的凸孔concave双线性耦合的鞍点问题,$ \ min _ {\ mathbf {x}}} \ max _ {\ mathbf {y Mathbf {y}} 〜f(\ mathbf {x}} },\ mathbf {y}) - g(\ mathbf {y})$,其中一个人可以访问$ f $,$ g $的随机一阶oracles以及biinear耦合函数$ h $。基于标准的随机外部分析,我们提出了随机\ emph {加速梯度 - extragradient(ag-eg)}下降的算法,该算法在一般随机设置中结合了外部和Nesterov的加速度。该算法利用计划重新启动以接收一种良好的非震动收敛速率,该算法与\ citet {ibrahim202020linear}和\ citet {zhang2021lower}相匹配,并在其相应的设置中,还有一个额外的统计误差期限,以及\ citet {zhang2021lower}最多达到恒定的预取子。这是在鞍点优化中实现这种相对成熟的最佳表征的第一个结果。
translated by 谷歌翻译
我们介绍和分析结构化的随机零订单下降(S-SZD),这是一种有限的差异方法,该方法在一组$ l \ leq d $正交方向上近似于随机梯度,其中$ d $是环境空间的维度。这些方向是随机选择的,并且可能在每个步骤中发生变化。对于平滑的凸功能,我们几乎可以确保迭代的收敛性和对$ o(d/l k^{ - c})$的功能值的收敛速率,每$ c <1/2 $,这是任意关闭的就迭代次数而言,是随机梯度下降(SGD)。我们的界限还显示了使用$ l $多个方向而不是一个方向的好处。对于满足polyak-{\ l} ojasiewicz条件的非convex函数,我们在这种假设下建立了随机Zeroth Order Order Order算法的第一个收敛速率。我们在数值模拟中证实了我们的理论发现,在数值模拟中,满足假设以及对超参数优化的现实世界问题,观察到S-SZD具有很好的实践性能。
translated by 谷歌翻译
随机多变最小化 - 最小化(SMM)是大多数变化最小化的经典原则的在线延伸,这包括采样I.I.D。来自固定数据分布的数据点,并最小化递归定义的主函数的主要替代。在本文中,我们引入了随机块大大化 - 最小化,其中替代品现在只能块多凸,在半径递减内的时间优化单个块。在SMM中的代理人放松标准的强大凸起要求,我们的框架在内提供了更广泛的适用性,包括在线CANDECOMP / PARAFAC(CP)字典学习,并且尤其是当问题尺寸大时产生更大的计算效率。我们对所提出的算法提供广泛的收敛性分析,我们在可能的数据流下派生,放松标准i.i.d。对数据样本的假设。我们表明,所提出的算法几乎肯定会收敛于速率$ O((\ log n)^ {1+ \ eps} / n ^ {1/2})$的约束下的非凸起物镜的静止点集合。实证丢失函数和$ O((\ log n)^ {1+ \ eps} / n ^ {1/4})$的预期丢失函数,其中$ n $表示处理的数据样本数。在一些额外的假设下,后一趋同率可以提高到$ o((\ log n)^ {1+ \ eps} / n ^ {1/2})$。我们的结果为一般马尔维亚数据设置提供了各种在线矩阵和张量分解算法的第一融合率界限。
translated by 谷歌翻译
我们考虑设计统一稳定的一阶优化算法以最小化的问题。统一的稳定性通常用于获得优化算法的概括误差范围,我们对实现它的一般方法感兴趣。对于欧几里得的几何形状,我们建议采用黑盒转换,给定平滑的优化算法,它产生了算法的均匀稳定版本,同时将其收敛速率保持在对数因素上。使用此减少,我们获得了一种(几乎)最佳算法,以平滑优化,并通过收敛速率$ \ widetilde {o}(1/t^2)$和均匀的稳定性$ O(t^2/n)$,解决一个开放的问题Chen等。(2018);阿蒂亚和科伦(2021)。对于更一般的几何形状,我们开发了一种镜下下降的变体,以平滑优化,收敛速率$ \ widetilde {o}(1/t)$和统一的稳定性$ O(t/n)$(t/n)$,留下了开放的问题转换方法如欧几里得情况。
translated by 谷歌翻译
最近对基于置换的SGD的接地结果进行了证实了广泛观察到的现象:随机排列提供更快的收敛性,而不是更换采样。但是,是随机的最佳状态吗?我们表明这一点在很大程度上取决于我们正在优化的功能,并且最佳和随机排放之间的收敛差距可能因指数而异。我们首先表明,对于具有光滑的第二衍生物的1维强凸功能,与随机相比,存在令人指导的收敛性的排列。但是,对于一般强凸的功能,随机排列是最佳的。最后,我们表明,对于二次,强凸的功能,与随机相比,存在易于构建的置换,从而导致加速会聚。我们的研究结果表明,最佳排列的一般收敛性表征不能捕获各个函数类的细微差别,并且可能错误地表明一个人不能比随机更好。
translated by 谷歌翻译
用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升(SGDA)和最近引入的随机共识优化(SCO)[Mescheder等,2017]。已知SGDA可以收敛到特定类别的游戏的静止点,但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题,但其收敛保证仅限于其确定性变体。在这项工作中,我们介绍了预期的共同胁迫条件,解释了它的好处,并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证,以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时,当它们使用恒定的步长时,我们提出了富有识别的步骤化切换规则,以保证对确切解决方案的融合。此外,我们的收敛保证在任意抽样范式下担保,因此,我们对迷你匹配的复杂性进行了解。
translated by 谷歌翻译
我们调查随机镜面下降(SMD)的趋同相对光滑和平滑凸优化。在相对平滑的凸优化中,我们为SMD提供了新的收敛保证,并持续步骤。对于平滑的凸优化,我们提出了一种新的自适应步骤方案 - 镜子随机Polyak Spectize(MSP)。值得注意的是,我们的收敛导致两个设置都不会使有界渐变假设或有界方差假设,并且我们向邻域显示在插值下消失的邻居的融合。MSP概括了最近提出的随机Polyak Spectize(SPS)(Loizou等,2021)以镜子血液镜子,并且在继承镜子血清的好处的同时,现代机器学习应用仍然是实用和高效的。我们将我们的结果与各种监督的学习任务和SMD的不同实例相结合,展示了MSP的有效性。
translated by 谷歌翻译
联合学习(FL)是机器学习的一个子领域,在该子机学习中,多个客户试图在通信约束下通过网络进行协作学习模型。我们考虑在二阶功能相似性条件和强凸度下联合优化的有限和联合优化,并提出了两种新算法:SVRP和催化的SVRP。这种二阶相似性条件最近越来越流行,并且在包括分布式统计学习和差异性经验风险最小化在内的许多应用中得到满足。第一种算法SVRP结合了近似随机点评估,客户采样和降低方差。我们表明,当功能相似性足够高时,SVRP是沟通有效的,并且在许多现有算法上取得了卓越的性能。我们的第二个算法,催化的SVRP,是SVRP的催化剂加速变体,在二阶相似性和强凸度下,现有的联合优化算法可实现更好的性能,并均匀地改善了现有的算法。在分析这些算法的过程中,我们提供了可能具有独立关注的随机近端方法(SPPM)的新分析。我们对SPPM的分析很简单,允许进行近似近端评估,不需要任何平滑度假设,并且在通信复杂性上比普通分布式随机梯度下降显示出明显的好处。
translated by 谷歌翻译
越来越多的机器学习问题,例如现有算法的鲁棒或对抗性变体,需要最小化自己定义为最大值的损耗函数。在(内部)最大化问题上携带随机梯度上升(SGA)步骤的环路,然后在(外部)最小化上进行SGD步骤,称为时期随机梯度\脑短幕(ESGDA)。虽然成功在实践中,ESGDA的理论分析仍然具有挑战性,但没有明确指导内部环路尺寸的选择,也没有内部/外部步长尺寸之间的相互作用。我们提出RSGDA(随机SGDA),是ESGDA的变种,具有随机环形尺寸,具有更简单的理论分析。 RSGDA在非透露X分钟/强凹幅最大设置上使用时,rsgda附带第一个(在SGDA算法中)几乎肯定的融合速率。 RSGDA可以使用最佳环路大小进行参数化,以保证已知为SGDA的最佳收敛速率。我们在玩具和更大的尺度问题上测试RSGDA,使用作为测试用最佳运输的分布鲁棒优化和单细胞数据匹配。
translated by 谷歌翻译
在本文中,我们考虑基于移动普通(SEMA)的广泛使用但不完全了解随机估计器,其仅需要{\ bf是一般无偏的随机oracle}。我们展示了Sema在一系列随机非凸优化问题上的力量。特别是,我们分析了基于SEMA的SEMA的{\ BF差异递归性能的各种随机方法(现有或新提出),即三个非凸优化,即标准随机非凸起最小化,随机非凸强烈凹入最小最大优化,随机均方优化。我们的贡献包括:(i)对于标准随机非凸起最小化,我们向亚当风格方法(包括ADAM,AMSGRAD,Adabound等)提供了一个简单而直观的融合证明,随着越来越大的“势头” “一阶时刻的参数,它给出了一种替代但更自然的方式来保证亚当融合; (ii)对于随机非凸强度凹入的最小值优化,我们介绍了一种基于移动平均估计器的单环原始 - 双随机动量和自适应方法,并确定其Oracle复杂性$ O(1 / \ epsilon ^ 4)$不使用大型批量大小,解决文献中的差距; (iii)对于随机双脚优化,我们介绍了一种基于移动平均估计器的单环随机方法,并确定其Oracle复杂性$ \ widetilde o(1 / \ epsilon ^ 4)$,而无需计算Hessian矩阵的SVD,改善最先进的结果。对于所有这些问题,我们还建立了使用随机梯度估计器的差异递减结果。
translated by 谷歌翻译
We consider the minimization of a convex objective function defined on a Hilbert space, which is only available through unbiased estimates of its gradients. This problem includes standard machine learning algorithms such as kernel logistic regression and least-squares regression, and is commonly referred to as a stochastic approximation problem in the operations research community. We provide a non-asymptotic analysis of the convergence of two well-known algorithms, stochastic gradient descent (a.k.a. Robbins-Monro algorithm) as well as a simple modification where iterates are averaged (a.k.a. Polyak-Ruppert averaging). Our analysis suggests that a learning rate proportional to the inverse of the number of iterations, while leading to the optimal convergence rate in the strongly convex case, is not robust to the lack of strong convexity or the setting of the proportionality constant. This situation is remedied when using slower decays together with averaging, robustly leading to the optimal rate of convergence. We illustrate our theoretical results with simulations on synthetic and standard datasets. kernel least-squares regression and logistic regression (see Section 2), with strong convexity assumptions (Section 3) and without (Section 4). − We provide a non-asymptotic analysis of Polyak-Ruppert averaging [4,5], with and without strong convexity (Sections 3.3 and 4.2). In particular, we show that slower decays of the learning rate, together with averaging, are crucial to robustly obtain fast convergence rates. − We illustrate our theoretical results through experiments on synthetic and non-synthetic examples in Section 5.Notation. We consider a Hilbert space H with a scalar product •, • . We denote by • the associated norm and use the same notation for the operator norm on bounded linear operators from H to H, defined as A = sup x 1 Ax (if H is a Euclidean space, then A is the largest singular value of A). We also use the notation "w.p.1" to mean "with probability one". We denote by E the expectation or conditional expectation with respect to the underlying probability space.
translated by 谷歌翻译