BREGMAN近端点算法（BPPA）是优化工具箱中的核心之一，一直在目睹新兴应用程序。通过简单易于实现更新规则，该算法对实证成功进行了几种引人注目的直觉，但严格的理由仍然很大程度上是未开发的。我们通过具有可分离数据的分类任务研究BPPA的计算属性，并证明与BPPA相关的可提供算法正则化效果。我们表明BPPA达到了非平凡的余量，这密切依赖于诱导BREGMAN发散的距离产生功能的条件数。我们进一步证明，对于一类问题，对条件数量的依赖性是紧张的，从而表明发散在影响所获得的解决方案的质量方面的重要性。此外，我们还将我们的调查结果扩展到镜像血统（MD），我们建立了边缘和BREGMAN发散之间的类似联系。我们通过具体示例演示，并显示BPPA / MD在相对于Mahalanobis距离的最大边缘解决方案方向上会聚。我们的理论调查结果是第一个展示良性学习特性BPPA / MD的态度，并且还提供校正算法设计中仔细选择的腐败。

We propose a new policy gradient method, named homotopic policy mirror descent (HPMD), for solving discounted, infinite horizon MDPs with finite state and action spaces. HPMD performs a mirror descent type policy update with an additional diminishing regularization term, and possesses several computational properties that seem to be new in the literature. We first establish the global linear convergence of HPMD instantiated with Kullback-Leibler divergence, for both the optimality gap, and a weighted distance to the set of optimal policies. Then local superlinear convergence is obtained for both quantities without any assumption. With local acceleration and diminishing regularization, we establish the first result among policy gradient methods on certifying and characterizing the limiting policy, by showing, with a non-asymptotic characterization, that the last-iterate policy converges to the unique optimal policy with the maximal entropy. We then extend all the aforementioned results to HPMD instantiated with a broad class of decomposable Bregman divergences, demonstrating the generality of the these computational properties. As a by product, we discover the finite-time exact convergence for some commonly used Bregman divergences, implying the continuing convergence of HPMD to the limiting policy even if the current policy is already optimal. Finally, we develop a stochastic version of HPMD and establish similar convergence properties. By exploiting the local acceleration, we show that for small optimality gap, a better than $\tilde{\mathcal{O}}(\left|\mathcal{S}\right| \left|\mathcal{A}\right| / \epsilon^2)$ sample complexity holds with high probability, when assuming a generative model for policy evaluation.

最新工作的一条有影响力的线重点关注的是针对可分离的线性分类的非规范梯度学习程序的泛化特性，并具有指数级的损失函数。这种方法概括地概括的能力归因于它们对大幅度预测指标的隐含偏见，无论是渐近的还是有限的时间。我们为此概括提供了另一个统一的解释，并将其与优化目标的两个简单属性相关联，我们将其称为可实现性和自我限制性。我们介绍了通过这些特性的不受约束随机凸优化的一般设置，并通过算法稳定性镜头分析梯度方法的概括。在这种更广泛的环境中，我们获得了梯度下降和随机梯度下降的尖锐稳定性边界，这些梯度下降即使适用于大量梯度步骤，并使用它们来得出这些算法的通用泛化界限。最后，作为一般边界的直接应用，我们返回使用可分离数据的线性分类设置，并为梯度下降和随机梯度下降建立了几种新颖的测试损失和测试精度界限，用于各种尾巴衰减速率的多种损耗函数。在某些情况下，我们的界限显着改善了文献中现有的概括误差界限。

我们检查了在未注册的逻辑回归问题上的梯度下降，并在线性可分离数据集上具有均匀的线性预测指标。我们显示了预测变量收敛到最大边缘（硬边缘SVM）解决方案的方向。结果还推广到其他单调的损失函数，在无穷大时降低了损失功能，多级问题，并在某个受限的环境中训练在深网中的重量层。此外，我们表明这种融合非常慢，只有在损失本身的融合中的对数。这可以有助于解释即使训练错误为零，并且训练损失非常小，并且正如我们所显示的，即使验证损失增加了，也可以继续优化逻辑或跨透明度损失的好处。我们的方法还可以帮助理解隐式正则化n更复杂的模型以及其他优化方法。

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

加速的近端算法（APPA），也称为“催化剂”，是从凸优化到近似近端计算（即正则最小化）的确定还原。这种减少在概念上是优雅的，可以保证强大的收敛速度。但是，这些速率具有多余的对数项，因此需要计算每个近端点至高精度。在这项工作中，我们提出了一个新颖的放松误差标准，用于加速近端点（recapp），以消除对高精度子问题解决方案的需求。我们将recapp应用于两个规范问题：有限的和最大结构的最小化。对于有限和问题，我们匹配了以前通过精心设计的问题特异性算法获得的最著名的复杂性。为了最大程度地减少$ \ max_y f（x，y）$，其中$ f $以$ x $为$ x $，而在$ y $中强烈concave，我们改进了受对数因素限制的最著名的（基于催化剂）。

