没有合适的资源?快使用搜索试试~ 我知道了~
Distributed Optimization and Statistical Learning via the Altern...
4星 · 超过85%的资源 需积分: 43 78 下载量 141 浏览量
2017-10-23
14:38:52
上传
评论 1
收藏 905KB PDF 举报
温馨提示
试读
125页
电子书Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers,包含了拉格朗日乘子法等多种最优化算法,描述清晰,是国外一些论文的参考文献之一
资源推荐
资源详情
资源评论
Foundations and Trends
R
!
in
Machine Learning
Vol. 3, No. 1 (2010) 1–122
c
! 2011 S. Boyd, N. Parikh, E. Chu, B. Peleato
and J. Eckstein
DOI: 10.1561/2200000016
Distributed Optimization and Statistical
Learning via the Alternating Direction
Method of Multipliers
Stephen Boyd
1
, Neal Parikh
2
, Eric Chu
3
Borja Peleato
4
and Jonathan Eckstein
5
1
Electrical Engineering Department, Stanford University, Stanford, CA
94305, USA, boyd@stanford.edu
2
Computer Science Department, Stanford University, Stanford, CA 94305,
USA, npparikh@cs.stanford.edu
3
Electrical Engineering Department, Stanford University, Stanford, CA
94305, USA, echu508@stanford.edu
4
Electrical Engineering Department, Stanford University, Stanford, CA
94305, USA, peleato@stanford.edu
5
Management Science and Information Systems Department and
RUTCOR, Rutgers University, Piscataway, NJ 08854, USA,
jeckstei@rci.rutgers.edu
Contents
1 Introduction 3
2 Precursors 7
2.1 Dual Ascent 7
2.2 Dual Decomposition 9
2.3 Augmented Lagrangians and the Method of Multipliers 10
3 Alternating Direction Method of Multipliers 13
3.1 Algorithm 13
3.2 Convergence 15
3.3 Optimality Conditions and Stopping Criterion 18
3.4 Extensions and Variations 20
3.5 Notes and References 23
4 General Patterns 25
4.1 Proximity Operator 25
4.2 Quadratic Objective Terms 26
4.3 Smooth Objective Terms 30
4.4 Decomposition 31
5 Constrained Convex Optimization 33
5.1 Convex Feasibility 34
5.2 Linear and Quadratic Programming 36
6 !
1
-Norm Problems 38
6.1 Least Absolute Deviations 39
6.2 Basis Pursuit 41
6.3 General !
1
Regularized Loss Minimization 42
6.4 Lasso 43
6.5 Sparse Inverse Covariance Selection 45
7 Consensus and Sharing 48
7.1 Global Variable Consensus Optimization 48
7.2 General Form Consensus Optimization 53
7.3 Sharing 56
8 Distributed Model Fitting 61
8.1 Examples 62
8.2 Splitting across Examples 64
8.3 Splitting across Features 66
9 Nonconvex Problems 73
9.1 Nonconvex Constraints 73
9.2 Bi-convex Problems 76
10 Implementation 78
10.1 Abstract Implementation 78
10.2 MPI 80
10.3 Graph Computing Frameworks 81
10.4 MapReduce 82
11 Numerical Examples 87
11.1 Small Dense Lasso 88
11.2 Distributed !
1
Regularized Logistic Regression 92
11.3 Group Lasso with Feature Splitting 95
11.4 Distributed Large-Scale Lasso with MPI 97
11.5 Regressor Selection 100
12 Conclusions 103
Acknowledgments 105
A Convergence Proof 106
References 111
Abstract
Many problems of recent interest in statistics and machine learning
can be posed in the framework of convex optimization. Due to the
explosion in size and complexity of modern datasets, it is increasingly
important to be able to solve problems with a very large number of fea-
tures or training examples. As a result, both the decentralized collection
or storage of these datasets as well as accompanying distributed solu-
tion methods are either necessary or at least highly desirable. In this
review, we argue that the alternating direction method of multipliers
is well suited to distributed convex optimization, and in particular to
large-scale problems arising in statistics, machine learning, and related
areas. The method was developed in the 1970s, with roots in the 1950s,
and is equivalent or closely related to many other algorithms, such
as dual decomposition, the method of multipliers, Douglas–Rachford
splitting, Spingarn’s method of partial inverses, Dykstra’s alternating
projections, Bregman iterative algorithms for !
1
problems, proximal
methods, and others. After briefly surveying the theory and history of
the algorithm, we discuss applications to a wide variety of statistical
and machine learning problems of recent interest, including the lasso,
sparse logistic regression, basis pursuit, covariance selection, support
vector machines, and many others. We also discuss general distributed
optimization, extensions to the nonconvex setting, and efficient imple-
mentation, including some details on distributed MPI and Hadoop
MapReduce implementations.
剩余124页未读,继续阅读
资源评论
- mzg123456782020-04-10不错的资源,学习中
- j_lc1234562018-09-02资源还可以
越野者
- 粉丝: 434
- 资源: 46
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功