期刊
IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING
卷 10, 期 2, 页码 242-255出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/JSTSP.2015.2505682
关键词
Empirical risk minimization; mini-batches; proximal methods; semi-stochastic gradient descent; sparse data; stochastic gradient descent; variance reduction
资金
- Google Doctoral Fellowship in Optimization Algorithms
- Gotshall Fellowship from Lehigh University, Bethlehem, PA, USA
- Engineering and Physical Sciences Research Council (EPSRC) [EP/K02325X/1]
- EPSRC [EP/K02325X/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/K02325X/1] Funding Source: researchfish
We propose mS2GD: a method incorporating a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent (S2GD). We consider the problem of minimizing a strongly convex function represented as the sum of an average of a large number of smooth convex functions, and a simple nonsmooth convex regularizer. Our method first performs a deterministic step (computation of the gradient of the objective function at the starting point), followed by a large number of stochastic steps. The process is repeated a few times with the last iterate becoming the new starting point. The novelty of our method is in introduction of mini-batching into the computation of stochastic steps. In each step, instead of choosing a single function, we sample functions, compute their gradients, and compute the direction based on this. We analyze the complexity of the method and show that it benefits from two speedup effects. First, we prove that as long as is below a certain threshold, we can reach any predefined accuracy with less overall work than without mini-batching. Second, our mini-batching scheme admits a simple parallel implementation, and hence is suitable for further acceleration by parallelization.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据