期刊
MATHEMATICAL PROGRAMMING
卷 144, 期 1-2, 页码 1-38出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-012-0614-z
关键词
Block coordinate descent; Huge-scale optimization; Composite minimization; Iteration complexity; Convex optimization; LASSO; Sparse regression; Gradient descent; Coordinate relaxation; Gauss-Seidel method
类别
资金
- EPSRC [EP/I017127/1, EP/G036136/1]
- Centre for Numerical algorithms and Intelligent Software
- Scottish Funding Council
- EPSRC [EP/G036136/1, EP/I017127/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/G036136/1, EP/I017127/1] Funding Source: researchfish
In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an -accurate solution with probability at least in at most iterations, where is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341-362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale -regularized least squares problems with a billion variables.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据