二重优化（BO）可用于解决各种重要的机器学习问题，包括但不限于超参数优化，元学习，持续学习和增强学习。常规的BO方法需要通过与隐式分化的低级优化过程进行区分，这需要与Hessian矩阵相关的昂贵计算。最近，人们一直在寻求BO的一阶方法，但是迄今为止提出的方法对于大规模的深度学习应用程序往往是复杂且不切实际的。在这项工作中，我们提出了一种简单的一阶BO算法，仅取决于一阶梯度信息，不需要隐含的区别，并且对于大规模的非凸函数而言是实用和有效的。我们为提出的方法提供了非注重方法分析非凸目标的固定点，并提出了表明其出色实践绩效的经验结果。

Bilevel优化是在机器学习的许多领域中最小化涉及另一个功能的价值函数的问题。在大规模的经验风险最小化设置中，样品数量很大，开发随机方法至关重要，而随机方法只能一次使用一些样品进行进展。但是，计算值函数的梯度涉及求解线性系统，这使得很难得出无偏的随机估计。为了克服这个问题，我们引入了一个新颖的框架，其中内部问题的解决方案，线性系统的解和主要变量同时发展。这些方向是作为总和写成的，使其直接得出无偏估计。我们方法的简单性使我们能够开发全球差异算法，其中所有变量的动力学都会降低差异。我们证明，萨巴（Saba）是我们框架中著名的传奇算法的改编，具有$ o（\ frac1t）$收敛速度，并且在polyak-lojasciewicz的假设下实现了线性收敛。这是验证这些属性之一的双光线优化的第一种随机算法。数值实验验证了我们方法的实用性。

二重优化发现在现代机器学习问题中发现了广泛的应用，例如超参数优化，神经体系结构搜索，元学习等。而具有独特的内部最小点（例如，内部功能是强烈凸的，都具有唯一的内在最小点）的理解，这是充分理解的，多个内部最小点的问题仍然是具有挑战性和开放的。为此问题设计的现有算法适用于限制情况，并且不能完全保证融合。在本文中，我们采用了双重优化的重新制定来限制优化，并通过原始的双二线优化（PDBO）算法解决了问题。 PDBO不仅解决了多个内部最小挑战，而且还具有完全一阶效率的情况，而无需涉及二阶Hessian和Jacobian计算，而不是大多数现有的基于梯度的二杆算法。我们进一步表征了PDBO的收敛速率，它是与多个内部最小值的双光线优化的第一个已知的非质合收敛保证。我们的实验证明了所提出的方法的预期性能。

近年来，已经开发出各种基于梯度的方法来解决机器学习和计算机视觉地区的双层优化（BLO）问题。然而，这些现有方法的理论正确性和实际有效性总是依赖于某些限制性条件（例如，下层单身，LLS），这在现实世界中可能很难满足。此外，以前的文献仅证明了基于其特定的迭代策略的理论结果，因此缺乏一般的配方，以统一分析不同梯度的BLO的收敛行为。在这项工作中，我们从乐观的双级视点制定BLOS，并建立一个名为Bi-Level血液血统聚合（BDA）的新梯度的算法框架，以部分地解决上述问题。具体而言，BDA提供模块化结构，以分级地聚合上层和下层子问题以生成我们的双级迭代动态。从理论上讲，我们建立了一般会聚分析模板，并导出了一种新的证据方法，以研究基于梯度的BLO方法的基本理论特性。此外，这项工作系统地探讨了BDA在不同优化场景中的收敛行为，即，考虑从解决近似子问题返回的各种解决方案质量（即，全局/本地/静止解决方案）。广泛的实验证明了我们的理论结果，并展示了所提出的超参数优化和元学习任务算法的优越性。源代码可在https://github.com/vis-opt-group/bda中获得。

