Nonlinear Consensus for Distributed Optimization

Hsu Kao, Vijay SubramanianarXiv 2023 · DOI · arXiv

TL;DR

This paper breaks the tradition of using simple linear averaging for consensus in distributed optimization. By introducing nonlinear transformations (like $p$-means) and relaxing strict matrix requirements, the authors demonstrate that nodes can reach agreement faster and more flexibly, significantly outperforming standard linear methods in practical simulations.

What Problem Does This Paper Address?

In distributed optimization, a network of agents (nodes) tries to minimize a global objective function. Most existing algorithms, like Distributed Gradient Descent (DGD), rely on two alternating steps: a descent step (where agents move toward their local optimum) and a consensus step (where agents average their values with their neighbors to stay in sync).

The "gap" identified here is that almost all literature assumes this consensus step must be linear—specifically, using "doubly stochastic" matrices where rows and columns sum to one. This is mathematically convenient but restrictive. It limits the speed of convergence and requires specific network symmetries. The authors ask: Can we use nonlinear transformations to reach consensus faster? And can we relax the matrix requirements to allow for more flexible communication protocols?

Methods

The authors introduce three main innovations to the consensus process:

  1. Nonlinear Transformations: Instead of a simple average, agents transform their neighbors' data using a monotonic Lipschitz function $\phi$, average it in that "warped" space, and then apply the inverse function $\phi^{-1}$. A key example is the $p$-mean (which generalizes arithmetic, geometric, and harmonic means).
  2. Relaxing Column Stochasticity: Standard proofs require consensus matrices to be doubly stochastic. The authors prove that for the primal variable (the actual solution $x$), you only need row stochasticity (ensuring agents stay within the "convex hull" of their neighbors). Column stochasticity is only strictly necessary for tracking the gradients.
  3. The Shrunk Cube Hull: By combining nonlinear transformations with relaxed matrix constraints, the authors define a "shrunk cube hull"—a much larger set of potential points an agent can move toward during the consensus step.
  4. Gradient-Oriented Consensus: They propose a specific strategy where agents pick a point in this cube hull that aligns with the negative total gradient. This allows the consensus step to contribute to the optimization goal, essentially "double-dipping" on progress.

These methods were integrated into two well-known frameworks: NEXT (for non-convex optimization) and DGD (for convex optimization).

Datasets

The paper evaluates these methods using numerical simulations rather than real-world datasets:

  • Network Topology: A 19-cell wrap-around hexagon network (common in cellular network modeling) where each node has 6 neighbors.
  • Objective Functions: Randomly generated quadratic functions with a "partial dependency structure," meaning a node's objective depends on its own variables and those of its neighbors.
  • Initial Conditions: Starting values were drawn from Chi-squared distributions to test how the algorithms perform when starting far below, near, or far above the optimal value.

Key Insights and Ideas

  • Beyond Asymptotics: While linear consensus takes infinite steps to reach perfect agreement (it's asymptotic), nonlinear operations like "Max" or "Min" can reach exact consensus in a finite number of steps equal to the network's diameter.
  • Direction Matters: The "best" nonlinear transformation depends on where you start. If initial values are lower than the optimum, a "Max" operation (high $p$ in $p$-mean) pulls values up toward the goal faster. If they are higher, a "Min" operation is better.
  • Consensus as Optimization: The most powerful idea is that the consensus step doesn't have to be "neutral." By using the "shrunk cube hull," agents can choose a consensus value that simultaneously satisfies the need for agreement and reduces the objective function.
  • Subprojections: The authors frame nonlinear consensus as a "subprojection" onto the consensus plane, allowing them to use stochastic approximation theory to guarantee convergence even when the transformations change over time.

Key Results

  • Convergence Guarantees: The authors provide rigorous proofs that these nonlinear schemes still converge to stationary points (for NEXT) or the global optimum (for DGD).
  • Speedup: In simulations, the Gradient-oriented Consensus in Cube Hull (Algorithm 10) consistently descended the fastest. It outperformed linear consensus by several orders of magnitude in terms of objective value reduction over the same number of iterations.
  • Flexibility: The results show that $p$-means with $p=5$ or $p=-3$ often beat the standard $p=1$ (linear) case, depending on the initial state of the network.

Limitations and Future Work

  • Data Dependency: The performance gains are highly sensitive to the relationship between the initial variables and the optimum. There is no single "magic" transformation that works best for every problem.
  • Theoretical vs. Practical Rates: While simulations show massive speedups, the theoretical "worst-case" convergence rate derived in the paper doesn't yet reflect this improvement over linear methods. Closing this gap between theory and practice is a noted challenge.
  • Manifold Extensions: The authors suggest extending these element-wise nonlinear transformations to Riemannian manifolds, which would allow for distributed optimization on more complex geometric surfaces.

Summary updated

Abstract

Distributed optimization algorithms have been studied extensively in the literature; however, underlying most algorithms is a linear consensus scheme, i.e. averaging variables from neighbors via doubly stochastic matrices. We consider nonlinear consensus schemes with a set of time-varying and agent-dependent monotonic Lipschitz nonlinear transformations, where we note the operation is a subprojection onto the consensus plane, which has been identified via stochastic approximation theory. For the proposed nonlinear consensus schemes, we establish convergence when combined with the NEXT algorithm [Lorenzo and Scutari, 2016], and analyze the convergence rate when combined with the DGD algorithm [Nedić and Ozdaglar, 2009]. In addition, we show that convergence can still be guaranteed even though column stochasticity is relaxed for the gossip of the primal variable, and then couple this with nonlinear transformations to show that as a result one can choose any point within the "shrunk cube hull" spanned from neighbors' variables during the consensus step. We perform numerical simulations to demonstrate the different consensus schemes proposed in the paper can outperform the traditional linear scheme.
BibTeX
@misc{kao2023nonlinear,
  author = {Hsu Kao and Vijay Subramanian},
  title = {{Nonlinear Consensus for Distributed Optimization}},
  year = {2023},
  eprint = {2303.06792},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.06792},
}
Figure