Neighbor-Only Hypergradients for Networked Leader–Follower Problems

Many engineered multi-agent systems have two levels. A coordinator, such as a grid operator setting tariffs or a city setting tolls, chooses parameters. Then many agents respond by jointly solving a constrained optimization problem in which each agent interacts only with its physical neighbors. Tuning the coordinator's parameters by gradient descent requires a hypergradient: the derivative of the coordinator's objective through the agents' optimal response. Today that derivative is computed in one of two ways. The first is centrally, by differentiating the agents' full optimality conditions. The second is by having every agent keep a copy of a global parameter vector and agree on it with all the others. Both throw away the fact that agent $i$ only ever shares constraints with a handful of neighbors.

This note proposes a different route. Smoothing the agents' hard constraints into soft penalties during the backward pass alone turns the hypergradient computation into a symmetric positive definite linear system. That system's nonzero pattern is exactly the agents' interaction graph. Such a system can be solved by message passing between neighbors, exactly on trees and with checkable convergence conditions on loopy graphs. Each agent's communication then scales with its neighborhood size rather than the network size. Global coupling constraints, such as a shared capacity limit, do not destroy this structure. Each one contributes only a low-rank correction that can be broadcast cheaply.

Core Claim

The research file frames a real obstacle. When a lower-level problem is replaced by its first-order optimality conditions, known as the KKT (Karush–Kuhn–Tucker) conditions, dual variables are added for every constraint. The result is an indefinite "saddle-point" system that couples agents and has no clean elimination order. Exact single-level KKT reformulations make things worse when they are solved with binary switching variables ("Big-M" mixed-integer programs), as in Proactive Demand Response for Data Centers and Yao et al.: there are $2^K$ possible configurations of which constraints are active.

The method we build on is dXPP (also; A Penalty Approach For Differentiation Through Black-box Quadratic Programming Solvers; A Penalty Approach For Differentiation Through Black-box Quadratic Programming Solvers). It keeps any black-box solver in the forward pass, replaces inequality constraints with softplus penalties only in the backward pass, and obtains a primal-only positive definite system. Its gradient converges to the exact KKT gradient as the smoothing parameter shrinks. dXPP was built and tested only on centralized problems.

Our claim is structural. Suppose agent $i$ controls a block $y_i$, the follower objective $g(x,y)$ decomposes over pairs or small groups of neighboring agents, and each constraint $h_c(y) \le 0$ touches only a neighborhood $N(c)$. Then the smoothed adjoint system takes the following form:

