Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
针对正则化优化问题，提出一种改进的逐次二次逼近方法，利用部分光滑正则化子的流形识别性质，在识别出光滑流形后切换至高效光滑优化方法，实现迭代次数和运行时间的超线性收敛。
Abstract For regularized optimization that minimizes the sum of a smooth term and a regularizer that promotes structured solutions, inexact proximal-Newton-type methods, or successive quadratic approximation (SQA) methods, are widely used for their superlinear convergence in terms of iterations. However, unlike the counter parts in smooth optimization, they suffer from lengthy running time in solving regularized subproblems because even approximate solutions cannot be computed easily, so their empirical time cost is not as impressive. In this work, we first show that for partly smooth regularizers, although general inexact solutions cannot identify the active manifold that makes the objective function smooth, approximate solutions generated by commonly-used subproblem solvers will identify this manifold, even with arbitrarily low solution precision. We then utilize this property to propose an improved SQA method, $$^{+}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow/><mml:mo>+</mml:mo></mml:msup></mml:math> , that switches to efficient smooth optimization methods after this manifold is identified. We show that for a wide class of degenerate solutions, $$^{+}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow/><mml:mo>+</mml:mo></mml:msup></mml:math> possesses superlinear convergence not only in iterations, but also in running time because the cost per iteration is bounded. In particular, our superlinear convergence result holds on problems satisfying a sharpness condition that is more general than that in existing literature. We also prove iterate convergence under a sharpness condition for inexact SQA, which is novel for this family of methods that could easily violate the classical relative-error condition frequently used in proving convergence under similar conditions. Experiments on real-world problems support that $$^{+}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow/><mml:mo>+</mml:mo></mml:msup></mml:math> improves running time over some modern solvers for regularized optimization.