- Journal Home
- Volume 22 - 2025
- Volume 21 - 2024
- Volume 20 - 2023
- Volume 19 - 2022
- Volume 18 - 2021
- Volume 17 - 2020
- Volume 16 - 2019
- Volume 15 - 2018
- Volume 14 - 2017
- Volume 13 - 2016
- Volume 12 - 2015
- Volume 11 - 2014
- Volume 10 - 2013
- Volume 9 - 2012
- Volume 8 - 2011
- Volume 7 - 2010
- Volume 6 - 2009
- Volume 5 - 2008
- Volume 4 - 2007
- Volume 3 - 2006
- Volume 2 - 2005
- Volume 1 - 2004
Cited by
- BibTex
- RIS
- TXT
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 "narrowness" 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.
}, issn = {2617-8710}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/ijnam/17870.html} }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 "narrowness" 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.