在本文中，我们考虑了第一和二阶技术来解决机器学习中产生的连续优化问题。在一阶案例中，我们提出了一种从确定性或半确定性到随机二次正则化方法的转换框架。我们利用随机优化的两相性质提出了一种具有自适应采样和自适应步长的新型一阶算法。在二阶案例中，我们提出了一种新型随机阻尼L-BFGS方法，该方法可以在深度学习的高度非凸起背景下提高先前的算法。这两种算法都在众所周知的深度学习数据集上进行评估并表现出有希望的性能。

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

We introduce SketchySGD, a stochastic quasi-Newton method that uses sketching to approximate the curvature of the loss function. Quasi-Newton methods are among the most effective algorithms in traditional optimization, where they converge much faster than first-order methods such as SGD. However, for contemporary deep learning, quasi-Newton methods are considered inferior to first-order methods like SGD and Adam owing to higher per-iteration complexity and fragility due to inexact gradients. SketchySGD circumvents these issues by a novel combination of subsampling, randomized low-rank approximation, and dynamic regularization. In the convex case, we show SketchySGD with a fixed stepsize converges to a small ball around the optimum at a faster rate than SGD for ill-conditioned problems. In the non-convex case, SketchySGD converges linearly under two additional assumptions, interpolation and the Polyak-Lojaciewicz condition, the latter of which holds with high probability for wide neural networks. Numerical experiments on image and tabular data demonstrate the improved reliability and speed of SketchySGD for deep learning, compared to standard optimizers such as SGD and Adam and existing quasi-Newton methods.

We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch. Despite using second-order information, these existing methods do not exhibit superlinear convergence, unless the stochastic noise is gradually reduced to zero during the iteration, which would lead to a computational blow-up in the per-iteration cost. We propose to address this limitation with Hessian averaging: instead of using the most recent Hessian estimate, our algorithm maintains an average of all the past estimates. This reduces the stochastic noise while avoiding the computational blow-up. We show that this scheme exhibits local $Q$-superlinear convergence with a non-asymptotic rate of $(\Upsilon\sqrt{\log (t)/t}\,)^{t}$, where $\Upsilon$ is proportional to the level of stochastic noise in the Hessian oracle. A potential drawback of this (uniform averaging) approach is that the averaged estimates contain Hessian information from the global phase of the method, i.e., before the iterates converge to a local neighborhood. This leads to a distortion that may substantially delay the superlinear convergence until long after the local neighborhood is reached. To address this drawback, we study a number of weighted averaging schemes that assign larger weights to recent Hessians, so that the superlinear convergence arises sooner, albeit with a slightly slower rate. Remarkably, we show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage, and still exhibits a superlinear convergence rate nearly (up to a logarithmic factor) matching that of uniform Hessian averaging.

We propose a trust-region stochastic sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with stochastic objectives and deterministic equality constraints. We consider a fully stochastic setting, where in each iteration a single sample is generated to estimate the objective gradient. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to employ indefinite Hessian matrices (i.e., Hessians without modification) in SQP subproblems. As a trust-region method for constrained optimization, our algorithm needs to address an infeasibility issue -- the linearized equality constraints and trust-region constraints might lead to infeasible SQP subproblems. In this regard, we propose an \textit{adaptive relaxation technique} to compute the trial step that consists of a normal step and a tangential step. To control the lengths of the two steps, we adaptively decompose the trust-region radius into two segments based on the proportions of the feasibility and optimality residuals to the full KKT residual. The normal step has a closed form, while the tangential step is solved from a trust-region subproblem, to which a solution ensuring the Cauchy reduction is sufficient for our study. We establish the global almost sure convergence guarantee for TR-StoSQP, and illustrate its empirical performance on both a subset of problems in the CUTEst test set and constrained logistic regression problems using data from the LIBSVM collection.

