An Optimal Algorithm for Strongly Convex Min-Min Optimization

摘要

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 μ_x-strongly convex in x and μ_y-strongly convex in y. The optimal accelerated gradient method of Yurii Nesterov achieves a convergence rate that requires approximately 𝒪((min(μ_x, μ_y))^-1/2) evaluations of the partial gradients ∇_x f and ∇_y f. In this paper, we propose a novel optimization algorithm that improves upon this complexity by requiring only 𝒪(μ_x^-1/2) computations of ∇_x f and 𝒪(μ_y^-1/2) computations of ∇_y f. This improvement is particularly advantageous in scenarios where there is a significant disparity between the strong convexity parameters, specifically when μ_x ≫μ_y. Furthermore, in practical applications where the computation of ∇_y f is considerably more efficient than that of ∇_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.