Adaptive Single-Pass Stochastic Gradient Descent in Input Sparsity Time
We study sampling algorithms for variance reduction methods for stochastic optimization. Although stochastic gradient descent (SGD) is widely used for large scale machine learning, it sometimes experiences slow convergence rates due to the high variance from uniform sampling. In this paper, we introduce an algorithm that approximately samples a gradient from the optimal distribution for a common finite-sum form with $n$ terms, while just making a single pass over the data, using input sparsity time, and $\tO{Td}$ space. Our algorithm can be implemented in big data models such as the streaming and distributed models. Moreover, we show that our algorithm can be generalized to approximately sample Hessians and thus provides variance reduction for second-order methods as well. We demonstrate the efficiency of our algorithm on large-scale datasets.
Code (0)
등록된 구현이 없습니다.
Tasks
Second-order methodsStochastic OptimizationSimilar Papers 제목 키워드 기반
Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches
In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) achieves the optimal rate of $O\left(\frac{…
Federated LearningStochastic Adaptive Gradient Descent Without Descent
We introduce a new adaptive step-size strategy for convex optimization with stochastic gradient that exploits the local geometry of the objective function only by means of a first-order stochastic oracle and without any …
Cutting Some Slack for SGD with Adaptive Polyak Stepsizes
Tuning the step size of stochastic gradient descent is tedious and error prone. This has motivated the development of methods that automatically adapt the step size using readily available information. In this paper, we …
Semi-Stochastic Gradient Descent Methods
In this paper we study the problem of minimizing the average of a large number ($n$) of smooth convex loss functions. We propose a new method, S2GD (Semi-Stochastic Gradient Descent), which runs for one or several epochs…
Optimal Adaptive and Accelerated Stochastic Gradient Descent
Stochastic gradient descent (\textsc{Sgd}) methods are the most powerful optimization tools in training machine learning and deep learning models. Moreover, acceleration (a.k.a. momentum) methods and diagonal scaling (a.…
BIG-bench Machine LearningStochastic Optimization