Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks

Shuoguang YangXuezhou ZhangMengdi Wang

article2022NeurIPS66 citations

Proposes a single-timescale gossip-based algorithm for decentralized stochastic bilevel optimization that achieves optimal per-agent sample complexity and a linear speedup with network size for both nonconvex and Polyak-Łojasiewicz objectives.

Listen

Modern distributed machine learning applications—such as hyperparameter tuning, meta-learning, and multi-agent reinforcement learning—increasingly rely on nested optimization structures known as bilevel optimization. In these problems, an outer decision depends directly on the outcome of an inner, lower-level task. In decentralized networks, data is spread across multiple devices or sensors that cannot share raw data due to privacy concerns and lack a central server to coordinate learning. Under these conditions, finding optimal solutions is exceptionally difficult because nodes cannot directly access the global calculations required to compute the necessary gradients.

The article develops and evaluates a decentralized, gossip-based stochastic approximation algorithm designed to solve these nested optimization problems collaboratively across communication networks. The framework enables participating nodes to solve both the inner and outer optimization levels simultaneously in a single timescale without relying on a central coordinator.

To establish mathematical and empirical credibility, the authors conducted theoretical convergence analyses across general nonconvex objectives and structured Polyak-Łojasiewicz conditions, which include strongly convex objectives. Nodes exchange only local parameter estimates with immediate network neighbors using a gossip protocol based on a doubly stochastic weighting matrix. The authors also evaluated the algorithm using simulated experiments on a ring network topology for two benchmark applications: tuning regularizers on a handwriting recognition dataset across up to 20 nodes and policy evaluation for multi-agent reinforcement learning across 100 states.

The analysis produced several key findings. First, the algorithm achieves optimal sample complexity, matching the theoretical performance of traditional single-server systems. It achieves a per-node sample complexity proportional to one over the number of nodes multiplied by the squared error tolerance for general nonconvex objectives, and one over the number of nodes multiplied by the error tolerance for structured objectives. Second, the algorithm demonstrates an exact linear speedup: as the number of network nodes increases, the per-node data samples required to reach a target accuracy decrease proportionally. Third, the mathematical analysis proves that network consensus errors diminish rapidly over time, meaning the specific communication topology does not degrade the long-term convergence rate. Finally, simulated experiments confirmed that the proposed approach converges faster and requires significantly fewer data samples to achieve target accuracy than baseline decentralized methods.

These findings demonstrate that organizations can deploy nested, multi-task machine learning over fully peer-to-peer networks without sacrificing computational efficiency or privacy. By communicating only parameter estimates rather than raw data, the method reduces privacy risks and data transfer costs. Furthermore, eliminating the central server prevents single-point-of-failure vulnerabilities, ensuring the system remains operational even if specific communication channels fail.

Decision-makers can consider implementing this peer-to-peer gossip framework for privacy-sensitive, multi-agent systems and edge-device networks. For future development, the article recommends investigating algorithmic variants with reduced iteration counts and lower per-round communication overhead, which would further optimize operational network bandwidth.

Confidence in these findings is supported by rigorous mathematical proofs and consistent numerical simulations. However, readers should note that the current experimental evaluations rely on simulated desktop environments and specific network configurations, such as ring topologies. Practical deployments across larger, highly irregular networks with real-world latency, packet drops, or asynchronous communication should be validated with targeted pilot testing.

Princeton University The Hong Kong University of Science and Technology communication networks optimization stochastic gossip-based stochastic bilevel optimization decentralized optimization bilevel optimization

arXiv: 2206.10870

