一种基于条件梯度的加速分布式在线学习算法.pdfVIP

第

50

卷

第

2

期自

动

化

学

报Vol.

50,

No.

2

2024

年

2

月ACTA

AUTOMATICA

SINICAFebruary,

2024

一种基于条件梯度的加速分布式在线学习算法

1121

吴庆涛

朱军龙

葛泉波

张明川

摘要

由于容易实施,

基于投影梯度的分布式在线优化模型逐渐成为一种主流的在线学习方法.

然而,

在处理大数据应

用时,

投影步骤成为该方法的计算瓶颈.

近年来,

研究者提出了面向凸代价函数的分布式在线条件梯度算法,

其悔界为

O,

其中是一个时间范围.

该算法存在两方面的问题,

一是其悔界劣于公认的悔界O;

二是没有分析非凸代

价函数的收敛性能,

而实际应用中代价函数大部分是非凸函数.

因此,

提出一种基于条件梯度的加速分布式在线学习算法,

使用Frank-Wolfe

步骤替代投影步骤,

避免昂贵的投影计算.

文中证明当局部代价函数为凸函数时,

所提算法达到公认的

悔界O;

当局部代价函数为潜在非凸函数时,

所提算法以速率O收敛到平稳点.

最后,

仿真实验验证了所提算法

的性能与理论证明的结论.

关键词

条件梯度,

分布式在线学习,

悔界,

收敛速率

引用格式

吴庆涛,

朱军龙,

葛泉波,

张明川.

一种基于条件梯度的加速分布式在线学习算法.

自动化学报,

2024,

50(2):

386−402

DOI

10.16383/j.aas.c210830

AnAcceleratedDistributedOnlineLearningAlgorithmBasedonConditionalGradient

1121

WU

Qing-Tao

ZHU

Jun-Long

GE

Quan-Bo

ZHANG

Ming-Chuan

Abstract

The

distributed

online

optimization

model

based

on

projected

gradient

has

become

a

prominent

paradigm

for

online

learning

due

to

its

simplicity.

However,

this

paradigm

is

incapable

of

handling

massive

data

ap-

plications

because

the

projection

step

becomes

the

computational

bottleneck.

Recent

studies

have

presented

the

dis-

3/4

tributed

online

conditional

gradient

algorithms

for

convex

cost

functions,

which

ac