Speaker：Professor Ching-Pei Lee (Institute of Statistical Science, Academia Sinica)
Topic：Improving Proximal-Newton-Type Methods for Regularized Optimization
Speaker：Professor Ching-Pei Lee (Institute of Statistical Science, Academia Sinica)
Date Time：FRI. Mar 12, 2021, 10:40 AM - 11:30 AM
Place： 4F-427, Assembly Building I
Abstract
For regularized optimization that minimizes the sum of a differentiable 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. This talk discusses our recent improvements of SQA in both theory and practice and consists of two parts. In the first part, we discuss its superlinear behavior for degenerate problems.
In particular, we show that superlinear convergence and even quadratic convergence is still attainable without a positive definite Hessian at the solutions, and even without twice-differentiability of the smooth term. We then propose a simple variant that is better than existing ones, in the sense that in addition to the minimum requirement of ensuring both global convergence and local superlinear convergence, the proposed variant also guarantees that the function value is always improving. In the second half of this talk, we consider further improvements SQA by utilizing the solution structure. More specifically, 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 that switches to efficient smooth optimization methods after this manifold is identified. We show that for a wide class of degenerate solutions, the proposed method possesses superlinear convergence not just 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 more general than that in existing literature. Experiments on real-world problems also confirm that our method greatly improves the state of the art for regularized optimization.
In particular, we show that superlinear convergence and even quadratic convergence is still attainable without a positive definite Hessian at the solutions, and even without twice-differentiability of the smooth term. We then propose a simple variant that is better than existing ones, in the sense that in addition to the minimum requirement of ensuring both global convergence and local superlinear convergence, the proposed variant also guarantees that the function value is always improving. In the second half of this talk, we consider further improvements SQA by utilizing the solution structure. More specifically, 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 that switches to efficient smooth optimization methods after this manifold is identified. We show that for a wide class of degenerate solutions, the proposed method possesses superlinear convergence not just 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 more general than that in existing literature. Experiments on real-world problems also confirm that our method greatly improves the state of the art for regularized optimization.