GSOS：高斯-塞德尔算子分裂算法，用于多项非光滑凸组合优化。资源-CSDN文库

98 浏览量 2021-03-11 23:29:11 上传评论收藏 584KB PDF 举报

高斯-塞德尔算子分裂算法（GSOS）是一种针对多项非光滑凸组合优化问题的快速算法。该算法在机器学习、信号处理和统计学等领域有着广泛的应用。GSOS算法利用了高斯-塞德尔技术来加速优化过程，并借助算子分裂技术来降低计算复杂性。此外，本文还提出了一种新技巧，用以建立GSOS算法的全局收敛性。通过引入算子优化理论中的工具，将GSOS迭代过程重新表述为两步迭代算法，并在此基础上建立算法的收敛性。本文还展示了如何应用GSOS算法来解决重叠群Lasso和图引导的融合Lasso问题，并通过数值实验表明GSOS算法在效率和效果上都优于现有的先进算法。在引入部分，文章聚焦于多项非光滑凸组合优化问题。具体来说，这个问题可以表述为在某个线性空间X中，最小化一个目标函数，该函数是可微凸函数f(x)和n个适当定义、下半连续的凸函数gi(x)的和。数学表达式为min x∈X f(x) + Σn i=1 gi(x)。在这里，gi:X→(−∞,+∞]为适当的下连续凸函数，对所有的i=1,...,n成立。而f:X→(−∞,+∞)是一个连续的凸函数，其梯度满足一个Lipschitz连续性条件，即梯度的差的范数的平方小于等于梯度差与变量差的内积，并且这个比例常数为1/L。 GSOS算法的提出主要基于以下几个方面：高斯-塞德尔技术能够在优化过程中加速，因为它允许在迭代过程中考虑当前解的最新信息。算子分裂技术的利用能够减少计算复杂性，因为它可以将复杂的问题分解为更简单的问题进行处理。文章中介绍的两步迭代算法的重表述，为建立GSOS算法的收敛性提供了理论基础。在实际应用中，GSOS算法被用来解决两类具有挑战性的优化问题：重叠群Lasso问题和图引导的融合Lasso问题。重叠群Lasso问题是统计学和机器学习中的一个重要问题，它涉及到在给定的线性空间中，寻找一个最优解使得一个可微分的凸函数和一个非光滑的凸函数之和最小化。这一类问题在诸如同时低秩和稀疏性、重叠群Lasso等方面有着广泛的应用。例如，Richard等人在2012年和Zhou等人在2013年分别对同时低秩和稀疏性问题进行了研究，而Zhao等人在2009年对重叠群Lasso问题进行了探讨。GSOS算法的应用范围广泛，可以在这些领域中为研究人员和工程师提供有效的优化工具。通过数值实验，GSOS算法在效率和效果上被证明优于现有的先进算法。实验中将GSOS算法与其他优化方法进行比较，展示了其在收敛速度以及优化结果质量上的优势。这种性能上的提升对于实际问题的求解是至关重要的，特别是在数据量庞大、问题规模复杂的情况下，有效的算法能够大幅度节约资源和时间。文章的创新之处在于不仅提出了一种新的算法，而且给出了一种能够保证该算法全局收敛性的新技巧。GSOS算法的提出与证明体现了计算机科学、数学和应用统计学等领域的交叉和融合，展示了多学科合作在解决复杂优化问题上的潜力。文章作者分别来自中国腾讯AILab、中山大学和香港中文大学。这些作者的联合工作，反映了学术界对于新兴算法研究的重视，也显示了跨机构合作在科学探索中的重要性。GSOS算法的研究对于推动相关学科的研究进展以及促进实践中的应用都有重要的意义。在机器学习、信号处理和统计学等领域，GSOS算法的提出为这些领域提供了新的工具，有助于解决现实世界中的复杂问题。

资源推荐

资源详情

资源评论

GSOS: Gauss-Seidel Operator Splitting Algorithm for

