对于光滑的强凸目标,梯度下降的经典理论可确保相对于梯度评估的数量的线性收敛。一个类似的非球形理论是具有挑战性的:即使目标在每一次迭代的目标流畅时,相应的本地模型也是不稳定的,传统的补救措施需要不可预测的许多切割平面。我们提出了对局部优化的梯度下降迭代的多点概括。虽然设计了一般目标,但我们受到“最大平滑”模型的动机,可在最佳状态下捕获子样本维度。当目标本身自象最大的情况时,我们证明了线性融合,并且实验表明了更普遍的现象。
translated by 谷歌翻译
我们考虑使用梯度下降来最大程度地减少$ f(x)= \ phi(xx^{t})$在$ n \ times r $因件矩阵$ x $上,其中$ \ phi是一种基础平稳凸成本函数定义了$ n \ times n $矩阵。虽然只能在合理的时间内发现只有二阶固定点$ x $,但如果$ x $的排名不足,则其排名不足证明其是全球最佳的。这种认证全球最优性的方式必然需要当前迭代$ x $的搜索等级$ r $,以相对于级别$ r^{\ star} $过度参数化。不幸的是,过度参数显着减慢了梯度下降的收敛性,从$ r = r = r = r^{\ star} $的线性速率到$ r> r> r> r> r^{\ star} $,即使$ \ phi $是$ \ phi $强烈凸。在本文中,我们提出了一项廉价的预处理,该预处理恢复了过度参数化的情况下梯度下降回到线性的收敛速率,同时也使在全局最小化器$ x^{\ star} $中可能不良条件变得不可知。
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 谷歌翻译
本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的,我们专注于适合高维优化的方法。我们在二次模型上构建直觉,以确定哪种方法适用于非凸优化,并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础,我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外,最后一章还提供了对更多理论方法的广泛审查,这在实践中并不像惯例。所以在某些情况下,这项工作试图回答这个问题:为什么默认值中包含的默认TensorFlow优化器?
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 谷歌翻译
我们提出了一种基于优化的基于优化的框架,用于计算差异私有M估算器以及构建差分私立置信区的新方法。首先,我们表明稳健的统计数据可以与嘈杂的梯度下降或嘈杂的牛顿方法结合使用,以便分别获得具有全局线性或二次收敛的最佳私人估算。我们在局部强大的凸起和自我协调下建立当地和全球融合保障,表明我们的私人估算变为对非私人M估计的几乎最佳附近的高概率。其次,我们通过构建我们私有M估计的渐近方差的差异私有估算来解决参数化推断的问题。这自然导致近​​似枢轴统计,用于构建置信区并进行假设检测。我们展示了偏置校正的有效性,以提高模拟中的小样本实证性能。我们说明了我们在若干数值例子中的方法的好处。
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 谷歌翻译
近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加,我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始,显示一般非凸面问题无法在合理的时间内有效地解决。然后,我们提供了一个问题列表,可以通过利用问题的结构来有效地找到全球最小化器,因为可能的问题。处理非凸性的另一种方法是放宽目标,从找到全局最小,以找到静止点或局部最小值。对于该设置,我们首先为确定性一阶方法的收敛速率提出了已知结果,然后是最佳随机和随机梯度方案的一般理论分析,以及随机第一阶方法的概述。之后,我们讨论了非常一般的非凸面问题,例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能,这仍然允许获得一阶的理论融合保证方法。然后,我们考虑更高阶和零序/衍生物的方法及其收敛速率,以获得非凸优化问题。
translated by 谷歌翻译
诸如压缩感测,图像恢复,矩阵/张恢复和非负矩阵分子等信号处理和机器学习中的许多近期问题可以作为约束优化。预计的梯度下降是一种解决如此约束优化问题的简单且有效的方法。本地收敛分析将我们对解决方案附近的渐近行为的理解,与全球收敛分析相比,收敛率的较小界限提供了较小的界限。然而,本地保证通常出现在机器学习和信号处理的特定问题领域。此稿件在约束最小二乘范围内,对投影梯度下降的局部收敛性分析提供了统一的框架。该建议的分析提供了枢转局部收敛性的见解,例如线性收敛的条件,收敛区域,精确的渐近收敛速率,以及达到一定程度的准确度所需的迭代次数的界限。为了证明所提出的方法的适用性,我们介绍了PGD的收敛分析的配方,并通过在四个基本问题上的配方的开始延迟应用来证明它,即线性约束最小二乘,稀疏恢复,最小二乘法使用单位规范约束和矩阵完成。
translated by 谷歌翻译
在深度学习中的优化分析是连续的,专注于(变体)梯度流动,或离散,直接处理(变体)梯度下降。梯度流程可符合理论分析,但是风格化并忽略计算效率。它代表梯度下降的程度是深度学习理论的一个开放问题。目前的论文研究了这个问题。将梯度下降视为梯度流量初始值问题的近似数值问题,发现近似程度取决于梯度流动轨迹周围的曲率。然后,我们表明,在具有均匀激活的深度神经网络中,梯度流动轨迹享有有利的曲率,表明它们通过梯度下降近似地近似。该发现允许我们将深度线性神经网络的梯度流分析转换为保证梯度下降,其几乎肯定会在随机初始化下有效地收敛到全局最小值。实验表明,在简单的深度神经网络中,具有传统步长的梯度下降确实接近梯度流。我们假设梯度流动理论将解开深入学习背后的奥秘。
translated by 谷歌翻译
We introduce a class of first-order methods for smooth constrained optimization that are based on an analogy to non-smooth dynamical systems. Two distinctive features of our approach are that (i) projections or optimizations over the entire feasible set are avoided, in stark contrast to projected gradient methods or the Frank-Wolfe method, and (ii) iterates are allowed to become infeasible, which differs from active set or feasible direction methods, where the descent motion stops as soon as a new constraint is encountered. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear, and is suitable for large-scale constrained optimization problems in which the feasible set fails to have a simple structure. The key underlying idea is that constraints are expressed in terms of velocities instead of positions, which has the algorithmic consequence that optimizations over feasible sets at each iteration are replaced with optimizations over local, sparse convex approximations. In particular, this means that at each iteration only constraints that are violated are taken into account. The result is a simplified suite of algorithms and an expanded range of possible applications in machine learning.
translated by 谷歌翻译
我们提供了新的基于梯度的方法,以便有效解决广泛的病态化优化问题。我们考虑最小化函数$ f:\ mathbb {r} ^ d \ lightarrow \ mathbb {r} $的问题,它是隐含的可分解的,作为$ m $未知的非交互方式的总和,强烈的凸起功能并提供方法这解决了这个问题,这些问题是缩放(最快的对数因子)作为组件的条件数量的平方根的乘积。这种复杂性绑定(我们证明几乎是最佳的)可以几乎指出的是加速梯度方法的几乎是指数的,这将作为$ F $的条件数量的平方根。此外,我们提供了求解该多尺度优化问题的随机异标变体的有效方法。而不是学习$ F $的分解(这将是过度昂贵的),而是我们的方法应用一个清洁递归“大步小步”交错标准方法。由此产生的算法使用$ \ tilde {\ mathcal {o}}(d m)$空间,在数字上稳定,并打开门以更细粒度的了解凸优化超出条件号的复杂性。
translated by 谷歌翻译
Cohen等人的深度学习实验。 [2021]使用确定性梯度下降(GD)显示学习率(LR)和清晰度(即Hessian最大的特征值)的稳定边缘(EOS)阶段不再像传统优化一样行为。清晰度稳定在$ 2/$ LR的左右,并且在迭代中损失不断上下,但仍有整体下降趋势。当前的论文数学分析了EOS阶段中隐式正则化的新机制,因此,由于非平滑损失景观而导致的GD更新沿着最小损失的多种流量进行了一些确定性流程发展。这与许多先前关于隐式偏差依靠无限更新或梯度中的噪声的结果相反。正式地,对于具有某些规律性条件的任何平滑函数$ l $,对于(1)标准化的GD,即具有不同的lr $ \ eta_t = \ frac {\ eta} {||的GD证明了此效果。 \ nabla l(x(t))||} $和损失$ l $; (2)具有常数LR和损失$ \ sqrt {l- \ min_x l(x)} $的GD。两者都可以证明进入稳定性的边缘,在歧管上相关的流量最小化$ \ lambda_ {1}(\ nabla^2 l)$。一项实验研究证实了上述理论结果。
translated by 谷歌翻译
我们研究无限制的黎曼优化的免投影方法。特别是,我们提出了黎曼弗兰克 - 沃尔夫(RFW)方法。我们将RFW的非渐近收敛率分析为最佳(高音)凸起问题,以及非凸起目标的临界点。我们还提出了一种实用的设置,其中RFW可以获得线性收敛速度。作为一个具体的例子,我们将RFW专用于正定矩阵的歧管,并将其应用于两个任务:(i)计算矩阵几何平均值(riemannian质心); (ii)计算Bures-Wasserstein重心。这两个任务都涉及大量凸间间隔约束,为此,我们表明RFW要求的Riemannian“线性”Oracle承认了闭合形式的解决方案;该结果可能是独立的兴趣。我们进一步专门从事RFW到特殊正交组,并表明这里也可以以封闭形式解决riemannian“线性”甲骨文。在这里,我们描述了数据矩阵同步的应用程序(促使问题)。我们补充了我们的理论结果,并对RFW对最先进的riemananian优化方法进行了实证比较,并观察到RFW竞争性地对计算黎曼心质的任务进行竞争性。
translated by 谷歌翻译
广义自我符合是许多重要学习问题的目标功能中存在的关键属性。我们建立了一个简单的Frank-Wolfe变体的收敛速率,该变体使用开环步数策略$ \ gamma_t = 2/(t+2)$,获得了$ \ Mathcal {o}(1/t)$收敛率对于这类功能,就原始差距和弗兰克 - 沃尔夫差距而言,$ t $是迭代计数。这避免了使用二阶信息或估计以前工作的局部平滑度参数的需求。我们还显示了各种常见病例的收敛速率的提高,例如,当所考虑的可行区域均匀地凸或多面体时。
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 谷歌翻译
策略梯度方法适用于复杂的,不理解的,通过对参数化的策略进行随机梯度下降来控制问题。不幸的是,即使对于可以通过标准动态编程技术解决的简单控制问题,策略梯度算法也会面临非凸优化问题,并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面,但没有次优的固定点。当这些条件得到加强时,该目标满足了产生收敛速率的Polyak-lojasiewicz(梯度优势)条件。当其中一些条件放松时,我们还可以在任何固定点的最佳差距上提供界限。
translated by 谷歌翻译
在本文中,我们研究并证明了拟牛顿算法的Broyden阶级的非渐近超线性收敛速率,包括Davidon - Fletcher - Powell(DFP)方法和泡沫 - 弗莱彻 - 夏诺(BFGS)方法。这些准牛顿方法的渐近超线性收敛率在文献中已经广泛研究,但它们明确的有限时间局部会聚率未得到充分调查。在本文中,我们为Broyden Quasi-Newton算法提供了有限时间(非渐近的)收敛分析,在目标函数强烈凸起的假设下,其梯度是Lipschitz连续的,并且其Hessian在最佳解决方案中连续连续。我们表明,在最佳解决方案的本地附近,DFP和BFGS生成的迭代以$(1 / k)^ {k / 2} $的超连线率收敛到最佳解决方案,其中$ k $是迭代次数。我们还证明了类似的本地超连线收敛结果,因为目标函数是自我协调的情况。几个数据集的数值实验证实了我们显式的收敛速度界限。我们的理论保证是第一个为准牛顿方法提供非渐近超线性收敛速率的效果之一。
translated by 谷歌翻译
Theoretical properties of bilevel problems are well studied when the lower-level problem is strongly convex. In this work, we focus on bilevel optimization problems without the strong-convexity assumption. In these cases, we first show that the common local optimality measures such as KKT condition or regularization can lead to undesired consequences. Then, we aim to identify the mildest conditions that make bilevel problems tractable. We identify two classes of growth conditions on the lower-level objective that leads to continuity. Under these assumptions, we show that the local optimality of the bilevel problem can be defined via the Goldstein stationarity condition of the hyper-objective. We then propose the Inexact Gradient-Free Method (IGFM) to solve the bilevel problem, using an approximate zeroth order oracle that is of independent interest. Our non-asymptotic analysis demonstrates that the proposed method can find a $(\delta, \varepsilon)$ Goldstein stationary point for bilevel problems with a zeroth order oracle complexity that is polynomial in $d, 1/\delta$ and $1/\varepsilon$.
translated by 谷歌翻译
最近对基于置换的SGD的接地结果进行了证实了广泛观察到的现象:随机排列提供更快的收敛性,而不是更换采样。但是,是随机的最佳状态吗?我们表明这一点在很大程度上取决于我们正在优化的功能,并且最佳和随机排放之间的收敛差距可能因指数而异。我们首先表明,对于具有光滑的第二衍生物的1维强凸功能,与随机相比,存在令人指导的收敛性的排列。但是,对于一般强凸的功能,随机排列是最佳的。最后,我们表明,对于二次,强凸的功能,与随机相比,存在易于构建的置换,从而导致加速会聚。我们的研究结果表明,最佳排列的一般收敛性表征不能捕获各个函数类的细微差别,并且可能错误地表明一个人不能比随机更好。
translated by 谷歌翻译