An Optimal Algorithm for Strongly Convex Min-Min Optimization

Dmitry Kovalev, Alexander Gasnikov, Grigory Malinovsky
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:2363-2379, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-kovalev25a, title = {An Optimal Algorithm for Strongly Convex Min-Min Optimization}, author = {Kovalev, Dmitry and Gasnikov, Alexander and Malinovsky, Grigory}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {2363--2379}, year = {2025}, editor = {Chiappa, Silvia and Magliacane, Sara}, volume = {286}, series = {Proceedings of Machine Learning Research}, month = {21--25 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v286/main/assets/kovalev25a/kovalev25a.pdf}, url = {https://proceedings.mlr.press/v286/kovalev25a.html}, 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.} }
Endnote
%0 Conference Paper %T An Optimal Algorithm for Strongly Convex Min-Min Optimization %A Dmitry Kovalev %A Alexander Gasnikov %A Grigory Malinovsky %B Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2025 %E Silvia Chiappa %E Sara Magliacane %F pmlr-v286-kovalev25a %I PMLR %P 2363--2379 %U https://proceedings.mlr.press/v286/kovalev25a.html %V 286 %X 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.
APA
Kovalev, D., Gasnikov, A. & Malinovsky, G.. (2025). An Optimal Algorithm for Strongly Convex Min-Min Optimization. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:2363-2379 Available from https://proceedings.mlr.press/v286/kovalev25a.html.

Related Material