Distributed Optimization via Aggregate Strong Convexity

22 concepts14 papers1 proposal

In distributed machine learning and multi-agent systems, a network of independent nodes collaborates to minimize a global objective function:

$$F(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$$

Here, each $f_i(x)$ represents the private, local cost function of agent $i$, based on its own local data.

For years, textbook convergence proofs for decentralized optimization relied on a strict assumption: every individual local function $f_i$ must be strongly convex. Strong convexity guarantees that a function has a minimum bound on its curvature, preventing it from becoming completely flat and ensuring that gradient descent can converge at a fast, linear rate.

However, this requirement rarely holds in the real world. If a single agent has an ill-conditioned dataset, too few samples, or irregular local features, its local objective $f_i$ might be weakly convex, flat, or even non-convex. Under classical theory, this weak local link would break the entire network's convergence guarantees.

A powerful realization has shifted this paradigm: the network does not need local perfection; it only needs global cooperation. As long as the aggregate global objective $F(x)$ is strongly convex, the system can still achieve fast, linear convergence. This concept is known as aggregate strong convexity (or sum convexity).


The Intuition: Curvature is Additive

To understand why aggregate strong convexity works, it helps to look at the optimization landscape through the lens of its derivatives.

For a function to be strongly convex with a parameter $\mu > 0$, its Hessian (the matrix of second derivatives) must satisfy $\nabla^2 f_i(x) \succeq \mu I$. This means the function always curves upward like a bowl.

If an individual agent's function is only weakly convex, its Hessian might have zero curvature in certain directions ($\nabla^2 f_i(x) \succeq 0$). If it is non-convex, the curvature could even be negative.

However, differentiation is a linear operator. The Hessian of the global objective is simply the average of the local Hessians:

$$\nabla^2 F(x) = \frac{1}{n} \sum_{i=1}^n \nabla^2 f_i(x)$$

If one agent's function is flat in a certain direction, but another agent's function is highly curved in that same direction, the sum of their Hessians will still be positive definite.

Local Function 1 (Flat/Weak)   +   Local Function 2 (Highly Curved)  =   Aggregate Function (Strongly Convex)
        \_______/                                 \ /                                    \_/

As long as the agents' deficiencies do not perfectly overlap, the collective network "pools" its curvature. This insight allows decentralized systems to solve complex problems efficiently by focusing on the aggregate mathematical structure rather than forcing every local component to meet strict requirements.


How Algorithms Share Curvature

If the global function is well-behaved but individual nodes only see their own poorly-behaved local functions, how do they actually exploit this aggregate curvature? The secret lies in how modern decentralized algorithms communicate.

In standard decentralized gradient descent, agents perform a local gradient step and then average their parameters with their neighbors. If local functions lack strong convexity, this naive approach causes agents to get stuck or drift apart. To fix this, advanced algorithms use mechanisms like gradient tracking or historical memory.

For instance, the EXTRA algorithm proposed by Shi et al. utilizes gradient information from the last two iterations rather than just the most recent one. By doing so, the algorithm implicitly tracks the difference between local gradients and the global average gradient. Shi et al. demonstrated that this allows the network to achieve exact linear convergence to the true global minimizer under a relaxed condition called aggregate restricted strong convexity, even when individual functions are completely non-convex.

Similarly, Ye et al. combined Nesterov’s acceleration with gradient tracking to create Decentralized Accelerated Proximal Gradient Descent (DAPG). They proved that by leveraging aggregate strong convexity, the network can coordinate agents with non-convex or poorly distributed local data while maintaining optimal computational complexity. The well-conditioned nodes effectively "pull" the ill-conditioned nodes along the correct path.


Blended Dynamics and Borrowed Curvature

This phenomenon can also be understood through physical and continuous-time analogies.

Blended Dynamics

Lee modeled distributed optimization as a system of "blended dynamics" using continuous-time proportional-integral (PI) couplings. Imagine each agent as a particle moving along its local energy landscape ($f_i$), but connected to its neighbors by physical springs. Even if some particles are on flat or indefinite terrain, the collective network forces act as a single blended entity governed by the sum of the landscapes. If the sum is convex, the entire interconnected system is drawn reliably to the global minimum.

Borrowed Curvature

This principle extends beyond distributed networks to centralized, large-scale problems. When optimizing portfolios containing thousands of assets, individual tax liabilities introduce non-convexities. However, Kochenderfer et al. demonstrated a "borrowed curvature" technique: when an objective function is composed of the sum of many independent terms, the aggregate function tends toward convexity as the number of terms increases. The dominant convex parts of the objective smooth out the local, non-convex wrinkles.


Broadening the Horizon: Sampling and Minimax

Relaxing the strong convexity requirement from the individual level to the aggregate level has unlocked solutions to several open problems in distributed learning.

  • Client Sampling: In large-scale federated learning, it is impractical to communicate with every node at every step. Instead, algorithms sample a random subset of nodes. Lin et al. showed that effective client sampling does not require every local node to possess a strongly convex objective. As long as the aggregate average across the entire network remains strongly convex, partial participation still guarantees convergence.
  • Minimax Optimization: Modern applications like Generative Adversarial Networks (GANs) rely on saddle-point (minimax) optimization rather than pure minimization. Chen et al. proved that global convergence in decentralized minimax problems can be achieved even when individual local functions fail to satisfy strict convexity or concavity, provided the aggregate global objective does.

By shifting the theoretical burden from the individual agent to the collective whole, aggregate strong convexity provides a more realistic and robust foundation for modern distributed optimization.

Key Foundational Work

A proximal gradient algorithm for decentralized nondifferentiable optimization (2015) — contributed 3 concept elements to this direction.
A Proximal Gradient Algorithm for Decentralized Composite Optimization. (2015) — contributed 2 concept elements to this direction.
Multi-agent constrained optimization of a strongly convex function over time-varying directed networks (2017) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_aggregate_strong_convexity_083148dc,
  title = {aggregate strong convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/aggregate-strong-convexity/rdr_083148dcbc9f4e858df955d12ea2cbe2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_aggregate_strong_convexity_083148dc_v1,
  title = {aggregate strong convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/aggregate-strong-convexity/rdr_083148dcbc9f4e858df955d12ea2cbe2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake