On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms
Stochastic gradient descent (SGD) algorithm is the method of choice in many machine learning tasks thanks to its scalability and efficiency in dealing with large-scale problems. In this paper, we focus on the shuffling version of SGD which matches the mainstream practical heuristics. We show the convergence to a global solution of shuffling SGD for a class of non-convex functions under over-parameterized settings. Our analysis employs more relaxed non-convex assumptions than previous literature. Nevertheless, we maintain the desired computational complexity as shuffling SGD has achieved in the general convex setting.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance. Despite extensive development of convergence guarantees under various assumptions in recent years, most requir…
Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling
When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then…
BIG-bench Machine LearningA Unified Convergence Analysis for Shuffling-Type Gradient Methods
In this paper, we propose a unified convergence analysis for a class of generic shuffling-type gradient methods for solving finite-sum optimization problems. Our analysis works with any sampling without replacement strat…
Vocal Bursts Type PredictionNesterov Accelerated Shuffling Gradient Method for Convex Optimization
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 diffe…
Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning
The global Lipschitz smoothness condition underlies most convergence and complexity analyses via two key consequences: the descent lemma and the gradient Lipschitz continuity. How to study the performance of optimization…