EE-Grad: Exploration and Exploitation for Cost-Efficient Mini-Batch SGD
This work addresses cost-efficiency in machine learning optimization for practitioners, but it is incremental as it builds on existing mini-batch SGD methods.
The paper tackles the problem of optimizing mini-batch sizes in stochastic gradient descent when costs for gradients of varying quality are unknown, proposing EE-Grad to balance exploration and exploitation, with theoretical guarantees for strongly convex objectives and numerical validation.
We present a generic framework for trading off fidelity and cost in computing stochastic gradients when the costs of acquiring stochastic gradients of different quality are not known a priori. We consider a mini-batch oracle that distributes a limited query budget over a number of stochastic gradients and aggregates them to estimate the true gradient. Since the optimal mini-batch size depends on the unknown cost-fidelity function, we propose an algorithm, {\it EE-Grad}, that sequentially explores the performance of mini-batch oracles and exploits the accumulated knowledge to estimate the one achieving the best performance in terms of cost-efficiency. We provide performance guarantees for EE-Grad with respect to the optimal mini-batch oracle, and illustrate these results in the case of strongly convex objectives. We also provide a simple numerical example that corroborates our theoretical findings.