非光滑凸问题投影型对偶平均优化方法的个体收敛性

对于一般凸问题,对偶平均方法的收敛性分析需要在对偶空间进行转换,难以得到个体收敛性结果.对此,文中首先给出对偶平均方法的简单收敛性分析,证明对偶平均方法具有与梯度下降法相同的最优个体收敛速率Ο(ln t√t).不同于梯度下降法,讨论2种典型的步长策略,验证对偶平均方法在个体收敛分析中具有步长策略灵活的特性.进一步,将个体收敛结果推广至随机形式,确保对偶平均方法可有效处理大规模机器学习问题.最后,在L1范数约束的hinge损失问题上验证理论分析的正确性.

一类时变有向图中的PUSH-SUM分布式对偶平均优化算法

利用push-sum通信协议并结合分布式对偶平均方法,在时变有向图中,讨论了一类带有简单约束集的分布式凸优化问题.首先提出了push-sum分布式对偶平均算法,然后分析了算法的收敛性,并得到了算法的收敛率为O(1/√T),最后用l1线性回归问题的数值结果验证了所提出算法的有效性.对比现有的一些结果,所提出的算法能用于求解带约束的分布式优化问题,并且去掉了网络通讯权矩阵是双随机的限制.

快速在线分布式对偶平均优化算法

为提高分布式在线优化算法的收敛速度,对底层网络拓扑依次添边,提出一种快速的一阶分布式在线对偶平均优化(FODD)算法。首先,对于分布式在线优化问题,运用添边方法使所选的边与网络模型快速混合,进而建立数学模型并设计FODD算法对其进行优化求解。其次,揭示了网络拓扑和在线分布式对偶平均收敛速度之间的关系,通过提高底层拓扑网络的代数连通度改进了Regret界,将在线分布式对偶平均(ODDA)算法从静态网络拓展到时变网络拓扑上,并证明了FODD算法的收敛性,同时解析地给出了收敛速度。最后的数值仿真表明:和ODDA算法相比,所提出的FODD算法具有更快的收敛速度。

对偶平均Minkowski对称度在Minkowski-临界点处的精确值（英文）

研究对偶平均Minkowski对称度的基本性质,特别地,讨论了凸体n支撑架的存在性和对偶平均Minkowski对称度函数在Minkowski-临界点处的取值。具体地,对半空间族建立了一个Helly型定理,利用此定理证明了任意凸体拥有至少一个n支撑架。文末,利用Minkowski对称度给出了凸体对偶平均对称度函数在Minkowski-临界点处的表达式。

基于AdaGrad自适应策略的对偶平均方法

AdaGrad将自适应矩阵应用到随机梯度下降法中,大大降低了工程上超参数搜索的高昂代价。AdaGrad不仅提供了优化方法自适应的研究思路,而且引领了深度学习优化方法新的研究方向,人们越来越多地考虑将自适应策略加入到优化算法的设计中去。对偶平均方法能够克服随机梯度下降法迭代后期收敛缓慢的固有弊端,并相较而言具有较高的收敛稳定性和灵活的步长策略,但自适应的对偶平均方法仍是空白。论文通过分析随机梯度下降法和对偶平均方法性能差异的本质原因,在保留对偶平均方法优势的基础上,将AdaGrad的自适应矩阵融入到方法框架中去,形成一种自适应的对偶平均方法:AdaDA,并通过一般凸函数优化分类实验验证算法的可行性与预期效果。

时滞多智能体网络中的Push-Sum分布式对偶平均算法研究

利用Push-Sum通信协议,结合分布式对偶平均方法,讨论了一类时滞多智能体网络中的分布式凸优化问题。提出了时滞的Push-Sum分布式对偶平均算法,并分析了算法的收敛性,得到算法的收敛率为O[(τ+1)~2/T^(1/2)]。这种算法可用于求解分布式优化问题,且不要求网络通讯矩阵是双随机的。

基于Bandit反馈的分布式在线对偶平均算法

