在线优化是一个完善的优化范式，旨在鉴于对以前的决策任务的正确答案，旨在做出一系列正确的决策。二重编程涉及一个分层优化问题，其中所谓的外部问题的可行区域受内部问题的解决方案集映射的限制。本文将这两个想法汇总在一起，并研究了在线双层优化设置，其中一系列随时间变化的二聚体问题又一个接一个地揭示了一个。我们将已知的单层在线算法的已知遗憾界限扩展到双重设置。具体而言，我们引入了新的杂种遗憾概念，开发了一种在线交替的时间平均梯度方法，该方法能够利用光滑度，并根据内部和外部极型序列的长度提供遗憾的界限。

我们在非静止环境中调查在线凸优化，然后选择\ emph {动态后悔}作为性能测量，定义为在线算法产生的累积损失与任何可行比较器序列之间的差异。让$ t $是$ p_t $ be的路径长度，基本上反映了环境的非平稳性，最先进的动态遗憾是$ \ mathcal {o}（\ sqrt {t（ 1 + p_t）}）$。虽然这一界限被证明是凸函数最佳的最低限度，但在本文中，我们证明可以进一步提高一些简单的问题实例的保证，特别是当在线功能平滑时。具体而言，我们提出了新的在线算法，可以利用平滑度并替换动态遗憾的$ t $替换依据\ {问题依赖性}数量：损耗函数梯度的变化，比较器序列的累积损失，以及比较器序列的累积损失最低术语的最低限度。这些数量是大多数$ \ mathcal {o}（t）$，良性环境中可能更小。因此，我们的结果适应了问题的内在难度，因为边界比现有结果更严格，以便在最坏的情况下保证相同的速率。值得注意的是，我们的算法只需要\ emph {一个}渐变，这与开发的方法共享相同的渐变查询复杂性，以优化静态遗憾。作为进一步的应用，我们将来自全信息设置的结果扩展到具有两点反馈的强盗凸优化，从而达到此类强盗任务的第一个相关的动态遗憾。

自适应梯度算法（例如Adagrad及其变体）在培训深神经网络方面已广受欢迎。尽管许多适合自适应方法的工作都集中在静态的遗憾上，作为实现良好遗憾保证的性能指标，但对这些方法的动态遗憾分析尚不清楚。与静态的遗憾相反，动态遗憾被认为是绩效测量的更强大的概念，因为它明确阐明了环境的非平稳性。在本文中，我们通过动态遗憾的概念在一个强大的凸面设置中浏览了Adagrad（称为M-Adagrad）的一种变体，该遗憾衡量了在线学习者的性能，而不是参考（最佳）解决方案，这可能会改变时间。我们证明了根据最小化序列的路径长度的束缚，该序列基本上反映了环境的非平稳性。此外，我们通过利用每个回合中学习者的多个访问权限来增强动态遗憾。经验结果表明，M-Adagrad在实践中也很好。

我们开发了一种使用无遗憾的游戏动态解决凸面优化问题的算法框架。通过转换最小化凸起函数以顺序方式解决Min-Max游戏的辅助问题的问题，我们可以考虑一系列必须在另一个之后选择其行动的两名员工的一系列策略。这些策略的常见选择是所谓的无悔的学习算法，我们描述了许多此类并证明了遗憾。然后，我们表明许多凸面优化的经典一阶方法 - 包括平均迭代梯度下降，弗兰克 - 沃尔夫算法，重球算法和Nesterov的加速方法 - 可以被解释为我们框架的特殊情况由于每个玩家都做出正确选择无悔的策略。证明该框架中的收敛速率变得非常简单，因为它们遵循适当已知的遗憾范围。我们的框架还引发了一些凸优化的特殊情况的许多新的一阶方法。

在线学习中，随机数据和对抗性数据是两个广泛研究的设置。但是许多优化任务都不是I.I.D.也不完全对抗，这使得对这些极端之间的世界有更好的理论理解具有根本的利益。在这项工作中，我们在在随机I.I.D.之间插值的环境中建立了在线凸优化的新颖遗憾界限。和完全的对抗损失。通过利用预期损失的平滑度，这些边界用梯度的方差取代对最大梯度长度的依赖，这是以前仅以线性损失而闻名的。此外，它们削弱了I.I.D.假设通过允许对抗中毒的回合，以前在专家和强盗设置中考虑过。我们的结果将其扩展到在线凸优化框架。在完全I.I.D.中情况，我们的界限与随机加速的结果相匹配，并且在完全对抗的情况下，它们优雅地恶化以符合Minimax的遗憾。我们进一步提供了下限，表明所有中级方案的遗憾上限都很紧张，从随机方差和损失梯度的对抗变异方面。

