An Optimal Algorithm for Strongly Convex Min-min Optimization
Not on the map. Why?
Abstract (arXiv)
In this paper we study the smooth strongly convex minimization problem minxminy f(x,y). The existing optimal first-order methods require O(√maxkappax,kappay log 1/ε) of computations of both nablax f(x,y) and nablay f(x,y), where kappax and kappay are condition numbers with respect to variable blocks x and y. We propose a new algorithm that only requires O(√kappax log 1/ε) of computations of nablax f(x,y) and O(√kappay log 1/ε) computations of nablay f(x,y). In some applications kappax gg kappay, and computation of nablay f(x,y) is significantly cheaper than computation of nablax f(x,y). In this case, our algorithm substantially outperforms the existing state-of-the-art methods.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 35 of its 56 references that are in the map. First posted on arXiv 29 Dec 2022.
Builds on
35 of 56 references.
References · 35
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2018On First-Order Meta-Learning Algorithmscited by 1,003
- 2020The Future of Digital Health with Federated Learningcited by 625
- 2018Federated Learning for Mobile Keyboard Predictioncited by 565
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
- 2020Personalized Federated Learning: A Meta-Learning Approachcited by 309
- 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
- 2018Federated Meta-Learning with Fast Convergence and Efficient Communicationcited by 154
- 2020Is Local SGD Better than Minibatch SGD?cited by 151
- 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
23 more
- 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
- 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
- 2021Federated Reconstruction: Partially Local Federated Learningcited by 78
- 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
- 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
- 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
- 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 19
- 2019On a Combination of Alternating Minimization and Nesterov's Momentumcited by 18
- 2014Gradient Sliding for Composite Optimizationcited by 14
- 2018Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functionscited by 14
- 2018Primal-dual accelerated gradient methods with small-dimensional relaxation oraclecited by 14
- 2022CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimizationcited by 11
- 2018Alternating Randomized Block Coordinate Descentcited by 8
- 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
- 2019Adaptive Catalyst for Smooth Convex Optimizationcited by 6
- 2021Hyperfast Second-Order Local Solvers for Efficient Statistically Preconditioned Distributed Optimizationcited by 5
- 2020Oracle Complexity Separation in Convex Optimizationcited by 4
- 2021Solving smooth min-min and min-max problems by mixed oracle algorithmscited by 4
- 2015About accelerated randomized methodscited by 2
- 2019Alternating Minimization Methods for Strongly Convex Optimizationcited by 2
- 2020A H"olderian backtracking method for min-max and min-min problemscited by 2
- 2014On the three-stage version of stable dynamic modelcited by 1
- 2022Tensor methods inside mixed oracle for min-min problemscited by 1
Built on by
Not cited yet.