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

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

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

我们扩展并结合了一些文献的工具，以设计快速，自适应，随时和无规模的在线学习算法。无尺寸的遗憾界限必须以最大损失线性缩放，既朝向大损失，缺乏较小亏损。自适应遗憾界限表明，算法可以利用易于数据，并且可能具有恒定的遗憾。我们寻求开发快速算法，依赖于尽可能少的参数，特别是它们应该是随时随地的，因此不依赖于时间范围。我们的第一和主要工具，IsoTuning是平衡遗憾权衡的想法的概括。我们开发了一套工具来轻松设计和分析这些学习率，并表明它们自动适应遗憾（无论是常量，$ O（\ log t）$，$ o（\ sqrt {t}）$，在Hindsight的最佳学习率的因子2中，对于相同的观察量的因子2中。第二种工具是在线校正，其允许我们获得许多算法的中心界限，以防止当域太大或仅部分约束时遗憾地被空隙。最后一个工具null更新，防止算法执行过多的更大的更新，这可能导致无限的后悔，甚至无效更新。我们使用这些工具开发一般理论并将其应用于几种标准算法。特别是，我们（几乎完全）恢复对无限域的FTRL的小损失的适应性，设计和证明无镜面下降的无缝的自适应保证（至少当Bregman发散在其第二个参数中凸出），延伸Adapt-ML-PROSIA令无规模的保证，并为Prod，Adahedge，Boa和软贝内斯提供了其他几个小贡献。

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

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

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

我们考虑在线线性优化问题，在每个步骤中，算法在单位球中播放点x_t $，损失$ \ langle c_t，x_t \ rangle $，x_t \ rangle $ for for some成本向量$ c_t $那么透露算法。最近的工作表明，如果算法接收到与$ C_T $之前的invial相关的提示$ h_t $，则它可以达到$ o（\ log t）$的遗憾保证，从而改善标准设置中$ \ theta（\ sqrt {t}）$。在这项工作中，我们研究了算法是否真正需要在每次步骤中需要提示的问题。有些令人惊讶的是，我们表明，只需在自然查询模型下只需在$ O（\ SQRT {T}）$暗示即可获得$ O（\ log t）$后悔;相比之下，我们还显示$ o（\ sqrt {t}）$提示不能优于$ \ omega（\ sqrt {t}）$后悔。我们为我们的结果提供了两种应用，以乐观的遗憾界限和弃权问题的乐观遗憾。

分位数（更普遍，KL）遗憾的界限，例如由癌症（Chaudhuri，Freund和Hsu 2009）及其变体实现的界限，放松了竞争最佳个别专家的目标，只能争夺大多数专家对抗性数据。最近，通过考虑可能既完全对抗或随机（i.i.D.），半对抗拉利范式（Bilodeau，Negrea和Roy 2020）提供了对抗性在线学习的替代放松。我们使用FTRL与单独的，新颖的根对数常规常规程序一起实现SIMIMAX最佳遗憾，这两者都可以解释为QuanchEdge的屈服变体。我们扩展了现有的KL遗憾的上限，统一地持有目标分布，可能是具有任意前锋的不可数专家课程;在有限的专家课程（紧密）上为Simitile遗憾提供第一个全信息下限;并为半逆势范式提供适应性最低的最低限度最佳算法，其适应真实，未知的约束更快，导致在现有方法上均匀改进遗憾。

We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

我们研究了在线凸优化，并具有由多个功能约束和相对简单的约束集组成的约束，例如欧几里得球。一般而言，由于在整个预测中执行约束在计算上都具有挑战性，因此我们允许决策违反功能约束，但旨在实现低遗憾和累积违反$ t $时间步骤的约束的侵犯。一阶方法实现$ \ MATHCAL {O}（\ sqrt {t}）$遗憾和$ \ Mathcal {o}（1）$约束违规，这是最著名的界限，但不考虑问题的结构信息。此外，现有的算法和分析仅限于欧几里得空间。在本文中，我们提供了一个\ emph {实例依赖性}在线凸优化的绑定，并通过新颖的在线原始偶发镜像算法获得的复杂约束。我们与实例有关的遗憾是通过损失函数顺序中的总梯度变化$ v _*（t）$量化的。所提出的算法在\ emph {eneral} non-euclidean空间中起作用，并同时实现$ \ nathcal {o}（\ sqrt {v _*（t）}）违法，这永远不会比最著名的$（\ Mathcal {o}（\ sqrt {t}），\ Mathcal {o}（1））$ result $更糟糕对于此问题，实现$ \ Mathcal {O}（T^{2/3}）$遗憾和约束违规。最后，我们的算法在计算上是有效的，因为它仅在每次迭代中执行镜像下降步骤，而不是解决一般的拉格朗日最小化问题。