在本文中，我们提出了一种新的Hessian逆自由单环算法（FSLA），用于彼此优化问题。 Bilevel优化的经典算法承认计算昂贵的双回路结构。最近，已经提出了几种单循环算法，其具有优化内部和外部变量。但是，这些算法尚未实现完全单循环。因为它们忽略了评估给定内部和外部状态的超梯度所需的循环。为了开发一个完全单环算法，我们首先研究超梯度的结构，并识别超梯度计算的一般近似配方，这些计算包括几种先前的常见方法，例如，通过时间，共轭渐变，\ emph {等}基于此配方，介绍一个新的状态变量来维护历史超梯度信息。将我们的新配方与内外变量的替代更新相结合，我们提出了一种高效的全循环算法。理论上我们可以显示新状态生成的错误可以界限，我们的算法收敛于$ O（\ epsilon ^ {-2}）$。最后，我们通过基于多个Bilevel优化的机器学习任务验证了我们验证的算法。

我们研究了一类算法，用于在内部级别物镜强烈凸起时求解随机和确定性设置中的彼此优化问题。具体地，我们考虑基于不精确的隐含区分的算法，并且我们利用热门开始策略来摊销精确梯度的估计。然后，我们介绍了一个统一的理论框架，受到奇异的扰动系统（Habets，1974）的研究来分析这种摊销算法。通过使用此框架，我们的分析显示了匹配可以访问梯度无偏见估计的Oracle方法的计算复杂度的算法，从而优于彼此优化的许多现有结果。我们在合成实验中说明了这些发现，并展示了这些算法对涉及几千个变量的超参数优化实验的效率。

本文分析了双模的彼此优化随机算法框架。 Bilevel优化是一类表现出两级结构的问题，其目标是使具有变量的外目标函数最小化，该变量被限制为对（内部）优化问题的最佳解决方案。我们考虑内部问题的情况是不受约束的并且强烈凸起的情况，而外部问题受到约束并具有平滑的目标函数。我们提出了一种用于解决如此偏纤维问题的两次时间尺度随机近似（TTSA）算法。在算法中，使用较大步长的随机梯度更新用于内部问题，而具有较小步长的投影随机梯度更新用于外部问题。我们在各种设置下分析了TTSA算法的收敛速率：当外部问题强烈凸起（RESP。〜弱凸）时，TTSA算法查找$ \ MATHCAL {O}（k ^ { - 2/3}）$ -Optimal（resp。〜$ \ mathcal {o}（k ^ {-2/5}）$ - 静止）解决方案，其中$ k $是总迭代号。作为一个应用程序，我们表明，两个时间尺度的自然演员 - 批评批评近端策略优化算法可以被视为我们的TTSA框架的特殊情况。重要的是，与全球最优政策相比，自然演员批评算法显示以预期折扣奖励的差距，以$ \ mathcal {o}（k ^ { - 1/4}）的速率收敛。

