Random Permutations Fix a Worst Case for Cyclic Coordinate Descent

Normierte ringe

Gelfand, I · 1941

Earlier work this paper cites.

On approximate solutions of systems of linear inequalities

Hoffman, A. J · 1952

Earlier work this paper cites.

Une propriété topologique des sous-ensembles analytiques réels

Łojasiewicz, S · 1963

Earlier work this paper cites.

Iterative solution of large linear systems

Original

Young, D. M. & Rheinboldt, W · 1971

Earlier work this paper cites.

Numerical methods for grid equations

Samarskii, A. A. & Nikolaev, E. S · 1989

Earlier work this paper cites.

On the convergence of the coordinate descent method for convex differentiable minimization

Luo, Z.-Q. & Tseng, P · 1992

Earlier work this paper cites.

Error bounds and convergence analysis of feasible descent methods: a general approach

Luo, Z.-Q. & Tseng, P · 1993

Cited alongside, same era.

Matrix computations

Golub, G. H. & Van Loan, C. F · 2012

Cited alongside, same era.

Efficiency of coordinate descent methods on huge-scale optimization problems

Nesterov, Y. E · 2012

Cited alongside, same era.

Asynchronous stochastic coordinate descent: Parallelism and convergence properties

Liu, J. & Wright, S. J · 2015

Cited alongside, same era.

Coordinate descent methods

Wright, S. J · 2015

Cited alongside, same era.

On lower and upper bounds in smooth and strongly convex optimization

Arjevani, Y., Shalev-Shwartz, S. & Shamir, O · 2016

Cited alongside, same era.

Iterative solution of large sparse systems of equations

Hackbusch, W · 2016

Closest in time.

Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition

Karimi, H., Nutini, J. & Schmidt, M · 2016

Closest in time.

Worst-case complexity of cyclic coordinate descent: O ⁡ ( n 2 ) {O}(n^{2}) gap with randomized version

Original

Sun, R. & Ye, Y · 2016

Closest in time.

Analyzing random permutations for cyclic coordinate descent

Wright, S. J. & Lee, C.-p · 2017

Closest in time.

On the convergence of block coordinate descent type methods

Beck, A. & Tetruashvili, L · 2060

Closest in time.