{
  "id": "2211.04088",
  "version": "v1",
  "published": "2022-11-08T08:39:30.000Z",
  "updated": "2022-11-08T08:39:30.000Z",
  "title": "A Penalty Based Method for Communication-Efficient Decentralized Bilevel Programming",
  "authors": [
    "Parvin Nazari",
    "Ahmad Mousavi",
    "Davoud Ataee Tarzanagh",
    "George Michailidis"
  ],
  "categories": [
    "cs.LG",
    "cs.DC",
    "math.OC"
  ],
  "abstract": "Bilevel programming has recently received attention in the literature, due to a wide range of applications, including reinforcement learning and hyper-parameter optimization. However, it is widely assumed that the underlying bilevel optimization problem is solved either by a single machine or in the case of multiple machines connected in a star-shaped network, i.e., federated learning setting. The latter approach suffers from a high communication cost on the central node (e.g., parameter server) and exhibits privacy vulnerabilities. Hence, it is of interest to develop methods that solve bilevel optimization problems in a communication-efficient decentralized manner. To that end, this paper introduces a penalty function based decentralized algorithm with theoretical guarantees for this class of optimization problems. Specifically, a distributed alternating gradient-type algorithm for solving consensus bilevel programming over a decentralized network is developed. A key feature of the proposed algorithm is to estimate the hyper-gradient of the penalty function via decentralized computation of matrix-vector products and few vector communications, which is then integrated within our alternating algorithm to give the finite-time convergence analysis under different convexity assumptions. Owing to the generality of this complexity analysis, our result yields convergence rates for a wide variety of consensus problems including minimax and compositional optimization. Empirical results on both synthetic and real datasets demonstrate that the proposed method works well in practice.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-08T08:39:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "communication-efficient decentralized bilevel programming",
      "bilevel optimization problem",
      "result yields convergence rates",
      "penalty function",
      "finite-time convergence analysis"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}