Multi-Term Nonsmooth Convex Composite Optimization

Li Shen

Wei Liu

Ganzhao Yuan

Shiqian Ma

Abstract

In this paper, we propose a fast Gauss-Seidel

Operator Splitting (GSOS) algorithm for ad-

dressing multi-term nonsmooth convex compos-

ite optimization, which has wide applications in

machine learning, signal processing and statistic-

s. The proposed GSOS algorithm inherits the ad-

vantage of the Gauss-Seidel technique to acceler-

ate the optimization procedure, and leverages the

operator splitting technique to reduce the com-

putational complexity. In addition, we develop

a new technique to establish the global conver-

gence of the GSOS algorithm. To be speciﬁc, we

ﬁrst reformulate the iterations of GSOS as a two-

step iterations algorithm by employing the tool of

operator optimization theory. Subsequently, we

establish the convergence of GSOS based on the

two-step iterations algorithm reformulation. At

last, we apply the proposed GSOS algorithm to

solve overlapping group Lasso and graph-guided

fused Lasso problems. Numerical experiments

show that our proposed GSOS algorithm is supe-

rior to the state-of-the-art algorithms in terms of

both efﬁciency and effectiveness.

1. Introduction

In this paper, we focus on the multi-term nonsmooth con-

vex composite optimization

min

x∈X

f(x) +

i=1

(x), (1)

where X is a linear space, g

: X → (−∞, +∞] is

a proper, lower semicontinuous convex function for al-

l i = 1, · · · , n, and f : X → (−∞, +∞) is a continuous

Tencent AI Lab, China

Sun Yat-sen University, China

The Chinese University of Hong Kong, China. Correspon-

dence to: Li Shen <mathshenli@gmail.com>, Wei Liu <wli-

u@ee.columbia.edu>.

Proceedings of the 34

International Conference on Machine

by the author(s).

differentiable convex function with its gradient satisfying

the inequality that



∇f(x) − ∇f (y)



≤



∇f(x) − ∇f (y), x − y



. (2)

The above multi-term nonsmooth convex composite opti-

mization problem (1) covers a large class of applications

in machine learning such as simultaneous low-rank and s-

parsity (Richard et al., 2012; Zhou et al., 2013), overlap-

ping group Lasso (Zhao et al., 2009; Jacob et al., 2009;

Mairal et al., 2010), graph-guided fused Lasso (Chen et al.,

2012; Kim & Xing, 2009), graph-guided logistic regres-

sion (Chen et al., 2011; Zhong & Kwok, 2014), variation-

al image restoration (Combettes & Pesquet, 2011; Dup

et al., 2009; Pustelnik et al., 2011), and other types of struc-

ture regularization paradigms (Teo et al., 2010; 2007). By

introducing the multi-term nonsmooth regularization term

i=1

(x) such as structured sparsity (Huang et al., 2011;

Bach et al., 2012; Bach, 2010) and nonnegativity (Chen &

Plemmons, 2015; Xu & Yin, 2013), more prior informa-

tion can be included to enhance the accuracy of regulariza-

tion models. However, due to the multi-term nonsmooth

regularization term

i=1

(x), the optimization problem

(1) is too complicated to be solved even for small n. For

n ≤ 2, some existing popular ﬁrst-order optimization

methods are accelerated proximal gradient method (Beck

& Teboulle, 2009; Nesterov, 2007), smoothing accelerat-

ed proximal gradient method (Nesterov, 2005a;b), three

operator splitting method (Davis & Yin, 2015), and some

primal-dual operator splitting methods such as majorized

alternating direction method of multiplier (ADMM) (Cui

et al., 2016; Lin et al., 2011), fast proximity method (Li &

Zhang, 2016), and so on.

On the other hand, when n ≥ 3, there also exist some al-

gorithms for solving problem (1). A directly method for

(1) is smoothing accelerated proximal gradient (S-APG)

