An Accelerated Primal Dual Algorithm with Backtracking for Decentralized Constrained Optimization

This paper proposes D-APDB, a distributed accelerated primal-dual algorithm with backtracking that achieves optimal $\mathcal{O}(1/K)$ convergence for decentralized constrained optimization over undirected networks without requiring prior knowledge of Lipschitz constants, making it the first method of its kind to handle private nonlinear constraints efficiently.

The Gist

Imagine a group of friends trying to plan the perfect group vacation. Everyone has their own preferences (some want the beach, others want mountains), their own budget limits, and they can't all meet in one big room to discuss everything at once. They are scattered across a city, connected only by walkie-talkies (the network).

This paper presents a new, super-smart way for these friends to solve their problem together without a boss telling them what to do. Here is the breakdown of their new strategy, D-APDB, explained in everyday terms.

The Problem: The "Too Many Rules" Puzzle

In the old days, if these friends wanted to solve this problem, they needed a "Rulebook" that told them exactly how big a step to take when making a decision.

• The Catch: To write this Rulebook, they needed to know the "smoothness" of everyone's preferences in advance. It's like needing to know exactly how slippery the ice is before you start walking.
• The Reality: In the real world, no one knows exactly how "slippery" (complex) their neighbors' data is. If they guess wrong, they might take steps that are too big (and fall) or too small (and never get anywhere).
• The Constraint: Some friends have private rules (like "I can't spend more than $500") that are hard to calculate. In the past, solving these required expensive, slow calculations that slowed down the whole group.

The Solution: The "Backtracking Hiker"

The authors propose a new method called D-APDB. Think of it as a group of hikers trying to find the lowest point in a foggy valley (the best solution) without a map.

1. The "Try and See" Strategy (Backtracking)
Instead of guessing the step size, the hikers use a technique called Backtracking.

• The Analogy: Imagine you are walking in the dark. You take a step forward. If you feel like you're slipping or hitting a wall, you immediately step back and try a smaller step. If the ground feels solid and you're moving toward the valley, you might even take a bigger step next time.
• In the Paper: Every agent (friend) tests a step size locally. If the math says, "Whoa, that was too big," they shrink the step size instantly. If it works, they keep going. They don't need to know the "slipperiness" of the terrain beforehand; they just feel it as they go.

2. The "Whisper Network" (Decentralized)
There is no central leader.

• The Analogy: Everyone only talks to their immediate neighbors. If Alice wants to know the group's average opinion, she asks Bob, who asks Charlie, and so on.
• The Innovation: The paper acknowledges that sometimes, for a quick "check-in" (like finding the maximum value in the group), the network can use a special "long-range whisper" (like LoRaWAN technology) that lets a message hop one extra time to reach everyone quickly, without needing a central server.

3. The "Momentum" Boost
The algorithm uses Momentum.

• The Analogy: Imagine a bowling ball rolling down a lane. Even if the lane gets a little bumpy, the ball's momentum keeps it moving forward smoothly.
• In the Paper: The algorithm remembers where it was a moment ago. This helps it smooth out the "wobbles" that happen when everyone is trying to agree, preventing them from oscillating back and forth forever.

Why This is a Big Deal

• No Crystal Ball Needed: You don't need to know the complex math constants (Lipschitz constants) of your neighbors' problems beforehand. The algorithm figures it out on the fly.
• Handles Hard Rules: It can deal with "private constraints" (like the $500 budget) that are mathematically difficult to solve, without slowing everyone down.
• Fast and Efficient: It proves mathematically that this group will reach the best solution at the fastest possible speed (the "optimal rate") for this type of problem.

The Real-World Test

The authors tested this on two scenarios:

1. The QCQP Problem: Like a group trying to design a shape that fits inside several different oval holes while minimizing material cost.
2. The SVM Problem: Like a group of doctors trying to train a machine to diagnose a disease using patient data split among them, without sharing the private patient records.

The Result: In both cases, their new "Backtracking Hiker" method found the solution faster and more reliably than the old methods that relied on guessing the step size or required a central boss.

Summary

D-APDB is a new way for a team of independent computers to solve a complex puzzle together. Instead of needing a pre-written manual on how fast to move, they use a "feel-it-as-you-go" approach (backtracking) to adjust their speed instantly. They use momentum to stay smooth and only talk to their neighbors, making them perfect for modern, decentralized networks like smart grids or sensor networks where no single computer knows everything.

Technical Summary

Here is a detailed technical summary of the paper "An Accelerated Primal Dual Algorithm with Backtracking for Decentralized Constrained Optimization."

1. Problem Statement

The paper addresses decentralized constrained optimization over an undirected network of $N$ agents. The goal is to collaboratively minimize a global objective function composed of agent-specific terms, subject to local constraints, without a central coordinator.

The specific problem formulation is:
$$\min_{x \in \mathbb{R}^n} \sum_{i \in \mathcal{N}} \phi_i(x) \quad \text{s.t.} \quad -g_i(x) \in \mathcal{K}_i, \quad \forall i \in \mathcal{N}$$
where:

• $\phi_i(x) = f_i(x) + \varphi_i(x)$: The local objective is a composite function consisting of a smooth convex function $f_i$ and a possibly non-smooth convex function $\varphi_i$ (e.g., an indicator function for set constraints or an $\ell_1$-norm regularizer).
• $-g_i(x) \in \mathcal{K}_i$: Agent $i$ has private functional constraints defined by a smooth $\mathcal{K}_i$-convex function $g_i$ and a closed convex cone $\mathcal{K}_i$.
• Communication Model: Agents can exchange high-volume data vectors (e.g., gradients) only with immediate neighbors via high-speed links (e.g., WiFi). Additionally, the network supports one-hop, low-rate information exchange beyond immediate neighbors (e.g., LoRaWAN) to facilitate global consensus on scalar values.

