Optimization Online


Inexact Successive Quadratic Approximation for Regularized Optimization

Ching-pei Lee (ching-pei***at***cs.wisc.edu)
Stephen Wright (swright***at***cs.wisc.edu)

Abstract: Successive quadratic approximations, or second-order proximal methods, are useful for minimizing functions that are a sum of a smooth part and a convex, possibly nonsmooth part that promotes a regularized solution. Most analyses of iteration complexity focus on the special case of proximal gradient method, or accelerated variants thereof. There have been only a few studies of methods that use a second-order approximation to the smooth part, due in part to the difficulty of obtaining closed-form solutions to the subproblems at each iteration. In practice, iterative algorithms need to be used to find inexact solutions to the subproblems. In this work, we present global analysis of the iteration complexity of inexact successive quadratic approximation methods, showing that it is sufficient to obtain an inexact solution of the subproblem to fixed multiplicative precision in order to guarantee the same order of convergence rate as the exact version, with complexity related proportionally to the degree of inexactness. Our result allows flexible choices of the second-order terms, including Newton and quasi-Newton choices, and does not necessarily require more time to be spent on the subproblem solves on later iterations. For problems exhibiting a property related to strong convexity, the algorithm converges at a global linear rate. For general convex problems, the convergence rate is linear in early stages, while the overall rate is $O(1/k)$. For nonconvex problems, a first-order optimality criterion converges to zero at a rate of $O(1/\sqrt{k})$.

Keywords: Convex optimization, Nonconvex optimization, Regularized optimization, Composite optimization, Variable metric, Proximal method, Second-order approximation, Inexact method

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 03/03/2018
Entry Accepted: 03/04/2018
Entry Last Modified: 03/27/2018

Modify/Update this entry

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


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