proposed by Nesterov (Nesterov, 2005a;b). Then, Yu (Yu,

2013) proposed a new approximation method called PA-

APG for handling (1) by combining the proximal average

approximation technique and Nesterov’s acceleration tech-

nique, which has been enhanced very recently by Shen

et al. (Shen et al., 2017). Their proposed method called

APA-APG adopts an adaptive stepsize strategy. However,

GSOS: Gauss-Seidel Operator Splitting Algorithm for Multi-Term Nonsmooth Convex Composite Optimization

the above mentioned methods S-APG, PA-APG and its en-

hanced version APA-APG all need a strict restriction on the

nonsmooth functions {g

(x)} that each g

(x) must be Lip-

schitz continuous. In addition, some primal-dual parallel

splitting methods (Briceno-Arias et al., 2011; Combettes

& Pesquet, 2007; 2008; Condat, 2013; V

u, 2013) gener-

alized from traditional operator splitting, such as forward

backward splitting method (Chen & Rockafellar, 1997) and

Douglas Rachford splitting method (Eckstein & Bertsekas,

1992), can also solve the multi-term nonsmooth convex

composite optimization problem (1). Different from pri-

or work, Raguet et al. (Raguet et al., 2013) proposed an

efﬁcient primal operator splitting method called general-

ized forward backward splitting method using the classic

forward backward splitting technique, which has shown

the superiority over numerous existing primal-dual splitting

methods (Monteiro & Svaiter, 2013; Combettes & Pesquet,

2012; Chambolle & Pock, 2011) in dealing with variation-

al image restoration problems. All the above mentioned

methods for problem (1) with n ≥ 3 share a common

feature that they all split the nonsmooth composite term

i=1

(x) in the Jacobi iteration manner, i.e., parallelly.

This is one of the main differences between existing split-

ting methods and our proposed method in this paper.

To split the nonsmooth composite term

i=1

(x) more

efﬁciently, we propose a novel operator splitting algorithm

to solve problem (1) by harnessing the advantage of Gauss-

Seidel iterations, i.e., the computation of the proximal

mapping of the current function g

(x) uses the proximal

mappings of g

(x) for all j < i which have already

been computed ahead. In addition, to further improve the

algorithm’s efﬁciency, we leverage the over-relaxation

acceleration technique. What’s more, we provide a new

strategy that the over-relaxation stepsize can be determined

adaptively, ensuring a larger value to accelerate the algo-

rithm. The most important is that the convergence of our

proposed GSOS algorithm is established by a newly devel-

oped analysis technique. In detail, given an invertible linear

operator R, we ﬁrst argue that the optimal solution set

[∇f +

i=1

∂g

]

−1

(0) of problem (1) can be recovered

by the zero point set



∗

)

−1

R, ∂g+A◦∇f◦A, N



−1

(0).

This is fulﬁlled through adopting the tool of operator

optimization theory, in which the composite operator

R, ∂g+A◦∇f◦A, N

is generalized from the deﬁnition of

the composite monotone operator S

λ,A,B

in (Eckstein

& Bertsekas, 1992). Next, by unitizing the deﬁnition of

the -enlargement of maximal monotone (Burachik et al.,

1998; 1997; Burachik & Svaiter, 1999; Svaiter, 2000),

we establish a key property for S

R, ∂g+A◦∇f◦A, N

that is, gph



R, (∂g+A

∗

◦∇f◦A)

[]

, N



⊆

gph



∗

[(R

∗

)

−1

R, ∂g+A

∗

◦∇f◦A, N

]

[]



. Based on

this observation, we equivalently reformulate the GSOS

algorithm as a two-step iterations algorithm. Then, the

global convergence of the proposed GSOS algorithm is

easily established based on this reformulation.

The closest algorithm to our proposed GSOS algorithm

is the generalized forward backward splitting method pro-

posed by Raguet et al. (Raguet et al., 2013). By carefully

selecting the scaling matrix H in the forthcoming GSOS

