Geometric descent method for convex composite minimization
This work provides an incremental improvement for researchers in optimization by developing a first-order method with optimal convergence rates for composite problems, particularly benefiting applications like regression with regularization.
The authors tackled nonsmooth and strongly convex composite optimization problems by extending the geometric descent method to propose the geometric proximal gradient method (GeoPG), which achieves an optimal linear convergence rate of (1-1/√κ) and outperforms Nesterov's accelerated proximal gradient method in ill-conditioned scenarios, as shown in numerical tests on linear and logistic regression with elastic net regularization.
In this paper, we extend the geometric descent method recently proposed by Bubeck, Lee and Singh to tackle nonsmooth and strongly convex composite problems. We prove that our proposed algorithm, dubbed geometric proximal gradient method (GeoPG), converges with a linear rate $(1-1/\sqrtκ)$ and thus achieves the optimal rate among first-order methods, where $κ$ is the condition number of the problem. Numerical results on linear regression and logistic regression with elastic net regularization show that GeoPG compares favorably with Nesterov's accelerated proximal gradient method, especially when the problem is ill-conditioned.