On the Finite Time Convergence of Cyclic Coordinate Descent Methods

Computer Science – Learning

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

20 pages

Scientific paper

Cyclic coordinate descent is a classic optimization method that has witnessed a resurgence of interest in machine learning. Reasons for this include its simplicity, speed and stability, as well as its competitive performance on $\ell_1$ regularized smooth optimization problems. Surprisingly, very little is known about its finite time convergence behavior on these problems. Most existing results either just prove convergence or provide asymptotic rates. We fill this gap in the literature by proving $O(1/k)$ convergence rates (where $k$ is the iteration counter) for two variants of cyclic coordinate descent under an isotonicity assumption. Our analysis proceeds by comparing the objective values attained by the two variants with each other, as well as with the gradient descent algorithm. We show that the iterates generated by the cyclic coordinate descent methods remain better than those of gradient descent uniformly over time.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the Finite Time Convergence of Cyclic Coordinate Descent Methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Finite Time Convergence of Cyclic Coordinate Descent Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Finite Time Convergence of Cyclic Coordinate Descent Methods will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-500341

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.