Timezone: »
In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framework for updating stochastic gradient estimates; when comparing to SAG/SAGA, SARAH does not require a storage of past gradients. The linear convergence rate of SARAH is proven under strong convexity assumption. We also prove a linear convergence rate (in the strongly convex case) for an inner loop of SARAH, the property that SVRG does not possess. Numerical experiments demonstrate the efficiency of our algorithm.
Author Information
Lam Nguyen (Lehigh University)
Jie Liu (Lehigh University)
Katya Scheinberg (Lehigh University)
Martin Takac (Lehigh University)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient »
Tue. Aug 8th 01:06 -- 01:24 AM Room Parkside 2
More from the Same Authors
-
2022 : Fast Convergence for Unstable Reinforcement Learning Problems by Logarithmic Mapping »
Wang Zhang · Lam Nguyen · Subhro Das · Alexandre Megretsky · Luca Daniel · Tsui-Wei Weng -
2023 Poster: ConCerNet: A Contrastive Learning Based Framework for Automated Conservation Law Discovery and Trustworthy Dynamical System Prediction »
Wang Zhang · Lily Weng · Subhro Das · Alexandre Megretsky · Luca Daniel · Lam Nguyen -
2022 Poster: Nesterov Accelerated Shuffling Gradient Method for Convex Optimization »
Trang Tran · Katya Scheinberg · Lam Nguyen -
2022 Spotlight: Nesterov Accelerated Shuffling Gradient Method for Convex Optimization »
Trang Tran · Katya Scheinberg · Lam Nguyen -
2022 Poster: The power of first-order smooth optimization for black-box non-smooth problems »
Alexander Gasnikov · Anton Novitskii · Vasilii Novitskii · Farshed Abdukhakimov · Dmitry Kamzolov · Aleksandr Beznosikov · Martin Takac · Pavel Dvurechenskii · Bin Gu -
2022 Spotlight: The power of first-order smooth optimization for black-box non-smooth problems »
Alexander Gasnikov · Anton Novitskii · Vasilii Novitskii · Farshed Abdukhakimov · Dmitry Kamzolov · Aleksandr Beznosikov · Martin Takac · Pavel Dvurechenskii · Bin Gu -
2021 Poster: SMG: A Shuffling Gradient-Based Method with Momentum »
Trang Tran · Lam Nguyen · Quoc Tran-Dinh -
2021 Spotlight: SMG: A Shuffling Gradient-Based Method with Momentum »
Trang Tran · Lam Nguyen · Quoc Tran-Dinh -
2020 Poster: Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization »
Quoc Tran-Dinh · Nhan H Pham · Lam Nguyen -
2019 Poster: Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD »
Marten van Dijk · Lam Nguyen · PHUONG_HA NGUYEN · Dzung Phan -
2019 Poster: PROVEN: Verifying Robustness of Neural Networks with a Probabilistic Approach »
Tsui-Wei Weng · Pin-Yu Chen · Lam Nguyen · Mark Squillante · Akhilan Boopathy · Ivan Oseledets · Luca Daniel -
2019 Oral: Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD »
Marten van Dijk · Lam Nguyen · PHUONG_HA NGUYEN · Dzung Phan -
2019 Oral: PROVEN: Verifying Robustness of Neural Networks with a Probabilistic Approach »
Tsui-Wei Weng · Pin-Yu Chen · Lam Nguyen · Mark Squillante · Akhilan Boopathy · Ivan Oseledets · Luca Daniel -
2018 Poster: SGD and Hogwild! Convergence Without the Bounded Gradients Assumption »
Lam Nguyen · PHUONG_HA NGUYEN · Marten van Dijk · Peter Richtarik · Katya Scheinberg · Martin Takac -
2018 Oral: SGD and Hogwild! Convergence Without the Bounded Gradients Assumption »
Lam Nguyen · PHUONG_HA NGUYEN · Marten van Dijk · Peter Richtarik · Katya Scheinberg · Martin Takac