本文提出了一个新的算法系列，用于在线优化复合目标。该算法可以解释为凸起梯度和$ p $ - 纳米算法的组合。结合适应性和乐观的算法思想，所提出的算法获得了序列依赖的遗憾上限，与稀疏目标决策变量的最著名界限相匹配。此外，该算法具有对流行的复合目标和约束的有效实现，并且可以通过最佳加速速率转换为随机优化算法，以实现流畅的目标。

在本文中，我们提出和分析了非凸复合目标的零阶优化算法，重点是降低复杂性依赖性对维度的依赖性。这是通过使用带有熵函数的随机镜下降方法利用决策集的低维结构来实现的，该方法在配备最大规范的空间中执行梯度下降。为了改善梯度估计，我们用基于Rademacher分布的采样方法替换了经典的高斯平滑法，并表明Mini Batch方法与非欧几里得几何形状相抵抗。为了避免调整超参数，我们分析了一般随机镜下降的自适应步骤，并表明所提出算法的自适应版本收敛而无需对问题进行先验知识。

We present a new family of subgradient methods that dynamically incorporate knowledge of the geometry of the data observed in earlier iterations to perform more informative gradient-based learning. Metaphorically, the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features. Our paradigm stems from recent advances in stochastic optimization and online learning which employ proximal functions to control the gradient steps of the algorithm. We describe and analyze an apparatus for adaptively modifying the proximal function, which significantly simplifies setting a learning rate and results in regret guarantees that are provably as good as the best proximal function that can be chosen in hindsight. We give several efficient algorithms for empirical risk minimization problems with common and important regularization functions and domain constraints. We experimentally study our theoretical analysis and show that adaptive subgradient methods outperform state-of-the-art, yet non-adaptive, subgradient algorithms.

我们调查随机镜面下降（SMD）的趋同相对光滑和平滑凸优化。在相对平滑的凸优化中，我们为SMD提供了新的收敛保证，并持续步骤。对于平滑的凸优化，我们提出了一种新的自适应步骤方案 - 镜子随机Polyak Spectize（MSP）。值得注意的是，我们的收敛导致两个设置都不会使有界渐变假设或有界方差假设，并且我们向邻域显示在插值下消失的邻居的融合。MSP概括了最近提出的随机Polyak Spectize（SPS）（Loizou等，2021）以镜子血液镜子，并且在继承镜子血清的好处的同时，现代机器学习应用仍然是实用和高效的。我们将我们的结果与各种监督的学习任务和SMD的不同实例相结合，展示了MSP的有效性。

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

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