许多现代的机器学习应用程序，例如多任务学习，都需要查找最佳模型参数来权衡多个可能相互冲突的目标功能。帕累托集的概念使我们能够专注于不能严格改进的（通常是无限的）模型集。但是，它不能为选择一个或几个特殊型号返回实际用户提供可行的程序。在本文中，我们考虑\ emph {在Pareto Set（Opt-In-Pareto）中进行优化，这是找到Pareto模型，以优化Pareto集中的额外参考标准函数。此功能可以编码从用户的特定偏好，也可以代表代表整个帕累托集的一组多元化的帕累托模型来代表一组多元化的帕累托模型。不幸的是，尽管是一个非常有用的框架，但在深度学习中，尤其是对于大规模，非凸面和非线性目标而言，对选择性pareto的有效算法已经很大程度上遗失了。一种幼稚的方法是将Riemannian歧管梯度下降应用于帕累托集，该片段由于需要对Hessian矩阵的本征估计而产生高计算成本。我们提出了一种一阶算法，该算法仅使用梯度信息近似求解pareto，具有高实用效率和理论上保证的收敛属性。从经验上讲，我们证明我们的方法在各种具有挑战性的多任务相关问题方面有效地工作。

基于梯度的高参数调整的优化方法可确保理论收敛到固定解决方案时，对于固定的上层变量值，双光线程序的下层级别强烈凸（LLSC）和平滑（LLS）。对于在许多机器学习算法中调整超参数引起的双重程序，不满足这种情况。在这项工作中，我们开发了一种基于不精确度（VF-IDCA）的基于依次收敛函数函数算法。我们表明，该算法从一系列的超级参数调整应用程序中实现了无LLSC和LLS假设的固定解决方案。我们的广泛实验证实了我们的理论发现，并表明，当应用于调子超参数时，提出的VF-IDCA会产生较高的性能。

最近，随机梯度下降（SGD）及其变体已成为机器学习（ML）问题大规模优化的主要方法。已经提出了各种策略来调整步骤尺寸，从自适应步骤大小到启发式方法，以更改每次迭代中的步骤大小。此外，动力已被广泛用于ML任务以加速训练过程。然而，我们对它们的理论理解存在差距。在这项工作中，我们开始通过为一些启发式优化方法提供正式保证并提出改进的算法来缩小这一差距。首先，我们分析了凸面和非凸口设置的Adagrad（延迟Adagrad）步骤大小的广义版本，这表明这些步骤尺寸允许算法自动适应随机梯度的噪声水平。我们首次显示延迟Adagrad的足够条件，以确保梯度几乎融合到零。此外，我们对延迟的Adagrad及其在非凸面设置中的动量变体进行了高概率分析。其次，我们用指数级和余弦的步骤分析了SGD，在经验上取得了成功，但缺乏理论支持。我们在平滑和非凸的设置中为它们提供了最初的收敛保证，有或没有polyak-{\ l} ojasiewicz（pl）条件。我们还显示了它们在PL条件下适应噪声的良好特性。第三，我们研究动量方法的最后迭代。我们证明了SGD的最后一个迭代的凸设置中的第一个下限，并以恒定的动量。此外，我们研究了一类跟随基于领先的领导者的动量算法，并随着动量和收缩的更新而增加。我们表明，他们的最后一个迭代具有最佳的收敛性，用于无约束的凸随机优化问题。

Two-level stochastic optimization formulations have become instrumental in a number of machine learning contexts such as continual learning, neural architecture search, adversarial learning, and hyperparameter tuning. Practical stochastic bilevel optimization problems become challenging in optimization or learning scenarios where the number of variables is high or there are constraints. In this paper, we introduce a bilevel stochastic gradient method for bilevel problems with lower-level constraints. We also present a comprehensive convergence theory that covers all inexact calculations of the adjoint gradient (also called hypergradient) and addresses both the lower-level unconstrained and constrained cases. To promote the use of bilevel optimization in large-scale learning, we introduce a practical bilevel stochastic gradient method (BSG-1) that does not require second-order derivatives and, in the lower-level unconstrained case, dismisses any system solves and matrix-vector products.

在评估目标时，在线优化嘈杂的功能需要在部署系统上进行实验，这是制造，机器人技术和许多其他功能的关键任务。通常，对安全输入的限制是未知的，我们只会获得嘈杂的信息，表明我们违反约束的距离有多近。但是，必须始终保证安全性，不仅是算法的最终输出。我们介绍了一种通用方法，用于在高维非线性随机优化问题中寻求一个固定点，其中在学习过程中保持安全至关重要。我们称为LB-SGD的方法是基于应用随机梯度下降（SGD），其精心选择的自适应步长大小到原始问题的对数屏障近似。我们通过一阶和零阶反馈提供了非凸，凸面和强键平滑约束问题的完整收敛分析。与现有方法相比，我们的方法通过维度可以更好地更新和比例。我们从经验上将样本复杂性和方法的计算成本比较现有的安全学习方法。除了合成基准测试之外，我们还证明了方法对在安全强化学习（RL）中政策搜索任务中最大程度地减少限制违规的有效性。

我们开发了快速算法和可靠软件，以凸出具有Relu激活功能的两层神经网络的凸优化。我们的工作利用了标准的重量罚款训练问题作为一组组-YELL_1 $调查的数据本地模型的凸重新印度，其中局部由多面体锥体约束强制执行。在零规范化的特殊情况下，我们表明此问题完全等同于凸“ Gated Relu”网络的不受约束的优化。对于非零正则化的问题，我们表明凸面式relu模型获得了RELU训练问题的数据依赖性近似范围。为了优化凸的重新制定，我们开发了一种加速的近端梯度方法和实用的增强拉格朗日求解器。我们表明，这些方法比针对非凸问题（例如SGD）和超越商业内部点求解器的标准训练启发式方法要快。在实验上，我们验证了我们的理论结果，探索组-ELL_1 $正则化路径，并对神经网络进行比例凸的优化，以在MNIST和CIFAR-10上进行图像分类。

现代统计应用常常涉及最小化可能是非流动和/或非凸起的目标函数。本文侧重于广泛的Bregman-替代算法框架，包括本地线性近似，镜像下降，迭代阈值，DC编程以及许多其他实例。通过广义BREGMAN功能的重新发出使我们能够构建合适的误差测量并在可能高维度下建立非凸起和非凸起和非球形目标的全球收敛速率。对于稀疏的学习问题，在一些规律性条件下，所获得的估算器作为代理人的固定点，尽管不一定是局部最小化者，但享受可明确的统计保障，并且可以证明迭代顺序在所需的情况下接近统计事实准确地快速。本文还研究了如何通过仔细控制步骤和放松参数来设计基于适应性的动力的加速度而不假设凸性或平滑度。

彼得纤维优化已广泛应用于许多重要的机器学习应用，例如普带的参数优化和元学习。最近，已经提出了几种基于动量的算法来解决贝韦尔优化问题。但是，基于SGD的算法的$ \ Mathcal {\ widetilde o}（\ epsilon ^ {-2}），那些基于势头的算法不会达到可释放的计算复杂性。在本文中，我们提出了两种用于双纤维优化的新算法，其中第一算法采用基于动量的递归迭代，第二算法采用嵌套环路中的递归梯度估计来降低方差。我们表明这两种算法都达到了$ \ mathcal {\ widetilde o}的复杂性（\ epsilon ^ { - 1.5}）$，这优于所有现有算法的级别。我们的实验验证了我们的理论结果，并展示了我们在封路数据应用程序中的算法的卓越实证性能。

近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加，我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始，显示一般非凸面问题无法在合理的时间内有效地解决。然后，我们提供了一个问题列表，可以通过利用问题的结构来有效地找到全球最小化器，因为可能的问题。处理非凸性的另一种方法是放宽目标，从找到全局最小，以找到静止点或局部最小值。对于该设置，我们首先为确定性一阶方法的收敛速率提出了已知结果，然后是最佳随机和随机梯度方案的一般理论分析，以及随机第一阶方法的概述。之后，我们讨论了非常一般的非凸面问题，例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能，这仍然允许获得一阶的理论融合保证方法。然后，我们考虑更高阶和零序/衍生物的方法及其收敛速率，以获得非凸优化问题。

策略梯度方法适用于复杂的，不理解的，通过对参数化的策略进行随机梯度下降来控制问题。不幸的是，即使对于可以通过标准动态编程技术解决的简单控制问题，策略梯度算法也会面临非凸优化问题，并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面，但没有次优的固定点。当这些条件得到加强时，该目标满足了产生收敛速率的Polyak-lojasiewicz（梯度优势）条件。当其中一些条件放松时，我们还可以在任何固定点的最佳差距上提供界限。

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$.

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

随机多变最小化 - 最小化（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}）$。我们的结果为一般马尔维亚数据设置提供了各种在线矩阵和张量分解算法的第一融合率界限。