随机梯度下降方法及其变体构成了实现机器学习问题的良好收敛速率的核心优化算法。尤其获得这些速率，特别是当这些算法用于手头的应用程序进行微调时。虽然这种调整过程可能需要大的计算成本，但最近的工作表明，通过线路搜索方法可以减少这些成本，可以迭代调整步骤。我们通过使用基于前向步骤模型建筑的新算法提出了一种替代方法来转移到随机线路搜索。该模型构建步骤包含了二阶信息，允许不仅调整步骤，还可以调整搜索方向。注意到深度学习模型参数分组（张量层），我们的方法构建其模型，并计算每个参数组的新步骤。这种新颖的对角化方法使所选择的步长自适应。我们提供收敛率分析，并通过实验表明，在大多数问题中，所提出的算法在大多数问题中实现更快的收敛性和更好的概括。此外，我们的实验表明，该方法的方法非常强大，因为它会收敛于各种初始步骤。

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

Is it possible for a first-order method, i.e., only first derivatives allowed, to be quadratically convergent? For univariate loss functions, the answer is yes -- the Steffensen method avoids second derivatives and is still quadratically convergent like Newton method. By incorporating an optimal step size we can even push its convergence order beyond quadratic to $1+\sqrt{2} \approx 2.414$. While such high convergence orders are a pointless overkill for a deterministic algorithm, they become rewarding when the algorithm is randomized for problems of massive sizes, as randomization invariably compromises convergence speed. We will introduce two adaptive learning rates inspired by the Steffensen method, intended for use in a stochastic optimization setting and requires no hyperparameter tuning aside from batch size. Extensive experiments show that they compare favorably with several existing first-order methods. When restricted to a quadratic objective, our stochastic Steffensen methods reduce to randomized Kaczmarz method -- note that this is not true for SGD or SLBFGS -- and thus we may also view our methods as a generalization of randomized Kaczmarz to arbitrary objectives.

我们引入了一种降低尺寸的二阶方法（DRSOM），用于凸和非凸的不受约束优化。在类似信任区域的框架下，我们的方法保留了二阶方法的收敛性，同时仅在两个方向上使用Hessian-Vector产品。此外，计算开销仍然与一阶相当，例如梯度下降方法。我们证明该方法的复杂性为$ O（\ epsilon^{ - 3/2}）$，以满足子空间中的一阶和二阶条件。DRSOM的适用性和性能通过逻辑回归，$ L_2-L_P $最小化，传感器网络定位和神经网络培训的各种计算实验展示。对于神经网络，我们的初步实施似乎在训练准确性和迭代复杂性方面与包括SGD和ADAM在内的最先进的一阶方法获得了计算优势。

鉴于Vanilla SGD的直接简单，本文在迷你批处理箱中提供了精细调整其阶梯尺寸。为了这样做，基于局部二次模型并仅使用嘈杂的梯度近似来估计曲率。一个人获得一种新的随机第一阶方法（步骤调谐的SGD），由二阶信息增强，这可以被视为古典Barzilai-Borwein方法的随机版本。我们的理论结果确保了几乎肯定的趋同集，我们提供了收敛速率。深度剩余网络培训的实验说明了我们方法的有利性质。对于我们在培训期间观察到的网络，突然下降的损失和中等阶段的测试精度的提高，产生比SGD，RMSPROP或ADAM更好的结果。

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

我们分析了一类养生问题，其中高级问题在于平滑的目标函数的最小化和下层问题是找到平滑收缩图的固定点。这种类型的问题包括元学习，平衡模型，超参数优化和数据中毒对抗性攻击的实例。最近的几项作品提出了算法，这些算法温暖了较低级别的问题，即他们使用先前的下级近似解决方案作为低级求解器的凝视点。这种温暖的启动程序使人们可以在随机和确定性设置中提高样品复杂性，在某些情况下可以实现订单的最佳样品复杂性。但是，存在一些情况，例如元学习和平衡模型，其中温暖的启动程序不适合或无效。在这项工作中，我们表明没有温暖的启动，仍然可以实现订单的最佳或近乎最佳的样品复杂性。特别是，我们提出了一种简单的方法，该方法在下层下使用随机固定点迭代，并在上层处预测不精确的梯度下降，该梯度下降到达$ \ epsilon $ -Stationary Point，使用$ O（\ Epsilon^{-2） }）$和$ \ tilde {o}（\ epsilon^{ - 1}）$样本分别用于随机和确定性设置。最后，与使用温暖启动的方法相比，我们的方法产生了更简单的分析，不需要研究上层和下层迭代之间的耦合相互作用

