Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
This work addresses optimization challenges in big data problems, offering a faster method for machine learning and AI applications, though it appears incremental as it builds on existing classes of methods.
The paper tackles the problem of minimizing smooth strongly convex finite sums more efficiently by introducing Finito, a new incremental gradient method that achieves a theoretical convergence rate four times faster than existing methods for large sums and demonstrates state-of-the-art performance in practice.
Recent advances in optimization theory have shown that smooth strongly convex finite sums can be minimized faster than by treating them as a black box "batch" problem. In this work we introduce a new method in this class with a theoretical convergence rate four times faster than existing methods, for sums with sufficiently many terms. This method is also amendable to a sampling without replacement scheme that in practice gives further speed-ups. We give empirical results showing state of the art performance.