我们研究了对抗性多臂土匪的元学习。我们考虑在线 - 在线设置，其中玩家（学习者）遇到了一系列多臂强盗情节。根据对手产生的损失，球员的表现被衡量为对每一集中最佳手臂的遗憾。问题的难度取决于对手选择的最佳手臂的经验分布。我们提出了一种算法，可以利用这种经验分布中的非均匀性，并得出与问题有关的遗憾界限。该解决方案包括一个内部学习者，该学习者分别播放每个情节，以及一个外部学习者，它更新了情节之间内部算法的超参数。如果最好的手臂分配远非统一，则它可以通过在每个情节上单独执行的任何在没有元学习的在线执行的在线算法来实现的最佳界限。

Projection operations are a typical computation bottleneck in online learning. In this paper, we enable projection-free online learning within the framework of Online Convex Optimization with Memory (OCO-M) -- OCO-M captures how the history of decisions affects the current outcome by allowing the online learning loss functions to depend on both current and past decisions. Particularly, we introduce the first projection-free meta-base learning algorithm with memory that minimizes dynamic regret, i.e., that minimizes the suboptimality against any sequence of time-varying decisions. We are motivated by artificial intelligence applications where autonomous agents need to adapt to time-varying environments in real-time, accounting for how past decisions affect the present. Examples of such applications are: online control of dynamical systems; statistical arbitrage; and time series prediction. The algorithm builds on the Online Frank-Wolfe (OFW) and Hedge algorithms. We demonstrate how our algorithm can be applied to the online control of linear time-varying systems in the presence of unpredictable process noise. To this end, we develop the first controller with memory and bounded dynamic regret against any optimal time-varying linear feedback control policy. We validate our algorithm in simulated scenarios of online control of linear time-invariant systems.

当在未知约束集中任意变化的分布中生成数据时，我们会考虑使用专家建议的预测。这种半反向的设置包括（在极端）经典的I.I.D.设置时，当未知约束集限制为单身人士时，当约束集是所有分布的集合时，不受约束的对抗设置。对冲状态中，对冲算法（长期以来已知是最佳的最佳速率（速率））最近被证明是对I.I.D.的最佳最小值。数据。在这项工作中，我们建议放松I.I.D.通过在约束集的所有自然顺序上寻求适应性来假设。我们在各个级别的Minimax遗憾中提供匹配的上限和下限，表明确定性学习率的对冲在极端之外是次优的，并证明人们可以在各个级别的各个层面上都能适应Minimax的遗憾。我们使用以下规范化领导者（FTRL）框架实现了这种最佳适应性，并采用了一种新型的自适应正则化方案，该方案隐含地缩放为当前预测分布的熵的平方根，而不是初始预测分布的熵。最后，我们提供了新的技术工具来研究FTRL沿半逆转频谱的统计性能。

在随着时间变化的组合环境中的在线决策激励，我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题，我们提供了一个通用框架，该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明，在完整信息设置下，由此产生的在线算法具有$ O（\ sqrt {t}）$（近似）遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展，我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪（t^{2/3}）$（近似）$（近似）的遗憾。展示了我们框架的灵活性，我们将脱机之间的转换应用于收入管理，市场设计和在线优化的几个问题，包括在线平台中的产品排名优化，拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法，例如用于最大化连续强的DR单调下调功能，这些功能受到凸约束的约束。我们表明，当应用于这些应用程序时，我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究，在这两种应用中，我们都观察到，转换的数值性能在实际情况下优于理论保证。

当培训数据共享与即将到来的测试样本相同的分布时，标准监督学习范式有效地工作。但是，在现实世界中，通常会违反此假设，尤其是在以在线方式出现测试数据时。在本文中，我们制定和调查了在线标签转移（OLAS）的问题：学习者从标记的离线数据训练初始模型，然后将其部署到未标记的在线环境中，而基础标签分布会随着时间的推移而变化，但标签 - 条件密度没有。非平稳性和缺乏监督使问题具有挑战性。为了解决难度，我们构建了一个新的无偏风险估计器，该风险估计器利用了未标记的数据，该数据表现出许多良性特性，尽管具有潜在的非跨性别性。在此基础上，我们提出了新颖的在线合奏算法来应对环境的非平稳性。我们的方法享有最佳的动态遗憾，表明该性能与千里眼的千里眼竞争，后者是事后看来的在线环境，然后选择每轮的最佳决定。获得的动态遗憾结合量表与标签分布转移的强度和模式，因此在OLAS问题中表现出适应性。进行广泛的实验以验证有效性和支持我们的理论发现。

