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 .
Algorithm is also considered in @cite_0 , with @math set either to @math or a BFGS approximation. Asymptotic convergence and a local rate are shown for the exact case. For inexact subproblem solutions, local results are proved under the assumption that the unit step size is always taken (which may not happen for inexact steps). A variant of Algorithm with a different step size criterion is discussed in @cite_28 , for the special case of @math . Inexactness of the subproblem solution is measured by the norm of a proximal-gradient step for @math . By utilizing specific properties of the @math norm, this paper showed a global convergence rate on the norm of the proximal gradient step on @math to zero, without requiring convexity of @math --- a result similar to our nonconvex result. However, the extension of their result to general @math is not obvious and, moreover, our inexactness condition avoids the cost of computing the proximal gradient step on @math . When @math is @math or a BFGS approximation, they obtain for the inexact version local convergence results similar to the exact case proved in @cite_0 .
@cite_0 @cite_28
2963173886 2162870776
We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing smooth functions, even when search directions are computed inexactly. Many popular methods tailored to problems arising in bioinformatics, signal processing, and statistical learning are special cases of proximal Newton-type methods, and our analysis yields new convergence results for some of these methods. We study a Newton-like method for the minimization of an objective function @math ? that is the sum of a smooth function and an @math l1 regularization term. This method, which is sometimes referred to in the literature as a proximal Newton method, computes a step by minimizing a piecewise quadratic model @math qk of the objective function @math ?. In order to make this approach efficient in practice, it is imperative to perform this inner minimization inexactly. In this paper, we give inexactness conditions that guarantee global convergence and that can be used to control the local rate of convergence of the iteration. Our inexactness conditions are based on a semi-smooth function that represents a (continuous) measure of the optimality conditions of the problem, and that embodies the soft-thresholding iteration. We give careful consideration to the algorithm employed for the inner minimization, and report numerical results on two test sets originating in machine learning.