Paper: Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent, Xiangru Lian et al. (2017). Provides the foundational analysis of decentralized stochastic gradient descent with gossip-based consensus and linear speedup that the source adapts to bilevel optimization.
Paper: Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling, John Duchi et al. (2010). Establishes the foundational theoretical framework for analyzing decentralized consensus and convergence scaling across communication network topologies using spectral graph theory.
Paper: Will Bilevel Optimizers Benefit from Loops, Kaiyi Ji et al. (2022). Analyzes convergence guarantees and gradient approximation mechanics in gradient-based bilevel optimization, which the source extends into a decentralized network setting.
Paper: A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse, Junyi Li et al. (2022). Introduces single-loop approximations for bilevel optimization that eliminate nested inner-loop iterations and matrix inversions, foundational to single-timescale stochastic bilevel solvers.
Paper: BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach, Bo Liu et al. (2022). Develops first-order reformulation techniques for bilevel optimization problems without requiring exact second-order Hessian inversions.

Paper: Lower Bounds and Accelerated Algorithms for Bilevel Optimization, Kaiyi Ji et al. (2023). Establishes theoretical lower complexity bounds and accelerated algorithms for bilevel optimization, pushing past the baseline convergence rates analyzed in the source.
Paper: Multi-Consensus Decentralized Accelerated Gradient Descent, Haishan Ye et al. (2023). Extends decentralized optimization by introducing multi-consensus accelerated gradient methods that achieve optimal computational and near-optimal communication complexity over graphs.

Cover for Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks

Abstract

Bilevel optimization have gained growing interests, with numerous applications being found in meta learning, minimax games, reinforcement learning, and nested composition optimization. This paper studies the problem of decentralized distributed stochastic bilevel optimization over a network where each agent can only communicate with its neighbors, and gives examples from multi-task, multi-agent learning and federated learning. In this paper, we propose a gossip-based decentralized bilevel learning algorithm that allows networked agents to solve both the inner and outer optimization problems in a single timescale and share information through network propagation. We show that our algorithm enjoys the Õ(1/(Kϵ₂)) per-agent sample complexity for general nonconvex bilevel optimization and Õ(1/(Kϵ)) for Polyak-Łojasiewicz objectives, achieving a speedup that scales linearly with the network size K. The sample complexities are optimal in both ϵ and K. We test our algorithm on the examples of hyperparameter tuning and decentralized reinforcement learning. Simulated experiments confirmed that our algorithm achieves the state-of-the-art training efficiency and test accuracy.

Topics

communication networks optimization stochastic

Keywords

gossip-based stochastic bilevel optimization decentralized optimization bilevel optimization communication networks gossip protocol stochastic gradient descent compositional optimization stochastic approximation scheme hyper-parameter optimization

1 Introduction
1.1 Example applications of SBO
1.2 Challenges with Distributed SBO
2 Related Works
3 Problem Setup
4 Algorithm
5 Theory
5.1 Nonconvex Objectives
5.2 PL Objectives
6 Numerical Experiments
7 Conclusion
Acknowledgments and Disclosure of Funding
References

Knowls

Knowl 1 — Decentralized stochastic bilevel optimization problem
definition
The paper formulates decentralized stochastic bilevel optimization over $K$ agents, where agent $k$ has local outer objective $f^k$ and inner objective $g^k$ . The agents jointly solve
$\min_{x\in\mathbb{R}^{d_x}} F(x):=f\bigl(x,y^\star(x)\bigr)=\frac{1}{K}\sum_{k=1}^{K}f^k\bigl(x,y^\star(x)\bigr), \qquad y^\star(x):=\arg\min_{y\in\mathbb{R}^{d_y}}g(x,y),$
where $g(x,y):=\frac{1}{K}\sum_{k=1}^{K}g^k(x,y)$ , $f^k(x,y)=\mathbb{E}[f^k(x,y;\zeta^k)]$ , and $g^k(x,y)=\mathbb{E}[g^k(x,y;\xi^k)]$ . The random variables $\zeta^k$ and $\xi^k$ may have heterogeneous distributions across agents, and each agent can communicate only with its network neighbors.

