More Web Proxy on the site http://driver.im/

research-article

On the Convergence of Block Coordinate Descent Type Methods

Authors:

Luba TetruashviliAuthors Info & Claims

SIAM Journal on Optimization, Volume 23, Issue 4

Pages 2037 - 2060

https://doi.org/10.1137/120887679

Published: 01 January 2013 Publication History

Abstract

In this paper we study smooth convex programming problems where the decision variables vector is split into several blocks of variables. We analyze the block coordinate gradient projection method in which each iteration consists of performing a gradient projection step with respect to a certain block taken in a cyclic order. Global sublinear rate of convergence of this method is established and it is shown that it can be accelerated when the problem is unconstrained. In the unconstrained setting we also prove a sublinear rate of convergence result for the so-called alternating minimization method when the number of blocks is two. When the objective function is also assumed to be strongly convex, linear rate of convergence is established.

References

[1]

A. Auslender, Optimisation, Masson, Paris, 1976.

[2]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183--202.

[3]

A. Beck and M. Teboulle, Gradient-based algorithms with applications to signal recovery problems, in Convex Optimization in Signal Processing and Communications, D. Palomar and Y. Eldar, eds., Cambridge University Press, Cambridge, UK, 2009, pp. 139--162.

[4]

D. P. Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific, Belmont, MA, 1999.

[5]

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation, Prentice-Hall, Englewood Cliffs, NJ, 1989.

[6]

I. S. Dhillon, P. D. Ravikumar, and A. Tewari, Nearest Neighbor Based Greedy Coordinate Descent, in Proceedings of NIPS, 2011, pp. 2160--2168.

[7]

L. Grippo and M. Sciandrone, Globally convergent block-coordinate techniques for unconstrained optimization, Optim. Methods Soft., 10 (1999), pp. 587--637.

[8]

T. Luo and P. Tseng, On the convergence of the coordinate descent method for convex differentiable minimization, J. Optim. Theory Appl., 72 (1992), pp. 7--35.

[9]

T. Luo and P. Tseng, Error bounds and convergence analysis of feasible descent methods: A general approach, Ann. Oper. Res., 46 (1993), pp. 157--178.

[10]

Y. Nesterov, Introductory Lectures on Convex Optimization, Kluwer, Boston, 2004.

[11]

Y. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k\sp{2})$, Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543--547.

[12]

Y. E. Nesterov, Gradient Methods for Minimizing Composite Objective Function, http://www.ecore.be/DPs/dp1191313936.pdf (2007).

[13]

Y. E. Nesterov, Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems, CORE Discussion paper 2010/2, 2010.

[14]

J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.

[15]

B. T. Polyak, Introduction to Optimization, Transl. Ser. Math. Engrg., Optimization Software, Inc., New York, 1987.

[16]

P. Richtarik and M. Takac, Efficient Serial and Parallel Coordinate Descent Methods for Huge-Scale Truss Topology Design, Oper. Res. Proc. 2011, Springer, 2012, pp. 27--32.

[17]

P. Richtarik and M. Takac, Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function, Math. Prog. Ser. A, (2012), pulished online.

[18]

A. Saha and A. Tewari, On the non-asymptotic convergence of cyclic coordinate descent methods, SIAM J. Optim., 23 (2013), pp. 576--601.

[19]

S. Shalev-Shwartz and A. Tewari, Stochastic methods for $\ell_1$-regularized loss minimization, J. Mach. Learn. Res., 12 (2011), pp. 1865--1892.

Cited By

Zhi MBi YCai LXu WWang HXiang THe Q(2025)Knowledge-Aware Parameter Coaching for Communication-Efficient Personalized Federated Learning in Mobile Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2024.346451224:1(321-337)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3464512
Peng LYin WSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Block acceleration without momentumProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693705(40295-40330)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693705
Zhi MBi YXu WWang HXiang TWooldridge MDy JNatarajan S(2024)Knowledge-aware parameter coaching for personalized federated learningProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i15.29651(17069-17077)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i15.29651
Show More Cited By

Index Terms

On the Convergence of Block Coordinate Descent Type Methods
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

On the complexity analysis of randomized block-coordinate descent methods

In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341---362, 2012), Richtárik and Takáă (Math Program 144(1---2):1---38, 2014) for minimizing the sum of a smooth convex function and ...
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

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 $$\varepsilon $$-accurate solution with probability at least $$1-...
A coordinate gradient descent method for nonsmooth separable minimization

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with ℓ1-regularization. We propose a (block) coordinate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 23, Issue 4

2013

627 pages

ISSN:1052-6234

DOI:10.1137/sjope8.23.4

Issue’s Table of Contents

© 2013, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2013

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhi MBi YCai LXu WWang HXiang THe Q(2025)Knowledge-Aware Parameter Coaching for Communication-Efficient Personalized Federated Learning in Mobile Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2024.346451224:1(321-337)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3464512
Peng LYin WSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Block acceleration without momentumProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693705(40295-40330)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693705
Zhi MBi YXu WWang HXiang TWooldridge MDy JNatarajan S(2024)Knowledge-aware parameter coaching for personalized federated learningProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i15.29651(17069-17077)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i15.29651
Takeda SAkagi YMarumo NNiwa KWooldridge MDy JNatarajan S(2024)Optimal transport with cyclic symmetryProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i14.29444(15211-15221)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i14.29444
Yang BNadarajah SSecomandi N(2024)Least Squares Monte Carlo and Pathwise Optimization for Merchant Energy ProductionOperations Research10.1287/opre.2018.034172:6(2758-2775)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1287/opre.2018.0341
Doerr BKnowles JNeumann ANeumann FLi XHandl J(2024)A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654169(493-501)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654169
Wen XChen CGuan XRen CMa YFang Y(2024)AoIT-Empowered Associated Network Slicing: Resource Orchestration for Joint MonitoringIEEE Transactions on Wireless Communications10.1109/TWC.2024.344687723:11_Part_2(16805-16820)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TWC.2024.3446877
Li RCabric D(2024)A Coordinate Descent Approach to Atomic Norm DenoisingIEEE Transactions on Signal Processing10.1109/TSP.2024.348653372(5077-5090)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3486533
Zhu HLiu YWu YLau V(2024)A Unified Framework for STAR-RIS Coefficients OptimizationIEEE Transactions on Signal Processing10.1109/TSP.2024.341301772(5107-5122)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3413017
Yu XWang GHuang XWang KXu WRui Y(2024)Energy Efficient Resource Allocation for Uplink RIS-Aided Millimeter-Wave Networks With NOMAIEEE Transactions on Mobile Computing10.1109/TMC.2022.322239223:1(423-436)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TMC.2022.3222392
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents