Nesterov Accelerated Shuffling Gradient Method for Convex Optimization

Trang H Tran, Katya Scheinberg, Lam M Nguyen
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:21703-21732, 2022.

Abstract

In this paper, we propose Nesterov Accelerated Shuffling Gradient (NASG), a new algorithm for the convex finite-sum minimization problems. Our method integrates the traditional Nesterov’s acceleration momentum with different shuffling sampling schemes. We show that our algorithm has an improved rate of $\Ocal(1/T)$ using unified shuffling schemes, where $T$ is the number of epochs. This rate is better than that of any other shuffling gradient methods in convex regime. Our convergence analysis does not require an assumption on bounded domain or a bounded gradient condition. For randomized shuffling schemes, we improve the convergence bound further. When employing some initial condition, we show that our method converges faster near the small neighborhood of the solution. Numerical simulations demonstrate the efficiency of our algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-tran22a, title = {{N}esterov Accelerated Shuffling Gradient Method for Convex Optimization}, author = {Tran, Trang H and Scheinberg, Katya and Nguyen, Lam M}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {21703--21732}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/tran22a/tran22a.pdf}, url = {https://proceedings.mlr.press/v162/tran22a.html}, abstract = {In this paper, we propose Nesterov Accelerated Shuffling Gradient (NASG), a new algorithm for the convex finite-sum minimization problems. Our method integrates the traditional Nesterov’s acceleration momentum with different shuffling sampling schemes. We show that our algorithm has an improved rate of $\Ocal(1/T)$ using unified shuffling schemes, where $T$ is the number of epochs. This rate is better than that of any other shuffling gradient methods in convex regime. Our convergence analysis does not require an assumption on bounded domain or a bounded gradient condition. For randomized shuffling schemes, we improve the convergence bound further. When employing some initial condition, we show that our method converges faster near the small neighborhood of the solution. Numerical simulations demonstrate the efficiency of our algorithm.} }
Endnote
%0 Conference Paper %T Nesterov Accelerated Shuffling Gradient Method for Convex Optimization %A Trang H Tran %A Katya Scheinberg %A Lam M Nguyen %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-tran22a %I PMLR %P 21703--21732 %U https://proceedings.mlr.press/v162/tran22a.html %V 162 %X In this paper, we propose Nesterov Accelerated Shuffling Gradient (NASG), a new algorithm for the convex finite-sum minimization problems. Our method integrates the traditional Nesterov’s acceleration momentum with different shuffling sampling schemes. We show that our algorithm has an improved rate of $\Ocal(1/T)$ using unified shuffling schemes, where $T$ is the number of epochs. This rate is better than that of any other shuffling gradient methods in convex regime. Our convergence analysis does not require an assumption on bounded domain or a bounded gradient condition. For randomized shuffling schemes, we improve the convergence bound further. When employing some initial condition, we show that our method converges faster near the small neighborhood of the solution. Numerical simulations demonstrate the efficiency of our algorithm.
APA
Tran, T.H., Scheinberg, K. & Nguyen, L.M.. (2022). Nesterov Accelerated Shuffling Gradient Method for Convex Optimization. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:21703-21732 Available from https://proceedings.mlr.press/v162/tran22a.html.

Related Material