$$ \Big(\nabla^2_{yy} g + \sum_{c} \tfrac{\rho}{\delta}\,\sigma'\!\big(h_c/\delta\big)\,\nabla h_c \nabla h_c^{\top} + \sum_c \rho\,\sigma\!\big(h_c/\delta\big)\nabla^2 h_c\Big)\, v = \nabla_y f . $$

Here $x$ is the leader's parameter and $f$ its objective, $\sigma$ is the logistic function (the derivative of softplus), $\rho$ is the penalty weight, $\delta$ is the smoothing width, and $v$ is the adjoint vector. The hypergradient is $\nabla_x f - (\nabla^2_{xy} g_\delta)^{\top} v$, where $g_\delta$ is the penalized objective. Block $(i,j)$ of the matrix is nonzero only if agents $i$ and $j$ share a factor of $g$ or a constraint. So the matrix is positive definite and has the sparsity of the coordination graph.

Positive definiteness is what makes neighbor-only solution possible. Eliminating agents in any order is numerically stable, and the size of the intermediate blocks is governed by the induced width of the graph. This is the same quantity that Kumar and Guestrin et al. showed controls variable elimination in factored planning. We are porting that tree-width argument from discrete maximization to continuous hypergradients.

A constraint that couples everyone, such as $\sum_i y_i \le C$, adds one dense rank-one term. We handle it with a Sherman–Morrison correction: one extra sparse solve plus a single scalar that all agents need to know. With $G$ such global constraints, the cost is $G+1$ sparse solves. This answers the file's "candidate gap" that dual multipliers of shared constraints collapse sparsity. They do so only in the saddle-point form, not in the smoothed primal form.

Research Program

The first component is the algorithm. The forward pass runs any distributed solver for the followers' convex problem. Our default is the coupled diffusion strategy of Alghunaim and Sayed, in which each agent tracks only the sub-vectors it shares, and we compare it against ADMM. The backward pass solves the adjoint system by message passing on the agents' graph. On trees and junction trees we use exact two-sweep elimination. On loopy graphs we use Gaussian belief propagation, a message-passing linear solver that converges when the matrix is walk-summable, and fall back to a few neighbor-only conjugate-gradient iterations otherwise. Each agent then forms its local contribution to $\nabla_x f$. If the leader's parameters are themselves local (per-node tariffs, for instance), the leader's gradient never needs global aggregation either.

The second component is analysis of the smoothing trade-off the file flags as open. Shrinking $\delta$ reduces bias but stiffens the curvature at near-active constraints. That stiffness both worsens conditioning and can break the diagonal dominance that loopy message passing relies on. We will bound two quantities together, both expected as $\delta \to 0$: the hypergradient bias, which inherits dXPP's convergence argument, and the message-passing contraction factor, which depends on the ratio of off-diagonal to diagonal curvature. From these we derive a $\delta$ schedule that balances them. We will also compare softplus against the linear-smoothed log barrier of CSAC-LB, which caps curvature outside the feasible set differently.

The third component is the application regime. We will study leader–follower problems on physical networks where locality is real. The main test is a distribution-grid operator setting time-varying per-bus tariffs and curtailment limits. Prosumer agents respond under linearized power-flow constraints on the radial IEEE-33 bus network, written with per-line flow variables so that every constraint is local to a tree edge. Substation capacity is the single global constraint.

Baselines

The naive reference point is a global-consensus decentralized bilevel method. Our primary choice is SLAM, a single-loop linearized augmented-Lagrangian method in which every node holds and agrees on the full upper- and lower-level vectors. DUET serves as the variant that does not require strong convexity. These are the only decentralized bilevel methods in the file, so they are the natural competitor for "solve it without a central node." We run them on the same graph with the same follower problem and the same number of communication rounds. We match tuning budgets: an equal-size grid over step sizes for every method. Beating them means reaching the same leader objective with per-agent communication that stays flat as $N$ grows, while theirs grows linearly. DUET reports 6% higher test accuracy than standard decentralized baselines on 5-agent MNIST meta-learning. There is no reported result on Lacuna for any of these methods on a grid or coordination-graph bilevel task.

The strongest existing method for hypergradient accuracy and speed is centralized dXPP with sparse Cholesky. On 1,000,000-variable sparse projections it reports a 4.2x to 9.2x backward-pass speedup over solver-agnostic methods, and relative gradient error versus exact KKT of $10^{-7}$ to $10^{-4}$ in most tests dXPP. We run it on the identical problems with the same $\delta$ and a fill-reducing ordering. We do not expect to beat it on single-machine wall-clock. Matching its gradient error within a factor of ten, with no node ever holding more than its neighborhood, counts as success.

For exactness on small instances, the reference is the Big-M mixed-integer reformulation solved to optimality, as in the demand-response line of work. This provides the true leader optimum against which to measure the suboptimality of every gradient method.

The ablation that isolates the key ingredient keeps everything identical except the backward pass. Instead of the smoothed primal system, it solves the exact KKT saddle-point system distributedly, using a neighbor-only primal–dual iterative solver of the type implicit in Landry et al. and Dyro et al., which differentiate centrally through augmented-Lagrangian or barrier-smoothed optimality conditions. If this ablation converges equally fast and equally robustly near weakly active constraints, smoothing is not what matters. A second ablation removes the Sherman–Morrison step and treats the global constraint as dense, to measure what the low-rank handling buys.

Why not just…?

Why not just run centralized dXPP with sparse Cholesky? Sparse Cholesky with a good ordering already is variable elimination, so on raw compute this alternative captures most of the tree-width benefit, and we say so plainly. The proposal's value lies elsewhere: settings with no trusted central node, private agent data, or bandwidth limits. There, dXPP needs every agent's Hessian block shipped to one place. Our experiments report both wall-clock and bytes communicated per agent. If an application has a central node and no privacy constraint, the honest recommendation is centralized dXPP.

Why not just unroll the distributed forward solver and backpropagate through its iterations? Unrolling ADMM or diffusion is neighbor-local by construction, so it is the most serious threat. Its weaknesses are that memory grows with the number of forward iterations and that gradient quality is tied to how far the forward solve ran. Our adjoint solve decouples the two. The file has no reported number for unrolled distributed solvers on these tasks, so we include this baseline directly. We sweep unroll depth and measure gradient error against the exact KKT gradient, per-agent memory, and leader suboptimality. If unrolling at modest depth matches us, we will narrow the claim to regimes with long forward horizons.

Why not just use the exact KKT reformulation as a mixed-integer program? That approach is exact but faces $2^K$ active-set configurations. The file's evidence is that an all-in-one formulation took 246 seconds against 30.7 seconds for a decomposed differentiable approach in Landry et al.. We use it only as ground truth on instances it can solve, and report the network size at which it stops returning within a fixed time budget.

Why not just fold the constraints into the leader's objective as penalties and skip the bilevel structure? That discards the followers' optimal response. The leader then optimizes against agents who would not behave as modeled, and penalty weights are notoriously hard to tune (CSAC-LB; Safe MARL in autonomous driving). We include a single-level penalized baseline and evaluate its chosen tariffs by re-solving the true follower problem.

Proposed Experiments

The first experiment is a controlled-topology study on synthetic coordination graphs: trees, rings, 2-D grids, and random graphs of increasing degree, with $N$ from 10 to 10,000 agents. Followers are convex quadratic programs whose local constraints are tuned so that a chosen fraction sits near-active, and there are 0, 1, or 5 global constraints. We measure relative hypergradient error against exact centralized KKT differentiation, message-passing rounds to a tolerance of $10^{-6}$, per-agent bytes, and per-agent memory, each as functions of $N$, induced width, and $\delta$. The decisive check is whether per-agent cost tracks induced width and stays flat in $N$ on trees and rings. A second check is whether the distributed KKT ablation degrades, through failure to converge or error blow-up, as constraints approach weak activity while the smoothed system does not.

The second experiment uses the grid application on the IEEE-33 bus network, with renewable scenarios from DDRE-33. That dataset reports Wasserstein distances of 0.0242 (wind) and 0.0232 (PV) to real data. Prosumer agents sit at each bus, and the leader learns per-bus tariffs that minimize peak substation load and voltage violations. We report leader cost, followers' realized constraint violations under the true hard constraints, and the gap to the mixed-integer optimum on short horizons. We compare against all baselines above at matched communication rounds. To test scaling on realistic topology, we replicate the feeder into multi-feeder trees of several hundred buses. No reported result on Lacuna exists for bilevel tariff design on IEEE-33, so every number here will be new and measured against our own exact reference.

The third experiment calibrates the $\delta$ trade-off. For each topology we trace hypergradient bias and message-passing contraction across $\delta$ spanning four orders of magnitude, softplus versus linear-smoothed log barrier. We then check whether the derived schedule matches the empirically best fixed $\delta$ at lower total communication. The proposal is falsified if either of two things holds: unrolled distributed solvers match our accuracy at equal memory, or loopy message passing on grids needs so many rounds near realistic $\delta$ that per-agent communication grows with $N$ anyway.