为解决梯度信息难以获取的分布式在线优化问题,提出了一种基于Bandit反馈的分布式在线对偶平均(DODA-B)算法。首先,该算法对原始梯度信息反馈进行了改进,提出了一种新的梯度估计,即Bandit反馈,利用函数值信息去近似原损失函数的梯度信息,克服了求解复杂函数梯度存在的计算量大等问题。然后,给出了该算法的收敛性分析,结果表明,Regret界的收敛速度为O(Tmax{k,1-k}),其中T是最大迭代次数。最后,利用传感器网络的一个特例进行了数值模拟计算,计算结果表明,所提算法的收敛速度与现有的分布式在线对偶平均(DODA)算法的收敛速度接近。与DODA算法相比,所提出算法的优点在于只考虑了函数值信息,使其更适用于梯度信息获取困难的实际问题。

基于对偶平均的动量方法研究综述

对偶平均(dual averaging)方法是一种颇具潜力的优化算法,它巧妙地利用过往所有梯度的信息,克服了传统一阶梯度算法无法摆脱的梯度消失的弊端,并得到稳定的收敛速率。而恰恰类似的是,动量方法同样是利用过往的梯度信息,目的在于在非凸优化问题中能够有效地逃离局部最小点和鞍点,而今年来动量方法也广泛活跃在凸优化领域,不单对一般的梯度下降算法起到加速作用,同时在没有光滑性条件的情况下,得到最优个体收敛速率。论文对对偶平均方法和动量方法的研究现状和存在的问题进行综述,分析两者的联系和区别,并在此基础上指出一些值得研究的问题。

切换网络下加速分布式在线加权对偶平均算法

研究了切换网络下加速分布式在线加权对偶平均算法,提出了A-DOWDA算法。首先利用加权因子对对偶变量进行加权,其次在有向切换网络是周期强连通,且对应的邻接矩阵是随机的而非双随机的条件下,加速了算法的收敛速率,最后通过数值实验验证了算法的可行性。

对偶海伦平均、几何平均与幂平均的不等式(二)

对于任意的实数p,两正数a与b的幂平均定义如下:Mp(a,b)=(ap 2+bp)1p p≠0槡ab p={0,以下将证明:对所有a,b>0,m∈(0,32)有如下的不等式:1)当m∈(0,32)时,M log2log3(m+2)-log2(a,b)≤23 Hm(a,b)+13 G(a,b)≤M 3(m4+2)(a,b);2)当m∈[23,+∞)时,M 43(m+2)(a,b)≤32 Hm(a,b)+31 G(a,b)≤M log3(mlo+g22)-log2(a,b)。其中当且仅当a=b时,等号成立,同时参数23(m+2),l og3(m l+o g22)-log2对于不等式是最优的临界值。给予两正数a,b的海伦平均,几何平均分别如下:Hm=a+bm++m 2槡ab,G(a,b)=槡ab。

对偶海伦平均、几何平均与幂平均的不等式(一)

对于任意的实数p,两正数a与b的幂平均定义如下:Mp(a,b)=(ap 2+bp)1p

关于二元幂平均的一个不等式

用控制的方法建立了一个有关二元幂平均的具有双参数的不等式,它给出涉及对偶Heron平均的一个不等式的推广和加细,最后提出了一个相关的猜想。

基于AdaGrad自适应DA方法的最优个体收敛速率

针对AdaGrad将自适应矩阵应用到随机梯度下降法中降低工程上超参数搜索的问题,提出一种自适应对偶平均方法。将AdaGrad自适应矩阵引入到对偶平均方法框架中,形成自适应的对偶平均方法,并通过凸优化实验验证其可行性和收敛效果。数学推导结果表明:对于非光滑条件下的一般凸函数AdaDA方法可以达到与维数相关O(1/√t)的最优个体收敛速率,为其提供了理论支撑。

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

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

基于对偶犹豫模糊几何Heronian平均算子的多属性决策方法及其应用

针对需要同时考虑变量隶属度、非隶属度以及关联性的融合问题,本文将对偶犹豫模糊集与Heronian平均算子相结合,定义了对偶犹豫模糊几何Heronian平均算子和对偶犹豫模糊几何加权Heronian平均算子,讨论了新算子的一些优良特性,包括幂等性、置换不变性、有界性、单调性等性质,并针对属性值为对偶犹豫模糊语言信息关联系的多属性决策问题,建立了基于对偶犹豫模糊几何加权Heronian平均算子的多属性决策模型,基于所定义的算子和建立的数学模型,提出了一种新的基于对偶犹豫模糊Heronian平均算子的多属性决策方法。最后,通过多属性决策算例验证了方法的有效性和可行性。

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

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