Heavy-Ball型动量方法的最优个体收敛速率

动量方法作为一种加速技巧被广泛用于提高一阶梯度优化算法的收敛速率.目前,大多数文献所讨论的动量方法仅限于Nesterov提出的加速方法,而对Polyak提出的Heavy-ball型动量方法的研究却较少.特别,在目标函数非光滑的情形下,Nesterov加速方法具有最优的个体收敛性,并在稀疏优化问题的求解中具有很好的效果.但对于Heavy-ball型动量方法,目前仅仅获得了平均输出形式的最优收敛速率,个体收敛是否具有最优性仍然未知.对于非光滑优化问题,通过巧妙地设置步长,证明了Heavy-ball型动量方法具有最优的个体收敛速率,从而说明了Heavy-ball型动量方法可以将投影次梯度方法的个体收敛速率加速至最优.作为应用,考虑了l\\-1范数约束的hinge损失函数优化问题.通过与同类的优化算法相比,实验验证了该理论分析的正确性以及所提算法在保持稀疏性方面的良好性能.     

线性插值投影次梯度方法的最优个体收敛速率

投影次梯度算法(projected subgradient method, PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在对偶平均方法(dual averaging method, DAM)的迭代中嵌入一种线性插值操作,得到一种拟单调的求解非光滑问题的次梯度方法,并证明了在一般凸情形下具有个体最优收敛速率,但其讨论仅限于对偶平均方法.通过使用相同技巧,提出了一种嵌入线性插值操作的投影次梯度方法,与线性插值对偶平均方法不同的是,所提方法还对投影次梯度方法本身进行了适当的修改以确保个体收敛性.同时证明了该方法在一般凸情形下可以获得个体最优收敛速率,并进一步将所获结论推广至随机方法情形.实验验证了理论分析的正确性以及所提算法在保持实时稳定性方面的良好性能.     

机器学习随机优化方法的个体收敛性研究综述

随机优化方法是求解大规模机器学习问题的主流方法,其研究的焦点问题是算法是否达到最优收敛速率与能否保证学习问题的结构。目前,正则化损失函数问题已得到了众多形式的随机优化算法,但绝大多数只是对迭代进行 平均的输出方式讨论了收敛速率,甚至无法保证最为典型的稀疏结构。与之不同的是,个体解能很好保持稀疏性,其最优收敛速率已经作为open问题被广泛探索。另外,随机优化普遍采用的梯度无偏假设往往不成立,加速方法收敛界中的偏差在有偏情形下会随迭代累积,从而无法应用。本文对一阶随机梯度方法的研究现状及存在的问题进行综述,其中包括个体收敛速率、梯度有偏情形以及非凸优化问题,并在此基础上指出了一些值得研究的问题。     

基于AdaGrad的自适应NAG方法及其最优个体收敛性

与梯度下降法相比,自适应梯度下降方法(AdaGrad)利用过往平方梯度的算数平均保存了历史数据的几何信息,在处理稀疏数据时获得了更紧的收敛界.另一方面,Nesterov加速梯度方法(Nesterov's accelerated gradient,NAG)在梯度下降法的基础上添加了动量运算,在求解光滑凸优化问题时具有数量...     

梯度有偏随机DA优化方法的个体收敛界分析

样本不满足独立同分布会使梯度估计在迭代过程中存在偏差,且最优的个体收敛界在噪声的干扰下无法确定。为此,提出一种线性插值随机对偶平均(DA)优化方法。给出DA方法收敛性的证明,在梯度估计有偏的基础上,求解得到一种线性插值DA随机优化方法不产生累积偏差的个体收敛界,以保证正则化损失函数结构下优化方法的个体收敛精度。实验结果表明,与随机加速方法相比,该方法具有较快的个体收敛速率与较高的收敛精度。     

基于AdaGrad+的自适应Heavy-Ball动量法及其最优个体收敛性

自适应策略与动量法是提升优化算法性能的常用方法。目前自适应梯度方法大多采用AdaGrad型策略，但该策略在约束优化中效果不佳，为此，研究人员提出了更适用于处理约束问题的AdaGrad+方法，但其与SGD一样在非光滑凸情形下未达到最优个体收敛速率，结合NAG动量也并未达到预期的加速效果。针对上述问题，文中将AdaGrad+调整步长的策略与Heavy-Ball型动量法加速收敛的优点相结合，提出了一种基于AdaGrad+的自适应动量法。通过设置加权动量项、巧妙选取时变参数和灵活处理自适应矩阵，证明了该方法对于非光滑一般凸问题具有最优个体收敛速率。最后在l_∞∞范数约束下，通过求解典型的hinge损失函数优化问题验证了理论分析的正确性，通过深度卷积神经网络训练实验验证了该方法在实际应用中也具有良好性能。     

多个体网络分布式随机投影无梯度优化算法

研究了有向多个体网络的无梯度优化问题,提出了一种分布式随机投影无梯度优化算法。假定网络的优化目标函数可分解成所有个体的目标函数之和,每个个体仅知其自身的目标函数及其自身的状态约束集。运用无梯度方法解决了因个体目标函数可能非凸而引起的次梯度无法计算问题,并结合随机投影算法解决了约束集未知或约束集投影运算受限的问题。在该算法作用下,所有个体状态几乎必然收敛到优化集内,并且网络目标函数得到最优。     

无线传感网络中速率效用与链路能耗的联合优化

针对能量受限的无线传感网络,提出了一种基于功率相关链路容量约束的源节点速率效用与链路能耗联合优化模型。针对传统对偶次梯度算法在分布式求解时存在收敛速度慢的缺点,提出了多步加权加速梯度方法,利用过去迭代计算历史信息来加快拉格朗日乘子的更新速率,从而快速取得速率效用与链路能耗的联合优化解。仿真实验表明,所提出的加速梯度方法取得了比对偶次梯度算法更快的收敛性。     

基于AdaBelief的Heavy-Ball动量方法

同时使用动量和自适应步长技巧的自适应矩估计(Adaptive Moment Estimation,Adam)型算法广泛应用于深度学习中.针对此方法不能同时在理论和实验上达到最优这一问题,文中结合AdaBelief灵活调整步长提高实验性能的技巧,以及仅采用指数移动平均(Exponential Moving Average,EMA)策略调整步长的Heavy-Ball动量方法加速收敛的优点,提出基于AdaBelief的Heavy-Ball动量方法.借鉴AdaBelief和Heavy-Ball动量方法收敛性分析的技巧,巧妙选取时变步长、动量系数,并利用添加动量项和自适应矩阵的方法,证明文中方法对于非光滑一般凸优化问题具有最优的个体收敛速率.最后,在凸优化问题和深度神经网络上的实验验证理论分析的正确性,并且证实文中方法可在理论上达到最优收敛性的同时提高性能.     

自适应策略下Heavy-Ball型动量法的最优个体收敛速率

同时使用自适应步长和动量两种优化技巧的AMSGrad在收敛性分析方面存在比自适应步长算法增加一个对数因子的问题.为了解决该问题,文中在非光滑凸情形下,巧妙选取动量和步长参数,证明自适应策略下Heavy-Ball型动量法具有最优的个体收敛速率,说明自适应策略下Heavy-Ball型动量法兼具动量的加速特性和自适应步长对超...     

An Edge-based Stochastic Proximal Gradient Algorithm for Decentralized Composite Optimization

This paper investigates decentralized composite optimization problems involving a common non-smooth regularization term over an undirected and connected network. In the same situation, there exist lots of gradient-based proximal distributed methods, but most of them are only sublinearly convergent. The proof of linear convergence for this series of algorithms is extremely difficult. To set up the problem, we presume all networked agents use the same non-smooth regularization term, which is the circumstance for most machine learning to implement based on centralized optimization. For this scenario, most existing proximal-gradient algorithms trend to ignore the cost of gradient evaluations, which results in degraded performance. To tackle this problem, we further set the local cost function to the average of a moderate amount of local cost subfunctions and develop an edge-based stochastic proximal gradient algorithm (SPG-Edge) by employing local unbiased stochastic averaging gradient method. When the non-smooth term does not exist, the proposed algorithm could be extended to some notable primal-dual domain algorithms, such as EXTRA and DIGing. Finally, we provide a simplified proof of linear convergence and conduct numerical experiments to illustrate the validity of theoretical results.

     

A family of subgradient-based methods for convex optimization problems in a unifying framework

We propose a new family of subgradient- and gradient-based methods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objective function is non-smooth, smooth, have composite/saddle structure, or are given by an inexact oracle model. We unified the way of constructing the subproblems which are necessary to be solved at each iteration of these methods. This permitted us to analyse the convergence of these methods in a unified way compared to previous results which required different approaches for each method/algorithm. Our contribution rely on two well-known methods in non-smooth convex optimization: the mirror-descent method (MDM) by Nemirovski-Yudin and the dual-averaging method by Nesterov. Therefore, our family of methods includes them and many other methods as particular cases. For instance, the proposed family of classical gradient methods and its accelerations generalize Devolder et al.'s, Nesterov's primal/dual gradient methods, and Tseng's accelerated proximal gradient methods. Also our family of methods can partially become special cases of other universal methods, too. As an additional contribution, the novel extended MDM removes the compactness assumption of the feasible region and the fixation of the total number of iterations which is required by the original MDM in order to attain the optimal complexity.     

基于梯度投影法与随机优化算法的约束优化方法

针对带有线性等式和不等式约束的无确定函数形式的约束优化问题,提出一种利用梯度投影法与遗传算法、同时扰动随机逼近等随机算法相结合的优化方法。该方法利用遗传算法进行全局搜索,利用同时扰动随机逼近算法进行局部搜索,算法在每次进化时根据线性约束计算父个体处的梯度投影方向,以产生新个体,从而能够严格保证新个体满足全部约束条件。将上述约束优化算法应用于典型约束优化问题,其仿真结果表明了所提出算法的可行性和收敛性。     

Optimization of unconstrained problems using a developed algorithm of spectral conjugate gradient method calculation

This paper presents a numerical investigation of the spectral conjugate directions formulation for optimizing unconstrained problems. A novel modified algorithm is proposed based on the conjugate gradient coefficient method. The algorithm employs the Wolfe inexact line search conditions to determine the optimum step length at each iteration and selects the appropriate conjugate gradient coefficient accordingly. The algorithm is evaluated through several numerical experiments using various unconstrained functions. The results indicate that the algorithm is highly stable, regardless of the starting point, and has better convergence rates and efficiency compared to classical methods in certain cases. Overall, this research provides a promising approach to solving unconstrained optimization problems.     

Wei–Yao–Liu conjugate gradient projection algorithm for nonlinear monotone equations with convex constraints

In this paper, the Wei–Yao–Liu (WYL) conjugate gradient projection algorithm will be studied for nonlinear monotone equations with convex constraints, which can be viewed as an extension of the WYL conjugate gradient method for solving unconstrained optimization problems. These methods can be applied to solving large-scale nonlinear equations due to the low storage requirement. We can obtain global convergence of our algorithm without requiring differentiability in the case that the equation is Lipschitz continuous. The numerical results show that the new algorithm is efficient.     

Optimization of limited network capacity with toll settings

A non-smooth optimization model is established for determining reserve capacity of a road network with toll settings. Optimization of limited network capacity with toll settings can be formulated as a mathematical program with equilibrium constraints (MPEC). A quasi-Newton subgradient projection and contractive method (QSPC) with global convergence is proposed. Numerical calculations are conducted using an example network where good results are obtained.