近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加,我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始,显示一般非凸面问题无法在合理的时间内有效地解决。然后,我们提供了一个问题列表,可以通过利用问题的结构来有效地找到全球最小化器,因为可能的问题。处理非凸性的另一种方法是放宽目标,从找到全局最小,以找到静止点或局部最小值。对于该设置,我们首先为确定性一阶方法的收敛速率提出了已知结果,然后是最佳随机和随机梯度方案的一般理论分析,以及随机第一阶方法的概述。之后,我们讨论了非常一般的非凸面问题,例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能,这仍然允许获得一阶的理论融合保证方法。然后,我们考虑更高阶和零序/衍生物的方法及其收敛速率,以获得非凸优化问题。
translated by 谷歌翻译
In this book chapter, we briefly describe the main components that constitute the gradient descent method and its accelerated and stochastic variants. We aim at explaining these components from a mathematical point of view, including theoretical and practical aspects, but at an elementary level. We will focus on basic variants of the gradient descent method and then extend our view to recent variants, especially variance-reduced stochastic gradient schemes (SGD). Our approach relies on revealing the structures presented inside the problem and the assumptions imposed on the objective function. Our convergence analysis unifies several known results and relies on a general, but elementary recursive expression. We have illustrated this analysis on several common schemes.
translated by 谷歌翻译
本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的,我们专注于适合高维优化的方法。我们在二次模型上构建直觉,以确定哪种方法适用于非凸优化,并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础,我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外,最后一章还提供了对更多理论方法的广泛审查,这在实践中并不像惯例。所以在某些情况下,这项工作试图回答这个问题:为什么默认值中包含的默认TensorFlow优化器?
translated by 谷歌翻译
本文是对解决平滑(强)单调随机变化不平等的方法的调查。首先,我们给出了随机方法最终发展的确定性基础。然后,我们回顾了通用随机配方的方法,并查看有限的总和设置。本文的最后部分致力于各种算法的各种(不一定是随机)的变化不平等现象。
translated by 谷歌翻译
最近,随机梯度下降(SGD)及其变体已成为机器学习(ML)问题大规模优化的主要方法。已经提出了各种策略来调整步骤尺寸,从自适应步骤大小到启发式方法,以更改每次迭代中的步骤大小。此外,动力已被广泛用于ML任务以加速训练过程。然而,我们对它们的理论理解存在差距。在这项工作中,我们开始通过为一些启发式优化方法提供正式保证并提出改进的算法来缩小这一差距。首先,我们分析了凸面和非凸口设置的Adagrad(延迟Adagrad)步骤大小的广义版本,这表明这些步骤尺寸允许算法自动适应随机梯度的噪声水平。我们首次显示延迟Adagrad的足够条件,以确保梯度几乎融合到零。此外,我们对延迟的Adagrad及其在非凸面设置中的动量变体进行了高概率分析。其次,我们用指数级和余弦的步骤分析了SGD,在经验上取得了成功,但缺乏理论支持。我们在平滑和非凸的设置中为它们提供了最初的收敛保证,有或没有polyak-{\ l} ojasiewicz(pl)条件。我们还显示了它们在PL条件下适应噪声的良好特性。第三,我们研究动量方法的最后迭代。我们证明了SGD的最后一个迭代的凸设置中的第一个下限,并以恒定的动量。此外,我们研究了一类跟随基于领先的领导者的动量算法,并随着动量和收缩的更新而增加。我们表明,他们的最后一个迭代具有最佳的收敛性,用于无约束的凸随机优化问题。
translated by 谷歌翻译
随机一阶方法是训练大规模机器学习模型的标准。随机行为可能导致算法的特定运行导​​致高度次优的目标值,而通常证明理论保证是出于目标值的期望。因此,从理论上保证算法具有很高的可能性,这一点至关重要。非平滑随机凸优化的现有方法具有复杂的界限,其依赖性对置信度或对数为负功率,但在额外的假设下是高斯(轻尾)噪声分布的额外假设,这些噪声分布在实践中可能不存在。在我们的论文中,我们解决了这个问题,并得出了第一个高概率收敛的结果,并以对数依赖性对非平滑凸的随机优化问题的置信度依赖,并带有非Sub-Gaussian(重尾)噪声。为了得出我们的结果,我们建议针对两种随机方法进行梯度剪辑的新步骤规则。此外,我们的分析适用于使用H \“较旧连续梯度的通用平滑目标,对于这两种方法,我们都为强烈凸出问题提供了扩展。最后,我们的结果暗示我们认为的第一种(加速)方法也具有最佳的迭代。在所有制度中,Oracle的复杂性,第二个机制在非平滑设置中都是最佳的。
translated by 谷歌翻译
在评估目标时,在线优化嘈杂的功能需要在部署系统上进行实验,这是制造,机器人技术和许多其他功能的关键任务。通常,对安全输入的限制是未知的,我们只会获得嘈杂的信息,表明我们违反约束的距离有多近。但是,必须始终保证安全性,不仅是算法的最终输出。我们介绍了一种通用方法,用于在高维非线性随机优化问题中寻求一个固定点,其中在学习过程中保持安全至关重要。我们称为LB-SGD的方法是基于应用随机梯度下降(SGD),其精心选择的自适应步长大小到原始问题的对数屏障近似。我们通过一阶和零阶反馈提供了非凸,凸面和强键平滑约束问题的完整收敛分析。与现有方法相比,我们的方法通过维度可以更好地更新和比例。我们从经验上将样本复杂性和方法的计算成本比较现有的安全学习方法。除了合成基准测试之外,我们还证明了方法对在安全强化学习(RL)中政策搜索任务中最大程度地减少限制违规的有效性。
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 谷歌翻译
We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch. Despite using second-order information, these existing methods do not exhibit superlinear convergence, unless the stochastic noise is gradually reduced to zero during the iteration, which would lead to a computational blow-up in the per-iteration cost. We propose to address this limitation with Hessian averaging: instead of using the most recent Hessian estimate, our algorithm maintains an average of all the past estimates. This reduces the stochastic noise while avoiding the computational blow-up. We show that this scheme exhibits local $Q$-superlinear convergence with a non-asymptotic rate of $(\Upsilon\sqrt{\log (t)/t}\,)^{t}$, where $\Upsilon$ is proportional to the level of stochastic noise in the Hessian oracle. A potential drawback of this (uniform averaging) approach is that the averaged estimates contain Hessian information from the global phase of the method, i.e., before the iterates converge to a local neighborhood. This leads to a distortion that may substantially delay the superlinear convergence until long after the local neighborhood is reached. To address this drawback, we study a number of weighted averaging schemes that assign larger weights to recent Hessians, so that the superlinear convergence arises sooner, albeit with a slightly slower rate. Remarkably, we show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage, and still exhibits a superlinear convergence rate nearly (up to a logarithmic factor) matching that of uniform Hessian averaging.
translated by 谷歌翻译
随机以外的(SEG)方法是解决各种机器学习任务中出现的最小最大优化和变分不等式问题(VIP)的最流行算法之一。然而,有关SEG的收敛性质的几个重要问题仍然是开放的,包括随机梯度的采样,迷你批量,用于单调有限和变分不等式的单调有限和变分别不等式,以及其他问题。为了解决这些问题,在本文中,我们开发了一种新颖的理论框架,使我们能够以统一的方式分析赛季的几种变体。除了标准设置之外,与均有界差异下的LipsChitzness和单调性或独立样本SEG相同 - 样本SEG,我们的方法可以分析之前从未明确考虑过的SEG的变体。值得注意的是,我们用任意抽样分析SEG,其中包括重要性采样和各种批量批量策略作为特殊情况。我们为SEG的新变种的率优于目前最先进的融合保证并依赖于更少的限制性假设。
translated by 谷歌翻译
众所周知,给定顺滑,界限 - 下面,并且可能的非透露函数,标准梯度的方法可以找到$ \ epsilon $ -stationary积分(渐变范围小于$ \ epsilon $)$ \ mathcal {O}(1 / \ epsilon ^ 2)$迭代。然而,许多重要的非渗透优化问题,例如与培训现代神经网络相关的问题,本质上是不平衡的,使这些结果不适用。在本文中,我们研究了来自Oracle复杂性视点的非透射性优化,其中假设算法仅向各个点处的函数提供访问。我们提供两个主要结果:首先,我们考虑越近$ \ epsilon $ -storationary积分的问题。这也许是找到$ \ epsilon $ -storationary积分的最自然的放松,这在非对象案例中是不可能的。我们证明,对于任何距离和epsilon $小于某些常数,无法有效地实现这种轻松的目标。我们的第二次结果涉及通过减少到平滑的优化来解决非光度非渗透优化的可能性:即,在光滑的近似值对目标函数的平滑近似下应用平滑的优化方法。对于这种方法,我们在温和的假设下证明了oracle复杂性和平滑度之间的固有权衡:一方面,可以非常有效地平滑非光滑非凸函数(例如,通过随机平滑),但具有尺寸依赖性因子在平滑度参数中,在插入标准平滑优化方法时,这会强烈影响迭代复杂性。另一方面,可以用合适的平滑方法消除这些尺寸因子,而是仅通过使平滑过程的Oracle复杂性呈指数大。
translated by 谷歌翻译
This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the wellknown convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free.Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.
translated by 谷歌翻译
我们提出和分析了几种随机梯度算法,以查找固定点或非convex中的局部最小值,可能是使用非平​​滑规则器,有限-AM和在线优化问题。首先,我们提出了一种基于降低的差异降低的简单近端随机梯度算法,称为XSVRG+。我们提供了对Proxsvrg+的干净分析,这表明它的表现优于确定性的近端下降(ProxGD),用于各种Minibatch尺寸,因此解决了Reddi等人中提出的一个开放问题。 (2016b)。此外,Proxsvrg+的使用近近端甲骨文调用比Proxsvrg(Reddi等,2016b)使用的距离要少得多,并通过避免进行完整的梯度计算来扩展到在线设置。然后,我们进一步提出了一种基于Sarah(Nguyen等,2017)的最佳算法,称为SSRGD,并表明SSRGD进一步提高了Proxsvrg+的梯度复杂性,并实现了最佳的上限,与已知的下限相匹配(Fang et et et and offang等人(Fang等人)(Fang等人)(Fang等人Al。,2018; Li等,2021)。此外,我们表明,Proxsvrg+和SSRGD都可以自动适应目标函数的局部结构,例如Polyak- \ l {} ojasiewicz(pl)有限的case中非convex函数的条件他们可以自动切换到更快的全局线性收敛,而无需在先前的工作proxsvrg中执行任何重新启动(Reddi等,2016b)。最后,我们专注于找到$(\ epsilon,\ delta)$的更具挑战性的问题 - 当地的最低限度,而不仅仅是找到$ \ epsilon $ -Approximate(一阶)固定点(这可能是一些不稳定的不稳定的鞍座点)。我们证明SSRGD可以找到$(\ epsilon,\ delta)$ - 局部最小值,只需添加一些随机的扰动即可。我们的算法几乎与查找固定点的对应物一样简单,并达到相似的最佳速率。
translated by 谷歌翻译
Recently, there has been great interest in connections between continuous-time dynamical systems and optimization algorithms, notably in the context of accelerated methods for smooth and unconstrained problems. In this paper we extend this perspective to nonsmooth and constrained problems by obtaining differential inclusions associated to novel accelerated variants of the alternating direction method of multipliers (ADMM). Through a Lyapunov analysis, we derive rates of convergence for these dynamical systems in different settings that illustrate an interesting tradeoff between decaying versus constant damping strategies. We also obtain perturbed equations capturing fine-grained details of these methods, which have improved stability and preserve the leading order convergence rates.
translated by 谷歌翻译
用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升(SGDA)和最近引入的随机共识优化(SCO)[Mescheder等,2017]。已知SGDA可以收敛到特定类别的游戏的静止点,但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题,但其收敛保证仅限于其确定性变体。在这项工作中,我们介绍了预期的共同胁迫条件,解释了它的好处,并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证,以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时,当它们使用恒定的步长时,我们提出了富有识别的步骤化切换规则,以保证对确切解决方案的融合。此外,我们的收敛保证在任意抽样范式下担保,因此,我们对迷你匹配的复杂性进行了解。
translated by 谷歌翻译
在本文中,我们重新审视了私人经验风险最小化(DP-erm)和差异私有随机凸优化(DP-SCO)的问题。我们表明,来自统计物理学(Langevin Exfusion(LD))的经过良好研究的连续时间算法同时为DP-SCO和DP-SCO提供了最佳的隐私/实用性权衡,$ \ epsilon $ -DP和$ $ \ epsilon $ -DP和$ (\ epsilon,\ delta)$ - dp均用于凸和强烈凸损失函数。我们为LD提供新的时间和尺寸独立统一稳定性,并使用我们为$ \ epsilon $ -DP提供相应的最佳超额人口风险保证。 $ \ epsilon $ -DP的DP-SCO保证的一个重要属性是,它们将非私人最佳界限匹配为$ \ epsilon \与\ infty $。在此过程中,我们提供了各种技术工具,这些工具可能引起独立的关注:i)在两个相邻数据集上运行损失功能时,一个新的r \'enyi Divergence绑定了LD,ii)最后一个过多的经验风险范围迭代LD,类似于Shamir和Zhang的嘈杂随机梯度下降(SGD)和iii)的LD,对LD进行了两期多余的风险分析,其中第一阶段是当扩散在任何合理意义上都没有在任何合理意义上融合到固定分布时,在第二阶段扩散已收敛到吉布斯分布的变体。我们的普遍性结果至关重要地依赖于LD的动力学。当它融合到固定分布时,我们获得了$ \ epsilon $ -DP的最佳界限。当它仅在很短的时间内运行$ \ propto 1/p $时,我们在$(\ epsilon,\ delta)$ -DP下获得最佳界限。在这里,$ p $是模型空间的维度。
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 谷歌翻译
最近的一些实证研究表明,重要的机器学习任务,例如训练深神网络,表现出低级别的结构,其中损耗函数仅在输入空间的几个方向上差异很大。在本文中,我们利用这种低级结构来降低基于规范梯度的方法(例如梯度下降(GD))的高计算成本。我们提出的\ emph {低率梯度下降}(lrgd)算法找到了$ \ epsilon $ - approximate的固定点$ p $ - 维功能,首先要识别$ r \ r \ leq p $重要的方向,然后估算真实的方向每次迭代的$ p $维梯度仅通过计算$ r $方向来计算定向衍生物。我们确定强烈凸和非convex目标函数的LRGD的“定向甲骨文复杂性”是$ \ Mathcal {o}(r \ log(1/\ epsilon) + rp) + rp)$ and $ \ Mathcal {o}(R /\ epsilon^2 + rp)$。当$ r \ ll p $时,这些复杂性小于$ \ mathcal {o}的已知复杂性(p \ log(1/\ epsilon))$和$ \ mathcal {o}(p/\ epsilon^2) {\ gd}的$分别在强凸和非凸口设置中。因此,LRGD显着降低了基于梯度的方法的计算成本,以实现足够低级别的功能。在分析过程中,我们还正式定义和表征精确且近似级别函数的类别。
translated by 谷歌翻译
我们考虑最小化高维目标函数的问题,该功能可以包括正则化术语,使用(可能的噪声)评估该功能。这种优化也称为无衍生,零阶或黑匣子优化。我们提出了一个新的$ \ textbf {z} $ feroth - $ \ textbf {o} $ rder $ \ textbf {r} $ ptimization方法,称为zoro。当潜在的梯度大致稀疏时,Zoro需要很少的客观函数评估,以获得降低目标函数的新迭代。我们通过自适应,随机梯度估计器实现这一点,然后是不精确的近端梯度方案。在一个新颖的大致稀疏梯度假设和各种不同的凸面设置下,我们显示了zoro的(理论和实证)收敛速率仅对对数依赖于问题尺寸。数值实验表明,Zoro在合成和实际数据集中优于具有相似假设的现有方法。
translated by 谷歌翻译
非滑动非概念优化问题在机器学习和业务决策中广泛出现,而两个核心挑战阻碍了具有有限时间收敛保证的有效解决方案方法的开发:缺乏计算可触及的最佳标准和缺乏计算功能强大的口腔。本文的贡献是两个方面。首先,我们建立了著名的Goldstein Subdferential〜 \ Citep {Goldstein-1977-Optimization}与均匀平滑之间的关系,从而为设计有限时间融合到一组无梯度的方法的基础和直觉提供了基础和直觉戈德斯坦固定点。其次,我们提出了无梯度方法(GFM)和随机GFM,用于解决一类非平滑非凸优化问题,并证明它们两个都可以返回$(\ delta,\ epsilon)$ - Lipschitz函数的Goldstein Sentary Point $ f $以$ o(d^{3/2} \ delta^{ - 1} \ epsilon^{ - 4})$的预期收敛速率为$ o(d^{3/2} \ delta^{ - 1} \ epsilon^{ - 4})$,其中$ d $是问题维度。还提出了两阶段版本的GFM和SGFM,并被证明可以改善大泄漏结果。最后,我们证明了2-SGFM使用\ textsc {minst}数据集对训练Relu神经网络的有效性。
translated by 谷歌翻译