本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的，我们专注于适合高维优化的方法。我们在二次模型上构建直觉，以确定哪种方法适用于非凸优化，并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础，我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外，最后一章还提供了对更多理论方法的广泛审查，这在实践中并不像惯例。所以在某些情况下，这项工作试图回答这个问题：为什么默认值中包含的默认TensorFlow优化器？

我们应用随机顺序二次编程（STOSQP）算法来求解受约束的非线性优化问题，在该问题是随机的，并且约束是确定性的。我们研究了一个完全随机的设置，其中每次迭代中只有一个样本可用于估计物镜的梯度和黑森州。我们允许stosqp选择一个随机架子$ \ bar {\ alpha} _t $适应性，使得$ \ beta_t \ leq \ leq \ bar {\ alpha} _t \ leq \ leq \ beta_t+beta_t+\ chi_t+\ chi_t $，wither = o（\ beta_t）$是预定的确定性序列。我们还允许STOSQP通过随机迭代求解器（例如，使用草图和项目方法）求解牛顿系统。而且我们不需要不精确的牛顿方向的近似误差即可消失。对于这个一般的STOSQP框架，我们建立了其最后一次迭代的渐近收敛速率，最差的案例迭代复杂性是副产品。我们执行统计推断。特别是，有了适当的衰减$ \ beta_t，\ chi_t $，我们表明：（i）STOSQP方案最多可以采用$ o（1/\ epsilon^4）$ iterations $ iterations $ iTerations以实现$ \ epsilon $ -Stationarity; （ii）几乎毫无疑问，$ \ |（x_t -x^\ star，\ lambda_t- \ lambda^\ star）\ | | = o（\ sqrt {\ beta_t \ log（1/\ beta_t）}）+o（\ chi_t/\ beta_t）$，其中$（x_t，\ lambda_t）$是primal-dimal-dimal-dialal-dialal-dialal-dual stosqp itselmate; （iii）序列$ 1/\ sqrt {\ beta_t} \ cdot（x_t -x^\ star，\ lambda_t- \ lambda_t- \ lambda^\ star）$收敛到平均零高斯分布，具有非琐事的共价矩阵。此外，我们建立了$（x_t，\ lambda_t）$的Berry-Esseen，以定量地测量其分布功能的收敛性。我们还为协方差矩阵提供了实用的估计器，可以使用iTerates $ \ {（x_t，\ lambda_t）\} _ t $构建$（x^\ star，\ lambda^\ star）$的置信区间（x^\ star，\ lambda^\ star）$。我们的定理使用最可爱的测试集中的非线性问题验证。

简单的随机动量方法被广泛用于机器学习优化，但它们的良好实践表现与文献中没有理论保证的理论保证相矛盾。在这项工作中，我们的目标是通过表明随机重球动量来弥合理论和实践之间的差距，该动力可以解释为具有动量的随机kaczmarz算法，保留了二次优化问题（确定性）重球动量的快速线性速率，至少在使用足够大的批次大小的小型匹配时。该分析依赖于仔细分解动量过渡矩阵，并使用新的光谱范围浓度界限来进行独立随机矩阵的产物。我们提供数值实验，以证明我们的边界相当锐利。

我们考虑使用梯度下降来最大程度地减少$ f（x）= \ phi（xx^{t}）$在$ n \ times r $因件矩阵$ x $上，其中$ \ phi是一种基础平稳凸成本函数定义了$ n \ times n $矩阵。虽然只能在合理的时间内发现只有二阶固定点$ x $，但如果$ x $的排名不足，则其排名不足证明其是全球最佳的。这种认证全球最优性的方式必然需要当前迭代$ x $的搜索等级$ r $，以相对于级别$ r^{\ star} $过度参数化。不幸的是，过度参数显着减慢了梯度下降的收敛性，从$ r = r = r = r^{\ star} $的线性速率到$ r> r> r> r> r^{\ star} $，即使$ \ phi $是$ \ phi $强烈凸。在本文中，我们提出了一项廉价的预处理，该预处理恢复了过度参数化的情况下梯度下降回到线性的收敛速率，同时也使在全局最小化器$ x^{\ star} $中可能不良条件变得不可知。

