gradient tracking

Fully First-Order Methods for Decentralized Bilevel Optimization

  • Xiaoyu Wang
  • Xuxing Chen
  • Shiqian Ma
  • Tong Zhang
    • Categories Nonlinear Optimization, Parallel Algorithms, Stochastic Programming Tags , , ,

    \(\) This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence … Read more

    Second-order Guarantees of Distributed gradient Algorithms

  • Amir Daneshmand
  • Vyacheslav Kungurtsev
  • Gesualdo Scutari
    • Categories Nonlinear Optimization Tags , ,

    We consider distributed smooth nonconvex unconstrained optimization over networks, modeled as a connected graph. We examine the behavior of distributed gradient-based algorithms near strict saddle points. Specifically, we establish that (i) the renowned Distributed Gradient Descent (DGD) algorithm likely converges to a neighborhood of a Second-order Stationary (SoS) solution; and (ii) the more recent class … Read more