SMG: A Shuffling Gradient-Based Method with Momentum

Trang Tran · Lam Nguyen · Quoc Tran-Dinh


Keywords: [ Non-convex Optimization ] [ Neuroscience and Cognitive Science ] [ Neuroscience ] [ Neuroscience and Cognitive Science -> Human or Animal Learning; Probabilistic Methods ] [ Belief Propagation; Probabilistic Meth ]

[ Abstract ]
[ Slides
[ Paper ]
[ Visit Poster at Spot C5 in Virtual World ]
Wed 21 Jul 9 a.m. PDT — 11 a.m. PDT
Spotlight presentation: Optimization (Nonconvex)
Wed 21 Jul 5 a.m. PDT — 6 a.m. PDT

Abstract: We combine two advanced ideas widely used in optimization for machine learning: \textit{shuffling} strategy and \textit{momentum} technique to develop a novel shuffling gradient-based method with momentum, coined \textbf{S}huffling \textbf{M}omentum \textbf{G}radient (SMG), for non-convex finite-sum optimization problems. While our method is inspired by momentum techniques, its update is fundamentally different from existing momentum-based methods. We establish state-of-the-art convergence rates of SMG for any shuffling strategy using either constant or diminishing learning rate under standard assumptions (i.e. \textit{$L$-smoothness} and \textit{bounded variance}). When the shuffling strategy is fixed, we develop another new algorithm that is similar to existing momentum methods, and prove the same convergence rates for this algorithm under the $L$-smoothness and bounded gradient assumptions. We demonstrate our algorithms via numerical simulations on standard datasets and compare them with existing shuffling methods. Our tests have shown encouraging performance of the new algorithms.

Chat is not available.