广义自我符合是许多重要学习问题的目标功能中存在的关键属性。我们建立了一个简单的Frank-Wolfe变体的收敛速率，该变体使用开环步数策略$ \ gamma_t = 2/（t+2）$，获得了$ \ Mathcal {o}（1/t）$收敛率对于这类功能，就原始差距和弗兰克 - 沃尔夫差距而言，$ t $是迭代计数。这避免了使用二阶信息或估计以前工作的局部平滑度参数的需求。我们还显示了各种常见病例的收敛速率的提高，例如，当所考虑的可行区域均匀地凸或多面体时。

在机器学习中，随机梯度下降（SGD）被广泛部署到使用具有同样复杂噪声模型的高度非凸目标的训练模型。不幸的是，SGD理论通常会做出限制性的假设，这些假设无法捕获实际问题的非跨性别，并且几乎完全忽略了实践中存在的复杂噪声模型。在这项工作中，我们在这一缺点上取得了长足的进步。首先，我们确定SGD的迭代将在几乎任意的非概念和噪声模型下全球收敛到固定点或分歧。在对文献中当前假设的非跨性别和噪声模型的共同行为的限制性稍微限制性的假设下，我们表明，即使迭代分歧，目标函数也无法分歧。由于我们的结果，可以将SGD应用于更大范围的随机优化问题，并在其全球收敛行为和稳定性上充满信心。

本文研究了关于Riemannian流形的大规模优化问题，其目标函数是负面概要损失的有限总和。这些问题在各种机器学习和信号处理应用中出现。通过在歧管环境中引入Fisher信息矩阵的概念，我们提出了一种新型的Riemannian自然梯度方法，可以将其视为自然梯度方法的自然扩展，从欧几里得环境到歧管设置。我们在标准假设下建立了我们提出的方法的几乎纯净的全球融合。此外，我们表明，如果损失函数满足某些凸度和平稳性条件，并且输入输出图满足了雅各布稳定条件，那么我们提出的方法享有局部线性 - 或在Riemannian jacobian的Lipschitz连续性下，输入输出图，甚至二次 - 收敛速率。然后，我们证明，如果网络的宽度足够大，则可以通过具有批归归量的两层完全连接的神经网络来满足Riemannian Jacobian稳定性条件。这证明了我们的收敛率结果的实际相关性。对机器学习产生的应用的数值实验证明了该方法比最先进的方法的优势。

我们研究了使用尖刺，现场依赖的随机矩阵理论研究迷你批次对深神经网络损失景观的影响。我们表明，批量黑森州的极值值的大小大于经验丰富的黑森州。我们还获得了类似的结果对Hessian的概括高斯牛顿矩阵近似。由于我们的定理，我们推导出作为批量大小的最大学习速率的分析表达式，为随机梯度下降（线性缩放）和自适应算法（例如ADAM（Square Root Scaling）提供了通知实际培训方案，例如光滑，非凸深神经网络。虽然随机梯度下降的线性缩放是在我们概括的更多限制性条件下导出的，但是适应优化者的平方根缩放规则是我们的知识，完全小说。随机二阶方法和自适应方法的百分比，我们得出了最小阻尼系数与学习率与批量尺寸的比率成比例。我们在Cifar-$ 100 $和ImageNet数据集上验证了我们的VGG / WimerEsnet架构上的索赔。根据我们对象检的调查，我们基于飞行学习率和动量学习者开发了一个随机兰齐齐竞争，这避免了对这些关键的超参数进行昂贵的多重评估的需求，并在预残留的情况下显示出良好的初步结果Cifar的architecure - $ 100 $。