我们解决了经典专家问题的长期“不可能的调整”问题，并表明，实际上可能实现后悔$ o \ lex（\ sqrt {（\ ln d）\ sum_t \ ell_ {t，i} ^ 2} \ \右）同时为所有专家$ i $ t-$-t-$ -round $ d $ -expert问题在哪里$ \ ell_ {t，i} $是专家$ i $的损失$ t $ 。我们的算法基于镜像血迹框架，具有校正项和加权熵规范器。虽然自然，但之前尚未研究该算法，并且需要仔细分析。对于任何预测向量$ M_T，我们还概括了refton to $ o reft（\ sqrt {（\ ln d）\ sum_t（\ ell_ {t，i}）^ 2} \右）$ $ Cylayer通过选择不同的$ M_T $来收到学习者，并恢复或改善许多现有结果。此外，我们使用相同的框架来创建一个组合一组基础算法的主算法，并学习最好的一个开销。我们的主人的新保证使我们能够为专家问题提供许多新的结果，并且更广泛的在线线性优化。

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

当学习者与其他优化代理进行连续游戏时，我们研究了遗憾最小化的问题：在这种情况下，如果所有玩家都遵循一种无重组算法，则相对于完全对手环境，可能会达到较低的遗憾。我们在变异稳定的游戏（包括所有凸孔和单调游戏的连续游戏）的背景下研究了这个问题，当玩家只能访问其个人回报梯度时。如果噪音是加性的，那么游戏理论和纯粹的对抗性设置也会获得类似的遗憾保证。但是，如果噪声是乘法的，我们表明学习者实际上可以持续遗憾。我们通过学习速率分离的乐观梯度方案实现了更快的速度 - 也就是说，该方法的外推和更新步骤被调整为不同的时间表，具体取决于噪声配置文件。随后，为了消除对精致的超参数调整的需求，我们提出了一种完全自适应的方法，可以在最坏的和最佳案例的遗憾保证之间平稳地插入。