Neural networks trained to minimize the logistic (a.k.a. cross-entropy) loss with gradient-based methods are observed to perform well in many supervised classification tasks. Towards understanding this phenomenon, we analyze the training and generalization behavior of infinitely wide two-layer neural networks with homogeneous activations. We show that the limits of the gradient flow on exponentially tailed losses can be fully characterized as a max-margin classifier in a certain non-Hilbertian space of functions. In presence of hidden low-dimensional structures, the resulting margin is independent of the ambiant dimension, which leads to strong generalization bounds. In contrast, training only the output layer implicitly solves a kernel support vector machine, which a priori does not enjoy such an adaptivity. Our analysis of training is non-quantitative in terms of running time but we prove computational guarantees in simplified settings by showing equivalences with online mirror descent. Finally, numerical experiments suggest that our analysis describes well the practical behavior of two-layer neural networks with ReLU activations and confirm the statistical benefits of this implicit bias.

在负面的感知问题中，我们给出了$ n $数据点$（{\ boldsymbol x} _i，y_i）$，其中$ {\ boldsymbol x} _i $是$ d $ -densional vector和$ y_i \ in \ { + 1，-1 \} $是二进制标签。数据不是线性可分离的，因此我们满足自己的内容，以找到最大的线性分类器，具有最大的\ emph {否定}余量。换句话说，我们想找到一个单位常规矢量$ {\ boldsymbol \ theta} $，最大化$ \ min_ {i \ le n} y_i \ langle {\ boldsymbol \ theta}，{\ boldsymbol x} _i \ rangle $ 。这是一个非凸优化问题（它相当于在Polytope中找到最大标准矢量），我们在两个随机模型下研究其典型属性。我们考虑比例渐近，其中$ n，d \ to \ idty $以$ n / d \ to \ delta $，并在最大边缘$ \ kappa _ {\ text {s}}（\ delta）上证明了上限和下限）$或 - 等效 - 在其逆函数$ \ delta _ {\ text {s}}（\ kappa）$。换句话说，$ \ delta _ {\ text {s}}（\ kappa）$是overparametization阈值：以$ n / d \ le \ delta _ {\ text {s}}（\ kappa） - \ varepsilon $一个分类器实现了消失的训练错误，具有高概率，而以$ n / d \ ge \ delta _ {\ text {s}}（\ kappa）+ \ varepsilon $。我们在$ \ delta _ {\ text {s}}（\ kappa）$匹配，以$ \ kappa \ to - \ idty $匹配。然后，我们分析了线性编程算法来查找解决方案，并表征相应的阈值$ \ delta _ {\ text {lin}}（\ kappa）$。我们观察插值阈值$ \ delta _ {\ text {s}}（\ kappa）$和线性编程阈值$ \ delta _ {\ text {lin {lin}}（\ kappa）$之间的差距，提出了行为的问题其他算法。

我们研究了具有有限和结构的平滑非凸化优化问题的随机重新洗脱（RR）方法。虽然该方法在诸如神经网络的训练之类的实践中广泛利用，但其会聚行为仅在几个有限的环境中被理解。在本文中，在众所周知的Kurdyka-LojasiewiCz（KL）不等式下，我们建立了具有适当递减步长尺寸的RR的强极限点收敛结果，即，RR产生的整个迭代序列是会聚并会聚到单个静止点几乎肯定的感觉。 In addition, we derive the corresponding rate of convergence, depending on the KL exponent and the suitably selected diminishing step sizes.当KL指数在$ [0，\ FRAC12] $以$ [0，\ FRAC12] $时，收敛率以$ \ mathcal {o}（t ^ { - 1}）$的速率计算，以$ t $ counting迭代号。当KL指数属于$（\ FRAC12,1）$时，我们的派生收敛速率是FORM $ \ MATHCAL {O}（T ^ { - Q}）$，$ Q \ IN（0,1）$取决于在KL指数上。基于标准的KL不等式的收敛分析框架仅适用于具有某种阶段性的算法。我们对基于KL不等式的步长尺寸减少的非下降RR方法进行了新的收敛性分析，这概括了标准KL框架。我们总结了我们在非正式分析框架中的主要步骤和核心思想，这些框架是独立的兴趣。作为本框架的直接应用，我们还建立了类似的强极限点收敛结果，为重组的近端点法。

黎曼优化中加速梯度方法的研究最近见证了显着的进展。然而，与欧几里德的环境相比，利莫曼环境仍然缺乏对加速的系统理解。我们重新审视\ citet {monteiro2013accelerated}的\ citet {monteiro2013accelerated}的\ citeterated {monteiro2013accelerated}，这是一个强大的框架，用于获得加速的欧几里德方法。随后，我们提出了一个Riemannian版的A-HPE。我们对Riemannian A-HPE分析的基础是欧几里德A-HPE的一系列洞察力，我们将仔细控制Riemannian几何形状引起的扭曲。我们描述了许多riemannian加速梯度方法作为我们框架的具体实例。

Convex function constrained optimization has received growing research interests lately. For a special convex problem which has strongly convex function constraints, we develop a new accelerated primal-dual first-order method that obtains an $\Ocal(1/\sqrt{\vep})$ complexity bound, improving the $\Ocal(1/{\vep})$ result for the state-of-the-art first-order methods. The key ingredient to our development is some novel techniques to progressively estimate the strong convexity of the Lagrangian function, which enables adaptive step-size selection and faster convergence performance. In addition, we show that the complexity is further improvable in terms of the dependence on some problem parameter, via a restart scheme that calls the accelerated method repeatedly. As an application, we consider sparsity-inducing constrained optimization which has a separable convex objective and a strongly convex loss constraint. In addition to achieving fast convergence, we show that the restarted method can effectively identify the sparsity pattern (active-set) of the optimal solution in finite steps. To the best of our knowledge, this is the first active-set identification result for sparsity-inducing constrained optimization.

我们考虑解决强大的马尔可夫决策过程（MDP）的问题，该过程涉及一组折扣，有限状态，有限的动作空间MDP，具有不确定的过渡核。计划的目的是找到一项强大的政策，以优化针对过渡不确定性的最坏情况值，从而将标准MDP计划作为特殊情况。对于$（\ Mathbf {s}，\ Mathbf {a}）$ - 矩形不确定性集，我们开发了一种基于策略的一阶方法，即稳健的策略镜像下降（RPMD），并建立$ \ Mathcal {o }（\ log（1/\ epsilon））$和$ \ Mathcal {o}（1/\ epsilon）$迭代复杂性，用于查找$ \ epsilon $ -optimal策略，并带有两个增加的步骤式方案。 RPMD的先前收敛适用于任何Bregman差异，前提是政策空间在以初始政策为中心时通过差异测量的半径限制了半径。此外，当布雷格曼的分歧对应于平方的欧几里得距离时，我们建立了一个$ \ mathcal {o}（\ max \ {1/\ epsilon，1/（\ eta \ eTa \ epsilon^2）\ epsilon^2）\任何常量的步进$ \ eta $。对于Bregman差异的一般类别，如果不确定性集满足相对强的凸度，则还为RPMD建立了类似的复杂性。当仅通过与名义环境的在线互动获得一阶信息时，我们进一步开发了一个名为SRPMD的随机变体。对于Bregman General Divergences，我们建立了一个$ \ MATHCAL {O}（1/\ Epsilon^2）$和$ \ Mathcal {O}（1/\ Epsilon^3）$样品复杂性，具有两个增加的静态方案。对于Euclidean Bregman Divergence，我们建立了一个$ \ MATHCAL {O}（1/\ Epsilon^3）$样本复杂性，并具有恒定的步骤。据我们所知，所有上述结果似乎是应用于强大的MDP问题的基于策略的一阶方法的新事物。

我们研究稀疏的线性回归在一个代理网络上，建模为无向图（没有集中式节点）。估计问题被制定为当地套索损失函数的最小化，加上共识约束的二次惩罚 - 后者是获取分布式解决方案方法的工具。虽然在优化文献中广泛研究了基于惩罚的共识方法，但其高维设置中的统计和计算保证仍不清楚。这项工作提供了对此公开问题的答案。我们的贡献是两倍。 First, we establish statistical consistency of the estimator: under a suitable choice of the penalty parameter, the optimal solution of the penalized problem achieves near optimal minimax rate $\mathcal{O}(s \log d/N)$ in $\ell_2 $ -loss，$ s $是稀疏性值，$ d $是环境维度，$ n $是网络中的总示例大小 - 这与集中式采样率相匹配。其次，我们表明，应用于惩罚问题的近端梯度算法，它自然导致分布式实现，线性地收敛到集中统计误差的顺序的公差 - 速率比例为$ \ mathcal {o}（ d）$，揭示不可避免的速度准确性困境。数值结果证明了衍生的采样率和收敛速率缩放的紧张性。

在本文中，我们提出了一种新的策略梯度（PG）方法，即用于解决一类正规化加固学习（RL）问题的块策略镜下降（BPMD）方法（强烈） - convex正规化器。与带有批处理更新规则的传统PG方法（访问和更新每个状态的策略）相比，BPMD方法通过部分更新规则具有廉价的每卷计算，该规则在采样状态上执行策略更新。尽管问题的性质和部分更新规则具有非概念性质，但我们还是为多种采样方案提供了统一的分析，并表明BPMD可以实现快速的线性收敛到全局最优性。特别是，均匀的采样导致可比的最坏情况总计算复杂性与批处理PG方法。还确定了一种与上policy采样的必要条件。通过混合采样方案，我们进一步表明，BPMD具有潜在的实例依赖性加速度，从而改善了对状态空间的依赖性，因此优于批次PG方法。然后，我们通过利用从样品构建的随机一阶信息扩展到随机设置。使用生成模型，$ \ tilde {\ mathcal {o}}（\ left \ lvert \ lerver \ mathcal {s} \ right \ rvert \ rvert \ left \ lest \ lerver \ lovt \ mathcal {a} \ right \ right \ rvert \ rvert \ rvert /\ epsilon） $ \ tilde {\ mathcal {o}}（\ left \ lvert \ m athcal {s} \ right \ rvert \ rvert \ left \ lest \ lvert \ lerver \ mathcal {a} \ right \ right \ rvert /\ epsilon^2）强率强度（分别为非巧克力符号）正规化器，其中$ \ epsilon $表示目标准确性。据我们所知，这是第一次开发和分析了块坐标下降方法，以进行强化学习的策略优化，这为解决大规模RL问题提供了新的观点。

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

Iterative regularization is a classic idea in regularization theory, that has recently become popular in machine learning. On the one hand, it allows to design efficient algorithms controlling at the same time numerical and statistical accuracy. On the other hand it allows to shed light on the learning curves observed while training neural networks. In this paper, we focus on iterative regularization in the context of classification. After contrasting this setting with that of regression and inverse problems, we develop an iterative regularization approach based on the use of the hinge loss function. More precisely we consider a diagonal approach for a family of algorithms for which we prove convergence as well as rates of convergence. Our approach compares favorably with other alternatives, as confirmed also in numerical simulations.

我们考虑非凸凹minimax问题，$ \ min _ {\ mathbf {x}} \ mathcal {y}} f（\ mathbf {x}，\ mathbf {y}）$， $ f $在$ \ mathbf {x} $ on $ \ mathbf {y} $和$ \ mathcal {y} $中的$ \ \ mathbf {y} $。解决此问题的最受欢迎的算法之一是庆祝的梯度下降上升（GDA）算法，已广泛用于机器学习，控制理论和经济学。尽管凸凹设置的广泛收敛结果，但具有相等步骤的GDA可以收敛以限制循环甚至在一般设置中发散。在本文中，我们介绍了两次尺度GDA的复杂性结果，以解决非膨胀凹入的最小问题，表明该算法可以找到函数$ \ phi（\ cdot）的静止点：= \ max _ {\ mathbf {Y} \ In \ Mathcal {Y}} F（\ CDOT，\ MATHBF {Y}）高效。据我们所知，这是对这一环境中的两次尺度GDA的第一个非因对药分析，阐明了其在培训生成对抗网络（GANS）和其他实际应用中的优越实际表现。

我们认为随机梯度下降及其在繁殖内核希尔伯特空间中二进制分类问题的平均变体。在使用损失函数的一致性属性的传统分析中，众所周知，即使在条件标签概率上假设低噪声状态时，预期的分类误差也比预期风险更慢。因此，最终的速率为sublinear。因此，重要的是要考虑是否可以实现预期分类误差的更快收敛。在最近的研究中，随机梯度下降的指数收敛速率在强烈的低噪声条件下显示，但前提是理论分析仅限于平方损耗函数，这对于二元分类任务来说是不足的。在本文中，我们在随机梯度下降的最后阶段中显示了预期分类误差的指数收敛性，用于在相似的假设下进行一类宽类可区分的凸损失函数。至于平均的随机梯度下降，我们表明相同的收敛速率来自训练的早期阶段。在实验中，我们验证了对$ L_2 $调查的逻辑回归的分析。

我们介绍并分析新的一阶优化算法系列，它概括并统一镜像血统和双平均。在该系列的框架内，我们定义了用于约束优化的新算法，这些算法结合了镜像血统和双平均的优点。我们的初步仿真研究表明，这些新算法在某些情况下显着优于可用方法。

成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型，并且通过双下降现象和通过优化景观的结构特性，从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功，但也众所周知，这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下，它们在扰动输入（鲁棒泛化）上的性能也会比良性输入（标准概括）的最佳可达到的性能更糟糕。因此，必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中，我们将通过专注于随机特征回归模型（具有随机第一层权重的两层神经网络）来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度，其中样本量，输入维度和参数的数量彼此成比例地生长，并且当模型发生前列地训练时，可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果，表明对于普遍训练的随机特征模型，高度公正化可能会损害鲁棒泛化。