遗憾已被广泛用作评估分布式多代理系统在线优化算法的性能的首选指标。但是，与代理相关的数据/模型变化可以显着影响决策，并需要在代理之间达成共识。此外，大多数现有的作品都集中在开发（强烈或非严格地）凸出的方法上，对于一般非凸损失的分布式在线优化中的遗憾界限，几乎没有得到很少的结果。为了解决这两个问题，我们提出了一种新型的综合遗憾，并使用新的基于网络的基于遗憾的度量标准来评估分布式在线优化算法。我们具体地定义了复合遗憾的静态和动态形式。通过利用我们的综合遗憾的动态形式，我们开发了一种基于共识的在线归一化梯度（CONGD）的伪convex损失方法，事实证明，它显示了与最佳器路径变化的规律性术语有关的透明性行为。对于一般的非凸损失，我们首先阐明了基于最近进步的分布式在线非凸学习的遗憾，因此没有确定性算法可以实现sublinear的遗憾。然后，我们根据离线优化的Oracle开发了分布式的在线非凸优化（Dinoco），而无需进入梯度。迪诺科（Dinoco）被证明是统一的遗憾。据我们所知，这是对一般分布在线非convex学习的第一个遗憾。

我们考虑非静止在线凸优化的框架，其中学习者寻求控制其动态遗憾，免于任意比较器序列。当损耗函数强烈凸或exy-yshave时，我们证明了强烈的自适应（SA）算法可以被视为在比较器序列的路径变化$ V_T $的路径变化中控制动态遗憾的原则方式。具体来说，我们展示了SA算法享受$ \ tilde o（\ sqrt {tv_t} \ vee \ log t）$和$ \ tilde o（\ sqrt {dtv_t} \ vee d \ log t）$动态遗憾强烈凸Exp-Trowave损失分别没有APRIORI $ v_t $。本发明进一步展示了原理方法的多功能性，在与高斯内核的界限线性预测器和在线回归的环境中进一步证明了原则方法。在一个相关的环境下，纸张的第二个组件解决了Zhdanov和Kalnishkan（2010）提出的一个开放问题，涉及与平方误差损失的在线内核回归。我们在一定处罚后悔的新下限，该遗憾地建立了在线内核Ridge回归（KRR）的近极低最低限度。我们的下限可以被视为vovk（2001）中派生的rkhs扩展，以便在有限维中在线线性回归。

我们介绍了一种在线凸优化算法，该算法利用了预测的亚级别下降，并具有最佳的自适应学习率。我们的方法为一系列一系列一般凸函数提供了二阶最小动态遗憾保证（即取决于平方的亚级别规范的总和），这些序列可能没有强大的凸度，平滑度，表现出色甚至Lipschitz-continunition。遗憾的保证是反对具有有界路径变化（即连续决策之间的距离之和）的任何比较者决策顺序。我们通过合并实际的亚级别规范来生成最坏的二阶动态遗憾的下限。我们表明，这种下限与我们在不变的因素内的遗憾保证匹配，这使我们的算法最小值最佳。我们还得出每个决策坐标的扩展。当比较器序列的路径变化的界限随着时间的流逝而增长或随着时间的流逝而部分到达时，我们演示了如何最好地保留我们的遗憾保证。我们进一步以算法为基础，以消除对比较路径变化的任何知识的需求，并在没有先验信息的情况下提供最小值的最佳二阶遗憾保证。我们的方法可以以最小的最佳方式（即每个遗憾保证）同时（普遍）（普遍）与所有比较序列竞争，这取决于相应的比较路径变化。我们讨论了对我们的方法的修改，以解决时间，计算和内存的复杂性降低。除了相应的路径变化外，我们还通过使遗憾保证还取决于比较器集的直径来进一步改善结果。

Bilevel programming has recently received attention in the literature, due to a wide range of applications, including reinforcement learning and hyper-parameter optimization. However, it is widely assumed that the underlying bilevel optimization problem is solved either by a single machine or in the case of multiple machines connected in a star-shaped network, i.e., federated learning setting. The latter approach suffers from a high communication cost on the central node (e.g., parameter server) and exhibits privacy vulnerabilities. Hence, it is of interest to develop methods that solve bilevel optimization problems in a communication-efficient decentralized manner. To that end, this paper introduces a penalty function based decentralized algorithm with theoretical guarantees for this class of optimization problems. Specifically, a distributed alternating gradient-type algorithm for solving consensus bilevel programming over a decentralized network is developed. A key feature of the proposed algorithm is to estimate the hyper-gradient of the penalty function via decentralized computation of matrix-vector products and few vector communications, which is then integrated within our alternating algorithm to give the finite-time convergence analysis under different convexity assumptions. Owing to the generality of this complexity analysis, our result yields convergence rates for a wide variety of consensus problems including minimax and compositional optimization. Empirical results on both synthetic and real datasets demonstrate that the proposed method works well in practice.

