@Article{IJNAM-17-4,
author = {Mohlenkamp, Martin and Young, Todd, R. and Bárány, Balázs},
title = {Transient Dynamics of Block Coordinate Descent in a Valley},
journal = {International Journal of Numerical Analysis and Modeling},
year = {2020},
volume = {17},
number = {4},
pages = {557--591},
abstract = {<p style="text-align: justify;">We investigate the transient dynamics of Block Coordinate Descent algorithms in
valleys of the optimization landscape. Iterates converge linearly to a vicinity of the valley floor
and then progress in a zig-zag fashion along the direction of the valley floor. When the valley sides
are symmetric, the contraction factor to a vicinity of the valley floor appears to be no worse than
1/8, but without symmetry the contraction factor can approach 1. Progress along the direction of
the valley floor is proportional to the gradient on the valley floor and inversely proportional to the &quot;narrowness&quot; of the valley. We quantify narrowness using the eigenvalues of the Hessian on the
valley floor and give explicit formulas for certain cases. Progress also depends on the direction of
the valley with respect to the blocks of coordinates. When the valley sides are symmetric, we give
an explicit formula for this dependence and use it to show that in higher dimensions nearly all
directions give progress similar to the worst case direction. Finally, we observe that when starting
the algorithm, the ordering of blocks in the first few steps can be important, but show that a
greedy strategy with respect to objective function improvement can be a bad choice.</p>},
issn = {2617-8710},
doi = {https://doi.org/2020-IJNAM-17870},
url = {https://global-sci.com/article/83033/transient-dynamics-of-block-coordinate-descent-in-a-valley}
}