摘
机器学中数值优化问题考虑规模维数较传统方法难高效解决问题年针规模机器学问题做研究较重类方法 机算法优化方法分阶梯度方法二阶牛顿方法两类针阶方法改进研究较成熟完善阶方法分两类原始方法偶方法原始方法较代表性SAGSAGASVRG偶方法SDCASPDC两种外加速方法CatalystKatyusha收敛速度阶方法达结果二阶方法目前机器学领域研究重方收敛速度优阶方法实践中会难度较实LBFGS方法机算法改进
文详细全面叙述机器学中种机算法介绍机算法发展历程研究方研究热点通数值试验较种常见机算法读者直观数值效果
关键词：规模机器学机算法优化方法
Stochastic Optimization Algorithm in Machine Learning
Abstract
For the optimization problem in machine learning field traditional method have difficulties in solving the high dimension and big data problem In recent years there are many researches in large scale machine learning problems especially stochastic algorithms Generally stochastic method can divided into two parts One is firstorder gradient method and the other is second order Newton method There is more improvement and research in first order method and the first order method is more mature and perfect There is two classes for first order method For the primal class SVRGSAGSAGA is the representation and SDCA SPDC for dual class Otherwise the acceleration method such as catalyst and katyusha which has the optimal con vergence speed for first order method is put forward in last two years Second order method is one important research area and it has better convergence but not better performance because it has to compute the hessian matrix one useful method is LBFGS and its variants
In this paper the author will introduce stochastic algorithms in machine learning area in detail In the end numerical experiments compare some common algorithm and give a direct view to readers
Key Words Largescale machine learning problemStochastic algorithmOptimization method
目 录
摘
I
Abstract
II
引 言
1
1 基础知识
5
2 阶方法
6
21 梯度降法（Gradient Descent）
6
22 机梯度方法（Stochastic Gradient Method）
7
23 方差减方法（Variance Reduction Method)
10
231机均梯度方法(StochasticAverage Gradient)
11
232 机方差减梯度方法(Stochastic Variance Reduction Gradient)
12
233 SAGA
13
24 机偶坐标升法（Stochastic Dual Coordinate Ascent）
14
25 机原始偶坐标法（Stochastic Primal Dual Coordinate）
16
26 加速方法Catalyst
19
27 Katyusha
20
3 二阶方法
22
31 牛顿法拟牛顿法
22
311 SR1
23
312 BFGSDFP
23
32 LimitedmemoryBFGS
24
33 机牛顿方法
25
4 数值实验
27
参考文献
29
致 谢
31
引 言
年着科学技术断进步发展尤计算机通信等领域进步互联网断普产生数速率提高时够容易廉价获取存储数数中蕴含量信息量数中发掘出效信息困难问题解决该问题尝试采种方式中较处理方式机器学数理统计方法
机器学利数建立模型进行预测中常见方法问题转化成优化模型进求解目标函数然数时代数数量数维数较高更效处理挖掘数仅断改进发展计算机硬件断改进机器学算法效率提高机器学算方法效率更赖数值优化算法改进必规模机器学中优化算法进行总结文力求详细全面现机器学中优化方法做概述学总结
定训练数集T {(x1 y1) (x2 y2) (xN yN)}机器学策略求验风
险损失模型常见验风险损失模型
Σ
min F(x) + g(x) 1 n
fi(x)
x∈ℜd
n i1
中 fi(x) ℜd → ℜ 凸光滑损失函数 fi样密切相关n代表着样数
然样容量时容易产生拟合现象防止拟合常验
风险加表示模型复杂度正化项惩罚项称结构风险损失函数
Σ
min F(x) + g(x) 1 n
fi(x) + g(x)
x∈ℜd
n i1
中 fi(x) ℜd → ℜ 凸光滑损失函数 fi样密切相关n代表着样数g(x) ℜd → ℜ正化函数通常凸函数
种形式问题机器学中着广应许机器学方法结成求形式优化问题：
线性支持量机转化成求优化问题[1][2][3]
Σ
min P(x) 1 n
λ
[1 − bi(aT x)] + ‖x‖2
x n i1
i + 2
中[a]+ max{0 a}
逻辑回结解决述优化问题[2][3]：
min P(x) 1 n log(1 + e−biaT x) + λ‖x‖2
x n
Σi1
i 2 2
LASSO转化成求解优化问题[2][3]：
min P(x) 1 Σn
(ai x − bi)2 + 1 ‖x‖2
x 2n
i1 2 1
解决问题难点优化变量维数d样数n较时求解 问题需非常计算量存储存种规模优化问题较常见方 法分批处理方法机算法批处理方法包括全梯度降方法拟牛顿LBFGS方法机方法机梯度降法（SGD）种算法改进机方差降梯度方法(SVRG)机均梯度方法(SAG)机偶坐标升法（SDCA）机原始偶坐标方法（SPDC）
梯度降法种线搜索方法[4]次迭代选择该点负梯度方作搜索方 负梯度方快降方称速降法仅利函数梯度信息称阶方法梯度方法次迭代方负梯度方
xk 1 xk − αkgk xk − αk Σn
∇ fi(xk)
+ n i1
收敛速度O(1n)种次线性迭代算法
种加速梯度算法AGD[4][5]形：
xk+1 xk + θ(xk − xk−1) − αk f ′(xk + θ(xk − xk−1))
收敛速度O(1n2)目标函数强凸函数时收敛速度线性收敛速度
梯度降方法需需计算n梯度计算量O(nd)nd时计算 量存储空间更实改进次迭代时机选择点计算梯度进行更新SGD形式[6][7]：
xk+1 xk − αk∇ fik (xk)
n
i1
需满足E[∇ fik (xk)|xk−1] 1 Σn ∇ fi(xk)改进处次迭代计算
n
量标准梯度降法1 机梯度降法(SGD)机量g(xk εk)函数全梯
度偏估计满足
E[F(x
) − α g(x ε ))] ≤ f (x ) − (α
α2L
− 2 2 2
α * L2) ‖ ∇F(x ) ‖ + E[g(x ε ) − F(x )]
k+1
k k k
k k k
k 2 2 k k k
式等号右边第二项预期误差第三项称方差方差存SGD需采变步长方式保证算法收敛方差存导致算法性足果够改进算法方差断减直零较代表性方差减方法三种分称SVRG[8]SAG[9][10]SAGA[11]三种方法更 新方式：
f ′ (xk) − f ′ (φk) 1 ′
j
xk 1 xk − α[
j j +
Σn f (φk)] (S AG)
+ n n
i1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (φk) 1 n f ′ (φk)] (S AGA)
+ j j j + n Σi1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (x) +
1 Σn
f ′ (x)] (S VRG)
+ j j ̃︀ n i1 i ̃︀
SAG[9]早提出具线性收敛速度机梯度方法次更新赖n
SAGA成结合SAGSVRG两种方法技巧提出新算法SVRG收敛
速度相适非强凸问题SVRG着良性质适非凸函数
外类较实方法机偶方法SDCA[12]SPDC[13]SDCA 原始问题转化偶形式采机坐标思想机选择偶坐标断求极直优值SPDC 原问题转化鞍点问题通交化原始变量化偶变量求鞍点正文中继续介绍着两种方法
牛顿方法[14]利函数二阶信息种优化方法现实中常常种似 牛顿方法拟牛顿法机器学领域中较常LBFGS拟牛顿方法 方法优值附达次线性收敛速度迭代格式：
xk+1 xk − αkHk∇Fk
中αk步长HkHessian阵逆种似更新方式：
Hk+1 VT HkVk + ρkyk sT
k k
k
yT sk
k
中ρk 1 Vk I − ρkyk sT sk xk+1 − xk yk ∇ fk+1 − ∇ fk
二阶方法计算中复杂度较高二阶方法改进存定难度关
二阶机方法工作较限正文介绍种改进算法
接第章介绍相关数学知识背景第二章分阶算法进行介绍第三章二阶算法做介绍第四章通实验优化算法
1基础知识
定义 1 LLipshistz连续 称函数f ℜd → ℜLLipschitz连续函数 L > 0 果
∀a b ∈ ℜd均
| f (a) − f (b)| ≤ L|a − b|
定义 2 γ 光滑称函数f ℜd → ℜγ−光滑函数γ > 0果意∀a b ∈ ℜd均
2
f (b) ≤ f (a) + ⟨∂ f (a) T (b − a)⟩ + γ‖b − a‖2
定义 3 凸函数 称函数f ℜd → ℜ凸函数果意∀a b ∈ ℜd均
f (b) ≥ f (a) + ⟨∂ f (a) T (b − a)⟩
定义 4 µ−强凸函数 称连续微函数f ℜd → ℜµ−强凸函数µ > 0果
意∀a b ∈ ℜd均
2
f (b) ≥ f (a) + ⟨∂ f (a) T (b − a)⟩ + µ‖b − a‖2
定义 5 条件数 果连续微函数f ℜd → ℜγ−光滑函数µ−强凸函数记
γ
κ
µ
称κ原函数条件数
定义 6 值点
∙ 点x*称局部值点果存x*领域N意x ∈ N均f (x) ≥ f (x*)
∙ 点x*称严格值点（强值点）果存x*领域N意x ∈
Nx Ç x*均f (x) > f (x*)
定理 1 阶必性条件果x*值点函数f x*开领域连续微
∇ f (x*) 0
定理 2 果函数f 凸函数意局部值点均全局值点外函数微时x满足∇ f (x) 0点均全局值点
2阶方法
21 梯度降法（Gradient Descent）
梯度降法种线搜索方法次迭代选择该点负梯度方作搜索方 负梯度方快降方称速降法仅利函数梯度信息称阶方法形式非常直观简单次迭代选择负梯度方作降方更新形式：
xk 1 xk − αkgk xk − αk Σn
∇ fi(xk)
+ n i1
中αk步长学率准确定Wolfe准Armijo准等
L
函数F凸函数梯度L − Lipshitz函数时取α 1 时收敛速度
达O(1k)[5]
f (xk) − f (x*) ≤
2L ‖ x0 − x* ‖2
2
k + 4
进步Fµ−强凸梯度L − lipshitz函数时收敛速度线性收敛[5]：
f (xk) − f (x*) ≤ L ( L − µ)2k ‖ x0 − x* ‖2
2 L + µ
Nesterov证明阶方法理优界[4][5]采种加速方法梯度降算法进行改进称Nesterov加速称算法加速梯度降算法（AGD）种常AGD 迭代方式：
xk+1 yk − αk f ′(yk)
yk+1 xk+1 + θ(xk+1 − xk)
L
函数F凸函数梯度L − Lipshitz函数时果αk
√ 2
2
µ)
速度
1 θ
√ √
L− µ
√L+ √µ 收敛
L
(2
zzzzzzzf (xk) − f (x*) ≤ min{(1 − √︂µ)k
√
4L
L + k
} * [ f (x0) − f (x*) + µ ‖ x0 − x* ‖2]
述收敛速度非强凸函数强凸函数适合函数非强凸时取µ0通 迭代格式出迭代时仅涉量加减数运算次迭代计算复杂度O(nd)
然步梯度降方法需需计算n梯度计算量O(nd)nd 时计算量存储空间改进梯度算法适规模机器学优化问题特数爆炸天成意义问题
然步梯度降方法需需计算n梯度计算量O(nd)nd 时计算量存储空间改进梯度算法适规模机器学优化问题特数爆炸天成意义问题
种较常见方法确定性提升梯度方法(deterministic incremental gradient
0
method)[15]称IGIG方法标准梯度降方法非常相似n函数形式目标函数区IG方法变量着中函数梯度方循环更新 具体成着两层循环算法次外层迭代成m次层迭代循环令初始点x0 ∈ ℜn意k > 0更新方式
x(k) x(k)
− αk∇ fi(x )
(k)
i i−1
中αk > 0代表着步长x(k+1) xk
i−1
0 n
IG方法性取决循环中迭代序果某具体问题果存已 知信息确定出迭代序σ(1 n 排列)IG方法性
x(k) x(k)
− αk∇ fσ
(x(k) )
i i−1
(i)
i−1
然现实中先验信息难获更倾采机采样方法
更新方法称机梯度方法(stochastic gradient method)者称Robbins
Monro[7] 算法
22 机梯度方法（Stochastic Gradient Method）
机梯度方法(SG)迭代程目标函数初始点步长等素唯决定程机标准梯度方法次迭代根某分布ε机选择 样点更新目标变量中种SG方法机梯度降算法(stochastic gradient
descent)SGD保证目标函数相邻两次迭代定降期意义
降算法[6][7]：
x(k+1) x(k) − αk∇ fik (x(k))
n
i1
满足Eε[∇ fik (x(k))] 1 Σn ∇ fi(x(k)) ∇F(x(k))
n
轮迭代计算量标准梯度法1 仅O(d)步长断减保证目标函数收敛优值点理SG做进步认识已知 结[16]考虑更般形式(SG)算法1
Algorithm 1 SG
选择初始点x1
for t12 m do
生成机变量εk 计算机量g(xk εk) 确定步长αk
−
更新： xK+1 xK αkg(xk εk)
end for
引理 1 果函数F(x)L光滑函数算法1满足等式意k ∈ N：
Eεk [F(xk+
1)] − F(xk) ≤ −αk∇F(xk)T E
[g(xk εk)] + 1 α2LE [‖ g(xk εk) ‖2]
εk 2 k εk 2
假设 1 目标函数SG(算法1)满足条件
(1) 函数F界序列{xk}开集中
(2) 存µG ≥ µ > 0意k ∈ N
∇F(xk)T Eε [g(xk εk)] ≥ µ ‖ ∇F(xk) ‖2
k 2
‖ Eεk [g(xk εk)] ‖2≤ µG ‖ ∇F(xk) ‖2
(3) 存M ≥ 0Mv ≥ 0意k ∈ N
k
2
Vε [g(xk sk)] ≤ M + Mv ‖ ∇F(xk) ‖2
引理 2 果函数F(x)LLipschitz函数满足假设1意k ∈ N满足等
式
E [F(x
1
+ α
)] − F(x ) ≤ −α ∇F(x )T E [g(x ε )] 2 LE
[‖ g(x ε ) ‖2]
εk k+1
k k k εk k k
2 k εk
k k 2
≤ −(µ − 1 αkLMG)αk ‖ ∇F(xk) ‖2 1 2 LM
2 2 + 2 αk
定理 3 果函数FLLipschitz连续函数µ−强凸函数假设算法1中步长固定
意k ∈ N均αk α µ
G
0 < α < LM
意k ∈ N等式：
E[F(xk) − F(x*)] ≤ αLM + (1 − αcµ)k−1(F(x1) − F(x*) − αLM )
2Cµ
→ ∞
k αLM
−− −→ 2Cµ
2cµ
述定理知果步长固定时算法终仅收敛优值点邻域附次优点通断减步长保证算法收敛优值点定理理保证
定理 4 果函数FLLipschitz连续函数µ−强凸函数假设算法1中步长采序
列更新：
β αk γ + k
中β > 1 γ > 0α1 ≤ µ
cµ
意k ∈ N：
LMG
v
E[F(xk) − F(x*)] ≤ γ + k
中
v β2LM *
max{ 2βcµ − 1) (γ + 1)(F(x1) − f (x ))}
机梯度降法(SGD)机量g(xk εk)函数全梯度偏估计 满
足F(xk) E[g(xk εk)]满足
E[F(x
) − α g(x ε ))] ≤ f (x ) − (α
α2L
α * L2) ‖ ∇F(x ) ‖ + E[g(x ε ) − F(x )]
k+1
k k k
k k k
k 2 2 k k k
− 2 2 2
式等号右边第二项预期误差第三项称方差方差存SGD需采变步长方式保证算法收敛方差存导致算法性欠缺果够改进算法方差断减直零便够提升算法性节中介绍三种样方法
机梯度方法相标准梯度方法更加效利数标准梯度方法次更
新目标变量需样实际问题中数会存定冗余
次全体数部分产生效果效率会更高通实验知机梯度方法刚开始降较剧烈会快达定精度次优解 者果忽略通信时间标准梯度方法收敛速度O(nlog(1s))(次迭代需计 算n梯度)然SGD 收敛速度O(1T )次计算梯度收敛速度1sn时实际中计算时间精度求限时SGD标准梯度效果差
23 方差减方法（Variance Reduction Method)
方差存机梯度方法性欠缺原通减方差提升算法性想法首先出种方差减观点[11]假设蒙特卡洛采样 方法更新EX果够高效计算出EYYX 着密切关系断θγ 断逼Y中θγ γ(X − Y) + EYEθγ EX EY 凸组合θγ 方差Var(θγ) γ2[Var(X) + Var(Y) − 2Cov(X Y)]果取γ 1θγ X 偏估计三种较典方法成采思想改进SGD分SAG(机 均梯度方法)SVRG(机方差减方法)SAGA
j
SAGA[11]SAG[9][10] X机梯度方法(SGD)方采样f ′ (xk)Y
做f ′ (φk)SAGA中γ 1SAG 中γ 1 SAG方差SAGA 1
j j n n2
SAGA估计偏估计SVRG[8]采Y f ′ (x)分外两层循环
三种方法更新方式：
j ̃︀
f ′ (xk) − f ′ (φk) 1 ′
j
xk 1 xk − α[
j j +
Σn f (φk)] (S AG)
+ n n
i1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (φk) 1 n f ′ (φk)] (S AGA)
+ j j j + n Σi1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (x) +
1 Σn
f ′ (x)] (S VRG)
+ j j ̃︀ n i1 i ̃︀
SAG[9]早提出具线性收敛速度机梯度方法次更新赖n
SAGA 成结合SAGSVRG两种方法技巧提出新算法SVRG收敛速度相适非强凸问题SVRG 着良性质适非凸函数年关SVRG研究断进行断发展接分介绍三种方法
231 机均梯度方法(Stochastic Average Gradient)
SAG[9][10]成IAG[17]种机版类似机梯度方法次迭代仅需样点计算方量次迭代量方全梯度偏估计 收敛速度线性SAG迭代格式：
xk 1 xk − αk Σn yk
+ n i1 i
中yk f ′ (xk)果i ikik机选取指标否yk保持变
i i i
i
k
SAG方法相SGD着明显优点采固定步长进行更新 着更快收敛性质线性收敛速度需存储n梯度nd 时存储量O(nd)存储量十分巨某特殊函数带线性预测形式函数fi(aT x)存储量减需O(d)果初始梯度选择零量yi 0算法迭代初始步长调1 直更新处k n样调整
提高收敛速度SAG算法[10]：
取合适步长时SAG种线性收敛算法收敛速度O(n + κ)log(1s)
Algorithm 2 SAG
d 0 yi 0 i 1 2 n
∀
for t12 m do
均匀采样 i ∈ 1 2 n d d − yi + f ′ (x)
i
i
yi f ′ (x)
x x − d
α
n
end for
定理[9]：
nL
定理 5 果函数f LLipschitz连续µ−强凸函数果固定步长αk 21
)k[3‖ 2 ix − x ‖+ ]o
关系式：
E[‖xk − x*‖2] ≥ (1 −
µ
8Ln
* 9 Σi‖ f ′ (x*)‖2 4nL2
µ
进步果n ≤ 8L 步长αk f rac12nµSAG迭代满足k ≥ n：
8n
E[ f (xk) − f (x*)] ≤ (1 − 1 )kC
中C [ 16L ‖x
− x*‖2 + 4Σi‖ f ′ (x*)‖2 (8log(1 + µn ) + 1)]
i
3n# 0
3n2µ 4L
式结果k ≥ n时前n步SG方法然前n步迭代均值作SAG初始值时yi 0然SAG着样收敛速度更加难分析实验中直接SAG方法里仅仅出理更界
L
SAG方法种线性收敛机梯度算法收敛速度O(n + κ)log(1s)SAG方法采定步长实际中取αk 1 L通常未知常采线搜索方式确定[9]次迭代存储量O(nd)计算量O(d)n d 较时会影响算法实际效率
232 机方差减梯度方法
SAG第取线性收敛效果机梯度方法机算法研究断深入机方差降梯度方法(SVRG)中重算法[8]等2013年 提出方法种具线性收敛算法适范围极广泛仅适强凸函数非强凸非凸情况样着收敛性质种方法需存储整梯度迭代程中需改变步步长实际操作中更加方便
̃︀
方法分两层循环m次点x计算次全梯度然该点计算 方量量全梯度偏估计然做次梯度降算法思想：
µ ∇F(x)
1 Σn
∇ fi(x)
̃︀ ̃︀
n i1 ̃︀
xt xt−1 − αt(∇ fi (xt−1) − ∇ fi (x) + µ)
t t ̃︀ ̃︀
中it 机{1 n}选择E[xt|xt−1] xt−1 − αt∇F(xt−1)
SVRG种方差断降方法根梯度迭代格式∇ fit (xt−1) − ∇ fit (x) + µ
̃︀ ̃︀ ̃︀t 1 (t 1)
x x(t)收敛x*时µ → 0∇ fi(x) → ∇ fi(x*)时
fi (x − ) − ∇ fi (x) + µ → ∇ fi(x − ) − ∇ fi(x*) → 0
̃︀ ̃︀
∇ t t ̃︀ ̃︀
通格式方差够效控制提高收敛速度SVRG算法
− +
线性收敛果FLLipschitz光滑连续µ 强凸时m足够α 1
µη(1−2Lη)m
2Lη 1−2Lη
< 1
EF(xs) − F(x*) ≤ αs[F(x0) − F(x*)]
中x*优值点 ̃︀ ̃︀
SVRG种线性收敛机算法循环需计算2m + n次梯度
Algorithm 3 SVRG
定初始量x0步长α正整数m
for k12 do
̃︀
计算方量µ ∇F(x0) n Σi1∇ fi(x0)
令x0
xk
̃︀ ̃︀
̃︀
1 n
for j12 m do
机选取ij ∈ 1 2 n
̃︀ ̃︀
x j x j−1 − α(∇ fij (xj−1) − ∇ fij (x0) + µ)
end for
选择(1)令x
x ̃︀
̃︀ ̃︀
̃︀
k+1
选择(2)令x
m
1 Σm x
选择(3)机选取j ∈ {1 2 m}令xk+1 x j
k+1 m j1̃︀j
end for ̃︀
全梯度方法计算复杂度相仅需O(log(1s))次外循环复杂度O(n +
κ)log(1s)
出次循环时计算方量时会全梯度信息SG 着明显差收敛性质较算法中会体现全梯度控制优化程总体方优化程会偏离整体方太远
SVRG方法收敛速度O(n + κ)log(1s)轮循环计算量O(nd + md)通常m取n倍数实际中取m 2nSVRG样适非强凸者非凸目标函数 着极性质参见[18][19][20]
233 SAGA
较 重 方 差 降 方 法 SAGA[11]方 法 SAGA 成SAGSVRG两种方法思想融合SAGA中次迭代方量成前 数次迭代方均值 j ∈ {1 n}机选取具体方式：
gk f ′ (xk) − f ′ (φk) 1 n f ′ (φk)
j j j + n Σi1 i i
n
出SAGA中方选取方式SAG类似仅仅1 换成1改变次选取方量全梯度偏估计成SVRGSAG两种思想结 合形成种新机算法[16][11]
初始化时需计算n梯度需O(nd)计算量外次迭代仅需 计算次方量计算量仅O(d)SG方法计算量相收 敛速度线性收敛目标函数f (x)LLipschitz光滑函数µ−强凸函数时果步
Algorithm 4 SAGA
定初始量x1步长α
for k12 n do
∇
计算梯度 fi(x1)
∇ ← ∇
存储梯度 fi(x[i]) fi(x1)
end for
for j12 do
机选取i ∈ 1 2 n
计算方量gk f ′ (xk) − f ′ (x[i]) + 1 Σn
f ′ (x[i])
i i
存储梯度∇ fi(x[i]) ← ∇ fi(xk)
xk+1 xk − αgk
n i1 i
end for
长α 2( 1
µn+L)
E[‖xk − x*‖2] ≤ (1 − µ )k(‖x1 − x*‖2) + nD
2 2(µn + L) 2 µn + L
3L
中D f (x1) − ∇ f (x*)T (x1 − x*) − f (x*)果µ未知情况选择α 1
会收类似收敛结果[11]
i
储标量̃︀f ′(aT xi) 样做存储量O(n)
i
SAGA线性收敛机算法收敛速度O(n + κ)log(1s)更加灵活初始化方式做轮机梯度获n 函数梯度样做函数初始化时期意义降加快收敛速度缺点SAGA方法需存 储n梯度n d 时需O(nd)存储量针特殊函数形式fi(x) ̃︀fi(aT x)存储量降低∇ fi(x) ̃︀f ′(aT xi)ai仅需i
机偶坐标升法（Stochastic Dual Coordinate Ascent）
坐标降方法(Coordinate descent)尤典方法基思想固定坐标针中某坐标目标函数做优化优化问题minx∈ℜd F(x)坐标降法更新方式：
∂F
xk 1 xk + αk∇i F(xk)ei ∇i F(xk) (xk)
+ k k k
∂xik
xik 代表着优化变量第ik坐标ik ∈ {1 d}机选取eik 代表ik 维1
余0单位量说次迭代仅量ik 维发生变化
坐标降法体现步长坐标选取步长采取精确搜索方法相求解维优化问题问题难度降低少实际更采取非精确搜索方法选取合适步长函数足够降ik选取常见三种 方法： 循环选取{1 d}循环选取{σ(1) σ(d)}σ{1 d}全排
列通常定次数发生改变次迭代放回机选取坐标ik ∈ {1 d}机方法第种方法更加效理者实践着更效果关原公开问题
机器学中正化验风险函数问题列问题：
min P(ω) [ 1 Σn
fi(aT ω) + λg(ω)]
ω∈ℜd
n i1 i
中fi(ω) g(x)均凸函数优化问题等价化偶函数形式：
max
D(α) [ 1 Σn − f *(−αi) − λg*( 1 Σn
aiαi)]
)α∈ℜd×n
n i1 i
λn i1
机坐标偶[12]种坐标降法思路坐标升方法相似 固定坐标中某坐标求解优化问题相CD方法化某函数F(x)SDCA化偶函数D(α)更新坐标时SDCA需求解函数值优化问题
机偶坐标升法（SDCA）理着保证种线性收敛
Algorithm 5 SDCA
初始化 α(0) 0v(0) 1 Σn
aiα(0)ω(0) ∇g*(0)
for t12 T do
λn i1 i
机选取 k ∈ 1 2 n 更新权值
y(t+1) arg max∆α − f *(−(α(t) + ∆αk)) − λg*(v(t) + 1 ak∆αk)
k k i k λn
α(t+1) a(t) + ∆αk
v k 1) v k + 1 a ∆α )
(t+
(t) i i
v(t+
ω(t+1) ∇g*( λn 1))
end for
输出(Averaging option)
令 α 1 ΣT
α(t)
T −T0 tT0+1
令 ω 1 ΣT
ω(t)
T −T0
返回 ω
tT0+1
输出(Random option)
∈
令 α α(t) ω ω(t) 意 t T0 + 1 T
返回 ω
机算法： L − Lipschitz 损失函数SDCA收敛速度O(n + L2(λs)) (1γ)光
滑损失函数达O((n + κ)log(1s)))
λs
λs
机梯度降(SGD)收敛速度O( 1 ) n ≫ 1 时 SGD效果
λn
λ
SDCA 1 ≫ s时SDCA更点实际情况1 O(n)者起
̃︀
码O( √n)阶SDCASGD效果 刚开始迭代时SDCA效果SGDSGD采更步长实际中常常采SGD SDCA 相结合方法初始迭代时先利SGD 原函数值快速降达某点ω 该点作SDCA 初始点进行迭代进优点分两阶段阶段1SGD 方式满足终止条件时α 阶段2SDCA更新令α(0) α
正前提坐标降法(CD)中指标选取方法概分三种方式机选取定序循环选取放回选取(次定序循环选取序会断改变)SDCA作种坐标升方法采三种方式实验表明 机方法远远优非机方法放回选取方式效果机选取效果更点算法中已观测然目前止种更新方式研究
较少放回抽取方式(without replacement)值进步研究
[21]等提出种加速方法算法收敛速度达(n + √κlog(1s))：
n
选择合适参数K O( 1 )β
For(t12 )
令P
κ (t−1) 2
̃︀t(ω) P(ω) + 2 ‖ ω − y ‖
̃︀
(t)
(t)
proxSDCA方法求解原函数似函数Pt(ω)(ω
Nesterov加速方法加速算法令y(t) ω(t) + β(ω(t) − ω(t−1)) Endfor
)α
{ √ } ≫
ASDCA着收敛性质 假设函数L − Lipshitz梯度连续 µ−强凸函数
APSDCA收敛速度O(n + min κ nκ )log(1s)) κ n时 收敛速度
O(n + √nκ)log(1s)阶机算法收敛速度
25 机原始偶坐标法（Stochastic Primal Dual Coordinate）
正化验风险函数问题列问题：
min P(x) [ 1 Σn
fi(aT x) + λg(x)]
x∈ℜd
n i1 i
中fi(x) g(x)均凸函数函数问题转化成原始偶鞍点问题：
min max 1 Σn (yi⟨ai x⟩ − f *(yi)) + g(x)
x∈ℜd y∈ℜn n
i1 i
鞍点问题成博弈问题通断化原始变量化偶变量断优
化优点机原始偶坐标法[13]变采样思想
算法6出种算法详细描述偶坐标原始坐标更新通通交
Algorithm 6 SPDC
输入 m 参数 τ σ θ ∈ ℜ+ x(0) y(0)迭代次数 T
初始化 x(0) x(0) u(0) 1 Σn
y(0)ai
for t12 T1 do
n i1 i
n
机选择指标集 K ⊂ {1 2 n} m 指标相概率 of m
选中
i
2σ
i
i
i
yt+1 arg maxβ∈ℜ{β⟨ai x(t)⟩− fi*(β) − 1 (β− y(t))2} (1) 果 i ∈ K 否y(t+1) y(t)
(t) 2
x∈ℜd
m
k∈K
k
k
k
2τ
2
x(t+1) arg min {g(x) + ⟨ut + 1 Σ (y(t+1) − y(t))a x⟩ + ‖x−x ‖ } (2)
−
n
k
k
u(t+1) u(t) + 1 Σk∈K (y(t+1) − y(t))ak (3)
x(t+1) x(t+1) + θ(x(t+1) x(t)) (4)
end for
输出 x(T ) y(T )
化y化x出增加两二次项引入参数στ两参
数仅控制正化项强弱控制次更新步长外引进u(t)x(t)
u(t)类SDCA中ω(t)定程度代表函数梯度信息x(t)通x(t) x(t+1)外推出种类似Nesterov 加速方式步证明时候着关键作
定理 6 假设φi(1γ)−光滑函数g λ−强凸函数令R
τ 1 √︂ mγ σ 1 √︃ nλ θ 1 − 1
max{‖ai‖2 i 1 n}果参数τσθ 选取
2R nλ
2R mγ
(nm) + R √︀(nm)(λγ)
意t ≥ 1批量SPDC算法收敛性：
( 1 2τ
+ λ)E[‖x(t) − x*‖2] + ( 4
+ γ)
E[‖y(t) − y*‖2]
2
2
2
2 )
1
1
m
σ
t
1
≤ θ (( 2τ
+ λ)‖x(0) − x*‖2 + ( 2
+ γ)
‖y(0) − y*‖2
m
σ
面推说明达s精度期迭代复杂度：
推 1 果φi(1γ)−光滑函数g λ−强凸函数参数前述定理设置算法6达条件
2
2
E[‖x(T ) − x*‖2] ≤ s E[‖y(T ) − y*‖2] ≤ s (11)
迭代次数T 满足
T ≥ ( n
+ R √︂ n )log C
m mλγ ( s )
中
( 1
+ λ)‖x(0) − x*‖2 + ( 1 + γ)‖y(0)−y*‖2
C 2τ
2 2σ m
2
2τ
4σ
min{ 1 + λ ( 1 + γ)m}
处理器时算法6次迭代需O(md)时间坐标yk更新完全独立坐标够分布式计算方式加速批量SPDC方法具体说够m处理器行更新子集K 中m 坐标然更新x(t+1)果忽略通信延迟次迭代仅仅需O(d) 时间毫惊讶m 时表明SPDC算法收敛更快次迭代更新偶变量
然目前关异步SPDC算法研究少文作者做出定探究
通减步长σ方式异步SPDC定条件着线性收敛收敛速度
SPDC缺点收敛速率常数R常数根问题定 特征量二范数值非标准化数算法会表现差特特征量二范数远时候
基想法次迭代选取偶坐标时非均匀采样概率选取具体
说坐标选取概率p 1 + ‖ak ‖2 着更范数特征量选取
2Σ
k 2n
n i1
‖ai‖2
性应该更时更新原始变量偶变量时更新表示式变
yt+1 arg max{β⟨ai x(t)⟩ − f *(β) − pin (β − y(t))2}
i
β∈ℜ
i 2σ i
外调整(13) 中ak权重更新原始变量
u(t+1) u(t) + 1 (y(t+1) − y(t))ak
pkn k k
定理 7 果φi(1γ)−光滑函数g λ−强凸函数参数前
述定理设置令R 1 Σn ‖ai‖2 果算法2中τ σ θ选值：
n
i1
4R
nλ
4R
γ
γλ
τ 1 √︂ γ σ 1 √︃ nλ θ 1 − (2n + 2R √︂ n )−1
意t ≥ 1
( 1 + λ)E[‖x(t) − x*‖2] + ( 7 + 2γ)E[‖y(t) − y*‖2]
2τ 2 16σ n 2
≤ θt(( 1 + λ)‖x(0) − x*‖2 + ( 1 + 2γ)‖y(0) − y*‖2)
2τ 2 2σ 2
定理5中参数θ定理5中θ进行较定理5中常数R特征量范数均值决 定值算法非标准特征量更加鲁棒果ai相互 独立均服某维正态分布n → ∞maxi{‖ai‖2}必然趋穷
n
i1
范数均值1 Σn ‖ai‖2 收敛E[‖ai‖2]
26 加速方法Catalyst
Nesterov加速方法GD着更收敛性质加速已机算法成值研究方节介绍加速框架适种阶机优化方法SAGSVRGSAGASDCA等强凸函数着线性收敛性质阶方法均通种框架加速
方法思想通结合Nesterov技巧迭代求解原函数着
优良性质似函数 种方法着收敛性质 强凸函数 达
O(n + √nκlog(1s)) 果函数非强凸加速非强凸函数收敛速
度
述算法次外循环成两步组成 分称Catalyst步加速步
Algorithm 7 Catalyst
{ }
输入初始点x0参数Kα0序列 sk 优化方法M 初始化 令q µ(µ + κ)y0 x0
for t12 T1 do
方法M寻找似解
xk ≈ arg min{Gk(x) F(x) + K ‖x − yk−1‖2} Gk(xk) − G* ≤ sk
x∈ℜd
计算αk ∈ (0 1)满足α2 (1 − αk)α2
2 k
+ qαk
计算 k k−1
yk xk + βk(xk − xk
1) βk αk−1(1 − αk−1)
end for
输出 x(T )
− α2
k−1
+ αk
Catalyst步原函数基础加二次强凸函数函数着更性
质果函数非强凸通添加二次项方式函数变成强凸函数果函
数强凸函数L+κ < L 知函数条件数变更加速步成
µ+κ µ
外推Nesterov 加速FISTA算法中采技术相似
定理 8 强凸函数收敛性 果令α0 √qa µ(µ + K)
9
sk 2 (F(x0 − f *)(1 − ρ)k ρ < √q
算法迭代序列{xk}
(
F(xk) − F* ≤ C(1 − ρ)k+1(F(x0) − F*) C
8
√ 2
q − ρ)
述定理种方法收敛速度线性sk选择变F* 事先知道F(x0) − F*界代通x0算偶距离
强凸函数果算法收敛速度O(n + κ)log(1s)Catalyst加速
收敛速度加速O(n + √nκ)log(1s)Catalyst加速方法需事先选取K序
列{sk}造成实际实现中苦难
27 Katyusha
全梯度方法优收敛速度通加Nesterov称种方法AGD机阶方法采取类似技巧进行加速样做稳定果某梯度估计值够精确加动量着方进步移动会损害收敛性 说简单Nesterov技巧加速目
Katyusha[22]种直接加速机算法强凸函数时间复杂度0(n +
√nκlog(1s))非强凸函数时间复杂度O(nlog(1s) + √nLs · ‖x0 − x*‖)
定理 9 果fiL光滑凸函数ψ(x)µ−强凸Katyusha算法
s * ⎧⎪⎨ O((1 + √σ(3Lm))−S m) · (F(x0) − F(x*)) mσ ≤ 3
L 4
L
4
E[F(x )] − F(x ) ≤ ⎪
̃︀ ⎩
O(15−s) · (F(x0) − F(x*)) mσ ≥ 3
果选择m O(n)达次优解F(xs) − F(x*) ≤ s需O((n + √nLσ) ·
s
log( F(x0)−F(x*) ))次迭代 ̃︀
Algorithm 8 Katyusha
√mσ 1
√
2
3L
初始化 令m2nτ 1 τ min{ }α 1 y z x0 x
2 2 1
for s12 S1 do
3τ1 L 0
0 ̃︀ 0
̃︀
µs f (xs)
fo∇r t12 T1 do
ksm+j
x τ z + τ xs + (1 − τ − τ )yk+1 1 k 2 1 2 k
1
2
zk+1 arg minz{ 2α ‖z − zk‖
+ ⟨̃︀∇k+1 z⟩ + ψ(z)}
̃︀∇k+1 µs + ∇ fi(̃︀xk+1) − ∇ fi(̃︀xs)机选取i ∈ {1 2 n}
3L
2
选择1：yk+1 arg miny{ 2 ‖y − xk+1‖
选择2：yk+1 xk+1 + τ1(zk+1 − zk)
+ ⟨̃︀∇k+1 y⟩ + ψ(y)}
̃︀
end forxs+1 (Σm−1(1 + ασ) j)−1 · (Σm−1(1 + ασ) j · ysm+ j+1)
end for
̃︀
输出 xs
j0
j0
̃︀ ̃︀ ̃︀
Katyusha已知唯种达优收敛速度机算法Katyusha 分外两层循环外循环m次循环组成理m意n倍数通常取m 2nxk+1 τ1zk + τ2 xs + (1 − τ1 − τ2)yk知xk+1成zkxsyk凸组合τ2 0时
2
Katyusha变成SVRG结合Nesterov技巧算法τ2 Ç 0时xs成负动量 矫正迭代方真实方偏离太保证梯度估计较精确 Katyusha方法优良性质关键称Katyusha动量实际τ2(0 1)中数调整参数验表明τ2 1 够达
效果
3 二阶方法
31 牛顿法拟牛顿法
种较重方法牛顿法(Newton)牛顿法利函数二阶信息迭代方效提高算法收敛速度牛顿法二阶泰勒展开假设某点xk
2
f (xk + p) ≈ f (xk) + ∇ f (xk)T p + 1 pT ∇2 f (x)p mk(p)
假 设 函 数 Hessian阵 正 定 通 化mk(p) 牛 顿 方
pk −∇2 f (xk)∇ f (xk)∇2 f (xk)正定pk * ∇ f (xk) < 0pk降方
牛顿方法迭代格式：
xk+1 xk − αk∇2 f (xk)∇ f (xk)
通常 迭代步长选择1 满足降情况条件时 会调整步长∇2 f (xk)正定时候出牛顿方存∇2 f (xk)逆存外 pk * ∇ f (xk)非负种情形会采相关技巧方降方牛顿方法着快局部收敛速度某条件达二次收敛速度牛顿方法缺点需计算Hessian阵∇2 f (xk)需求逆n时候计算量存储量太
拟牛顿法(QuasiNewton)牛顿法改进需计算Hessian阵逆矩 阵着超线性收敛速度次迭代矩阵Bk似Hessian 阵时矩阵通前步相关信息迭代通常Bk称正定矩阵记逆Hk函数二次连续微时
∇ fk(xk+1 − xk) ≈ ∇ fk+1 − ∇ fk
BkHessian阵似然希Bk满足等式
Bk+1 sk yk
中yk ∇ fk+1 − ∇ fksk xk+1 − xk称述等式割线方程更新格式：
xk+1 xk − αkHk∇Fk
拟牛顿方法种迭代方式常见秩1修正秩2修正两种方式秩1方法
称SR1(symmetricrankone) 方法较代表秩2方法BFGSDFP方法
311 SR1
SR1迭代格式示：
Bk+1 Bk +
(yk − Bk sk)(yk − Bk sk)T
(yk − Bk sk)T sk
Bk正定矩阵时SR1迭代保证Bk+1着正定性质SR1缺点迭代会突然消失(yk − Bk sk)T sk Ç 0满足割线方程迭代格式唯确定 yk Bk sk满足割线方程仅Bk+1 Bk果yk Ç Bk ss(yk − Bk sk)T sk 0会满足割线方程SR1迭代序列种情形表明SR1方法数值稳定性
然SR1方法然着错性质说SR1方法真实Hessian阵着
更似BFGS方法效果
312 BFGSDFP
BFGS方法迭代方式
k
k
k
Hk+1 (I − ρk skyT )Hk(I − ρkyk sT ) + ρk sk sT
sT yk
中ρk 1 skyk > 0时果Hk正定矩阵Hk+1正定矩阵通常选
k
+1
取H0 δI δ > 0根ShermanMorrisonWoodbury公式写出Bk+1 Hk−1 更新方
式
BFGS方法目前止效拟牛顿方法目标函数二次函数时着超线 性收敛性质采精确线搜索时理实验均保证BFGS着修复性 质ρk极正数时显然样估计会导致收敛速度变慢BFGS会 数步纠正样问题BFGS着良性重原
种著名方式DFP成BFGS方法偶形式格式
k
k
k
Bk+1 (I − ρkyk sT )Bk(I − ρk skyT ) + ρkykyT
果BFGSDFP方法做线性组合Broyden类方法
k+1
k+1
Bk+1 (1 − φk)BBFGS + φk BDFP
32 LimitedmemoryBFGS
拟牛顿法迭代格式：
xk+1 xk − αkHk∇Fk
中αk步长HkHessian阵逆种似中种更新方式BFGS格
式着效果
Hk+1 VT HkVk + ρkyk sT
k k
k
yT sk
k
中ρk 1 Vk I − ρkyk sT sk xk+1 − xk yk ∇ fk+1 − ∇ fk
步更新Hk时候需利前步信息数维数样数量
Algorithm 9 LBFGS twoloop
a fk
← ∇
for ik1k2 km do
end forr ← H q
i
0
αi ← ρi sT q q ← q − αiyi
k
for ikmkm+1 k1 do
i
←
β ρiyT r
← −
r r + si(αi β)
end for
输出 Hk∇ fk r
较时需耗费相计算量储存空间减算法时间复杂度Nocedal 等提出LBFGS算法次更新仅前m步相关信息通常m选320中 常数提出相实twoloop算法更新Hk∇ fk 种方法非显式利Hk需计算Hk · ∇ fk时需存储Hessian阵(n × n)者减少存储开支
LBFGS种二阶方法twoloop算法提出降低开销规模 机器学问题运算量存储量非常惊vectorfree LBFGS[23] 种更加实算法较twoloop运算复杂度LBFGS 算法更加适应分布式计算环境
Hk∇ fk成{si yi}∇ fk线性组合整计算程中参变量保持变运算程仅仅设计两量积形式通直 接求系数减少计算量仅仅需输入2m + 1量两两间积(2m + 1) × (2m + 1)积矩阵更新时候够利先前留积矩阵信息计算量者存开销远远twoloop算法
Algorithm 10 vectorfree LBFGS twoloop
输入 (2m + 1) (2m + 1)积矩阵令δ2m+1 1余系数δi 0 for ik1k2 km do
−
*
ji(km)+1
α l1
Σ 2m+1δlblbj
i
−
δ b j·bm+ j
m+ j δm+ j αi
end for
for i12 2m+1 do
δi bm·b2m δi
end for
b2m·b2m
for ikmkm+1 k1 do ji(km)+1
l1
β Σ2m+1δlbm+ j·bl
b j·bm+ j
−
δ j δ j + (αi β)
end for
输出 Hk∇ fk r
33 机牛顿方法
机LBFGS方法结合方差减思想[24]提出种机LBFGS方法 方法实践中表现需降步长强凸函数算法线性收敛速度
算法参数控制mLMm次迭代断减方差需 计算次全梯度L步需更新函数Hessian阵量sr记录2L步均降 方yr通Hessian阵似矩阵sr相通常意义LBFGS方法 通常yr通计算梯度
种具线性收敛速度算法果函数二次连续微凸函数
意τ ⊆ {1 2 N}均
λI ⪯ ∇2 fτ(ω) ⪯ ΛI λ > 0 L > 0
E[ f (ω ) − f ( *)] ≤ k E[ f ( ) − f (
*)]
1(2mη) + ηΓ2Λ2
k ω α ω0 ω
α
γλ − ηΓ2Λ2
适选择mML时α < 1然种算法没充分利二阶信息种方法通结合机方差减思想机拟牛顿方法取线性收敛效果相关数值实验证明算法性然种方法需调整参数mML疑增算法
Algorithm 11 机LBFGS
输入 ω0参数 mM L批量 b bH步长 η
初始化 r0H0I
for k012 do
∇
计算全梯度 µk f (ωk)
令 x0 ωk
for t0 m1 do
⊆
机选择集合 S kt 1 N
∇
计算机梯度 fS kt (xt)
∇ − ∇
计算方差减梯度 vt fS kt (xt) fS kt (ωk) + µk
−
令 xt+1 xt ηHrvt
果 t整L rr+1
令 ur 1 Σt−1 x j
L jt−L 2
机采样τr ⊆ 1 N 机似∇ fτr (µr)
− ∇
计算 sr ur ur−1 yr 2 fτr (µr)sr 更新 Hr
end for
∈ { − }
ωk+1 xi 机 i 0 m 1 选择
end for
实现难度
规模问题二阶方法研究工作较限二阶方法值进步研究关机二阶算法参见[25][26][27][28]
4 数值实验
节采造数进行相关数值实验较算法通实验
算法收敛速度直观认识
i1
生成500独立分布数{ai bi}n
根模型
b ⟨ai x*⟩ + s a ∼ N(0 Σ) s ∼ N(0 1)
a ∈ ℜd d 500x*全1列量Σ病态角矩阵角线元素
Σ j j j−2{ai bi}考虑求解嵴回模型实验设定参考[13]
min 1 Σn
1 (aT x − bi)2 + λ‖x‖2
x∈ℜd n
i1 2 i 2 2
较种算法求解问题数值性取λ{1e − 3 1e − 4 1e − 5 1e − 6}四
种取值
步长选取SGD选择步长1T SVRG选择步长01LSAGA选择步长13LSAG选择步长12L竖轴log(P(xT ) − P(x*))横轴梯度估计次数全体数数值
Algorithm
Runtime
SGD
O(1s2)
SAG
0(n + κ)log(1s)
SAGA
0(n + κ)log(1s)
SVRG
0(n + κ)log(1s)
SDCA
0(n + κ)log(1s)
SPDC
L − Lipshitzµ−强凸函数言种算法收敛速度：
0(n + √nκ)log(1s)
理结果出SGD收敛速度慢种方法数值实验表现明显 SPDC 作种加速方法收敛速度快远远优种算法 SAGSVRGSAGA 三种算法说理收敛速度致数值试验中性十分相实际中应该根具体问题选择种算法SDCA作种偶方法 数值结果够稳定收敛速度较
SGD SVRG SAGA
SAG
SPDC
SDCA
0
−2
−4
−6
−8
−10
lambda1e−3
lambda1e−4
SGD SVRG SAGA SAG
SPDC
SDCA
1
0
−1
−2
−3
−4
−5
−12 −6
−14 −7
−16
−18
0 10 20 30 40 50 60
−8
−9
0 10 20 30 40 50 60
1 1
lambda1e−5
SGD SVRG
SAGA
SAG SPDC SDCA
1
SGD SVRG
SAGA
SAG SPDC SDCA
05
lambda1e−6
05
0
−05
−1
0
−05
−15 −1
−2
−25
−15
−3
−2
−35
−4
0 10 20 30 40 50 60
−25
0 10 20 30 40 50 60
1 1
参 考 文 献
[1] Cortes C Vapnik V Supportvector networks[J] Machine learning 1995 20(3)273–297
[2] Hastie T Tibshirani R & Friedman J(2008) The Elements of Statistical Learning Data Mining Inference and Prediction[缺文献类型标志代码][Sl] Springer New York
[3] Bishop C M Pattern recognition and machine learning[M][Sl] Springer 2006
[4] Nesterov Y A method of solving a convex programming problem with convergence rate O (1k2)[C]Soviet Mathematics Doklady [Sl] [sn] 198327372–376
[5] Nesterov Y Introductory lectures on convex optimization A basic course[缺文献类型标志代
码][Sl] Springer Science & Business Media
[6] Zhang T Solving large scale linear prediction problems using stochastic gradient descent algorithm s[C]Proceedings of the twentyfirst international conference on Machine learning [Sl] [sn] 2004116
[7] Robbins H Monro S A stochastic approximation method[J] The annals of mathematical statistics 1951400–407
[8] Johnson R Zhang T Accelerating stochastic gradient descent using predictive variance reduc tion[C]Advances in Neural Information Processing Systems [Sl] [sn] 2013315–323
[9] Roux N L Schmidt M Bach F R A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets[M] Pereira F Burges C J C Bottou L et al Advances in Neural Information Processing Systems 25[Sl] Curran Associates Inc 20122663–2671
[10] Schmidt M Le Roux N Bach F Minimizing finite sums with the stochastic average gradient[J] Math ematical Programming 20131–30
[11] Defazio A Bach F LacosteJulien S SAGA A Fast Incremental Gradient Method With Support for NonStrongly Convex Composite Objectives[M] Ghahramani Z Welling M Cortes C et al Ad vances in Neural Information Processing Systems 27[Sl] Curran Associates Inc 20141646–1654
[12] ShalevShwartz S Zhang T Stochastic dual coordinate ascent methods for regularized loss minimiza tion[J] Journal of Machine Learning Research 2013 14(Feb)567–599
[13] Zhang Y Lin X Stochastic PrimalDual Coordinate Method for Regularized Empirical Risk Minimiza tion[C]ICML [Sl] [sn] 2015353–361
[14] Wright S Nocedal J Numerical optimization[J] Springer Science 1999 3567–68
[15] Gu¨ rbu¨ zbalaban M Ozdaglar A Parrilo P Why random reshuffling beats stochastic gradient descen t[J] arXiv preprint arXiv151008560 2015
[16] Bottou L Curtis F E Nocedal J Optimization methods for largescale machine learning[J] arXiv preprint arXiv160604838 2016
[17] Blatt D Hero A O Gauchman H A convergent incremental gradient method with a constant step size[J] SIAM Journal on Optimization 2007 18(1)29–51
[18] AllenZhu Z Yuan Y Improved SVRG for nonstronglyconvex or sumofnonconvex objec tives[R][Sl] Technical report arXiv preprint 2016
[19] AllenZhu Z Hazan E Variance reduction for faster nonconvex optimization[J] arXiv preprint arX iv160305643 2016
[20] Reddi S J Hefny A Sra S et al Stochastic variance reduction for nonconvex optimization[J] arXiv preprint arXiv160306160 2016
[21] ShalevShwartz S Zhang T Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[C]ICML [Sl] [sn] 201464–72
[22] AllenZhu Z Katyusha The first direct acceleration of stochastic gradient methods[J] arXiv preprint arXiv160305953 2016
[23] Chen W Wang Z Zhou J Largescale LBFGS using MapReduce[C]Advances in Neural Information Processing Systems [Sl] [sn] 20141332–1340
[24] Moritz P Nishihara R Jordan M I A linearlyconvergent stochastic lbfgs algorithm[C]Proceedings of the Nineteenth International Conference on Artificial Intelligence and Statistics [Sl] [sn] 2016
[25] Byrd R H Hansen S L Nocedal J et al A stochastic quasiNewton method for largescale optimiza tion[J] SIAM Journal on Optimization 2016 26(2)1008–1031
[26] Bordes A Bottou L Gallinari P Sgdqn Careful quasinewton stochastic gradient descent[J] Journal of Machine Learning Research 2009 10(Jul)1737–1754
[27] Poole B Fast largescale optimization by unifying stochastic gradient and quasiNewton methods[J] 2014
[28] Lucchi A McWilliams B Hofmann T A variance reduced stochastic newton method[J] arXiv preprint arXiv150308316 2015
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
摘
机器学中数值优化问题考虑规模维数较传统方法难高效解决问题年针规模机器学问题做研究较重类方法 机算法优化方法分阶梯度方法二阶牛顿方法两类针阶方法改进研究较成熟完善阶方法分两类原始方法偶方法原始方法较代表性SAGSAGASVRG偶方法SDCASPDC两种外加速方法CatalystKatyusha收敛速度阶方法达结果二阶方法目前机器学领域研究重方收敛速度优阶方法实践中会难度较实LBFGS方法机算法改进
文详细全面叙述机器学中种机算法介绍机算法发展历程研究方研究热点通数值试验较种常见机算法读者直观数值效果
关键词：规模机器学机算法优化方法
Stochastic Optimization Algorithm in Machine Learning
Abstract
For the optimization problem in machine learning field traditional method have difficulties in solving the high dimension and big data problem In recent years there are many researches in large scale machine learning problems especially stochastic algorithms Generally stochastic method can divided into two parts One is firstorder gradient method and the other is second order Newton method There is more improvement and research in first order method and the first order method is more mature and perfect There is two classes for first order method For the primal class SVRGSAGSAGA is the representation and SDCA SPDC for dual class Otherwise the acceleration method such as catalyst and katyusha which has the optimal con vergence speed for first order method is put forward in last two years Second order method is one important research area and it has better convergence but not better performance because it has to compute the hessian matrix one useful method is LBFGS and its variants
In this paper the author will introduce stochastic algorithms in machine learning area in detail In the end numerical experiments compare some common algorithm and give a direct view to readers
Key Words Largescale machine learning problemStochastic algorithmOptimization method
目 录
摘
I
Abstract
II
引 言
1
1 基础知识
5
2 阶方法
6
21 梯度降法（Gradient Descent）
6
22 机梯度方法（Stochastic Gradient Method）
7
23 方差减方法（Variance Reduction Method)
10
231机均梯度方法(StochasticAverage Gradient)
11
232 机方差减梯度方法(Stochastic Variance Reduction Gradient)
12
233 SAGA
13
24 机偶坐标升法（Stochastic Dual Coordinate Ascent）
14
25 机原始偶坐标法（Stochastic Primal Dual Coordinate）
16
26 加速方法Catalyst
19
27 Katyusha
20
3 二阶方法
22
31 牛顿法拟牛顿法
22
311 SR1
23
312 BFGSDFP
23
32 LimitedmemoryBFGS
24
33 机牛顿方法
25
4 数值实验
27
参考文献
29
致 谢
31
引 言
年着科学技术断进步发展尤计算机通信等领域进步互联网断普产生数速率提高时够容易廉价获取存储数数中蕴含量信息量数中发掘出效信息困难问题解决该问题尝试采种方式中较处理方式机器学数理统计方法
机器学利数建立模型进行预测中常见方法问题转化成优化模型进求解目标函数然数时代数数量数维数较高更效处理挖掘数仅断改进发展计算机硬件断改进机器学算法效率提高机器学算方法效率更赖数值优化算法改进必规模机器学中优化算法进行总结文力求详细全面现机器学中优化方法做概述学总结
定训练数集T {(x1 y1) (x2 y2) (xN yN)}机器学策略求验风
险损失模型常见验风险损失模型
Σ
min F(x) + g(x) 1 n
fi(x)
x∈ℜd
n i1
中 fi(x) ℜd → ℜ 凸光滑损失函数 fi样密切相关n代表着样数
然样容量时容易产生拟合现象防止拟合常验
风险加表示模型复杂度正化项惩罚项称结构风险损失函数
Σ
min F(x) + g(x) 1 n
fi(x) + g(x)
x∈ℜd
n i1
中 fi(x) ℜd → ℜ 凸光滑损失函数 fi样密切相关n代表着样数g(x) ℜd → ℜ正化函数通常凸函数
种形式问题机器学中着广应许机器学方法结成求形式优化问题：
线性支持量机转化成求优化问题[1][2][3]
Σ
min P(x) 1 n
λ
[1 − bi(aT x)] + ‖x‖2
x n i1
i + 2
中[a]+ max{0 a}
逻辑回结解决述优化问题[2][3]：
min P(x) 1 n log(1 + e−biaT x) + λ‖x‖2
x n
Σi1
i 2 2
LASSO转化成求解优化问题[2][3]：
min P(x) 1 Σn
(ai x − bi)2 + 1 ‖x‖2
x 2n
i1 2 1
解决问题难点优化变量维数d样数n较时求解 问题需非常计算量存储存种规模优化问题较常见方 法分批处理方法机算法批处理方法包括全梯度降方法拟牛顿LBFGS方法机方法机梯度降法（SGD）种算法改进机方差降梯度方法(SVRG)机均梯度方法(SAG)机偶坐标升法（SDCA）机原始偶坐标方法（SPDC）
梯度降法种线搜索方法[4]次迭代选择该点负梯度方作搜索方 负梯度方快降方称速降法仅利函数梯度信息称阶方法梯度方法次迭代方负梯度方
xk 1 xk − αkgk xk − αk Σn
∇ fi(xk)
+ n i1
收敛速度O(1n)种次线性迭代算法
种加速梯度算法AGD[4][5]形：
xk+1 xk + θ(xk − xk−1) − αk f ′(xk + θ(xk − xk−1))
收敛速度O(1n2)目标函数强凸函数时收敛速度线性收敛速度
梯度降方法需需计算n梯度计算量O(nd)nd时计算 量存储空间更实改进次迭代时机选择点计算梯度进行更新SGD形式[6][7]：
xk+1 xk − αk∇ fik (xk)
n
i1
需满足E[∇ fik (xk)|xk−1] 1 Σn ∇ fi(xk)改进处次迭代计算
n
量标准梯度降法1 机梯度降法(SGD)机量g(xk εk)函数全梯
度偏估计满足
E[F(x
) − α g(x ε ))] ≤ f (x ) − (α
α2L
− 2 2 2
α * L2) ‖ ∇F(x ) ‖ + E[g(x ε ) − F(x )]
k+1
k k k
k k k
k 2 2 k k k
式等号右边第二项预期误差第三项称方差方差存SGD需采变步长方式保证算法收敛方差存导致算法性足果够改进算法方差断减直零较代表性方差减方法三种分称SVRG[8]SAG[9][10]SAGA[11]三种方法更 新方式：
f ′ (xk) − f ′ (φk) 1 ′
j
xk 1 xk − α[
j j +
Σn f (φk)] (S AG)
+ n n
i1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (φk) 1 n f ′ (φk)] (S AGA)
+ j j j + n Σi1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (x) +
1 Σn
f ′ (x)] (S VRG)
+ j j ̃︀ n i1 i ̃︀
SAG[9]早提出具线性收敛速度机梯度方法次更新赖n
SAGA成结合SAGSVRG两种方法技巧提出新算法SVRG收敛
速度相适非强凸问题SVRG着良性质适非凸函数
外类较实方法机偶方法SDCA[12]SPDC[13]SDCA 原始问题转化偶形式采机坐标思想机选择偶坐标断求极直优值SPDC 原问题转化鞍点问题通交化原始变量化偶变量求鞍点正文中继续介绍着两种方法
牛顿方法[14]利函数二阶信息种优化方法现实中常常种似 牛顿方法拟牛顿法机器学领域中较常LBFGS拟牛顿方法 方法优值附达次线性收敛速度迭代格式：
xk+1 xk − αkHk∇Fk
中αk步长HkHessian阵逆种似更新方式：
Hk+1 VT HkVk + ρkyk sT
k k
k
yT sk
k
中ρk 1 Vk I − ρkyk sT sk xk+1 − xk yk ∇ fk+1 − ∇ fk
二阶方法计算中复杂度较高二阶方法改进存定难度关
二阶机方法工作较限正文介绍种改进算法
接第章介绍相关数学知识背景第二章分阶算法进行介绍第三章二阶算法做介绍第四章通实验优化算法
1基础知识
定义 1 LLipshistz连续 称函数f ℜd → ℜLLipschitz连续函数 L > 0 果
∀a b ∈ ℜd均
| f (a) − f (b)| ≤ L|a − b|
定义 2 γ 光滑称函数f ℜd → ℜγ−光滑函数γ > 0果意∀a b ∈ ℜd均
2
f (b) ≤ f (a) + ⟨∂ f (a) T (b − a)⟩ + γ‖b − a‖2
定义 3 凸函数 称函数f ℜd → ℜ凸函数果意∀a b ∈ ℜd均
f (b) ≥ f (a) + ⟨∂ f (a) T (b − a)⟩
定义 4 µ−强凸函数 称连续微函数f ℜd → ℜµ−强凸函数µ > 0果
意∀a b ∈ ℜd均
2
f (b) ≥ f (a) + ⟨∂ f (a) T (b − a)⟩ + µ‖b − a‖2
定义 5 条件数 果连续微函数f ℜd → ℜγ−光滑函数µ−强凸函数记
γ
κ
µ
称κ原函数条件数
定义 6 值点
∙ 点x*称局部值点果存x*领域N意x ∈ N均f (x) ≥ f (x*)
∙ 点x*称严格值点（强值点）果存x*领域N意x ∈
Nx Ç x*均f (x) > f (x*)
定理 1 阶必性条件果x*值点函数f x*开领域连续微
∇ f (x*) 0
定理 2 果函数f 凸函数意局部值点均全局值点外函数微时x满足∇ f (x) 0点均全局值点
2阶方法
21 梯度降法（Gradient Descent）
梯度降法种线搜索方法次迭代选择该点负梯度方作搜索方 负梯度方快降方称速降法仅利函数梯度信息称阶方法形式非常直观简单次迭代选择负梯度方作降方更新形式：
xk 1 xk − αkgk xk − αk Σn
∇ fi(xk)
+ n i1
中αk步长学率准确定Wolfe准Armijo准等
L
函数F凸函数梯度L − Lipshitz函数时取α 1 时收敛速度
达O(1k)[5]
f (xk) − f (x*) ≤
2L ‖ x0 − x* ‖2
2
k + 4
进步Fµ−强凸梯度L − lipshitz函数时收敛速度线性收敛[5]：
f (xk) − f (x*) ≤ L ( L − µ)2k ‖ x0 − x* ‖2
2 L + µ
Nesterov证明阶方法理优界[4][5]采种加速方法梯度降算法进行改进称Nesterov加速称算法加速梯度降算法（AGD）种常AGD 迭代方式：
xk+1 yk − αk f ′(yk)
yk+1 xk+1 + θ(xk+1 − xk)
L
函数F凸函数梯度L − Lipshitz函数时果αk
√ 2
2
µ)
速度
1 θ
√ √
L− µ
√L+ √µ 收敛
L
(2
zzzzzzzf (xk) − f (x*) ≤ min{(1 − √︂µ)k
√
4L
L + k
} * [ f (x0) − f (x*) + µ ‖ x0 − x* ‖2]
述收敛速度非强凸函数强凸函数适合函数非强凸时取µ0通 迭代格式出迭代时仅涉量加减数运算次迭代计算复杂度O(nd)
然步梯度降方法需需计算n梯度计算量O(nd)nd 时计算量存储空间改进梯度算法适规模机器学优化问题特数爆炸天成意义问题
然步梯度降方法需需计算n梯度计算量O(nd)nd 时计算量存储空间改进梯度算法适规模机器学优化问题特数爆炸天成意义问题
种较常见方法确定性提升梯度方法(deterministic incremental gradient
0
method)[15]称IGIG方法标准梯度降方法非常相似n函数形式目标函数区IG方法变量着中函数梯度方循环更新 具体成着两层循环算法次外层迭代成m次层迭代循环令初始点x0 ∈ ℜn意k > 0更新方式
x(k) x(k)
− αk∇ fi(x )
(k)
i i−1
中αk > 0代表着步长x(k+1) xk
i−1
0 n
IG方法性取决循环中迭代序果某具体问题果存已 知信息确定出迭代序σ(1 n 排列)IG方法性
x(k) x(k)
− αk∇ fσ
(x(k) )
i i−1
(i)
i−1
然现实中先验信息难获更倾采机采样方法
更新方法称机梯度方法(stochastic gradient method)者称Robbins
Monro[7] 算法
22 机梯度方法（Stochastic Gradient Method）
机梯度方法(SG)迭代程目标函数初始点步长等素唯决定程机标准梯度方法次迭代根某分布ε机选择 样点更新目标变量中种SG方法机梯度降算法(stochastic gradient
descent)SGD保证目标函数相邻两次迭代定降期意义
降算法[6][7]：
x(k+1) x(k) − αk∇ fik (x(k))
n
i1
满足Eε[∇ fik (x(k))] 1 Σn ∇ fi(x(k)) ∇F(x(k))
n
轮迭代计算量标准梯度法1 仅O(d)步长断减保证目标函数收敛优值点理SG做进步认识已知 结[16]考虑更般形式(SG)算法1
Algorithm 1 SG
选择初始点x1
for t12 m do
生成机变量εk 计算机量g(xk εk) 确定步长αk
−
更新： xK+1 xK αkg(xk εk)
end for
引理 1 果函数F(x)L光滑函数算法1满足等式意k ∈ N：
Eεk [F(xk+
1)] − F(xk) ≤ −αk∇F(xk)T E
[g(xk εk)] + 1 α2LE [‖ g(xk εk) ‖2]
εk 2 k εk 2
假设 1 目标函数SG(算法1)满足条件
(1) 函数F界序列{xk}开集中
(2) 存µG ≥ µ > 0意k ∈ N
∇F(xk)T Eε [g(xk εk)] ≥ µ ‖ ∇F(xk) ‖2
k 2
‖ Eεk [g(xk εk)] ‖2≤ µG ‖ ∇F(xk) ‖2
(3) 存M ≥ 0Mv ≥ 0意k ∈ N
k
2
Vε [g(xk sk)] ≤ M + Mv ‖ ∇F(xk) ‖2
引理 2 果函数F(x)LLipschitz函数满足假设1意k ∈ N满足等
式
E [F(x
1
+ α
)] − F(x ) ≤ −α ∇F(x )T E [g(x ε )] 2 LE
[‖ g(x ε ) ‖2]
εk k+1
k k k εk k k
2 k εk
k k 2
≤ −(µ − 1 αkLMG)αk ‖ ∇F(xk) ‖2 1 2 LM
2 2 + 2 αk
定理 3 果函数FLLipschitz连续函数µ−强凸函数假设算法1中步长固定
意k ∈ N均αk α µ
G
0 < α < LM
意k ∈ N等式：
E[F(xk) − F(x*)] ≤ αLM + (1 − αcµ)k−1(F(x1) − F(x*) − αLM )
2Cµ
→ ∞
k αLM
−− −→ 2Cµ
2cµ
述定理知果步长固定时算法终仅收敛优值点邻域附次优点通断减步长保证算法收敛优值点定理理保证
定理 4 果函数FLLipschitz连续函数µ−强凸函数假设算法1中步长采序
列更新：
β αk γ + k
中β > 1 γ > 0α1 ≤ µ
cµ
意k ∈ N：
LMG
v
E[F(xk) − F(x*)] ≤ γ + k
中
v β2LM *
max{ 2βcµ − 1) (γ + 1)(F(x1) − f (x ))}
机梯度降法(SGD)机量g(xk εk)函数全梯度偏估计 满
足F(xk) E[g(xk εk)]满足
E[F(x
) − α g(x ε ))] ≤ f (x ) − (α
α2L
α * L2) ‖ ∇F(x ) ‖ + E[g(x ε ) − F(x )]
k+1
k k k
k k k
k 2 2 k k k
− 2 2 2
式等号右边第二项预期误差第三项称方差方差存SGD需采变步长方式保证算法收敛方差存导致算法性欠缺果够改进算法方差断减直零便够提升算法性节中介绍三种样方法
机梯度方法相标准梯度方法更加效利数标准梯度方法次更
新目标变量需样实际问题中数会存定冗余
次全体数部分产生效果效率会更高通实验知机梯度方法刚开始降较剧烈会快达定精度次优解 者果忽略通信时间标准梯度方法收敛速度O(nlog(1s))(次迭代需计 算n梯度)然SGD 收敛速度O(1T )次计算梯度收敛速度1sn时实际中计算时间精度求限时SGD标准梯度效果差
23 方差减方法（Variance Reduction Method)
方差存机梯度方法性欠缺原通减方差提升算法性想法首先出种方差减观点[11]假设蒙特卡洛采样 方法更新EX果够高效计算出EYYX 着密切关系断θγ 断逼Y中θγ γ(X − Y) + EYEθγ EX EY 凸组合θγ 方差Var(θγ) γ2[Var(X) + Var(Y) − 2Cov(X Y)]果取γ 1θγ X 偏估计三种较典方法成采思想改进SGD分SAG(机 均梯度方法)SVRG(机方差减方法)SAGA
j
SAGA[11]SAG[9][10] X机梯度方法(SGD)方采样f ′ (xk)Y
做f ′ (φk)SAGA中γ 1SAG 中γ 1 SAG方差SAGA 1
j j n n2
SAGA估计偏估计SVRG[8]采Y f ′ (x)分外两层循环
三种方法更新方式：
j ̃︀
f ′ (xk) − f ′ (φk) 1 ′
j
xk 1 xk − α[
j j +
Σn f (φk)] (S AG)
+ n n
i1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (φk) 1 n f ′ (φk)] (S AGA)
+ j j j + n Σi1 i i
xk 1 xk − α[ f ′ (xk) − f ′ (x) +
1 Σn
f ′ (x)] (S VRG)
+ j j ̃︀ n i1 i ̃︀
SAG[9]早提出具线性收敛速度机梯度方法次更新赖n
SAGA 成结合SAGSVRG两种方法技巧提出新算法SVRG收敛速度相适非强凸问题SVRG 着良性质适非凸函数年关SVRG研究断进行断发展接分介绍三种方法
231 机均梯度方法(Stochastic Average Gradient)
SAG[9][10]成IAG[17]种机版类似机梯度方法次迭代仅需样点计算方量次迭代量方全梯度偏估计 收敛速度线性SAG迭代格式：
xk 1 xk − αk Σn yk
+ n i1 i
中yk f ′ (xk)果i ikik机选取指标否yk保持变
i i i
i
k
SAG方法相SGD着明显优点采固定步长进行更新 着更快收敛性质线性收敛速度需存储n梯度nd 时存储量O(nd)存储量十分巨某特殊函数带线性预测形式函数fi(aT x)存储量减需O(d)果初始梯度选择零量yi 0算法迭代初始步长调1 直更新处k n样调整
提高收敛速度SAG算法[10]：
取合适步长时SAG种线性收敛算法收敛速度O(n + κ)log(1s)
Algorithm 2 SAG
d 0 yi 0 i 1 2 n
∀
for t12 m do
均匀采样 i ∈ 1 2 n d d − yi + f ′ (x)
i
i
yi f ′ (x)
x x − d
α
n
end for
定理[9]：
nL
定理 5 果函数f LLipschitz连续µ−强凸函数果固定步长αk 21
)k[3‖ 2 ix − x ‖+ ]o
关系式：
E[‖xk − x*‖2] ≥ (1 −
µ
8Ln
* 9 Σi‖ f ′ (x*)‖2 4nL2
µ
进步果n ≤ 8L 步长αk f rac12nµSAG迭代满足k ≥ n：
8n
E[ f (xk) − f (x*)] ≤ (1 − 1 )kC
中C [ 16L ‖x
− x*‖2 + 4Σi‖ f ′ (x*)‖2 (8log(1 + µn ) + 1)]
i
3n# 0
3n2µ 4L
式结果k ≥ n时前n步SG方法然前n步迭代均值作SAG初始值时yi 0然SAG着样收敛速度更加难分析实验中直接SAG方法里仅仅出理更界
L
SAG方法种线性收敛机梯度算法收敛速度O(n + κ)log(1s)SAG方法采定步长实际中取αk 1 L通常未知常采线搜索方式确定[9]次迭代存储量O(nd)计算量O(d)n d 较时会影响算法实际效率
232 机方差减梯度方法
SAG第取线性收敛效果机梯度方法机算法研究断深入机方差降梯度方法(SVRG)中重算法[8]等2013年 提出方法种具线性收敛算法适范围极广泛仅适强凸函数非强凸非凸情况样着收敛性质种方法需存储整梯度迭代程中需改变步步长实际操作中更加方便
̃︀
方法分两层循环m次点x计算次全梯度然该点计算 方量量全梯度偏估计然做次梯度降算法思想：
µ ∇F(x)
1 Σn
∇ fi(x)
̃︀ ̃︀
n i1 ̃︀
xt xt−1 − αt(∇ fi (xt−1) − ∇ fi (x) + µ)
t t ̃︀ ̃︀
中it 机{1 n}选择E[xt|xt−1] xt−1 − αt∇F(xt−1)
SVRG种方差断降方法根梯度迭代格式∇ fit (xt−1) − ∇ fit (x) + µ
̃︀ ̃︀ ̃︀t 1 (t 1)
x x(t)收敛x*时µ → 0∇ fi(x) → ∇ fi(x*)时
fi (x − ) − ∇ fi (x) + µ → ∇ fi(x − ) − ∇ fi(x*) → 0
̃︀ ̃︀
∇ t t ̃︀ ̃︀
通格式方差够效控制提高收敛速度SVRG算法
− +
线性收敛果FLLipschitz光滑连续µ 强凸时m足够α 1
µη(1−2Lη)m
2Lη 1−2Lη
< 1
EF(xs) − F(x*) ≤ αs[F(x0) − F(x*)]
中x*优值点 ̃︀ ̃︀
SVRG种线性收敛机算法循环需计算2m + n次梯度
Algorithm 3 SVRG
定初始量x0步长α正整数m
for k12 do
̃︀
计算方量µ ∇F(x0) n Σi1∇ fi(x0)
令x0
xk
̃︀ ̃︀
̃︀
1 n
for j12 m do
机选取ij ∈ 1 2 n
̃︀ ̃︀
x j x j−1 − α(∇ fij (xj−1) − ∇ fij (x0) + µ)
end for
选择(1)令x
x ̃︀
̃︀ ̃︀
̃︀
k+1
选择(2)令x
m
1 Σm x
选择(3)机选取j ∈ {1 2 m}令xk+1 x j
k+1 m j1̃︀j
end for ̃︀
全梯度方法计算复杂度相仅需O(log(1s))次外循环复杂度O(n +
κ)log(1s)
出次循环时计算方量时会全梯度信息SG 着明显差收敛性质较算法中会体现全梯度控制优化程总体方优化程会偏离整体方太远
SVRG方法收敛速度O(n + κ)log(1s)轮循环计算量O(nd + md)通常m取n倍数实际中取m 2nSVRG样适非强凸者非凸目标函数 着极性质参见[18][19][20]
233 SAGA
较 重 方 差 降 方 法 SAGA[11]方 法 SAGA 成SAGSVRG两种方法思想融合SAGA中次迭代方量成前 数次迭代方均值 j ∈ {1 n}机选取具体方式：
gk f ′ (xk) − f ′ (φk) 1 n f ′ (φk)
j j j + n Σi1 i i
n
出SAGA中方选取方式SAG类似仅仅1 换成1改变次选取方量全梯度偏估计成SVRGSAG两种思想结 合形成种新机算法[16][11]
初始化时需计算n梯度需O(nd)计算量外次迭代仅需 计算次方量计算量仅O(d)SG方法计算量相收 敛速度线性收敛目标函数f (x)LLipschitz光滑函数µ−强凸函数时果步
Algorithm 4 SAGA
定初始量x1步长α
for k12 n do
∇
计算梯度 fi(x1)
∇ ← ∇
存储梯度 fi(x[i]) fi(x1)
end for
for j12 do
机选取i ∈ 1 2 n
计算方量gk f ′ (xk) − f ′ (x[i]) + 1 Σn
f ′ (x[i])
i i
存储梯度∇ fi(x[i]) ← ∇ fi(xk)
xk+1 xk − αgk
n i1 i
end for
长α 2( 1
µn+L)
E[‖xk − x*‖2] ≤ (1 − µ )k(‖x1 − x*‖2) + nD
2 2(µn + L) 2 µn + L
3L
中D f (x1) − ∇ f (x*)T (x1 − x*) − f (x*)果µ未知情况选择α 1
会收类似收敛结果[11]
i
储标量̃︀f ′(aT xi) 样做存储量O(n)
i
SAGA线性收敛机算法收敛速度O(n + κ)log(1s)更加灵活初始化方式做轮机梯度获n 函数梯度样做函数初始化时期意义降加快收敛速度缺点SAGA方法需存 储n梯度n d 时需O(nd)存储量针特殊函数形式fi(x) ̃︀fi(aT x)存储量降低∇ fi(x) ̃︀f ′(aT xi)ai仅需i
机偶坐标升法（Stochastic Dual Coordinate Ascent）
坐标降方法(Coordinate descent)尤典方法基思想固定坐标针中某坐标目标函数做优化优化问题minx∈ℜd F(x)坐标降法更新方式：
∂F
xk 1 xk + αk∇i F(xk)ei ∇i F(xk) (xk)
+ k k k
∂xik
xik 代表着优化变量第ik坐标ik ∈ {1 d}机选取eik 代表ik 维1
余0单位量说次迭代仅量ik 维发生变化
坐标降法体现步长坐标选取步长采取精确搜索方法相求解维优化问题问题难度降低少实际更采取非精确搜索方法选取合适步长函数足够降ik选取常见三种 方法： 循环选取{1 d}循环选取{σ(1) σ(d)}σ{1 d}全排
列通常定次数发生改变次迭代放回机选取坐标ik ∈ {1 d}机方法第种方法更加效理者实践着更效果关原公开问题
机器学中正化验风险函数问题列问题：
min P(ω) [ 1 Σn
fi(aT ω) + λg(ω)]
ω∈ℜd
n i1 i
中fi(ω) g(x)均凸函数优化问题等价化偶函数形式：
max
D(α) [ 1 Σn − f *(−αi) − λg*( 1 Σn
aiαi)]
)α∈ℜd×n
n i1 i
λn i1
机坐标偶[12]种坐标降法思路坐标升方法相似 固定坐标中某坐标求解优化问题相CD方法化某函数F(x)SDCA化偶函数D(α)更新坐标时SDCA需求解函数值优化问题
机偶坐标升法（SDCA）理着保证种线性收敛
Algorithm 5 SDCA
初始化 α(0) 0v(0) 1 Σn
aiα(0)ω(0) ∇g*(0)
for t12 T do
λn i1 i
机选取 k ∈ 1 2 n 更新权值
y(t+1) arg max∆α − f *(−(α(t) + ∆αk)) − λg*(v(t) + 1 ak∆αk)
k k i k λn
α(t+1) a(t) + ∆αk
v k 1) v k + 1 a ∆α )
(t+
(t) i i
v(t+
ω(t+1) ∇g*( λn 1))
end for
输出(Averaging option)
令 α 1 ΣT
α(t)
T −T0 tT0+1
令 ω 1 ΣT
ω(t)
T −T0
返回 ω
tT0+1
输出(Random option)
∈
令 α α(t) ω ω(t) 意 t T0 + 1 T
返回 ω
机算法： L − Lipschitz 损失函数SDCA收敛速度O(n + L2(λs)) (1γ)光
滑损失函数达O((n + κ)log(1s)))
λs
λs
机梯度降(SGD)收敛速度O( 1 ) n ≫ 1 时 SGD效果
λn
λ
SDCA 1 ≫ s时SDCA更点实际情况1 O(n)者起
̃︀
码O( √n)阶SDCASGD效果 刚开始迭代时SDCA效果SGDSGD采更步长实际中常常采SGD SDCA 相结合方法初始迭代时先利SGD 原函数值快速降达某点ω 该点作SDCA 初始点进行迭代进优点分两阶段阶段1SGD 方式满足终止条件时α 阶段2SDCA更新令α(0) α
正前提坐标降法(CD)中指标选取方法概分三种方式机选取定序循环选取放回选取(次定序循环选取序会断改变)SDCA作种坐标升方法采三种方式实验表明 机方法远远优非机方法放回选取方式效果机选取效果更点算法中已观测然目前止种更新方式研究
较少放回抽取方式(without replacement)值进步研究
[21]等提出种加速方法算法收敛速度达(n + √κlog(1s))：
n
选择合适参数K O( 1 )β
For(t12 )
令P
κ (t−1) 2
̃︀t(ω) P(ω) + 2 ‖ ω − y ‖
̃︀
(t)
(t)
proxSDCA方法求解原函数似函数Pt(ω)(ω
Nesterov加速方法加速算法令y(t) ω(t) + β(ω(t) − ω(t−1)) Endfor
)α
{ √ } ≫
ASDCA着收敛性质 假设函数L − Lipshitz梯度连续 µ−强凸函数
APSDCA收敛速度O(n + min κ nκ )log(1s)) κ n时 收敛速度
O(n + √nκ)log(1s)阶机算法收敛速度
25 机原始偶坐标法（Stochastic Primal Dual Coordinate）
正化验风险函数问题列问题：
min P(x) [ 1 Σn
fi(aT x) + λg(x)]
x∈ℜd
n i1 i
中fi(x) g(x)均凸函数函数问题转化成原始偶鞍点问题：
min max 1 Σn (yi⟨ai x⟩ − f *(yi)) + g(x)
x∈ℜd y∈ℜn n
i1 i
鞍点问题成博弈问题通断化原始变量化偶变量断优
化优点机原始偶坐标法[13]变采样思想
算法6出种算法详细描述偶坐标原始坐标更新通通交
Algorithm 6 SPDC
输入 m 参数 τ σ θ ∈ ℜ+ x(0) y(0)迭代次数 T
初始化 x(0) x(0) u(0) 1 Σn
y(0)ai
for t12 T1 do
n i1 i
n
机选择指标集 K ⊂ {1 2 n} m 指标相概率 of m
选中
i
2σ
i
i
i
yt+1 arg maxβ∈ℜ{β⟨ai x(t)⟩− fi*(β) − 1 (β− y(t))2} (1) 果 i ∈ K 否y(t+1) y(t)
(t) 2
x∈ℜd
m
k∈K
k
k
k
2τ
2
x(t+1) arg min {g(x) + ⟨ut + 1 Σ (y(t+1) − y(t))a x⟩ + ‖x−x ‖ } (2)
−
n
k
k
u(t+1) u(t) + 1 Σk∈K (y(t+1) − y(t))ak (3)
x(t+1) x(t+1) + θ(x(t+1) x(t)) (4)
end for
输出 x(T ) y(T )
化y化x出增加两二次项引入参数στ两参
数仅控制正化项强弱控制次更新步长外引进u(t)x(t)
u(t)类SDCA中ω(t)定程度代表函数梯度信息x(t)通x(t) x(t+1)外推出种类似Nesterov 加速方式步证明时候着关键作
定理 6 假设φi(1γ)−光滑函数g λ−强凸函数令R
τ 1 √︂ mγ σ 1 √︃ nλ θ 1 − 1
max{‖ai‖2 i 1 n}果参数τσθ 选取
2R nλ
2R mγ
(nm) + R √︀(nm)(λγ)
意t ≥ 1批量SPDC算法收敛性：
( 1 2τ
+ λ)E[‖x(t) − x*‖2] + ( 4
+ γ)
E[‖y(t) − y*‖2]
2
2
2
2 )
1
1
m
σ
t
1
≤ θ (( 2τ
+ λ)‖x(0) − x*‖2 + ( 2
+ γ)
‖y(0) − y*‖2
m
σ
面推说明达s精度期迭代复杂度：
推 1 果φi(1γ)−光滑函数g λ−强凸函数参数前述定理设置算法6达条件
2
2
E[‖x(T ) − x*‖2] ≤ s E[‖y(T ) − y*‖2] ≤ s (11)
迭代次数T 满足
T ≥ ( n
+ R √︂ n )log C
m mλγ ( s )
中
( 1
+ λ)‖x(0) − x*‖2 + ( 1 + γ)‖y(0)−y*‖2
C 2τ
2 2σ m
2
2τ
4σ
min{ 1 + λ ( 1 + γ)m}
处理器时算法6次迭代需O(md)时间坐标yk更新完全独立坐标够分布式计算方式加速批量SPDC方法具体说够m处理器行更新子集K 中m 坐标然更新x(t+1)果忽略通信延迟次迭代仅仅需O(d) 时间毫惊讶m 时表明SPDC算法收敛更快次迭代更新偶变量
然目前关异步SPDC算法研究少文作者做出定探究
通减步长σ方式异步SPDC定条件着线性收敛收敛速度
SPDC缺点收敛速率常数R常数根问题定 特征量二范数值非标准化数算法会表现差特特征量二范数远时候
基想法次迭代选取偶坐标时非均匀采样概率选取具体
说坐标选取概率p 1 + ‖ak ‖2 着更范数特征量选取
2Σ
k 2n
n i1
‖ai‖2
性应该更时更新原始变量偶变量时更新表示式变
yt+1 arg max{β⟨ai x(t)⟩ − f *(β) − pin (β − y(t))2}
i
β∈ℜ
i 2σ i
外调整(13) 中ak权重更新原始变量
u(t+1) u(t) + 1 (y(t+1) − y(t))ak
pkn k k
定理 7 果φi(1γ)−光滑函数g λ−强凸函数参数前
述定理设置令R 1 Σn ‖ai‖2 果算法2中τ σ θ选值：
n
i1
4R
nλ
4R
γ
γλ
τ 1 √︂ γ σ 1 √︃ nλ θ 1 − (2n + 2R √︂ n )−1
意t ≥ 1
( 1 + λ)E[‖x(t) − x*‖2] + ( 7 + 2γ)E[‖y(t) − y*‖2]
2τ 2 16σ n 2
≤ θt(( 1 + λ)‖x(0) − x*‖2 + ( 1 + 2γ)‖y(0) − y*‖2)
2τ 2 2σ 2
定理5中参数θ定理5中θ进行较定理5中常数R特征量范数均值决 定值算法非标准特征量更加鲁棒果ai相互 独立均服某维正态分布n → ∞maxi{‖ai‖2}必然趋穷
n
i1
范数均值1 Σn ‖ai‖2 收敛E[‖ai‖2]
26 加速方法Catalyst
Nesterov加速方法GD着更收敛性质加速已机算法成值研究方节介绍加速框架适种阶机优化方法SAGSVRGSAGASDCA等强凸函数着线性收敛性质阶方法均通种框架加速
方法思想通结合Nesterov技巧迭代求解原函数着
优良性质似函数 种方法着收敛性质 强凸函数 达
O(n + √nκlog(1s)) 果函数非强凸加速非强凸函数收敛速
度
述算法次外循环成两步组成 分称Catalyst步加速步
Algorithm 7 Catalyst
{ }
输入初始点x0参数Kα0序列 sk 优化方法M 初始化 令q µ(µ + κ)y0 x0
for t12 T1 do
方法M寻找似解
xk ≈ arg min{Gk(x) F(x) + K ‖x − yk−1‖2} Gk(xk) − G* ≤ sk
x∈ℜd
计算αk ∈ (0 1)满足α2 (1 − αk)α2
2 k
+ qαk
计算 k k−1
yk xk + βk(xk − xk
1) βk αk−1(1 − αk−1)
end for
输出 x(T )
− α2
k−1
+ αk
Catalyst步原函数基础加二次强凸函数函数着更性
质果函数非强凸通添加二次项方式函数变成强凸函数果函
数强凸函数L+κ < L 知函数条件数变更加速步成
µ+κ µ
外推Nesterov 加速FISTA算法中采技术相似
定理 8 强凸函数收敛性 果令α0 √qa µ(µ + K)
9
sk 2 (F(x0 − f *)(1 − ρ)k ρ < √q
算法迭代序列{xk}
(
F(xk) − F* ≤ C(1 − ρ)k+1(F(x0) − F*) C
8
√ 2
q − ρ)
述定理种方法收敛速度线性sk选择变F* 事先知道F(x0) − F*界代通x0算偶距离
强凸函数果算法收敛速度O(n + κ)log(1s)Catalyst加速
收敛速度加速O(n + √nκ)log(1s)Catalyst加速方法需事先选取K序
列{sk}造成实际实现中苦难
27 Katyusha
全梯度方法优收敛速度通加Nesterov称种方法AGD机阶方法采取类似技巧进行加速样做稳定果某梯度估计值够精确加动量着方进步移动会损害收敛性 说简单Nesterov技巧加速目
Katyusha[22]种直接加速机算法强凸函数时间复杂度0(n +
√nκlog(1s))非强凸函数时间复杂度O(nlog(1s) + √nLs · ‖x0 − x*‖)
定理 9 果fiL光滑凸函数ψ(x)µ−强凸Katyusha算法
s * ⎧⎪⎨ O((1 + √σ(3Lm))−S m) · (F(x0) − F(x*)) mσ ≤ 3
L 4
L
4
E[F(x )] − F(x ) ≤ ⎪
̃︀ ⎩
O(15−s) · (F(x0) − F(x*)) mσ ≥ 3
果选择m O(n)达次优解F(xs) − F(x*) ≤ s需O((n + √nLσ) ·
s
log( F(x0)−F(x*) ))次迭代 ̃︀
Algorithm 8 Katyusha
√mσ 1
√
2
3L
初始化 令m2nτ 1 τ min{ }α 1 y z x0 x
2 2 1
for s12 S1 do
3τ1 L 0
0 ̃︀ 0
̃︀
µs f (xs)
fo∇r t12 T1 do
ksm+j
x τ z + τ xs + (1 − τ − τ )yk+1 1 k 2 1 2 k
1
2
zk+1 arg minz{ 2α ‖z − zk‖
+ ⟨̃︀∇k+1 z⟩ + ψ(z)}
̃︀∇k+1 µs + ∇ fi(̃︀xk+1) − ∇ fi(̃︀xs)机选取i ∈ {1 2 n}
3L
2
选择1：yk+1 arg miny{ 2 ‖y − xk+1‖
选择2：yk+1 xk+1 + τ1(zk+1 − zk)
+ ⟨̃︀∇k+1 y⟩ + ψ(y)}
̃︀
end forxs+1 (Σm−1(1 + ασ) j)−1 · (Σm−1(1 + ασ) j · ysm+ j+1)
end for
̃︀
输出 xs
j0
j0
̃︀ ̃︀ ̃︀
Katyusha已知唯种达优收敛速度机算法Katyusha 分外两层循环外循环m次循环组成理m意n倍数通常取m 2nxk+1 τ1zk + τ2 xs + (1 − τ1 − τ2)yk知xk+1成zkxsyk凸组合τ2 0时
2
Katyusha变成SVRG结合Nesterov技巧算法τ2 Ç 0时xs成负动量 矫正迭代方真实方偏离太保证梯度估计较精确 Katyusha方法优良性质关键称Katyusha动量实际τ2(0 1)中数调整参数验表明τ2 1 够达
效果
3 二阶方法
31 牛顿法拟牛顿法
种较重方法牛顿法(Newton)牛顿法利函数二阶信息迭代方效提高算法收敛速度牛顿法二阶泰勒展开假设某点xk
2
f (xk + p) ≈ f (xk) + ∇ f (xk)T p + 1 pT ∇2 f (x)p mk(p)
假 设 函 数 Hessian阵 正 定 通 化mk(p) 牛 顿 方
pk −∇2 f (xk)∇ f (xk)∇2 f (xk)正定pk * ∇ f (xk) < 0pk降方
牛顿方法迭代格式：
xk+1 xk − αk∇2 f (xk)∇ f (xk)
通常 迭代步长选择1 满足降情况条件时 会调整步长∇2 f (xk)正定时候出牛顿方存∇2 f (xk)逆存外 pk * ∇ f (xk)非负种情形会采相关技巧方降方牛顿方法着快局部收敛速度某条件达二次收敛速度牛顿方法缺点需计算Hessian阵∇2 f (xk)需求逆n时候计算量存储量太
拟牛顿法(QuasiNewton)牛顿法改进需计算Hessian阵逆矩 阵着超线性收敛速度次迭代矩阵Bk似Hessian 阵时矩阵通前步相关信息迭代通常Bk称正定矩阵记逆Hk函数二次连续微时
∇ fk(xk+1 − xk) ≈ ∇ fk+1 − ∇ fk
BkHessian阵似然希Bk满足等式
Bk+1 sk yk
中yk ∇ fk+1 − ∇ fksk xk+1 − xk称述等式割线方程更新格式：
xk+1 xk − αkHk∇Fk
拟牛顿方法种迭代方式常见秩1修正秩2修正两种方式秩1方法
称SR1(symmetricrankone) 方法较代表秩2方法BFGSDFP方法
311 SR1
SR1迭代格式示：
Bk+1 Bk +
(yk − Bk sk)(yk − Bk sk)T
(yk − Bk sk)T sk
Bk正定矩阵时SR1迭代保证Bk+1着正定性质SR1缺点迭代会突然消失(yk − Bk sk)T sk Ç 0满足割线方程迭代格式唯确定 yk Bk sk满足割线方程仅Bk+1 Bk果yk Ç Bk ss(yk − Bk sk)T sk 0会满足割线方程SR1迭代序列种情形表明SR1方法数值稳定性
然SR1方法然着错性质说SR1方法真实Hessian阵着
更似BFGS方法效果
312 BFGSDFP
BFGS方法迭代方式
k
k
k
Hk+1 (I − ρk skyT )Hk(I − ρkyk sT ) + ρk sk sT
sT yk
中ρk 1 skyk > 0时果Hk正定矩阵Hk+1正定矩阵通常选
k
+1
取H0 δI δ > 0根ShermanMorrisonWoodbury公式写出Bk+1 Hk−1 更新方
式
BFGS方法目前止效拟牛顿方法目标函数二次函数时着超线 性收敛性质采精确线搜索时理实验均保证BFGS着修复性 质ρk极正数时显然样估计会导致收敛速度变慢BFGS会 数步纠正样问题BFGS着良性重原
种著名方式DFP成BFGS方法偶形式格式
k
k
k
Bk+1 (I − ρkyk sT )Bk(I − ρk skyT ) + ρkykyT
果BFGSDFP方法做线性组合Broyden类方法
k+1
k+1
Bk+1 (1 − φk)BBFGS + φk BDFP
32 LimitedmemoryBFGS
拟牛顿法迭代格式：
xk+1 xk − αkHk∇Fk
中αk步长HkHessian阵逆种似中种更新方式BFGS格
式着效果
Hk+1 VT HkVk + ρkyk sT
k k
k
yT sk
k
中ρk 1 Vk I − ρkyk sT sk xk+1 − xk yk ∇ fk+1 − ∇ fk
步更新Hk时候需利前步信息数维数样数量
Algorithm 9 LBFGS twoloop
a fk
← ∇
for ik1k2 km do
end forr ← H q
i
0
αi ← ρi sT q q ← q − αiyi
k
for ikmkm+1 k1 do
i
←
β ρiyT r
← −
r r + si(αi β)
end for
输出 Hk∇ fk r
较时需耗费相计算量储存空间减算法时间复杂度Nocedal 等提出LBFGS算法次更新仅前m步相关信息通常m选320中 常数提出相实twoloop算法更新Hk∇ fk 种方法非显式利Hk需计算Hk · ∇ fk时需存储Hessian阵(n × n)者减少存储开支
LBFGS种二阶方法twoloop算法提出降低开销规模 机器学问题运算量存储量非常惊vectorfree LBFGS[23] 种更加实算法较twoloop运算复杂度LBFGS 算法更加适应分布式计算环境
Hk∇ fk成{si yi}∇ fk线性组合整计算程中参变量保持变运算程仅仅设计两量积形式通直 接求系数减少计算量仅仅需输入2m + 1量两两间积(2m + 1) × (2m + 1)积矩阵更新时候够利先前留积矩阵信息计算量者存开销远远twoloop算法
Algorithm 10 vectorfree LBFGS twoloop
输入 (2m + 1) (2m + 1)积矩阵令δ2m+1 1余系数δi 0 for ik1k2 km do
−
*
ji(km)+1
α l1
Σ 2m+1δlblbj
i
−
δ b j·bm+ j
m+ j δm+ j αi
end for
for i12 2m+1 do
δi bm·b2m δi
end for
b2m·b2m
for ikmkm+1 k1 do ji(km)+1
l1
β Σ2m+1δlbm+ j·bl
b j·bm+ j
−
δ j δ j + (αi β)
end for
输出 Hk∇ fk r
33 机牛顿方法
机LBFGS方法结合方差减思想[24]提出种机LBFGS方法 方法实践中表现需降步长强凸函数算法线性收敛速度
算法参数控制mLMm次迭代断减方差需 计算次全梯度L步需更新函数Hessian阵量sr记录2L步均降 方yr通Hessian阵似矩阵sr相通常意义LBFGS方法 通常yr通计算梯度
种具线性收敛速度算法果函数二次连续微凸函数
意τ ⊆ {1 2 N}均
λI ⪯ ∇2 fτ(ω) ⪯ ΛI λ > 0 L > 0
E[ f (ω ) − f ( *)] ≤ k E[ f ( ) − f (
*)]
1(2mη) + ηΓ2Λ2
k ω α ω0 ω
α
γλ − ηΓ2Λ2
适选择mML时α < 1然种算法没充分利二阶信息种方法通结合机方差减思想机拟牛顿方法取线性收敛效果相关数值实验证明算法性然种方法需调整参数mML疑增算法
Algorithm 11 机LBFGS
输入 ω0参数 mM L批量 b bH步长 η
初始化 r0H0I
for k012 do
∇
计算全梯度 µk f (ωk)
令 x0 ωk
for t0 m1 do
⊆
机选择集合 S kt 1 N
∇
计算机梯度 fS kt (xt)
∇ − ∇
计算方差减梯度 vt fS kt (xt) fS kt (ωk) + µk
−
令 xt+1 xt ηHrvt
果 t整L rr+1
令 ur 1 Σt−1 x j
L jt−L 2
机采样τr ⊆ 1 N 机似∇ fτr (µr)
− ∇
计算 sr ur ur−1 yr 2 fτr (µr)sr 更新 Hr
end for
∈ { − }
ωk+1 xi 机 i 0 m 1 选择
end for
实现难度
规模问题二阶方法研究工作较限二阶方法值进步研究关机二阶算法参见[25][26][27][28]
4 数值实验
节采造数进行相关数值实验较算法通实验
算法收敛速度直观认识
i1
生成500独立分布数{ai bi}n
根模型
b ⟨ai x*⟩ + s a ∼ N(0 Σ) s ∼ N(0 1)
a ∈ ℜd d 500x*全1列量Σ病态角矩阵角线元素
Σ j j j−2{ai bi}考虑求解嵴回模型实验设定参考[13]
min 1 Σn
1 (aT x − bi)2 + λ‖x‖2
x∈ℜd n
i1 2 i 2 2
较种算法求解问题数值性取λ{1e − 3 1e − 4 1e − 5 1e − 6}四
种取值
步长选取SGD选择步长1T SVRG选择步长01LSAGA选择步长13LSAG选择步长12L竖轴log(P(xT ) − P(x*))横轴梯度估计次数全体数数值
Algorithm
Runtime
SGD
O(1s2)
SAG
0(n + κ)log(1s)
SAGA
0(n + κ)log(1s)
SVRG
0(n + κ)log(1s)
SDCA
0(n + κ)log(1s)
SPDC
L − Lipshitzµ−强凸函数言种算法收敛速度：
0(n + √nκ)log(1s)
理结果出SGD收敛速度慢种方法数值实验表现明显 SPDC 作种加速方法收敛速度快远远优种算法 SAGSVRGSAGA 三种算法说理收敛速度致数值试验中性十分相实际中应该根具体问题选择种算法SDCA作种偶方法 数值结果够稳定收敛速度较
SGD SVRG SAGA
SAG
SPDC
SDCA
0
−2
−4
−6
−8
−10
lambda1e−3
lambda1e−4
SGD SVRG SAGA SAG
SPDC
SDCA
1
0
−1
−2
−3
−4
−5
−12 −6
−14 −7
−16
−18
0 10 20 30 40 50 60
−8
−9
0 10 20 30 40 50 60
1 1
lambda1e−5
SGD SVRG
SAGA
SAG SPDC SDCA
1
SGD SVRG
SAGA
SAG SPDC SDCA
05
lambda1e−6
05
0
−05
−1
0
−05
−15 −1
−2
−25
−15
−3
−2
−35
−4
0 10 20 30 40 50 60
−25
0 10 20 30 40 50 60
1 1
参 考 文 献
[1] Cortes C Vapnik V Supportvector networks[J] Machine learning 1995 20(3)273–297
[2] Hastie T Tibshirani R & Friedman J(2008) The Elements of Statistical Learning Data Mining Inference and Prediction[缺文献类型标志代码][Sl] Springer New York
[3] Bishop C M Pattern recognition and machine learning[M][Sl] Springer 2006
[4] Nesterov Y A method of solving a convex programming problem with convergence rate O (1k2)[C]Soviet Mathematics Doklady [Sl] [sn] 198327372–376
[5] Nesterov Y Introductory lectures on convex optimization A basic course[缺文献类型标志代
码][Sl] Springer Science & Business Media
[6] Zhang T Solving large scale linear prediction problems using stochastic gradient descent algorithm s[C]Proceedings of the twentyfirst international conference on Machine learning [Sl] [sn] 2004116
[7] Robbins H Monro S A stochastic approximation method[J] The annals of mathematical statistics 1951400–407
[8] Johnson R Zhang T Accelerating stochastic gradient descent using predictive variance reduc tion[C]Advances in Neural Information Processing Systems [Sl] [sn] 2013315–323
[9] Roux N L Schmidt M Bach F R A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets[M] Pereira F Burges C J C Bottou L et al Advances in Neural Information Processing Systems 25[Sl] Curran Associates Inc 20122663–2671
[10] Schmidt M Le Roux N Bach F Minimizing finite sums with the stochastic average gradient[J] Math ematical Programming 20131–30
[11] Defazio A Bach F LacosteJulien S SAGA A Fast Incremental Gradient Method With Support for NonStrongly Convex Composite Objectives[M] Ghahramani Z Welling M Cortes C et al Ad vances in Neural Information Processing Systems 27[Sl] Curran Associates Inc 20141646–1654
[12] ShalevShwartz S Zhang T Stochastic dual coordinate ascent methods for regularized loss minimiza tion[J] Journal of Machine Learning Research 2013 14(Feb)567–599
[13] Zhang Y Lin X Stochastic PrimalDual Coordinate Method for Regularized Empirical Risk Minimiza tion[C]ICML [Sl] [sn] 2015353–361
[14] Wright S Nocedal J Numerical optimization[J] Springer Science 1999 3567–68
[15] Gu¨ rbu¨ zbalaban M Ozdaglar A Parrilo P Why random reshuffling beats stochastic gradient descen t[J] arXiv preprint arXiv151008560 2015
[16] Bottou L Curtis F E Nocedal J Optimization methods for largescale machine learning[J] arXiv preprint arXiv160604838 2016
[17] Blatt D Hero A O Gauchman H A convergent incremental gradient method with a constant step size[J] SIAM Journal on Optimization 2007 18(1)29–51
[18] AllenZhu Z Yuan Y Improved SVRG for nonstronglyconvex or sumofnonconvex objec tives[R][Sl] Technical report arXiv preprint 2016
[19] AllenZhu Z Hazan E Variance reduction for faster nonconvex optimization[J] arXiv preprint arX iv160305643 2016
[20] Reddi S J Hefny A Sra S et al Stochastic variance reduction for nonconvex optimization[J] arXiv preprint arXiv160306160 2016
[21] ShalevShwartz S Zhang T Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[C]ICML [Sl] [sn] 201464–72
[22] AllenZhu Z Katyusha The first direct acceleration of stochastic gradient methods[J] arXiv preprint arXiv160305953 2016
[23] Chen W Wang Z Zhou J Largescale LBFGS using MapReduce[C]Advances in Neural Information Processing Systems [Sl] [sn] 20141332–1340
[24] Moritz P Nishihara R Jordan M I A linearlyconvergent stochastic lbfgs algorithm[C]Proceedings of the Nineteenth International Conference on Artificial Intelligence and Statistics [Sl] [sn] 2016
[25] Byrd R H Hansen S L Nocedal J et al A stochastic quasiNewton method for largescale optimiza tion[J] SIAM Journal on Optimization 2016 26(2)1008–1031
[26] Bordes A Bottou L Gallinari P Sgdqn Careful quasinewton stochastic gradient descent[J] Journal of Machine Learning Research 2009 10(Jul)1737–1754
[27] Poole B Fast largescale optimization by unifying stochastic gradient and quasiNewton methods[J] 2014
[28] Lucchi A McWilliams B Hofmann T A variance reduced stochastic newton method[J] arXiv preprint arXiv150308316 2015
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