我们考虑在下一个成本和约束函数的预测存在下对在线凸优化的一般问题。通过将具有预测自适应动态步骤组合的跟随 - 正则化的引导迭代来设计一种新的原始双向算法。该算法实现$ \ mathcal o（t ^ {\ frac {3- \ beta} {4}）$后悔和$ \ mathcal o（t ^ {\ frac {1+ \ beta} {2}）$约束通过参数$ \ beta \！\ in \！[1/2,1）$可调的违规界限，并且具有与预测质量缩小的恒定因素，实现最终$ \ mathcal o（1）$遗憾的完美预测。我们的工作扩展了这个约束OCO设置的FTRL框架，并优于基于最先进的贪婪的解决方案，而不会对预测质量，成本函数或约束的几何形状的条件突出，而不是凸出的。

一流拍卖基本上基于Vickrey拍卖的基于程序化广告的传统竞标方法。就学习而言，首次拍卖更具挑战性，因为最佳招标策略不仅取决于物品的价值，还需要一些其他出价的知识。他们已经升级了续集学习的几种作品，其中许多人考虑以对抗方式选择买方或对手最大出价的型号。即使在最简单的设置中，这也会导致算法，其后悔在$ \ sqrt {t} $方面与时间纵横为$ t $。专注于买方对静止随机环境扮演的情况，我们展示了如何实现显着较低的遗憾：当对手的最大竞标分布是已知的，我们提供了一种遗留算法，其后悔可以低至$ \ log ^ 2（t ）$;在必须顺序地学习分发的情况下，对于任何$ \ epsilon> 0 $来说，该算法的概括可以达到$ t ^ {1/3 + \ epsilon} $。为了获得这些结果，我们介绍了两种可能对自己兴趣感兴趣的新颖思想。首先，通过在发布的价格设置中获得的结果进行输，我们提供了一个条件，其中一流的挡板效用在其最佳状态下局部二次。其次，我们利用观察到，在小子间隔上，可以更准确地控制经验分布函数的变化的浓度，而不是使用经典的DVORETZKY-Kiefer-Wolfowitz不等式来控制。数值模拟确认，我们的算法比各种出价分布中提出的替代方案更快地收敛，包括在实际的程序化广告平台上收集的出价。

不受限制的在线线性优化（OLO）是研究机器学习模型培训的实用问题。现有作品提出了许多基于潜在的算法，但总的来说，这些潜在功能的设计在很大程度上取决于猜测。为了简化此工作流程，我们提出了一个框架，该框架通过求解部分微分方程（PDE）来生成新的潜在功能。具体来说，当损失是1-lipschitz时，我们的框架会产生一种新颖的算法，并随时随地遗憾绑定$ c \ sqrt {t}+|| || u || \ sqrt {2t} [\ sqrt {\ sqrt {\ log（1+|| |||/c）}+2] $，其中$ c $是用户指定的常数，$ u $是任何比较器未知和无限的先验者。这样的界限实现了最佳的损失重格折衷，而没有不切实际的tuble俩。此外，匹配的下限表明，包括常量乘数$ \ sqrt {2} $在内的领先订单项很紧。据我们所知，提出的算法是第一个实现此类最佳性的算法。

一系列不受限制的在线凸优化中的作品已经调查了同时调整比较器的规范$ u $和梯度的最大规范$ g $的可能性。在完全的一般性中，已知匹配的上限和下界表明，这是不可避免的$ g u^3 $的不可避免的成本，当$ g $或$ u $提前知道时，这是不需要的。令人惊讶的是，Kempka等人的最新结果。 （2019年）表明，在特定情况下，不需要这样的适应性价格，例如$ -Lipschitz损失（例如铰链损失）。我们通过表明我们专门研究任何其他常见的在线学习损失，我们的结果涵盖了日志损失，（线性和非参数）逻辑回归，我们实际上从来没有任何代价来为适应性支付的代价，从而跟进这一观察结果，我们会跟进这一观察结果。方形损耗预测，以及（线性和非参数）最小二乘回归。我们还通过提供对$ U $的明确依赖的下限来填补文献中的几个空白。在所有情况下，我们都会获得无标度算法，这些算法在数据恢复下是合理的不变。我们的一般目标是在不关心计算效率的情况下建立可实现的速率，但是对于线性逻辑回归，我们还提供了一种适应性方法，该方法与Agarwal等人的最新非自适应算法一样有效。 （2021）。

我们考虑非静止在线凸优化的框架，其中学习者寻求控制其动态遗憾，免于任意比较器序列。当损耗函数强烈凸或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扩展，以便在有限维中在线线性回归。

资源限制的在线分配问题是收入管理和在线广告中的核心问题。在这些问题中，请求在有限的地平线期间顺序到达，对于每个请求，决策者需要选择消耗一定数量资源并生成奖励的动作。目标是最大限度地提高累计奖励，这是对资源总消费的限制。在本文中，我们考虑一种数据驱动的设置，其中使用决策者未知的输入模型生成每个请求的奖励和资源消耗。我们设计了一般的算法算法，可以在各种输入模型中实现良好的性能，而不知道它们面临的类型类型。特别是，我们的算法在独立和相同的分布式输入以及各种非静止随机输入模型下是渐近的最佳选择，并且当输入是对抗性时，它们达到渐近最佳的固定竞争比率。我们的算法在Lagrangian双色空间中运行：它们为使用在线镜像血管更新的每个资源维护双倍乘数。通过相应地选择参考功能，我们恢复双梯度下降和双乘法权重更新算法。与现有的在线分配问题的现有方法相比，所产生的算法简单，快速，不需要在收入函数，消费函数和动作空间中凸起。我们将应用程序讨论到网络收入管理，在线竞标，重复拍卖，预算限制，与高熵的在线比例匹配，以及具有有限库存的个性化分类优化。