When the inner objective is strongly convex in $y$ , the outer gradient is characterized by
$\nabla F(x)=\nabla_x f\bigl(x,y^\star(x)\bigr)-\nabla^2_{xy}g\bigl(x,y^\star(x)\bigr)\left[\nabla^2_{yy}g\bigl(x,y^\star(x)\bigr)\right]^{-1}\nabla_y f\bigl(x,y^\star(x)\bigr),$
where $\nabla^2_{xy}g\in\mathbb{R}^{d_x\times d_y}$ , $\nabla^2_{yy}g\in\mathbb{R}^{d_y\times d_y}$ , and $\nabla_y f\in\mathbb{R}^{d_y}$ . The decentralized difficulty is that the terms in this expression must be estimated from heterogeneous local data and aggregated through neighbor communication.
Knowl 2 — Oracle, network, and regularity conditions
assumption
The theoretical guarantees assume the following conditions for the decentralized bilevel problem. Each agent can query an independent sampling oracle that returns unbiased stochastic estimates of $\nabla_x f^k$ , $\nabla_y f^k$ , $\nabla_y g^k$ , $\nabla^2_{xy}g^k$ , and $\nabla^2_{yy}g^k$ at any $(x,y)$ . The communication network is represented by a symmetric, nonnegative, doubly stochastic matrix $W\in\mathbb{R}^{K\times K}$ , and its disagreement factor satisfies
$\left\|W-\frac{1}{K}\mathbf{1}\mathbf{1}^{\mathsf T}\right\|_2=\rho<1,$
where $\mathbf{1}\in\mathbb{R}^{K}$ is the all-ones vector and $\|\cdot\|_2$ is the spectral norm.

The outer functions have an optimal solution, their gradients with respect to $x$ and $y$ are $L_f$ -Lipschitz in $(x,y)$ , and their stochastic gradient estimates have uniformly bounded second moments by $C_f^2$ . The averaged inner objective $g(x,y)$ is $\mu_g$ -strongly convex in $y$ . Each $g^k$ is twice continuously differentiable; $\nabla_y g^k$ , $\nabla^2_{xy}g^k$ , and $\nabla^2_{yy}g^k$ are Lipschitz in $(x,y)$ , with constants $L_g$ and $\widetilde L_g$ as appropriate. The stochastic inner gradients and Hessians have bounded second moments, including bounds $C_g^2$ for $\nabla_y g^k$ and $L_g^2$ for the Hessian estimates. Finally, for some $0<\kappa_g\leq \mu_g/L_g\leq 1$ , the Hessian samples satisfy
$\mathbb{E}\left[\left\|I-\frac{1}{L_g}\nabla^2_{yy}g^k(x,y;\xi^k)\right\|_2^2\right]\leq (1-\kappa_g)^2,$
where $I\in\mathbb{R}^{d_y\times d_y}$ is the identity matrix. These conditions permit heterogeneity in both the outer and inner objectives.
Knowl 3 — Gossip-based single-timescale DSBO algorithm
algorithm
The proposed method maintains, at every agent $k$ , primal variables $(x_t^k,y_t^k)$ and network-averaged estimators $s_t^k\approx\nabla_x f$ , $h_t^k\approx\nabla_y f$ , $u_t^k\approx\nabla^2_{xy}g$ , and $q_t^k\approx[\nabla^2_{yy}g]^{-1}$ . Here $x_t^k\in\mathbb{R}^{d_x}$ , $y_t^k\in\mathbb{R}^{d_y}$ , $s_t^k\in\mathbb{R}^{d_x}$ , $h_t^k\in\mathbb{R}^{d_y}$ , $u_t^k\in\mathbb{R}^{d_x\times d_y}$ , and $q_t^k\in\mathbb{R}^{d_y\times d_y}$ . Let $\mathcal{N}_k$ be agent $k$ 's neighbors, $w_{kj}$ the entries of the gossip matrix, $\alpha_t$ the outer stepsize, $\beta_t$ the inner stepsize, $\gamma_t$ the estimator stepsize, and $b$ the number of Hessian samples used for the inverse-Hessian approximation.

