An Optimal Algorithm for Strongly Convex Min-Min Optimization

Abstract

We consider the problem of minimizing a function $ f(x, y) $, where $ f $ is a smooth and strongly convex function with respect to both variables, being $ \mu_x $-strongly convex in $ x $ and $ \mu_y $-strongly convex in $ y $. The optimal accelerated gradient method of Yurii Nesterov achieves a convergence rate that requires approximately $ \mathcal{O}((\min(\mu_x, \mu_y))^{-1/2}) $ evaluations of the partial gradients $ \nabla_x f $ and $ \nabla_y f $. In this paper, we propose a novel optimization algorithm that improves upon this complexity by requiring only $ \mathcal{O}(\mu_x^{-1/2}) $ computations of $ \nabla_x f $ and $ \mathcal{O}(\mu_y^{-1/2}) $ computations of $ \nabla_y f $. This improvement is particularly advantageous in scenarios where there is a significant disparity between the strong convexity parameters, specifically when $ \mu_x \gg \mu_y $. Furthermore, in practical applications where the computation of $ \nabla_y f $ is considerably more efficient than that of $ \nabla_x f $, the proposed method leads to a substantial reduction in the overall wall-clock time required for optimization. As a key application, we consider Partially Local Federated Learning, a setting in which the model is partitioned into a local component and a global component. We demonstrate how our proposed method can be effectively applied in this framework, highlighting its practical advantages in improving computational efficiency.