Timezone: »
This paper introduces an efficient second-order method for solving the elastic net problem. Its key innovation is a computationally efficient technique for injecting curvature information in the optimization process which admits a strong theoretical performance guarantee. In particular, we show improved run time over popular first-order methods and quantify the speed-up in terms of statistical measures of the data matrix. The improved time complexity is the result of an extensive exploitation of the problem structure and a careful combination of second-order information, variance reduction techniques, and momentum acceleration. Beside theoretical speed-up, experimental results demonstrate great practical performance benefits of curvature information, especially for ill-conditioned data sets.
Author Information
Vien Mai (KTH Royal Institute of Technology)
Mikael Johansson (KTH Royal Institute of Technology)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Curvature-Exploiting Acceleration of Elastic Net Computations »
Wed. Jun 12th 01:30 -- 04:00 AM Room Pacific Ballroom #196
More from the Same Authors
-
2023 Poster: Generalized Polyak Step Size for First Order Optimization with Momentum »
Xiaoyu Wang · Mikael Johansson · Tong Zhang -
2023 Poster: Delay-agnostic Asynchronous Coordinate Update Algorithm »
Xuyang Wu · Changxin Liu · Sindri Magnússon · Mikael Johansson -
2022 Poster: Delay-Adaptive Step-sizes for Asynchronous Learning »
Xuyang Wu · Sindri Magnússon · Hamid Reza Feyzmahdavian · Mikael Johansson -
2022 Spotlight: Delay-Adaptive Step-sizes for Asynchronous Learning »
Xuyang Wu · Sindri Magnússon · Hamid Reza Feyzmahdavian · Mikael Johansson -
2021 Poster: Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness »
Vien Mai · Mikael Johansson -
2021 Oral: Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness »
Vien Mai · Mikael Johansson -
2020 Poster: Anderson Acceleration of Proximal Gradient Methods »
Vien Mai · Mikael Johansson -
2020 Poster: Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization »
Vien Mai · Mikael Johansson