At each iteration, every agent samples local first- and second-order information, gossips each estimator with its neighbors, updates the inner and outer variables, and constructs the inverse-Hessian estimator as follows:
Input: Stepsizes $\{\alpha_t\}$ , $\{\beta_t\}$ , $\{\gamma_t\}$ , iterations $T$ , sampling oracle, gossip matrix $W$ , Hessian bound $L_g$ , and truncation length $b$
Initialize $x_0^k=y_0^k=s_0^k=h_0^k=u_0^k=0$ and $v_{0,i}^k=\mu_g I$ for every agent $k$ and $i=1,\ldots,b$
For $t=0,\ldots,T-1$
    At every agent $k$ , sample $\nabla_x f^k$ , $\nabla_y f^k$ , $\nabla_y g^k$ , $\nabla^2_{xy}g^k$ , and independent $\nabla^2_{yy}g^k$ samples at $(x_t^k,y_t^k)$
     $x_{t+1}^k = \sum_{j\in\mathcal{N}_k}w_{kj}x_t^j-\alpha_t(s_t^k-u_t^kq_t^kh_t^k)$
     $y_{t+1}^k = \sum_{j\in\mathcal{N}_k}w_{kj}y_t^j-\beta_t\nabla_y g^k(x_t^k,y_t^k)$
     $s_{t+1}^k=(1-\gamma_t)\sum_{j\in\mathcal{N}_k}w_{kj}s_t^j+\gamma_t\nabla_x f^k(x_t^k,y_t^k)$
     $h_{t+1}^k=(1-\gamma_t)\sum_{j\in\mathcal{N}_k}w_{kj}h_t^j+\gamma_t\nabla_y f^k(x_t^k,y_t^k)$
     $u_{t+1}^k=(1-\gamma_t)\sum_{j\in\mathcal{N}_k}w_{kj}u_t^j+\gamma_t\nabla^2_{xy}g^k(x_t^k,y_t^k)$
    Set $Q_{t+1,0}^k=I$
    For $i=1,\ldots,b$
         $v_{t+1,i}^k=(1-\gamma_t)\sum_{j\in\mathcal{N}_k}w_{kj}v_{t,i}^j+\gamma_t\nabla^2_{yy}g^k(x_t^k,y_t^k)$
         $Q_{t+1,i}^k=I+(I-L_g^{-1}v_{t+1,i}^k)Q_{t+1,i-1}^k$
    End for
     $q_{t+1}^k=L_g^{-1}Q_{t+1,b}^k$
