Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
This work addresses foundational limitations in optimization algorithms for machine learning, providing theoretical insights that are incremental but crucial for algorithm design.
The paper investigates the limitations of applying variance-reduction and acceleration techniques to finite sum optimization problems, showing that achieving certain complexity bounds requires additional information like knowledge of individual functions or explicit strong convexity parameters, and it establishes optimal bounds for smooth convex finite sums under specific conditions.
We study the conditions under which one is able to efficiently apply variance-reduction and acceleration schemes on finite sum optimization problems. First, we show that, perhaps surprisingly, the finite sum structure by itself, is not sufficient for obtaining a complexity bound of $\tilde{\cO}((n+L/μ)\ln(1/ε))$ for $L$-smooth and $μ$-strongly convex individual functions - one must also know which individual function is being referred to by the oracle at each iteration. Next, we show that for a broad class of first-order and coordinate-descent finite sum algorithms (including, e.g., SDCA, SVRG, SAG), it is not possible to get an `accelerated' complexity bound of $\tilde{\cO}((n+\sqrt{n L/μ})\ln(1/ε))$, unless the strong convexity parameter is given explicitly. Lastly, we show that when this class of algorithms is used for minimizing $L$-smooth and convex finite sums, the optimal complexity bound is $\tilde{\cO}(n+L/ε)$, assuming that (on average) the same update rule is used in every iteration, and $\tilde{\cO}(n+\sqrt{nL/ε})$, otherwise.