我们介绍了基于目标观点的线性和二次近似值的非线性控制算法的实现。我们提出了一种梯度下降,一种高斯 - 纽顿方法,一种牛顿方法,具有线性二次或二次近似值的差分动态编程方法,各种线路搜索策略以及这些算法的正则变体。我们在可区分的编程框架中得出所有算法的计算复杂性,并提出足够的最佳条件。我们比较了几个基准的算法,例如使用汽车的自行车模型进行自动驾驶。该算法用公开可用的软件包中的可区分编程语言进行编码。
translated by 谷歌翻译
The notion of a Moreau envelope is central to the analysis of first-order optimization algorithms for machine learning. Yet, it has not been developed and extended to be applied to a deep network and, more broadly, to a machine learning system with a differentiable programming implementation. We define a compositional calculus adapted to Moreau envelopes and show how to integrate it within differentiable programming. The proposed framework casts in a mathematical optimization framework several variants of gradient back-propagation related to the idea of the propagation of virtual targets.
translated by 谷歌翻译
机器人设计优化,模仿学习和系统标识共享一个常见的问题,该问题需要对机器人或任务参数进行优化,同时在优化机器人运动的同时。为了解决这些问题,我们可以使用可区分的最佳控制,以使机器人运动相对于参数的运动的梯度。我们提出了一种通过敏感性分析(SA)通过差分动态编程(DDP)算法进行分析分析计算这些梯度的方法。我们表明,计算梯度时必须包括二阶动力学项。但是,在计算运动时,我们不需要包括它们。我们验证我们在摆和双摆系统上的方法。此外,我们比较使用使用迭代线性二次调节器(ILQR)的衍生物,该线性二次调节器(ILQR)在Kinova ARM的共同设计任务上忽略了这些二阶术语,我们在其中优化了目标机器人的链路长度达到任务。我们表明,使用ILQR梯度忽略二阶动力学的优化会影响衍生物的计算。取而代之的是,使用DDP梯度优化,对于一系列初始设计,使我们的公式扩展到复杂的系统。
translated by 谷歌翻译
目标传播(TP)算法计算目标,而不是神经网络的梯度,并以与梯度反向传播(BP)类似但不同的方式向后传播它们。首先将该想法作为扰动替代的反向传播,当训练多层神经网络时可能在梯度评估中获得更高的准确性(Lecun等,1989)。然而,TP仍然是具有许多变体的模板算法,而不是良好识别的算法。重新审视Lecun等人的见解,(1989),最近的Lee等人。 (2015),我们介绍了一个简单版本的目标传播,基于网络层的正则化反转,可在可差异的编程框架中实现。我们将其计算复杂性与BP之一进行了比较,并与BP相比,描绘了TP可以吸引的制度。我们展示了我们的TP如何用于培训具有关于各种序列建模问题的长序列的经常性神经网络。实验结果强调了在实践中在TP中规范化的重要性。
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 谷歌翻译
差分动态编程(DDP)是用于轨迹优化的直接单射击方法。它的效率来自对时间结构的开发(最佳控制问题固有的)和系统动力学的明确推出/集成。但是,它具有数值不稳定,与直接多个射击方法相比,它的初始化选项有限(允许对控件的初始化,但不能对状态进行初始化),并且缺乏对控制约束的正确处理。在这项工作中,我们采用可行性驱动的方法来解决这些问题,该方法调节数值优化过程中的动态可行性并确保控制限制。我们的可行性搜索模拟了只有动态约束的直接多重拍摄问题的数值解决。我们证明我们的方法(命名为box-fddp)具有比Box-DDP+(单个射击方法)更好的数值收敛性,并且其收敛速率和运行时性能与使用The Solded Sound的最新直接转录配方竞争内部点和主动集算法在Knitro中提供。我们进一步表明,Box-FDP可以单调地降低动态可行性误差 - 与最先进的非线性编程算法相同。我们通过为四足动物和人形机器人产生复杂而运动的运动来证明我们的方法的好处。最后,我们强调说,Box-FDDP适用于腿部机器人中的模型预测控制。
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 谷歌翻译
近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加,我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始,显示一般非凸面问题无法在合理的时间内有效地解决。然后,我们提供了一个问题列表,可以通过利用问题的结构来有效地找到全球最小化器,因为可能的问题。处理非凸性的另一种方法是放宽目标,从找到全局最小,以找到静止点或局部最小值。对于该设置,我们首先为确定性一阶方法的收敛速率提出了已知结果,然后是最佳随机和随机梯度方案的一般理论分析,以及随机第一阶方法的概述。之后,我们讨论了非常一般的非凸面问题,例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能,这仍然允许获得一阶的理论融合保证方法。然后,我们考虑更高阶和零序/衍生物的方法及其收敛速率,以获得非凸优化问题。
translated by 谷歌翻译
最近有兴趣的兴趣在教师学生环境中的各种普遍性线性估计问题中的渐近重建性能研究,特别是对于I.I.D标准正常矩阵的案例。在这里,我们超越这些矩阵,并证明了具有具有任意界限频谱的旋转不变数据矩阵的凸遍的线性模型的重建性能的分析公式,严格地确认使用来自统计物理的副本衍生的猜想。该公式包括许多问题,例如压缩感测或稀疏物流分类。通过利用消息通过算法和迭代的统计特性来实现证明,允许表征估计器的渐近实证分布。我们的证据是基于构建Oracle多层向量近似消息传递算法的会聚序列的构建,其中通过检查等效动态系统的稳定性来完成收敛分析。我们说明了我们对主流学习方法的数值示例的要求,例如稀疏的逻辑回归和线性支持矢量分类器,显示中等大小模拟和渐近预测之间的良好一致性。
translated by 谷歌翻译
We study the smooth minimax optimization problem $\min_{\bf x}\max_{\bf y} f({\bf x},{\bf y})$, where $f$ is $\ell$-smooth, strongly-concave in ${\bf y}$ but possibly nonconvex in ${\bf x}$. Most of existing works focus on finding the first-order stationary points of the function $f({\bf x},{\bf y})$ or its primal function $P({\bf x})\triangleq \max_{\bf y} f({\bf x},{\bf y})$, but few of them focus on achieving second-order stationary points. In this paper, we propose a novel approach for minimax optimization, called Minimax Cubic Newton (MCN), which could find an $\big(\varepsilon,\kappa^{1.5}\sqrt{\rho\varepsilon}\,\big)$-second-order stationary point of $P({\bf x})$ with calling ${\mathcal O}\big(\kappa^{1.5}\sqrt{\rho}\varepsilon^{-1.5}\big)$ times of second-order oracles and $\tilde{\mathcal O}\big(\kappa^{2}\sqrt{\rho}\varepsilon^{-1.5}\big)$ times of first-order oracles, where $\kappa$ is the condition number and $\rho$ is the Lipschitz continuous constant for the Hessian of $f({\bf x},{\bf y})$. In addition, we propose an inexact variant of MCN for high-dimensional problems to avoid calling expensive second-order oracles. Instead, our method solves the cubic sub-problem inexactly via gradient descent and matrix Chebyshev expansion. This strategy still obtains the desired approximate second-order stationary point with high probability but only requires $\tilde{\mathcal O}\big(\kappa^{1.5}\ell\varepsilon^{-2}\big)$ Hessian-vector oracle calls and $\tilde{\mathcal O}\big(\kappa^{2}\sqrt{\rho}\varepsilon^{-1.5}\big)$ first-order oracle calls. To the best of our knowledge, this is the first work that considers the non-asymptotic convergence behavior of finding second-order stationary points for minimax problems without the convex-concave assumptions.
translated by 谷歌翻译
通过行业对非线性退化的地平线控制(RHC)策略的广泛采用导致了30多年的激烈研究工作,以为这些方法提供稳定性保证。但是,当前的理论保证要求可以将每个(通常是非covex)计划问题解决为(近似)全球最优性,这是基于衍生的基于衍生的局部优化方法的不现实要求,通常用于RHC的实际实现。本文迈出了第一步,当将内部计划问题解决到一阶固定点时,但不一定是全球最佳选择,可以理解非线性RHC的稳定性保证。特别注意反馈可线化的系统,并提供了正面和负面结果的混合物。我们确定,在某些强大条件下,一阶解决方案可实现RHC稳定可线化的系统。至关重要的是,这种保证要求将其应用于计划问题的状态成本在某种意义上与系统的全球几何形状兼容,并且一个简单的反示例证明了这种情况的必要性。这些结果突出了需要重新考虑基于优化的控制背景下全局几何形状的作用。
translated by 谷歌翻译
我们提出了一种基于差分动态编程框架的算法,以处理轨迹优化问题,其中地平线在线确定而不是修复先验。该算法表现出直线,二次,时间不变问题的精确一步收敛,并且足够快,以便实时非线性模型预测控制。我们在离散时间案例中显示了非线性算法的派生,并将该算法应用于各种非线性问题。最后,我们展示了与标准MPC控制器相比的最佳地平线模型预测控制方案在平面机器人的障碍避免问题上的功效。
translated by 谷歌翻译
我们提出了一个基于预测校正范式的统一框架,用于在原始和双空间中的预测校正范式。在此框架中,以固定的间隔进行了连续变化的优化问题,并且每个问题都通过原始或双重校正步骤近似解决。通过预测步骤的输出,该解决方案方法是温暖启动的,该步骤的输出可以使用过去的信息解决未来问题的近似。在不同的假设集中研究并比较了预测方法。该框架涵盖的算法的示例是梯度方法的时变版本,分裂方法和著名的乘数交替方向方法(ADMM)。
translated by 谷歌翻译
本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的,我们专注于适合高维优化的方法。我们在二次模型上构建直觉,以确定哪种方法适用于非凸优化,并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础,我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外,最后一章还提供了对更多理论方法的广泛审查,这在实践中并不像惯例。所以在某些情况下,这项工作试图回答这个问题:为什么默认值中包含的默认TensorFlow优化器?
translated by 谷歌翻译
顺序凸编程(SCP)最近已获得了解决最佳控制问题的有效方法,并已成功应用于多个不同的领域。但是,SCP的理论分析受到了相对有限的关注,并且通常仅限于离散时间配方。在本文中,我们介绍了对连续时间最佳控制问题的相当一般类别的SCP程序的统一分析。除了在连续时间环境中保证收敛的推导外,我们的分析还揭示了两个新的数值和实际见解。首先,我们展示了如何更轻松地考虑歧管型约束,这是对机械系统的最佳控制的定义特征。其次,我们展示了如何通过从间接最佳控制中注入技术来利用我们的理论分析来加速基于SCP的最佳控制方法。
translated by 谷歌翻译
对于光滑的强凸目标,梯度下降的经典理论可确保相对于梯度评估的数量的线性收敛。一个类似的非球形理论是具有挑战性的:即使目标在每一次迭代的目标流畅时,相应的本地模型也是不稳定的,传统的补救措施需要不可预测的许多切割平面。我们提出了对局部优化的梯度下降迭代的多点概括。虽然设计了一般目标,但我们受到“最大平滑”模型的动机,可在最佳状态下捕获子样本维度。当目标本身自象最大的情况时,我们证明了线性融合,并且实验表明了更普遍的现象。
translated by 谷歌翻译
我们提出了一种新颖的二阶优化框架,用于训练新兴的深度连续时间模型,特别是神经常规方程(神经杂物杂物)。由于他们的训练已经涉及昂贵的梯度计算来通过求解向后ode,因此导出有效的二阶方法变得高度不变。然而,灵感来自最近的最佳控制(OC)对训练深网络的解释,我们表明,可以采用称为差分编程的特定连续时间oC方法,以获得同一O(1 )内存成本。我们进一步探索了二阶衍生品的低级别表示,并表明它导致借助基于Kronecker的分子化的有效的预处理更新。由此产生的方法 - 命名的snopt - 收敛于壁钟时间中的一阶基线的速度要快得多,并且改进仍然在各种应用中保持一致,例如,图像分类,生成流量和时间序列预测。我们的框架还实现了直接的架构优化,例如神经杂物的集成时间,具有二阶反馈策略,加强了OC视角作为深度学习中优化的原则性工具。我们的代码可在https://github.com/ghliu/snopt上获得。
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 谷歌翻译
策略梯度方法适用于复杂的,不理解的,通过对参数化的策略进行随机梯度下降来控制问题。不幸的是,即使对于可以通过标准动态编程技术解决的简单控制问题,策略梯度算法也会面临非凸优化问题,并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面,但没有次优的固定点。当这些条件得到加强时,该目标满足了产生收敛速率的Polyak-lojasiewicz(梯度优势)条件。当其中一些条件放松时,我们还可以在任何固定点的最佳差距上提供界限。
translated by 谷歌翻译
在这项工作中,我们证明了如何通过预期最大化算法来处理随机和风险敏感的最佳控制问题。我们展示了这种处理如何实现为两个独立的迭代程序,每个迭代程序都会产生一个独特但密切相关的密度函数序列。我们激励将这些密度解释为信念,将ERGO作为确定性最佳政策的概率代理。更正式的两个固定点迭代方案是根据代表可靠的期望最大化方法的确定性最佳策略一致的固定点得出的。我们倾向于指出我们的结果与控制范式密切相关。在此推理中的控制是指旨在将最佳控制作为概率推断的实例的方法集合。尽管所说的范式已经导致了几种强大的强化学习算法的发展,但基本问题陈述通常是由目的论论证引入的。我们认为,目前的结果表明,较早的控制作为推理框架实际上将一个步骤与所提出的迭代程序中的一个步骤隔离。在任何情况下,本疗法都为他们提供了有效性的义学论点。通过暴露基本的技术机制,我们旨在为控制作为一种推断为取代当前最佳控制范式的框架的普遍接受。为了激发提出的治疗的普遍相关性,我们在勾勒出未来算法开发的大纲之前,进一步讨论了与路径积分控制和其他研究领域的相似之处。
translated by 谷歌翻译