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 con- verges at a global linear rate. For general convex problems, the convergence rate is linear in early stages, while the overall rate is @math . For nonconvex problems, a first-order optimality criterion converges to zero at a rate of @math .
Variant 2 of Algorithm is proposed in @cite_18 @cite_26 for convex and strongly convex objectives, with inexactness defined additively as in . For convex @math , showed that if @math and @math converge then a @math convergence rate is achievable. The same rate can be achieved if @math for any @math . When @math is @math -strongly convex, showed that if @math is finite (where @math , @math is the upper bound for @math , and @math is as defined in ), then a global R-linear convergence rate is attained. In both cases, the conditions require a certain rate of decrease for @math , a condition that can be achieved by performing more and more inner iterations as @math increases. By contrast, our multiplicative inexactness criterion can be attained with a fixed number of inner iterations. Moreover, we attain a Q-linear rather than an R-linear result.
@cite_18 @cite_26
2962748029 2963573197
Recently several methods were proposed for sparse optimization which make careful use of second-order information ( in Sparse inverse covariance matrix estimation using quadratic approximation. In: NIPS, 2011; in An improved GLMNET for l1-regularized logistic regression and support vector machines. National Taiwan University, Taipei City, 2011; in Newton-like methods for sparse inverse covariance estimation. In: NIPS, 2012; in A family of second-order methods for convex l1-regularized optimization. Technical report, 2012) to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent. Here we propose a general framework, which includes slightly modified versions of existing algorithms and also a new algorithm, which uses limited memory BFGS Hessian approximations, and provide a novel global convergence rate analysis, which covers methods that solve subproblems via coordinate descent. A general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed by Scheinberg and Tang (Math Program 160:495–529, 2016) and a sublinear global convergence rate has been established. In this paper, we analyze the global convergence rate of this method, in the both exact and inexact settings, in the case when the objective function is strongly convex. We also investigate a practical variant of this method by establishing a simple stopping criterion for the subproblem optimization. Furthermore, we consider an accelerated variant, based on FISTA of Beck and Teboulle (SIAM 2:183–202, 2009), to the proximal quasi-Newton algorithm. (SIAM 22:1042–1064, 2012) considered a similar accelerated method, where the convergence rate analysis relies on very strong impractical assumptions on Hessian estimates. We present a modified analysis while relaxing these assumptions and perform a numerical comparison of the accelerated proximal quasi-Newton algorithm and the regular one. Our analysis and computational results show that acceleration may not bring any benefit in the quasi-Newton setting.