End for
Output $\bar{x}_t=K^{-1}\sum_{k=1}^{K}x_t^k$
The outer update uses the estimated bilevel gradient $s_t^k-u_t^kq_t^kh_t^k$ , while the inner update is a stochastic gradient step on the local inner objective combined with gossip averaging. All agents perform the inner and outer updates on the same iteration timescale.
Knowl 4 — Truncated stochastic inverse-Hessian estimator
model/method
The algorithm estimates the inverse of the averaged inner Hessian without requiring an unbiased inverse-Hessian sample. For a positive-definite Hessian $H=\nabla^2_{yy}g(x,y)$ and a scalar $L_g$ satisfying the paper's Hessian bounds, the inverse is approximated by the truncated Neumann series
$H^{-1}=\frac{1}{L_g}\left(I-\left(I-\frac{1}{L_g}H\right)\right)^{-1} \approx \frac{1}{L_g}\sum_{j=0}^{b}\left(I-\frac{1}{L_g}H\right)^j,$
where $b$ is the truncation length. Because the local inverse Hessians do not average to the inverse of the averaged Hessian, the method instead constructs $b$ independently gossiped Hessian estimators $v_{t,1}^k,\ldots,v_{t,b}^k$ . It recursively forms
$Q_{t,0}^k=I, \qquad Q_{t,i}^k=I+\left(I-\frac{1}{L_g}v_{t,i}^k\right)Q_{t,i-1}^k, \qquad q_t^k=\frac{1}{L_g}Q_{t,b}^k.$
The resulting $q_t^k\in\mathbb{R}^{d_y\times d_y}$ is used in $u_t^kq_t^kh_t^k$ to estimate the Hessian-vector correction in the bilevel gradient. The paper chooses $b=\Theta(\log T)$ in both convergence regimes, making the truncation error decrease sufficiently quickly while requiring only logarithmically many additional Hessian samples per iteration.
Knowl 5 — Nonconvex convergence and linear sample speedup
theoretical result
For a generally nonconvex outer objective $F$ , use constant stepsizes over a horizon of $T$ iterations:
$\alpha_t=C_0\sqrt{\frac{K}{T}}, \qquad \beta_t=\gamma_t=\sqrt{\frac{K}{T}}, \qquad b=\Theta(\log T),$
where $C_0>0$ is sufficiently small. Under the sampling, network, smoothness, bounded-moment, and strong-convexity conditions stated for the decentralized bilevel problem, the network average $\bar{x}_t=K^{-1}\sum_{k=1}^{K}x_t^k$ satisfies
$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|\nabla F(\bar{x}_t)\right\|^2\right] \leq O\left(\frac{1}{\sqrt{KT}}\right) +O\left(\frac{K}{T(1-\rho)^2}\right).$
The first term gives the main stochastic optimization rate, while the second is the network-consensus error. For a fixed connected network, the consensus term is lower order as $T$ grows, so the asymptotic rate is independent of the network topology. Ignoring logarithmic factors from $b$ , obtaining an $\varepsilon$ -stationary point in the criterion $T^{-1}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\bar{x}_t)\|^2]\leq\varepsilon$ requires $\widetilde O(1/(K\varepsilon^2))$ samples per agent, exhibiting a linear speedup in $K$ .
Knowl 6 — PL convergence and optimal sample complexity
theoretical result
Suppose the outer objective satisfies the Polyak–Łojasiewicz condition
$2\mu\bigl(F(x)-F^\star\bigr)\leq\|\nabla F(x)\|^2$
for some $\mu>0$ , where $F^\star=\min_xF(x)$ . This class includes strongly convex objectives. With diminishing stepsizes
$\alpha_t=\frac{2}{\mu(C_1+t)}, \qquad \beta_t=\gamma_t=\frac{C_1}{C_1+t}, \qquad b=\Theta(\log T),$
where $C_1$ is sufficiently large, the algorithm satisfies
$\mathbb{E}\left[F(\bar{x}_T)\right]-F^\star \leq O\left(\frac{1}{KT}\right) +O\left(\frac{\log T}{T^2(1-\rho)^2}\right).$
The network-consensus term decays faster than the leading $O(1/(KT))$ term for a fixed connected network. Consequently, finding an $\varepsilon$ -optimal point with expected gap at most $\varepsilon$ requires $O(1/(K\varepsilon))$ iterations and $\widetilde O(1/(K\varepsilon))$ stochastic samples per agent. Thus the method achieves linear speedup with the number of agents and the optimal dependence on $\varepsilon$ claimed for decentralized stochastic bilevel optimization.
Knowl 7 — Communication properties and central-server specialization
model/method
Each agent communicates estimator states and model variables with only its neighbors rather than transmitting raw local data. In one iteration, agent $k$ performs $O(|\mathcal{N}_k|)$ neighbor communications, where $|\mathcal{N}_k|$ is its neighborhood size, instead of communicating with all $K$ agents. The algorithm therefore preserves local-data privacy at the communication level and can continue operating after an individual communication link fails, provided the remaining network stays connected.

