  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 regularization. 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 fact, iterative algorithms may need to be used to find inexact
solutions to these subproblems. In this work, we present global analysis of the
iteration complexity of inexact successive quadratic approximation methods,
showing that an inexact solution of the subproblem that is within a fixed
multiplicative precision of optimality suffices to guarantee the same order of
convergence rate as the exact version, with complexity related in an intuitive
way to the measure of inexactness. Our result allows flexible choices of the
second-order term, including Newton and quasi-Newton choices, and does not
necessarily require increasing precision of the subproblem solution on later
iterations. For problems exhibiting a property related to strong convexity, the
algorithms converge at global linear rates. 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})$.