我们研究了在线马尔可夫决策过程（MDP），具有对抗性变化的损失功能和已知过渡。我们选择动态遗憾作为绩效度量，定义为学习者和任何可行的变化策略序列之间的绩效差异。这项措施严格比标准的静态遗憾要强得多，该标准遗憾的是，基准通过固定的政策将学习者的绩效表现为学习者的表现。我们考虑了三种在线MDP的基础模型，包括无情节循环随机路径（SSP），情节SSP和Infinite-Horizo​​n MDP。对于这三个模型，我们提出了新颖的在线集合算法并分别建立了动态​​遗憾保证，在这种情况下，情节性（无环）SSP的结果在时间范围和某些非平稳性度量方面是最佳的最低限度。此外，当学习者遇到的在线环境是可以预测的时，我们设计了改进的算法并为情节（无环）SSP实现更好的动态遗憾界限；此外，我们证明了无限 - 摩恩MDP的不可能结果。

我们研究了非参数在线回归中的快速收敛速度，即遗憾的是关于具有有界复杂度的任意函数类来定义后悔。我们的贡献是两倍： - 在绝对损失中的非参数网上回归的可实现设置中，我们提出了一种随机适当的学习算法，该算法在假设类的顺序脂肪破碎尺寸方面获得了近乎最佳的错误。在与一类Littlestone维度$ D $的在线分类中，我们的绑定减少到$ d \ cdot {\ rm poly} \ log t $。这结果回答了一个问题，以及适当的学习者是否可以实现近乎最佳错误的界限;以前，即使在线分类，绑定的最知名错误也是$ \ tilde o（\ sqrt {dt}）$。此外，对于真实值（回归）设置，在这项工作之前，界定的最佳错误甚至没有以不正当的学习者所知。 - 使用上述结果，我们展示了Littlestone维度$ D $的一般总和二进制游戏的独立学习算法，每个玩家达到后悔$ \ tilde o（d ^ {3/4} \ cdot t ^ {1 / 4}）$。该结果概括了Syrgkanis等人的类似结果。 （2015）谁表明，在有限的游戏中，最佳遗憾可以从普通的o（\ sqrt {t}）$中的$ o（\ sqrt {t}）为游戏设置中的$ o（t ^ {1/4}）$。要建立上述结果，我们介绍了几种新技术，包括：分层聚合规则，以实现对实际类别的最佳错误，Hanneke等人的适当在线可实现学习者的多尺度扩展。 （2021），一种方法来表明这种非参数学习算法的输出是稳定的，并且证明Minimax定理在所有在线学习游戏中保持。

In the framework of online convex optimization, most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. To tackle this problem HK12 proposed the study of projection-free methods that replace projections with less expensive computations. The most common approach is based on the Frank-Wolfe method, that uses linear optimization computation in lieu of projections. Recent work by GK22 gave sublinear adaptive regret guarantees with projection free algorithms based on the Frank Wolfe approach. In this work we give projection-free algorithms that are based on a different technique, inspired by Mhammedi22, that replaces projections by set-membership computations. We propose a simple lazy gradient-based algorithm with a Minkowski regularization that attains near-optimal adaptive regret bounds. For general convex loss functions we improve previous adaptive regret bounds from $O(T^{3/4})$ to $O(\sqrt{T})$, and further to tight interval dependent bound $\tilde{O}(\sqrt{I})$ where $I$ denotes the interval length. For strongly convex functions we obtain the first poly-logarithmic adaptive regret bounds using a projection-free algorithm.

我们开发了一个修改的在线镜下降框架，该框架适用于在无界域中构建自适应和无参数的算法。我们利用这项技术来开发第一个不受限制的在线线性优化算法，从而达到了最佳的动态遗憾，我们进一步证明，基于以下规范化领导者的自然策略无法取得相似的结果。我们还将镜像下降框架应用于构建新的无参数隐式更新，以及简化和改进的无限规模算法。

标准联合优化方法成功地适用于单层结构的随机问题。然而，许多当代的ML问题 - 包括对抗性鲁棒性，超参数调整和参与者 - 批判性 - 属于嵌套的双层编程，这些编程包含微型型和组成优化。在这项工作中，我们提出了\ fedblo：一种联合交替的随机梯度方法来解决一般的嵌套问题。我们在存在异质数据的情况下为\ fedblo建立了可证明的收敛速率，并引入了二聚体，最小值和组成优化的变化。\ fedblo引入了多种创新，包括联邦高级计算和降低方差，以解决内部级别的异质性。我们通过有关超参数\＆超代理学习和最小值优化的实验来补充我们的理论，以证明我们方法在实践中的好处。代码可在https://github.com/ucr-optml/fednest上找到。

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