在约束凸优化中，基于椭球体或切割平面方法的现有方法与环境空间的尺寸不符比展出。诸如投影梯度下降的替代方法，仅为诸如欧几里德球等简单凸起集提供的计算益处，其中可以有效地执行欧几里德投影。对于其他集合，投影的成本可能太高。为了规避这些问题，研究了基于着名的Frank-Wolfe算法的替代方法。这些方法在每次迭代时使用线性优化Oracle而不是欧几里德投影;前者通常可以有效地执行。此类方法还扩展到在线和随机优化设置。然而，对于一般凸套，弗兰克 - 沃尔夫算法及其变体不会在后悔或速率方面实现最佳性能。更重要的是，在某些情况下，他们使用的线性优化Oracle仍然可以计算得昂贵。在本文中，我们远离Frank-Wolfe风格的算法，并提出了一种新的减少，将任何在欧几里德球（其中投影廉价）上定义的任何算法的算法转移到球上包含的受限组C上的算法，而不牺牲原始算法的性能多大。我们的缩减需要O（t log t）在t回合后对C的成员资格Oracle调用，并且不需要对C的线性优化。使用我们的减少，我们恢复最佳遗憾界限[resp。在在线[RESP的迭代次数方面。随机]凸优化。当环境空间的尺寸大时，我们的保证在离线凸优化设置中也是有用的。

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

为了通过分布式在线学习中的本地光计算处理复杂的约束，最近的一项研究提出了一种称为分布式在线条件梯度（D-OCG）的无投影算法（D-OCG），并获得了$ O（T^{3/4}）$遗憾的是凸出损失，其中$ t $是总回合的数量。但是，它需要$ t $通信回合，并且不能利用强大的损失凸度。在本文中，我们提出了一个改进的D-OCG的变体，即D-BOCG，可以达到相同的$ O（t^{3/4}）$遗憾，只有$ o（\ sqrt {t}）$凸损失的通信回合，以及$ o（t^{2/3}（\ log t）^{1/3}）$的更好遗憾，少于$ o（t^{1/3}（\ log log） t）^{2/3}）$通信回合，以实现强烈凸出的损失。关键思想是采用延迟的更新机制，以降低通信复杂性，并重新定义D-OCG中的替代损失功能以利用强凸度。此外，我们提供了下限，以证明D-BOCG所需的$ O（\ sqrt {t}）$通信回合是最佳的（以$ t $为单位）实现$ O（T^{3/4} ）$遗憾带有凸损失，以及$ o（t^{1/3}（\ log t）^{2/3}）$ d-bocg所需的通信回合近距离）实现$ o（t^{2/3}（\ log t）^{1/3}）$遗憾的是，强烈凸出的损失归属于多凝集因子。最后，为了处理更具挑战性的强盗设置，其中只有损失值可用，我们将经典的单点梯度估计器纳入D-BOCG，并获得类似的理论保证。

本文研究了拟牛顿方法求解强凸强凹鞍点问题（SPP）。我们提出了SPP一般贪婪Broyden族更新，其中有$明确的局部超线性收敛速度的变体{\mathcalØ}\大（\大（1\压裂{1}{N\卡帕^2}\大）^ {K（K-1）/ 2}\大）$，其中$N $是问题的尺寸，$ \卡帕$是条件数和$$ķ是迭代次数。设计和算法的分析是基于估计不定Hessian矩阵的平方，这是从在凸优化古典准牛顿方法的不同。我们还提出两个具体Broyden族算法与BFGS型和SR1型更新，其享受的$更快的局部收敛速度\mathcalØ\大（\大（1\压裂{1} {N}\大）^{K（K-1）/ 2}\大）$。

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

在论文中，我们提出了一类加速的零顺序，用于非凸迷你优化和最小值优化的一类加速的零序命令和一流的动量方法。具体而言，我们提出了一种新的加速零级动量（ACC-ZOM）方法，用于黑箱迷你优化。此外，我们证明我们的ACC-ZOM方法达到$ \ TILDE {O}的较低查询复杂性（D ^ {3/4} \ epsilon ^ {-3}）$寻找$ \ epsilon $ -stationary point，这通过$ o（d ^ {1/4}）$ of the $ d $表示可变尺寸。特别是，ACC-ZOM不需要现有的零点随机算法中所需的大批次。同时，我们提出了一种加速\ TextBF {Zeroth-Order} moneotum血管下降（ACC-ZOMDA）方法，用于\ TextBF {Black-Box} Minimax-Optimization，它获得$ \ TINDE {O}的查询复杂性（（d_1 + d_2）^ {3/4} \ kappa_y ^ {4.5} \ epsilon ^ { - 3}）$没有大批次查找$ \ epsilon $ -stationary point，其中$ d_1 $和$ d_2 $ demote变量尺寸和$ \ kappa_y $是条件号。此外，我们提出了一种加速\ TextBF {一阶}势头血管下降（ACC-MDA）方法，用于\ textBF {White-Box} Minimax优化，它具有$ \ tilde {o}（\ kappa_y ^ { 4.5} \ epsilon ^ { - 3}）$无大批次查找$ \ epsilon $ -stationary point。特别是，我们的ACC-MDA可以获得$ \ tilde {o}（\ kappa_y ^ {2.5} \ epsilon ^ {-3}）$的较低渐变复杂性，具有批量尺寸$ o（\ kappa_y ^ 4）$。对黑匣子对抗攻击深度神经网络（DNN）和中毒攻击的广泛实验结果表明了我们算法的效率。

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

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

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

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

The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated Learning with Formal Differential Privacy Guarantees"). In this case, a concrete bound on the error is very relevant to reduce the privacy parameter. The standard mechanism for continual counting is the binary mechanism. We present a novel mechanism and show that its mean squared error is both asymptotically optimal and a factor 10 smaller than the error of the binary mechanism. We also show that the constants in our analysis are almost tight by giving non-asymptotic lower and upper bounds that differ only in the constants of lower-order terms. Our algorithm is a matrix mechanism for the counting matrix and takes constant time per release. We also use our explicit factorization of the counting matrix to give an upper bound on the excess risk of the private learning algorithm of Denisov et al. (NeurIPS 2022). Our lower bound for any continual counting mechanism is the first tight lower bound on continual counting under approximate differential privacy. It is achieved using a new lower bound on a certain factorization norm, denoted by $\gamma_F(\cdot)$, in terms of the singular values of the matrix. In particular, we show that for any complex matrix, $A \in \mathbb{C}^{m \times n}$, \[ \gamma_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] where $\|\cdot \|$ denotes the Schatten-1 norm. We believe this technique will be useful in proving lower bounds for a larger class of linear queries. To illustrate the power of this technique, we show the first lower bound on the mean squared error for answering parity queries.

我们提出了一种基于优化的基于优化的框架，用于计算差异私有M估算器以及构建差分私立置信区的新方法。首先，我们表明稳健的统计数据可以与嘈杂的梯度下降或嘈杂的牛顿方法结合使用，以便分别获得具有全局线性或二次收敛的最佳私人估算。我们在局部强大的凸起和自我协调下建立当地和全球融合保障，表明我们的私人估算变为对非私人M估计的几乎最佳附近的高概率。其次，我们通过构建我们私有M估计的渐近方差的差异私有估算来解决参数化推断的问题。这自然导致近​​似枢轴统计，用于构建置信区并进行假设检测。我们展示了偏置校正的有效性，以提高模拟中的小样本实证性能。我们说明了我们在若干数值例子中的方法的好处。

对于函数的矩阵或凸起的正半明确度（PSD）的形状约束在机器学习和科学的许多应用中起着核心作用，包括公制学习，最佳运输和经济学。然而，存在很少的功能模型，以良好的经验性能和理论担保来强制执行PSD-NESS或凸起。在本文中，我们介绍了用于在PSD锥中的值的函数的内核平方模型，其扩展了最近建议编码非负标量函数的内核平方型号。我们为这类PSD函数提供了一个代表性定理，表明它构成了PSD函数的普遍近似器，并在限定的平等约束的情况下导出特征值界限。然后，我们将结果应用于建模凸起函数，通过执行其Hessian的核心量子表示，并表明可以因此表示任何平滑且强凸的功能。最后，我们说明了我们在PSD矩阵值回归任务中的方法以及标准值凸起回归。

我们提出了随机方差降低算法，以求解凸 - 凸座鞍点问题，单调变异不平等和单调夹杂物。我们的框架适用于Euclidean和Bregman设置中的外部，前向前后和前反向回复的方法。所有提出的方法都在与确定性的对应物相同的环境中收敛，并且它们要么匹配或改善了解决结构化的最低最大问题的最著名复杂性。我们的结果加强了变异不平等和最小化之间的差异之间的对应关系。我们还通过对矩阵游戏的数值评估来说明方法的改进。