A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization

• URL: http://arxiv.org/abs/2410.14115v1
• Date: Fri, 18 Oct 2024 02:00:45 GMT
• Title: A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization
• Authors: Min Wen, Chengchang Liu, Ahmed Abdelmoniem, Yipeng Zhou, Yuedong Xu,
• Abstract summary: This paper introduces a fully first-order decentralized method for decentralized Bilevel optimization, $textC2$DFB. $textC2$DFB is both compute- and communicate-efficient.
• Score: 16.020878731214083
• License:
• Abstract: Bilevel optimization, crucial for hyperparameter tuning, meta-learning and reinforcement learning, remains less explored in the decentralized learning paradigm, such as decentralized federated learning (DFL). Typically, decentralized bilevel methods rely on both gradients and Hessian matrices to approximate hypergradients of upper-level models. However, acquiring and sharing the second-order oracle is compute and communication intensive. % and sharing this information incurs heavy communication overhead. To overcome these challenges, this paper introduces a fully first-order decentralized method for decentralized Bilevel optimization, $\text{C}^2$DFB which is both compute- and communicate-efficient. In $\text{C}^2$DFB, each learning node optimizes a min-min-max problem to approximate hypergradient by exclusively using gradients information. To reduce the traffic load at the inner-loop of solving the lower-level problem, $\text{C}^2$DFB incorporates a lightweight communication protocol for efficiently transmitting compressed residuals of local parameters. % during the inner loops. Rigorous theoretical analysis ensures its convergence % of the algorithm, indicating a first-order oracle calls of $\tilde{\mathcal{O}}(\epsilon^{-4})$. Experiments on hyperparameter tuning and hyper-representation tasks validate the superiority of $\text{C}^2$DFB across various typologies and heterogeneous data distributions.

Related papers

• Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration [66.43954501171292]
  We introduce Catalyst Acceleration and propose an acceleration Decentralized Federated Learning algorithm called DFedCata. DFedCata consists of two main components: the Moreau envelope function, which addresses parameter inconsistencies, and Nesterov's extrapolation step, which accelerates the aggregation phase. Empirically, we demonstrate the advantages of the proposed algorithm in both convergence speed and generalization performance on CIFAR10/100 with various non-iid data distributions.
  arXiv  Detail & Related papers  (2024-10-09T06:17:16Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  Traditional gradient-based bi-level optimization algorithms are ill-suited to meet the demands of large-scale applications. We introduce $(textFG)2textU$, which achieves an unbiased approximation of the meta gradient for bi-level optimization. $(textFG)2textU$ is inherently designed to support parallel computing, enabling it to effectively leverage large-scale distributed computing systems.
  arXiv  Detail & Related papers  (2024-06-20T08:21:52Z)
• Asynchronous Distributed Bilevel Optimization [20.074079852690048]
  We propose Asynchronous Distributed Bilevel (ADBO) algorithm to tackle bilevel optimization problems. The complexity of ADBO to obtain the $epsilon$-stationary point is upper bounded by $mathcalO(frac1epsilon 2)$.
  arXiv  Detail & Related papers  (2022-12-20T07:44:48Z)
• DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization [27.317118892531827]
  We develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale approximation with momentum and gradient-tracking) We show that the DIAMOND enjoys $mathcalO(epsilon-3/2)$ in sample and communication complexities for achieving an $epsilon$-stationary solution.
  arXiv  Detail & Related papers  (2022-12-05T15:58:00Z)
• A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming [14.35928967799696]
  This paper introduces a penalty function-based decentralized algorithm for solving bilevel programming problems over a decentralized network. A key feature of the proposed algorithm is the estimation of the hyper-gradient of the penalty function. Our theoretical framework ensures non-asymptotic convergence to the optimal solution of the original problem under various convexity conditions.
  arXiv  Detail & Related papers  (2022-11-08T08:39:30Z)
• INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks [24.02913189682224]
  Decentralized bilevel optimization problems have received increasing attention in the networking machine learning communities. Low sample and communication complexities are two fundamental challenges that remain under-explored. Our work is the first that both low sample and communication complexities for solving decentralized bilevel optimization problems over networks.
  arXiv  Detail & Related papers  (2022-07-27T04:19:28Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  Local methods are one of the promising approaches to reduce communication time. We show that the communication complexity is better than non-local methods when the local datasets is smaller than the smoothness local loss.
  arXiv  Detail & Related papers  (2022-02-12T15:12:17Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  Internet-of-things, networked sensing, autonomous systems and federated learning call for decentralized algorithms for finite-sum optimizations. We develop DEcentralized STochastic REcurSive methodDESTRESS for non finite-sum optimization. Detailed theoretical and numerical comparisons show that DESTRESS improves upon prior decentralized algorithms.
  arXiv  Detail & Related papers  (2021-10-04T03:17:41Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.