An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms
This work addresses the time-consuming step-size tuning issue for large-scale optimization tasks in machine learning, but it is incremental as it builds on existing SAGA methods.
The paper tackled the problem of manual step-size tuning in stochastic variance reduced methods by proposing adaptive variants of the SAGA algorithm, resulting in a memory-efficient variant with fast convergence and competitive performance on standard datasets.
Stochastic variance reduced methods have shown strong performance in solving finite-sum problems. However, these methods usually require the users to manually tune the step-size, which is time-consuming or even infeasible for some large-scale optimization tasks. To overcome the problem, we propose and analyze several novel adaptive variants of the popular SAGA algorithm. Eventually, we design a variant of Barzilai-Borwein step-size which is tailored for the incremental gradient method to ensure memory efficiency and fast convergence. We establish its convergence guarantees under general settings that allow non-Euclidean norms in the definition of smoothness and the composite objectives, which cover a broad range of applications in machine learning. We improve the analysis of SAGA to support non-Euclidean norms, which fills the void of existing work. Numerical experiments on standard datasets demonstrate a competitive performance of the proposed algorithm compared with existing variance-reduced methods and their adaptive variants.