algorithm, it is easy to check that GSOS covers the gener-

alized forward backward splitting method as a special case.

Another highly related algorithm to our proposed GSOS al-

gorithm is the matrix splitting method (Luo & Tseng, 1991;

Yuan et al., 2016). Choosing the scaling matrix H suitably,

the proposed GSOS algorithm can inherit the advantage of

the matrix splitting technique which has shown the efﬁcien-

cy in (Yuan et al., 2016) for coping with a special class of

coordinate separable composite optimization problems.

The rest of this paper is organized as follows. In Section 2,

we ﬁrst give the deﬁnitions of some useful notations which

can make the paper much more readable. We also establish

some lemmas and propositions based on monotone opera-

tor theory (Bauschke & Combettes, 2011), which are the

key to the convergence of the GSOS algorithm. In Section

3, we present the proposed GSOS algorithm and then an-

alyze its convergence and iteration complexity. In Section

4, we conduct numerical experiments on overlapping group

Lasso and graph-guided fused Lasso problems to evaluate

the efﬁcacy of the GSOS algorithm. Finally, we draw con-

clusions in Section 5.

2. Preliminaries and Notations

Let Y =

i=1

be the product space of X

with X

= X

for all i ∈ {1, 2, · · · , n}. Let V be a linear space and V

⊥

be its complementary space with the following deﬁnitions

V =



y ∈ Y | y

= · · · = y



, V

⊥



y ∈ Y |

= 0



Let I

: X → X be the identity map and E

X → Y be a block linear operator deﬁned as E



· · · I



∗

. Let A : Y → X be a linear oper-

ator deﬁned as Ay =

∗

y =

i=1

. Hence, its

adjoint operator A

∗

: X → Y is deﬁned as A

∗

x =

Let H, R : Y → Y be block lower triangular linear invert-

ible operators satisfying (R

∗

)

−1

= H and H + H

∗

 0.

Moreover, H is deﬁned as







1,1

0 · · · 0

n−1,1

· · · H

n−1,n−1

n,1

· · · H

n−1,n

n,n







, (3)

where H

i,j

: X → X is a linear operator for all (i, j) ∈

{1, · · · , n}. It is worthwhile to emphasize that H

i,i

is also

possible to be a lower triangular linear operator satisfying

剩余9页未读，继续阅读

评论收藏

内容反馈

weixin_38700779

粉丝: 11
资源: 924

GSOS：高斯-塞德尔算子分裂算法，用于多项非光滑凸组合优化。

38613152GSOS_fireflyalgorithm_萤火虫_firefly_萤火虫算法.zip

38613152GSOS_fireflyalgorithm_萤火虫_firefly_萤火虫算法_源码.zip

基于CORDIC的反正弦和反余弦计算的FPGA实现

BA无标度网络中的SIR模型

使用3DCNN和卷积LSTM进行手势识别学习时空特征

基于三次贝塞尔曲线的类汽车曲率连续路径平滑

基于机器学习的设备剩余寿命预测方法综述

基于维纳过程的退化模型，具有递归过滤算法，可用于估计剩余使用寿命

基于FPGA的奇异值和特征值分解的快速实现。

磁悬浮系统自适应模糊PID控制器的设计

基于BP神经网络的人口预测

两轮平衡车的建模与控制研究

无人机协同目标的多无人机协同搜索方法

基于改进遗传算法的六自由度机器人时间最优轨迹规划

一种基于深度学习的机械臂抓取方法

基于深度神经网络的交通流量预测

一种去除ECG中基线漂移和工频干扰的高效滤波方法

适用于1-8GHz宽带应用的原始Vivaldi天线

亮度保持和细节增强的红外图像增强方法

近场中的磁偶极子模型

基于多目标优化算法的多无人机协同航迹规划

一种基于LMS算法的流水线ADC数字校准算法

弗兰克（Frank）编码的LFM波形及其在MIMO雷达中的应用

最新资源