Key Challenge: Existing decentralized primal-dual methods typically require prior knowledge of global Lipschitz constants (for gradients of $f_i$ and Jacobians of $g_i$) to set step sizes. These constants are often unknown, difficult to estimate, or vary significantly across agents. Using conservative, globally synchronized step sizes based on worst-case estimates leads to slow convergence.

2. Methodology: D-APDB and D-APDB0

The authors propose D-APDB (Distributed Accelerated Primal-Dual with Backtracking) and a variant D-APDB0 (for unconstrained or simple set-constrained problems).

Core Mechanism: Distributed Backtracking

Unlike standard methods that use fixed step sizes, D-APDB employs a distributed backtracking line search to adaptively determine step sizes based on local smoothness.

• Local Search: Each agent $i$ performs a local backtracking loop to find a candidate primal step size $\tilde{\tau}_i^k$. It tests a candidate step against a local merit function $E_i^k(\cdot, \cdot)$ derived from the primal-dual gap and curvature information.
• Global Consensus: To synchronize the momentum parameter $\eta_k$, agents perform a max-consensus operation across the network. This ensures that if any agent reduces its step size (due to backtracking), the global momentum parameter is adjusted accordingly to maintain stability.
• Communication Efficiency:
  • High-bandwidth: Agents exchange $n$-dimensional vectors (primal/dual variables) with immediate neighbors once per iteration.
  • Low-bandwidth: Agents perform a single max-consensus operation per iteration (e.g., using LoRaWAN protocols) to coordinate the global step size scaling factor $\eta_k$.

Algorithmic Structure

The algorithm is an accelerated primal-dual method based on the Chambolle-Pock framework but modified for decentralization and backtracking:

1. Dual Update (Consensus): Updates the dual variable associated with the consensus constraint ($Ax=0$) using a momentum term.
2. Primal Update: Performs a proximal gradient step using the local gradient, the consensus dual variable, and the local constraint dual variable.
3. Dual Update (Constraints): Projects the dual variable associated with local constraints $g_i(x)$ onto the dual cone $\mathcal{K}_i^*$.
4. Backtracking Loop: If the trial point does not satisfy the descent condition (based on the merit function), the step size is shrunk by a factor $\rho \in (0,1)$ and the trial is repeated.

3. Key Contributions

1. First Parameter-Free Method for General Constrained Problems: To the authors' knowledge, D-APDB is the first distributed method that achieves optimal convergence rates for composite convex optimization with nonlinear functional constraints without requiring prior knowledge of Lipschitz constants.
2. Adaptive Step Sizes: The method automatically adapts to local smoothness via distributed backtracking, eliminating the need for global grid searches or conservative step size tuning.
3. Optimal Convergence Rates: The authors establish an $O(1/K)$ convergence rate for:
   • Sub-optimality (objective value gap).
   • Infeasibility (constraint violation).
   • Consensus violation (disagreement among agents).
   • This rate matches the best-known rates for parameter-dependent methods.
4. Handling Non-Smoothness and Constraints: The method handles non-smooth terms ($\varphi_i$) and general conic constraints ($g_i(x) \in \mathcal{K}_i$), including cases where projections onto the constraint set are expensive (handled via dual ascent rather than primal projection).
5. Variant D-APDB0: A specialized version for problems without complex functional constraints (or with cheap projections), which also achieves $O(1/K)$ rates without Lipschitz knowledge.

4. Theoretical Results

• Convergence Guarantees: Under standard assumptions (smoothness of $f_i$ and $g_i$, convexity, and network connectivity), the ergodic iterate sequence converges to the optimal solution with an $O(1/K)$ rate.
• Boundedness: The authors prove that the dual iterates remain bounded, which is crucial for the convergence analysis when dealing with nonlinear constraints.
• Complexity: The total number of gradient and projection evaluations required to reach an $\epsilon$-optimal solution is bounded by $O(\frac{1}{\epsilon})$, with a logarithmic factor related to the initial step size and the contraction factor of the backtracking.
• Assumptions: The method relies on the existence of a Slater point (for constraint qualification) and assumes agents know bounds on the optimal dual variables for nonlinear constraints (which can be computed via a preliminary Phase I procedure).

5. Numerical Results

The authors validate the algorithm on three distributed problems:

1. Distributed QCQP with $\ell_1$-regularization: D-APDB significantly outperforms a fixed-step baseline (D-APD) in terms of sub-optimality, consensus error, and constraint violation. The backtracking allows D-APDB to take larger steps initially, accelerating early convergence.
2. Distributed Unconstrained QP ($\ell_1$-regularized): D-APDB0 is compared against D-APD and a global adaptive method (global DATOS). D-APDB0 achieves faster convergence and lower error, demonstrating the benefit of node-specific step sizes over global ones.
3. Distributed Primal SVM Training: In a classification task, D-APDB converges faster and achieves lower constraint violation compared to the fixed-step D-APD, even when the Lipschitz constants are unknown.

6. Significance

This work bridges a critical gap in decentralized optimization. While parameter-free methods exist for unconstrained or simple constrained problems, handling nonlinear functional constraints in a fully decentralized, parameter-free manner was an open challenge.

• Practical Impact: The algorithm is highly suitable for real-world applications like smart grids, sensor networks, and multi-robot systems where network topology and local data characteristics (smoothness) vary, and global parameters are unknown.
• Robustness: By removing the dependency on global Lipschitz constants, the method is more robust to heterogeneous agent environments and reduces the engineering overhead of tuning step sizes.
• Communication Efficiency: The design respects the constraints of modern wireless networks (high-speed local links + low-speed global consensus), making it deployable in resource-constrained IoT environments.