A central-server version is obtained by replacing neighbor gossip with synchronous aggregation by a server. In that setting all agents receive a common iterate, the consensus-error terms disappear, and the corresponding variant retains the nonconvex convergence rate $O(1/\sqrt{KT})$ .
Knowl 8 — Federated hyperparameter-optimization experiment
experimental setup
The paper evaluates the method on federated hyperparameter optimization for binary handwriting recognition using the Australia handwriting dataset. Each example has a feature vector $w_i\in\mathbb{R}^{14}$ and label $z_i\in\{0,1\}$ . The outer validation objective uses a sigmoid-based loss, while the inner training objective uses the training loss plus the strongly convex regularizer
$R(x,y)=\sum_{i=1}^{d}\frac{x_i^2}{2}\|y_i\|^2,$
where $x$ is the hyperparameter vector and $y$ is the model parameter vector. The data are randomly split into training and validation sets and then distributed across agents. The communication network is a ring with self-weight and neighbor weights $w_{ij}=1/3$ for $j\in\{i-1,i,i+1\}$ .

The proposed method uses $b=200$ , $T=20{,}000$ , $\alpha_t=0.1\sqrt{K/T}$ , and $\beta_t=\gamma_t=10\sqrt{K/T}$ . Ten independent simulations compare the method with a decentralized extension of the double-loop BSA baseline. For $K=5$ , the proposed method reaches a given validation accuracy with fewer total samples than the baseline. Runs with $K=5,10,20$ converge faster as $K$ increases, supporting the predicted decentralized speedup.
Knowl 9 — Decentralized policy-evaluation experiment
experimental setup
The second experiment studies distributed policy evaluation in a finite-state Markov decision process. Let $\mathcal{S}$ be the state space, let $\phi_s\in\mathbb{R}^{m}$ be a state feature, and approximate the value function by $V(s)=\phi_s^{\mathsf T}x$ . For discount factor $\gamma\in(0,1)$ and regularization coefficient $\lambda>0$ , the regularized Bellman objective is
$F(x)=\frac{1}{2|\mathcal{S}|}\sum_{s\in\mathcal{S}} \left(\phi_s^{\mathsf T}x-\mathbb{E}_{s'}\left[r(s,s')+\gamma\phi_{s'}^{\mathsf T}x\mid s\right]\right)^2 +\frac{\lambda}{2}\|x\|^2.$
With heterogeneous reward functions $r^k$ at $K$ agents, the inner response for state $s$ is
$y_s^\star(x)=\phi_s^{\mathsf T}x-\mathbb{E}_{s'}\left[\frac{1}{K}\sum_{k=1}^{K}r^k(s,s')+\gamma\phi_{s'}^{\mathsf T}x\mid s\right],$
and the objective can be written as $f(x,y^\star(x))=(2|\mathcal{S}|)^{-1}\sum_{s\in\mathcal{S}}(y_s^\star(x))^2+(\lambda/2)\|x\|^2$ . The experiment uses $|\mathcal{S}|=100$ , $\lambda=1$ , ring networks with $K=5,10,20$ , and ten independent simulations per network size. The proposed method is compared with a double-loop DSGD baseline.

The proposed method outperforms DSGD for $K=5$ . The log mean-squared error decreases with an empirical slope close to $-1$ , consistent with the $O(1/t)$ PL/strongly-convex rate. Achieving an error threshold of $10^{-6}$ requires approximately the same total number of samples for $K=5,10,20$ , so the samples required per agent decrease approximately linearly with $K$ .
Knowl 10 — Remaining efficiency limitations
limitation
The paper establishes convergence and sample-complexity guarantees but does not provide a lower-iteration-complexity or lower-communication-cost algorithm. The authors identify reducing the number of iterations and the communication burden as future work. The reported experiments are also conducted primarily on simulated ring networks; larger network sizes and fully connected or randomly connected topologies are treated only as supplementary extensions rather than as a full characterization of topology-dependent practical costs.

Coverage note — Related-work comparisons, background applications, proof derivations, and supplementary topology experiments were omitted because they do not add separate load-bearing contributions beyond the extracted methods, guarantees, and main experiments.

References

1.Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. In International Conference on Machine Learning, pages 367–376. PMLR, 2020.
2.Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. arXiv preprint arXiv:1805.08136, 2018.
3.Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37–44, 1973.
4.Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1–27, 2011. URL https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.
5.Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671, 2021a.
6.Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937–4948, 2021b.
7.Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems. arXiv preprint arXiv:2106.13781, 2021c.
8.Nicolas Couellan and Wenjuan Wang. On the convergence of stochastic bi-level gradient methods. Optimization, 2016.
9.Evin J Cramer, John E Dennis, Jr, Paul D Frank, Robert Michael Lewis, and Gregory R Shubin. Problem formulation for multidisciplinary optimization. SIAM Journal on Optimization, 4(4):754–776, 1994.
10.Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
11.Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61(12):3740–3754, 2016.
12.Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pages 1568–1577. PMLR, 2018.
13.Hongchang Gao and Heng Huang. Periodic stochastic gradient descent with momentum for decentralized training. arXiv preprint arXiv:2008.10435, 2020.
14.Jason Ge, Zhaoran Wang, Mengdi Wang, and Han Liu. Minimax-optimal privacy-preserving sparse pca in distributed systems. In International Conference on Artificial Intelligence and Statistics, pages 1589–1598. PMLR, 2018.
15.Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59–99, 2016.
16.Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.
17.Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1):960–979, 2020.
18.Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266, 2021.
19.Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and-bound rules for linear bilevel programming. SIAM Journal on scientific and Statistical Computing, 13(5):1194–1217, 1992.
20.Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170, 2020.
21.Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882–4892. PMLR, 2021.
22.Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34, 2021.
23.Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv:1907.09356, 2019.
24.Guanghui Lan and Yi Zhou. Random gradient extrapolation for distributed and stochastic optimization. SIAM Journal on Optimization, 28(4):2753–2782, 2018.
25.Guanghui Lan, Soomin Lee, and Yi Zhou. Communication-efficient algorithms for decentralized and stochastic optimization. Mathematical Programming, 180(1):237–284, 2020.
26.Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pages 1159–1167. PMLR, 2017a.
27.Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017b.
28.Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pages 3043–3052. PMLR, 2018.
29.Jialin Liu, Yuantao Gu, and Mengdi Wang. Averaging random projection: A fast online solution for large-scale constrained stochastic optimization. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3586–3590, 2015.
30.Eli Livne. Integrated aeroservoelastic optimization: status and direction. Journal of Aircraft, 36(1):122–145, 1999.
31.Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
32.Takayuki Okuno, Akiko Takeda, Akihiro Kawana, and Motokazu Watanabe. On lp-hyperparameter learning via bilevel nonsmooth optimization. Journal of Machine Learning Research, 22(245):1–47, 2021.
33.Shi Pu and Angelia Nedic. Distributed stochastic gradient tracking methods. Mathematical Programming, 187(1):409–457, 2021.
34.Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.5647, 2011.
35.A. Ruszczynski and A. Shapiro. Optimization of convex risk functions. Mathematics of Operations Research, 31(3):433–452, 2006.
36.Andrzej Ruszczynski. A stochastic subgradient method for nonsmooth nonconvex multilevel composition optimization. SIAM Journal on Control and Optimization, 59(3):2301–2320, 2021.
37.Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn–tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51–63, 2005.
38.Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
39.Jaroslaw Sobieszczanski-Sobieski and Raphael T Haftka. Multidisciplinary aerospace design optimization: survey of recent developments. Structural optimization, 14(1):1–23, 1997.
40.Murtaza Taj and Andrea Cavallaro. Distributed and decentralized multicamera tracking. IEEE Signal Processing Magazine, 28(3):46–58, 2011.
41.Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. arXiv preprint arXiv:2205.02215, 2022.
42.Shenyinying Tu. Two-Stage Decomposition Algorithms and Their Application to Optimal Power Flow Problems. PhD thesis, Northwestern University, 2021.
43.Shenyinying Tu, Andreas Wächter, and Ermin Wei. A two-stage decomposition approach for ac optimal power flow. IEEE Transactions on Power Systems, 36(1):303–312, 2020.
44.Heinrich Von Stackelberg and Stackelberg Heinrich Von. The theory of the market economy. Oxford University Press, 1952.
45.M. Wang and J. Liu. A stochastic compositional gradient method using markov samples. In Proceedings of the 2016 Winter Simulation Conference, pages 702–713. IEEE Press, 2016.
46.M. Wang, E. X. Fang, and H. Liu. Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2):419–449, 2017a.
47.M. Wang, J. Liu, and E. X. Fang. Accelerating stochastic composition optimization. The Journal of Machine Learning Research, 18(1):3721–3743, 2017b.
48.Mengdi Wang and Dimitri P Bertsekas. Incremental constraint projection methods for variational inequalities. Mathematical Programming, 150(2):321–363, 2015.
49.Mengdi Wang and Dimitri P Bertsekas. Stochastic first-order methods with random constraint projection. SIAM Journal on Optimization, 26(1):681–717, 2016.
50.Mengdi Wang, Ji Liu, and Ethan Fang. Accelerating stochastic composition optimization. In Advances in Neural Information Processing Systems, pages 1714–1722, 2016.
51.Xiaohan Wang, Mengdi Wang, and Yuantao Gu. A distributed tracking algorithm for reconstruction of graph signals. IEEE Journal of Selected Topics in Signal Processing, 9(4):728–740, 2015.
52.Ran Xin, Usman K Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimization with accelerated convergence. IEEE Transactions on Signal Processing, 68:6255–6271, 2020.
53.Ran Xin, Usman K Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 69:1842–1858, 2021.
54.Yue Xu, Zengde Deng, Mengdi Wang, Wenjun Xu, Anthony Man-Cho So, and Shuguang Cui. Voting-based multiagent reinforcement learning for intelligent iot. IEEE Internet of Things Journal, 8(4):2681–2693, 2020.
55.Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34, 2021.
56.S. Yang, M. Wang, and E. X. Fang. Multilevel stochastic gradient methods for nested composition optimization. SIAM Journal on Optimization, 29(1):616–659, 2019.

Citation

MLA

Yang, S., et al. “Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 238–52, https://proceedings.neurips.cc/paper_files/paper/2022/file/01db36a646c07c64dd39a92b4eceb417-Paper-Conference.pdf.

APA

Yang, S., Zhang, X., & Wang, M. (2022). Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks. Advances in Neural Information Processing Systems, 35, 238–252. https://proceedings.neurips.cc/paper_files/paper/2022/file/01db36a646c07c64dd39a92b4eceb417-Paper-Conference.pdf

Chicago

Yang, S., X. Zhang, and M. Wang. 2022. “Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks”. Advances in Neural Information Processing Systems 35: 238–52. https://proceedings.neurips.cc/paper_files/paper/2022/file/01db36a646c07c64dd39a92b4eceb417-Paper-Conference.pdf.

Harvard

Yang, S., Zhang, X. and Wang, M. (2022) “Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 238–252. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/01db36a646c07c64dd39a92b4eceb417-Paper-Conference.pdf.

Vancouver

1. Yang S, Zhang X, Wang M (2022) Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 238–252

BibTeX

@inproceedings{yang2022decentralized,
  title = {Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks},
  author = {Yang, Shuoguang and Zhang, Xuezhou and Wang, Mengdi},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {238-252},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/01db36a646c07c64dd39a92b4eceb417-Paper-Conference.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Decentralized stochastic bilevel optimization problem

Knowl 2 — Oracle, network, and regularity conditions

Knowl 3 — Gossip-based single-timescale DSBO algorithm

Knowl 4 — Truncated stochastic inverse-Hessian estimator

Knowl 5 — Nonconvex convergence and linear sample speedup

Knowl 6 — PL convergence and optimal sample complexity

Knowl 7 — Communication properties and central-server specialization

Knowl 8 — Federated hyperparameter-optimization experiment

Knowl 9 — Decentralized policy-evaluation experiment

Knowl 10 — Remaining efficiency limitations

References

Citation

BibTeX

Access the Paper