-

 

 

 




Optimization Online





 

Inexact Coordinate Descent: Complexity and Preconditioning

Rachael Tappenden( R.Tappenden***at***ed.ac.uk )
Peter Richtarik(peter.richtarik***at***ed.ac.uk)
Jacek Gondzio(J.Gondzio***at***ed.ac.uk)

Abstract: In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In his work we relax this requirement, and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update as well as the use of preconditioning for further acceleration.

Keywords: inexact methods, block coordinate descent, convex optimization, iteration complexity, preconditioning, conjugate gradients

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation:

Download: [PDF]

Entry Submitted: 08/30/2013
Entry Accepted: 08/30/2013
Entry Last Modified: 08/30/2013

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society