Mert Gürbüzbalaban

Backtracking across a network


For a first-order method running on one machine, a line search chooses the stepsize without knowing the Lipschitz constants in advance. Carrying the idea over to decentralized optimization is harder. Each agent sees only its own loss and constraint, yet the agents must coordinate their stepsizes: the accelerated iteration needs one momentum parameter for the whole network, so a stepsize one agent rejects changes the step every other agent takes. This page illustrates D-APDB, the decentralized accelerated primal–dual method with backtracking of Xu, Aybat and Gürbüzbalaban (J. Nonlinear Var. Anal., 2026; arXiv:2512.07085), on a small constrained consensus problem in the plane, and compares it with the same iteration run with the stepsizes the theory prescribes from the constants (D-APD) and with D-APDB’s initial stepsize kept fixed without any test. The experiments show how distributed backtracking works, why the test is needed, and when the stepsizes it accepts do and do not turn into faster convergence than the prescribed ones.

Press Play to watch the three runs evolve. Panel A shows the agents’ iterates approaching a common solution, next to three measures of convergence: the relative suboptimality, the consensus error and the constraint violation. Panel B shows how backtracking adjusts the agents’ stepsizes: it compares the stepsizes D-APDB accepts with the conservative values the analysis certifies from the Lipschitz constants and dual bounds, and it counts the additional candidate updates the backtracking costs. The six experiments under What to try highlight different aspects of the method; precise definitions of the plotted quantities and of the algorithms are under What is being computed.

12 agents on a small-world network with 24 edges, each with its own quadratic loss and its own ellipse constraint, projecting onto the box [−10, 10]²

agents Ninstance 7
curvature spread
constraints
box ±R
D-APDB start τ̄
shrink ρ
methods
A The run: agents in the plane, and the three diagnostics of the paper’s experiments
agents of
x*x₁x₂box ±10: outside the view
k = 0 of 3,000
1e211e-21e-41e-61e-81101001,000iterations k (log)1/krelative suboptimality |φ(x̄ₖ) − φ*| / |φ*|1e211e-21e-41e-61e-81101001,000iterations k (log)1/kconsensus error Σᵢ‖xᵢ − x̄ₖ‖² / (N‖x̄ₖ‖²)1e211e-21e-41e-61e-81101001,000iterations k (log)1/kconstraint violation maxᵢ (gᵢ(x̄ₖ))₊

last iterates against k; the dotted line of slope −1 is a reference slope (the O(1/K) rate the paper proves for weighted averages), not a bound on these curves; values below 10⁻⁸ are drawn at 10⁻⁸ and a gap in a curve is a value of exactly zero

Left: the agents’ ellipses, whose intersection is the feasible region (shaded), level sets of the total loss Σᵢ fᵢ around its unconstrained minimizer (the small hollow dot), each agent’s own minimizer (+), and the agents’ iterates xᵢᵏ (dots, with their trails) linked by the edges of the network; the larger ring is the network average x̄ᵏ and × the solution. Right: the three last-iterate diagnostics of the paper’s experiments, evaluated at x̄ᵏ, for every method shown. Switch the agents drawn to no test to see what the optimistic start does without the backtracking test.

B The stepsizes: what the line search settles on, against the safe values
0.020.050.10.20.51101001,000stepsize τᵢᵏ of each agent (log); dashed: the safe τ̂ᵢiterations k (log)135791101001,000candidate updates per agent at iteration k (D-APDB)iterations k (log)

Left: the stepsize of each of the 12 agents under D-APDB, which can only decrease, and does so exactly when some agent’s test fails (the triangles); all agents shrink by the same factor, so they keep their initial proportions. The dashed lines are the safe stepsizes τ̂ᵢ that D-APD uses throughout: an agent’s own test is guaranteed to pass at or below its τ̂ᵢ, but a cut forced by another agent can take it lower; the guaranteed floor is τ̄ᵢ · min(1, ρ · minⱼ τ̂ⱼ/τ̄ⱼ) (see What is being computed). Right: candidate updates per agent at each iteration, on average: all local trials, plus one recomputation per agent whenever the synchronized factor ηᵏ exceeds one (every agent recomputes then, including the one whose cut set ηᵏ); one means the first trial passed and nobody backtracked. A triangle marks an iteration at which some agent rejected trials, however many.

Methodτᵢ at the endbacktracking (D-APDB)suboptimalityconsensusviolation
D-APDB (backtracking)0.21 from 1.01× at k = 0; 3,008 candidate updates per agent7.8e-43.4e-86.8e-4
D-APD, safe steps τ̂ᵢ3.9e-2 – 6.4e-2—6.9e-54.6e-80
Fixed τ̄, no test1.0—11110

All rows run the same primal–dual iteration (defined under What is being computed) for 3,000 iterations from the same starting points; they differ only in how the stepsizes are chosen. The safe stepsizes τ̂ᵢ of D-APD are 3.9e-2 – 6.4e-2 here, computed from each agent’s smoothness constant, the Lipschitz constant and the bound Cgᵢ of its constraint’s gradient over the box, and the dual bound Bᵢ = 13 – 14 from the Slater point. The last three columns are the diagnostics at the final iteration, for the network average x̄. A “candidate update” is one primal–dual step computed, accepted or not, including the recomputation every agent performs after a max-consensus with ηᵏ > 1; the candidates beyond the 3,000 iterations are the extra work of the line search, on top of evaluating the tests and the max-consensus itself.

The key idea is that each agent can decide locally whether a trial stepsize satisfies the required condition; the agents then share one scalar, the largest of their stepsize reduction factors, to keep their updates synchronized. The coordination costs one network-wide max-consensus at every iteration, and a number of rejected trials that is bounded over the whole run (by a logarithm of the ratio between the initial and the safe stepsize), not a fixed number per iteration. In return D-APDB keeps the paper’s O(1/K) guarantees without prior knowledge of the Lipschitz constants; for nonlinear constraints it still needs a large enough bound on the optimal multipliers to define the dual projection set, but that bound does not enter the choice of stepsizes.

What to try

The page opens with instance 7, twelve agents, ellipse constraints, curvature spread ×10, the box [−10,10]2[-10, 10]^2, ρ=0.9\rho = 0.9, and D-APDB started from τˉ=1\bar\tau = 1 for every agent, with no constants. Three terms recur. The safe stepsize τ^i\hat\tau_i is the value the analysis certifies for agent ii from the constants; D-APD runs with it, and it is the dashed line of panel B. A candidate update is one primal–dual step computed by an agent, whether accepted or rejected. A cut is an iteration at which the shared shrink factor exceeds one, so that every agent’s stepsize is reduced; the triangles of panel B mark them. Six experiments; press reset before each one, since each starts from that opening configuration and changes only what it says, and the numbers quoted are for it.

  1. Watch the test fire once. Press Play. In panel A the agents first head for their own minimizers (+), then the network’s edges shorten as the consensus multipliers build up, and the cloud converges to x⋆x^\star on the boundary of the feasible region. In panel B a single triangle at k=0k = 0 marks the only iteration at which any agent rejected trials: the common stepsize drops from 1 to about 0.2, three to five times the dashed safe values, and is never cut again; the table counts about eight candidate updates per agent beyond the 3,000 accepted ones, all of them at iteration 0 (seven rejected trials per agent on average, fifteen for the agent that set η0\eta^0, plus the recomputation); the tests and the max-consensus are still evaluated at every iteration. The failure is in the constraint terms of the test, not the curvature term: for the agents whose trial point lies outside their own ellipse, the primal–dual product τ~σ~ ∥∇gi(x~)∥2\tilde\tau\tilde\sigma\,\|\nabla g_i(\tilde x)\|^2 at τ~=1\tilde\tau = 1 is far above cα(1−δ)/2c_\alpha(1-\delta)/2, the local form of the condition behind τi′′\tau_i'', while the curvature term alone would have accepted a stepsize of 1.
  2. Why the test is needed. Switch the agents drawn to no test. At first the fixed stepsize looks healthy. As the active constraint’s multiplier approaches its optimal value, the primal–dual updates turn out to be unstable at this stepsize: from about iteration 800 the consensus error starts to grow, at iteration 900 the agents fly apart to the walls of the box and the multiplier jumps to its bound, and the consensus error ends four orders of magnitude above where it had been and never recovers. D-APDB had found the same initial stepsize too large at iteration 0, from local quantities alone, and reduced it before proceeding. A failed test does not prove that a fixed stepsize must become unstable: the condition is sufficient for convergence, not necessary, and a stepsize between 0.2 and 1 may well converge without a test. What the instance shows is that the rejected value does fail, and that the test saw it eight hundred iterations before the first symptom.
  3. The cost of conservative stepsizes. Step the box through 5, 10, 20. The dashed lines in panel B fall (their medians are about 0.06, 0.05, 0.025: at the small box the dual radius binds, at the larger ones CgiC_{g_i}, a bound over the whole box, does), and D-APD’s curves slow down accordingly; D-APDB’s accepted stepsize and curves do not move on this instance, because its test only sees the points the agents visit and the box is never touched. (The box can matter to D-APDB when the projection onto it becomes active, and the start 20 τ^i20\,\hat\tau_i moves with it.) The paper’s twenty-dimensional experiments are the extreme of this effect.
  4. Early and late, and the role of the consensus stepsize γ\gamma. With the opening controls D-APDB makes faster progress than D-APD at first, and D-APD overtakes it later. Across instances 1–30, D-APDB has the lower relative suboptimality in 29 instances at iteration 100, in 26 at 200, in 15 at 300, and in only 4 at 3,000. To understand this, vary the initial stepsize. Starting from 0.3 gives a far better end of run (relative suboptimality 5×10−75 \times 10^{-7} at 3,000, against D-APD’s 7×10−57 \times 10^{-5} and 8×10−48 \times 10^{-4} for the start 1; the lower of the two in 22 of those 30 instances), whereas starting from 3 or 10 stalls (0.11 and 0.22). Yet backtracking lands on nearly the same primal stepsize in all four cases, about 0.2 (0.197, 0.206, 0.215, 0.225: the accepted values lie on the geometric grid τˉρm\bar\tau\rho^m of each start, so they are close but not equal). The difference is the consensus stepsize γk\gamma^k. After the cut it equals cγ/(τˉ(2/cα+1/cς))c_\gamma/(\bar\tau(2/c_\alpha + 1/c_\varsigma)), inversely proportional to the start (factors 1/0.3, 1, 1/3, 1/10 relative to the start 1): the scale cγ/τˉc_\gamma/\bar\tau of γk\gamma^k is fixed from the initial guess and only the factor involving ηk\eta^k changes, so two runs with nearly identical primal stepsizes can have consensus stepsizes thirty times apart. Backtracking corrects an optimistic guess in the primal step, but the guess is remembered in the consensus step, and on these instances the end-of-run ranking follows the consensus stepsize.
  5. What the synchronization costs. Set constraints: none, the start to 10 and the spread to ×100. Now the tests fail at several scattered iterations (the triangles), each time because some agent’s step turns into its stiff direction, and every failure cuts every agent. Compare the start 20 τ^i20\,\hat\tau_i, under which the agents’ stepsizes are cut once and stay in proportion to their own curvatures, with the common start, under which every agent ends at the same value, 0.65 here, below the safe stepsizes of nine of the twelve agents (the floor above only guarantees that it cannot fall below ρmin⁡jτ^j=0.32\rho \min_j \hat\tau_j = 0.32). The single shared ηk\eta^k is what keeps the paper’s analysis intact; its price is that the most conservative agent sets the pace for all.
  6. The shrink factor, and new instances. Set ρ\rho to 0.5: at the first iteration the agents reject about one trial each on average (three for the agent that sets the maximum) instead of about seven (fifteen), but the stepsize lands at 0.125 instead of 0.206, since a coarse search overshoots by up to the factor ρ\rho. Then put ρ\rho back to 0.9 (or press reset) and step through instances with next and previous: in instances 1–30 with the opening controls the cutting happens in a single iteration every time and D-APDB has the lower relative suboptimality at iteration 100 in 29 of the 30, while the ratio of the final stepsize to the safe ones (approximately 1.2 to 5.3 across those runs, and with ρ=0.5\rho = 0.5 on instance 11 between 0.84 and 1.66) and the end-of-run comparison vary with the instance and, as experiment 4 shows, with the start.

What is being computed

Notation. The local vectors (xix_i, aia_i, xˉi\bar x_i, sis_i, rir_i) are in R2\mathbb R^2; the stacked primal vector is in R2N\mathbb R^{2N} and the edge multipliers in R2∣E∣\mathbb R^{2|\mathcal E|}. ∥⋅∥\|\cdot\| is the Euclidean norm of a vector and the spectral norm of a matrix, (u)+=max⁡{u,0}(u)_+ = \max\{u, 0\}, and Ni\mathcal N_i is the set of neighbors of agent ii in the graph. The constants δ,cα,cβ,cς\delta, c_\alpha, c_\beta, c_\varsigma are the test parameters of the paper and c=cα+cβ+cςc = c_\alpha + c_\beta + c_\varsigma throughout; the center of the instance is written xcx_c to keep cc for that sum.

The problem. NN agents sit on a connected undirected graph G=(N,E)\mathcal G = (\mathcal N, \mathcal E), a random cycle through all NN agents with NN further random edges, so ∣E∣=2N|\mathcal E| = 2N, as in the paper’s experiments. Agent ii privately holds a smooth convex loss, a simple set, and one constraint:

fi(x)=12(x−ai)⊤Qi (x−ai),ϕi=indicator of the box [−R,R]2,gi(x)=12(x−xˉi)⊤Ai (x−xˉi)−1  ≤  0,\begin{gathered} f_i(x) = \tfrac12 (x - a_i)^\top Q_i\,(x - a_i), \\ \phi_i = \text{indicator of the box } [-R, R]^2, \\ g_i(x) = \tfrac12 (x - \bar x_i)^\top A_i\,(x - \bar x_i) - 1 \;\le\; 0, \end{gathered}

with Qi,Ai≻0Q_i, A_i \succ 0, so ∇fi(x)=Qi(x−ai)\nabla f_i(x) = Q_i(x - a_i) and ∇gi(x)=Ai(x−xˉi)\nabla g_i(x) = A_i(x - \bar x_i). Writing φi=ϕi+fi\varphi_i = \phi_i + f_i for the local composite objective, the network has to solve

φ⋆=min⁡x∈R2 ∑i∈Nφi(x)s.t.gi(x)≤0  for every i∈N,\begin{gathered} \varphi^\star = \min_{x \in \mathbb R^2}\ \sum_{i \in \mathcal N} \varphi_i(x) \\ \text{s.t.}\quad g_i(x) \le 0 \ \text{ for every } i \in \mathcal N, \end{gathered}

every agent ending with the same solution x⋆x^\star, although no agent sees another agent’s loss or constraint. The feasible set is [−R,R]2∩⋂i{x:gi(x)≤0}[-R, R]^2 \cap \bigcap_i \{x : g_i(x) \le 0\}: the box, intersected with the NN filled ellipses (boundaries included). In the plane the data can be drawn: aia_i is the minimizer of agent ii’s own loss (the ++ marks), and the shaded region is the intersection of the ellipses. The losses are biased toward a common direction so that the constraints tend to bind: in the opening instance and in instances 1–30 (the instance number is shown next to the controls) the optimizer lies on the boundary of the feasible region, with one ellipse constraint active (gi(x⋆)>−10−6g_i(x^\star) > -10^{-6}) in 26 of those 30 instances and two in 4; the generator’s parameter ranges do not force this for every instance. With constraints: none the ellipses are dropped and the problem is the composite consensus problem of the paper’s Algorithm 2. The reference solution x⋆x^\star, its value φ⋆\varphi^\star and the multipliers θi⋆\theta_i^\star are computed by a log-barrier interior-point method on the centralized problem, then polished by Newton’s method on the stationarity equation and the equations of the constraints selected as active at the barrier point (the ellipses with gi>−10−6g_i > -10^{-6} there and the box faces within 10−610^{-6} of it), in the unknowns (x,θ,μ)(x, \theta, \mu) with μ\mu the multipliers of the selected faces. The multipliers of the solved system are clipped at zero, and the polished point is accepted on the strength of its complete KKT residual, the largest of ∥∇F(x)+∑iθi∇gi(x)+∑jμjnj∥∞\|\nabla F(x) + \sum_i \theta_i \nabla g_i(x) + \sum_j \mu_j n_j\|_\infty (with F=∑ifiF = \sum_i f_i and njn_j the outward normal of box face jj), the positive parts of all NN ellipse values and of the four box inequalities ±xj−R\pm x_j - R, the negative parts of all multipliers, and all complementarity products ∣θigi(x)∣|\theta_i g_i(x)| and ∣μj(±xj−R)∣|\mu_j(\pm x_j - R)|: it is accepted when that residual is below 10−1210^{-12}, and the barrier point would be kept otherwise. All 5,400 problems tried (instances 0–99 at every combination of the agents, spread, box and constraints chips) accepted the polished point, with complete residuals below 1.6×10−151.6 \times 10^{-15}. The reference multipliers are not used by the distributed runs.

Instance generator. Qi=Lfi Ri diag(1,ωi) Ri⊤Q_i = L_{f_i}\, R_i\,\mathrm{diag}(1, \omega_i)\, R_i^\top with a uniformly random rotation RiR_i, ωi\omega_i uniform in [0.1,0.5][0.1, 0.5], and Lfi=0.1 s ui−1/2L_{f_i} = 0.1\, s^{\,u_i - 1/2}, uiu_i uniform in [0,1][0,1], where ss is the curvature spread: the agents’ smoothness constants range over a factor ss around 0.10.1. The minimizers ai=xc+ri(cos⁡ψi,sin⁡ψi)a_i = x_c + r_i(\cos\psi_i, \sin\psi_i) with xc=(0.5,0.5)x_c = (0.5, 0.5), rir_i uniform in [3.2,4.0][3.2, 4.0] and ψi\psi_i within ±0.6\pm 0.6 rad of a direction common to the instance. AiA_i has a uniformly random orientation and eigenvalues uniform in [0.12,0.4][0.12, 0.4] (semi-axes between 2.2 and 4.1); its center xˉi\bar x_i is within ±0.5\pm 0.5 of xcx_c in each coordinate. The Slater point used below is the centroid of the ellipses’ centers, xs=1N∑ixˉix_s = \tfrac1N \sum_i \bar x_i, which lies strictly inside every ellipse by construction. Starting points xi0x_i^0 are uniform in [−4,4]2[-4, 4]^2, independently for each agent. The instance number seeds the generator: next and previous step through instances, and reset restores the opening configuration (instance 7).

The iteration. Agent ii keeps a copy xix_i of the decision variable, a multiplier θi≥0\theta_i \ge 0 for its own constraint, a vector sis_i that encodes the multipliers of the consensus constraints xi=xjx_i = x_j, (i,j)∈E(i, j) \in \mathcal E, and its stepsize τi\tau_i. At each iteration it receives sjks_j^k from its neighbors j∈Nij \in \mathcal N_i and forms, locally,

rik=∇gi(xik) θik+∑j∈Ni(sik−sjk),r_i^k = \nabla g_i(x_i^k)\,\theta_i^k + \sum_{j \in \mathcal N_i} (s_i^k - s_j^k),

the pull of its constraint and of its neighbors on xix_i (the paper shows that the consensus multipliers themselves, λ=As\lambda = A\mathbf s with A=H⊗I2A = H \otimes I_2 and HH an oriented edge–node incidence matrix of the graph, never need to be formed; AA is not to be confused with the ellipse matrices AiA_i). Given a trial stepsize τ~\tilde\tau and a momentum factor η\eta, the step is

p~=rik+η (rik−rik−1),x~=proxτ~ϕi ⁣(xik−τ~ (∇fi(xik)+p~)),θ~=Π[0,Bi] ⁣(θik+ζτ~ gi(x~)),\begin{gathered} \tilde p = r_i^k + \eta\,(r_i^k - r_i^{k-1}), \\ \tilde x = \mathrm{prox}_{\tilde\tau \phi_i}\!\big(x_i^k - \tilde\tau\,(\nabla f_i(x_i^k) + \tilde p)\big), \\ \tilde\theta = \Pi_{[0, B_i]}\!\big(\theta_i^k + \zeta\tilde\tau\, g_i(\tilde x)\big), \end{gathered}

where the prox of the box indicator is the coordinatewise projection onto [−R,R]2[-R, R]^2, the dual stepsize is σ=ζτ\sigma = \zeta\tau with a fixed ζ>0\zeta > 0, and BiB_i is the radius of the dual projection, which the paper’s bounded-dual-domain assumption requires to satisfy Bi≥2 θi⋆B_i \ge 2\,\theta_i^\star for a non-affine gig_i (an affine constraint needs no such radius); the radius must also be positive, since a zero radius would pin θi\theta_i at zero, and the radii used here are (see below). This is the step of the accelerated primal–dual method of Hamedani and Aybat, with the consensus multipliers updated before the primal step rather than after it; the paper makes this change so that every quantity in an agent’s test is final when the test is run. The initialization is

xi−1=xi0,θi−1=θi0=0,si0=0,ri−1=ri0=0,τi−1=τˉi,\begin{gathered} x_i^{-1} = x_i^0, \qquad \theta_i^{-1} = \theta_i^0 = 0, \qquad s_i^0 = 0, \\ r_i^{-1} = r_i^0 = 0, \qquad \tau_i^{-1} = \bar\tau_i, \end{gathered}

which makes the momentum and consensus updates at k=0k = 0 unambiguous. D-APDB and the two fixed-step methods below all take exactly this step and differ only in how τ~\tilde\tau and η\eta are chosen.

Definition: D-APDB (Algorithm 1 of the paper)

D-APDB (distributed accelerated primal–dual method with backtracking) takes initial stepsizes τˉi>0\bar\tau_i > 0, a shrink factor ρ∈(0,1)\rho \in (0, 1), test parameters δ,cα,cβ,cς>0\delta, c_\alpha, c_\beta, c_\varsigma > 0 with δ+c<1\delta + c < 1, a dual ratio ζ>0\zeta > 0 and cγ∈(0,1/(2∣E∣)]c_\gamma \in (0, 1/(2|\mathcal E|)], and runs each iteration kk in two phases.

Local line search. Agent ii tries τ~=τik−1\tilde\tau = \tau_i^{k-1} with the local momentum ηi=τik−1/τ~\eta_i = \tau_i^{k-1}/\tilde\tau, computes the candidate (x~,θ~)(\tilde x, \tilde\theta) above, and accepts it if

Eik(x~,θ~)  ≤  −δτ~ ∥x~−xik∥2−δζτ~ ∥θ~−θik∥2,whereEik(x,θ)=2Λi(x)−1−cτ~ ∥x−xik∥2−1ζτ~ ∥θ−θik∥2+2τ~cα ∥∇gi(x) (θ−θik)∥2+τ~cβ ∥(∇gi(x)−∇gi(xik)) θik∥2,\begin{gathered} E_i^k(\tilde x, \tilde\theta) \;\le\; -\frac{\delta}{\tilde\tau}\,\|\tilde x - x_i^k\|^2 - \frac{\delta}{\zeta\tilde\tau}\,\|\tilde\theta - \theta_i^k\|^2, \\[2pt] \text{where}\quad E_i^k(x,\theta) = 2\Lambda_i(x) - \frac{1 - c}{\tilde\tau}\,\|x - x_i^k\|^2 \\ \qquad - \frac{1}{\zeta\tilde\tau}\,\|\theta - \theta_i^k\|^2 + \frac{2\tilde\tau}{c_\alpha}\,\big\|\nabla g_i(x)\,(\theta - \theta_i^k)\big\|^2 \\ \qquad + \frac{\tilde\tau}{c_\beta}\,\big\|\big(\nabla g_i(x) - \nabla g_i(x_i^k)\big)\,\theta_i^k\big\|^2, \end{gathered}

with Λi(x)=fi(x)−fi(xik)−⟨∇fi(xik),x−xik⟩\Lambda_i(x) = f_i(x) - f_i(x_i^k) - \langle \nabla f_i(x_i^k), x - x_i^k \rangle; otherwise it sets τ~←ρ τ~\tilde\tau \leftarrow \rho\,\tilde\tau and tries again. (The paper writes the coefficients of EikE_i^k through auxiliary sequences αik=cα/τik−1\alpha_i^k = c_\alpha/\tau_i^{k-1}, βik=cβ/τik−1\beta_i^k = c_\beta/\tau_i^{k-1}, ς~ik+1=cς/τ~\tilde\varsigma_i^{k+1} = c_\varsigma/\tilde\tau and so on; with those definitions and ηi=τik−1/τ~\eta_i = \tau_i^{k-1}/\tilde\tau the coefficients collapse to the ones shown.) The test is a single inequality on the sum, so slack in one term can offset another; read term by term, it is the paper’s sufficient condition for a safe stepsize with every global constant replaced by its local counterpart. The first two terms compare τ~\tilde\tau with (1−δ−c)/L(1 - \delta - c)/L, where LL is the curvature of fif_i along the step actually taken (for a quadratic, Λi(x)=12(x−xik)⊤Qi(x−xik)\Lambda_i(x) = \tfrac12 (x - x_i^k)^\top Q_i (x - x_i^k)); the fourth term involves the gradient of the constraint at the point reached rather than its maximum over the domain; and the last term involves the actual change of that gradient times the multiplier in hand rather than a Lipschitz constant times a dual bound. Nothing in the test is a global constant.

Synchronization. Each agent runs its test on its own, but the agents cannot simply keep the stepsizes their tests accepted: the accelerated iteration needs one momentum parameter for the whole network, so the reductions have to be coordinated. Each agent therefore reports the factor ηi\eta_i by which its test made it shrink, the network computes the largest of them, ηk=max⁡iηi\eta^k = \max_i \eta_i, by max-consensus, and every agent sets τik=τik−1/ηk\tau_i^k = \tau_i^{k-1}/\eta^k. The stepsizes therefore never increase, all shrink by the same factor, and the agents keep their initial proportions: τik=τˉi/qk\tau_i^k = \bar\tau_i / q_k with a common factor qk=∏l=0kηlq_k = \prod_{l=0}^{k} \eta^l. This is what gives the analysis its common momentum parameter; it also means that a reduction one agent needs is imposed on the entire network. The network then updates

γk=cγτˉ(2cα+ηkcς)−1,sik+1=sik+γk((1+ηk) xik−ηkxik−1),\begin{gathered} \gamma^k = \frac{c_\gamma}{\bar\tau}\Big(\frac{2}{c_\alpha} + \frac{\eta^k}{c_\varsigma}\Big)^{-1}, \\ s_i^{k+1} = s_i^k + \gamma^k\big((1 + \eta^k)\,x_i^k - \eta^k x_i^{k-1}\big), \end{gathered}

with τˉ=max⁡iτˉi\bar\tau = \max_i \bar\tau_i. If ηk>1\eta^k > 1, every agent recomputes (xik+1,θik+1)(x_i^{k+1}, \theta_i^{k+1}) with τik\tau_i^k and ηk\eta^k (for the agent that set the maximum this reproduces its accepted candidate); otherwise the candidates are kept. Each agent then sends sik+1s_i^{k+1} to its neighbors and forms rik+1r_i^{k+1}. Communication per iteration, in the paper’s accounting: one exchange of a vector with the neighbors, plus one network-wide maximum of a scalar, which the paper assumes as a primitive (by synchronous flooding it takes as many rounds as the graph’s diameter). Without constraints (gi≡0g_i \equiv 0) the constraint terms are removed, cβ=0c_\beta = 0, the test reduces to Λi(x~)≤1−δ−cα−cς2τ~ ∥x~−xik∥2\Lambda_i(\tilde x) \le \tfrac{1 - \delta - c_\alpha - c_\varsigma}{2\tilde\tau}\,\|\tilde x - x_i^k\|^2, and the method is D-APDB-0, Algorithm 2. On this page δ=cα=cς=0.1\delta = c_\alpha = c_\varsigma = 0.1, cβ=0.1c_\beta = 0.1 with constraints and 00 without, ζ=1\zeta = 1, and cγ=1/(2∣E∣)c_\gamma = 1/(2|\mathcal E|), the endpoint Algorithm 1 permits, as in the paper’s experiments and code. The paper’s theorems are stated for this choice; one step of the printed proof of iterate convergence uses cγc_\gamma strictly below it, a technical point that bounding the incidence terms together rather than agent by agent (λmax⁡(H⊤H)<2∣E∣\lambda_{\max}(H^\top H) < 2|\mathcal E| for a connected graph with at least three agents) restores. The chips set ρ\rho and the start τˉi\bar\tau_i, either one value τˉ\bar\tau for every agent, which uses no constants, or, as in the paper’s experiments, twenty times each agent’s safe stepsize defined next, which does.

The safe stepsizes. The paper proves (its sufficient condition for the line search) that agent ii’s test passes for every τ~≤τ^i\tilde\tau \le \hat\tau_i, where

τ^i=min⁡{τi′, τi′′},τi′′=1Cgicα(1−δ)2ζ,Lfi τi′+Lgi2Bi2cβ (τi′)2=1−δ−c(τi′>0);gi≡0:τ^i=1−δ−cα−cς2Lfi,\begin{gathered} \hat\tau_i = \min\{\tau_i',\ \tau_i''\}, \qquad \tau_i'' = \frac{1}{C_{g_i}}\sqrt{\frac{c_\alpha (1 - \delta)}{2\zeta}}, \\ L_{f_i}\,\tau_i' + \frac{L_{g_i}^2 B_i^2}{c_\beta}\,(\tau_i')^2 = 1 - \delta - c \quad (\tau_i' > 0); \\ g_i \equiv 0:\quad \hat\tau_i = \frac{1 - \delta - c_\alpha - c_\varsigma}{2 L_{f_i}}, \end{gathered}

in terms of the smoothness constant Lfi=∥Qi∥L_{f_i} = \|Q_i\|, the Lipschitz constant Lgi=∥Ai∥L_{g_i} = \|A_i\| of ∇gi\nabla g_i, the bound Cgi=max⁡x∈[−R,R]2∥∇gi(x)∥C_{g_i} = \max_{x \in [-R,R]^2} \|\nabla g_i(x)\| over the whole box (attained at a corner, since the norm of an affine map is convex), and the dual radius BiB_i. The constraint-free line is the paper’s choice for gi≡0g_i \equiv 0 (with cβ=0c_\beta = 0, so c=cα+cςc = c_\alpha + c_\varsigma): half the uniform threshold (1−δ−c)/Lfi(1 - \delta - c)/L_{f_i} that the smoothness constant certifies, conservative because a particular step passes at a larger value when its direction has lower curvature than LfiL_{f_i}. Two consequences. Agent ii can only reject a trial larger than τ^i\hat\tau_i, each of its rejections is at most ρ\rho times the previous one, and the first is at most τˉi\bar\tau_i, so over the whole run it rejects at most ⌈log⁡1/ρ(τˉi/τ^i)⌉\lceil \log_{1/\rho}(\bar\tau_i/\hat\tau_i)\rceil trials (none if τˉi≤τ^i\bar\tau_i \le \hat\tau_i). And since the common factor qkq_k only grows when some agent rejects, which requires that agent to still be above its own threshold, the factor never exceeds max⁡{1,max⁡jτˉj/(ρτ^j)}\max\{1, \max_j \bar\tau_j/(\rho\hat\tau_j)\}, which gives the floor

τik  ≥  τˉi min⁡{1, ρmin⁡jτ^jτˉj}.\tau_i^k \;\ge\; \bar\tau_i \,\min\Big\{1,\ \rho \min_j \frac{\hat\tau_j}{\bar\tau_j}\Big\}.

Note what this does and does not say: an agent’s own test never pushes it below ρτ^i\rho\hat\tau_i, but a cut forced by another agent can, so the floor is a network quantity. With the proportional start τˉi=20 τ^i\bar\tau_i = 20\,\hat\tau_i it reduces to the individual τik≥ρ τ^i\tau_i^k \ge \rho\,\hat\tau_i; with a common start τˉ\bar\tau the guaranteed lower bound on the common stepsize is min⁡{τˉ,ρmin⁡jτ^j}\min\{\bar\tau, \rho \min_j \hat\tau_j\}, which equals τˉ\bar\tau when τˉ≤ρmin⁡jτ^j\bar\tau \le \rho \min_j \hat\tau_j and ρmin⁡jτ^j\rho \min_j \hat\tau_j otherwise. It is a bound, not the value the common stepsize settles on: a run in which no cut occurs keeps its stepsize at τˉ\bar\tau, which can exceed the bound (constraints: none, spread ×1, start 3, ρ=0.5\rho = 0.5: every τ^i=3.5\hat\tau_i = 3.5, no trial is rejected, the stepsize stays at 3 and the bound is 1.75), and a run with cuts ends wherever the last cut left it (experiment 5).

D-APD and the untested run. D-APD, the benchmark of the paper, is the same iteration with τi≡τ^i\tau_i \equiv \hat\tau_i, η≡1\eta \equiv 1 and γ\gamma from the same formula with τˉ=max⁡iτ^i\bar\tau = \max_i \hat\tau_i: the fixed stepsizes the analysis certifies as safe, which require every constant above. Here the agents are given LfiL_{f_i}, LgiL_{g_i} and CgiC_{g_i} exactly, and compute BiB_i the way one would in practice, from the Slater point xsx_s and weak duality: since every fi≥0f_i \ge 0, any optimal multiplier satisfies θi⋆≤φ(xs)/(−gi(xs))\theta_i^\star \le \varphi(x_s)/(-g_i(x_s)) with φ=∑ifi\varphi = \sum_i f_i, so

Bi=2 φ(xs)−gi(xs)  ≥  2 θi⋆B_i = \frac{2\,\varphi(x_s)}{-g_i(x_s)} \;\ge\; 2\,\theta_i^\star

meets the paper’s assumption. D-APDB uses the same BiB_i, but only as the radius of the projection of θi\theta_i, where a loose radius changes nothing as long as the projection stays inactive; in τ^i\hat\tau_i a loose radius shrinks the step. The third run, fixed τˉ\bar\tau, no test, keeps D-APDB’s initial stepsizes, sets η≡1\eta \equiv 1, uses the constant consensus stepsize cγ/(τˉ(2/cα+1/cς))c_\gamma/(\bar\tau(2/c_\alpha + 1/c_\varsigma)) from the same formula, and never tests.

How to read the comparison. D-APD is not a competitor on equal terms: it is handed the constants, and D-APDB with a common start is not. The paper’s claim is that D-APDB keeps D-APD’s guarantees without the Lipschitz constants (for nonlinear constraints it still uses the dual radius BiB_i, which does not enter its stepsizes), at the price of one max-consensus at every iteration and a number of rejected trials that is bounded over the whole run, and that in the paper’s experiments (twenty-dimensional QCQPs and SVM training on twelve agents) it converges faster because the safe stepsizes are far below what the local tests accept. The plane is a different regime: with two coordinates and a modest box the safe stepsizes are only a few times too small, so the speed comparison at the end of a run can go either way, for a reason the panels make visible (experiment 4 under What to try). What the page is for is to see the mechanism: when the tests fail, what the stepsizes settle on relative to the safe values, what the synchronization costs, and what the untested start does.

The diagnostics, and the theorem. The plots show the behavior of the current iterates, and the theorem is about something else; the distinction is easy to overlook. For the network average xˉk=1N∑ixik\bar x^k = \tfrac1N \sum_i x_i^k of the current iterates the panels plot, on logarithmic axes, the three last-iterate diagnostics of the paper’s experiments: the relative suboptimality ∣φ(xˉk)−φ⋆∣/∣φ⋆∣|\varphi(\bar x^k) - \varphi^\star| / |\varphi^\star| with φ=∑ifi\varphi = \sum_i f_i (the iterates stay in the box, so the indicators contribute nothing), the consensus error ∑i∥xik−xˉk∥2/(N∥xˉk∥2)\sum_i \|x_i^k - \bar x^k\|^2 / (N \|\bar x^k\|^2), and the constraint violation max⁡i (gi(xˉk))+\max_i\, (g_i(\bar x^k))_+, shown unnormalized because xˉ0\bar x^0 can be feasible here (the paper divides by the initial violation and plots log⁡(1+⋅)\log(1 + \cdot) of the suboptimality). In the code the two denominators are guarded as max⁡{10−12,∣φ⋆∣}\max\{10^{-12}, |\varphi^\star|\} and Nmax⁡{10−12,∥xˉk∥2}N\max\{10^{-12}, \|\bar x^k\|^2\}; the plots draw values below 10−810^{-8} at 10−810^{-8} and leave a gap where a value is exactly zero, and the table reports the unclamped values. The paper’s O(1/K)O(1/K) guarantee (its main theorem) concerns weighted averages of the iterates over time rather than the last iterates shown here, and its own measures of consensus violation and infeasibility rather than the normalized quantities plotted: the weighted temporal averages x^iK=∑k<Ktkxik/∑k<Ktk\hat x_i^K = \sum_{k < K} t_k x_i^k / \sum_{k < K} t_k of each agent, with t0=1t_0 = 1, tk+1=tk/ηk+1t_{k+1} = t_k/\eta^{k+1}, stacked as x^K=(x^1K,…,x^NK)\hat{\mathbf x}^K = (\hat x_1^K, \dots, \hat x_N^K), satisfy, for any initial stepsizes τˉi>0\bar\tau_i > 0,

∣∑iφi(x^iK)−φ⋆∣=O(1/K),∑iθi⋆ (gi(x^iK))++∥λ⋆∥ ∥Ax^K∥=O(1/K),\begin{gathered} \Big|\sum_i \varphi_i(\hat x_i^K) - \varphi^\star\Big| = O(1/K), \\ \sum_i \theta_i^\star\,\big(g_i(\hat x_i^K)\big)_+ + \|\lambda^\star\|\,\|A\hat{\mathbf x}^K\| = O(1/K), \end{gathered}

where λ⋆\lambda^\star is an optimal multiplier of the consensus constraints and ∥Ax^K∥\|A\hat{\mathbf x}^K\| is the disagreement across edges; moreover the iterates (xik,θik)(x_i^k, \theta_i^k) converge to a primal–dual solution. The objective is evaluated at each agent’s own average rather than at a network average, the consensus measure is an incidence residual rather than a normalized squared disagreement, and the feasibility measure is weighted by the optimal multipliers, so it says nothing by itself about a constraint whose θi⋆=0\theta_i^\star = 0. The plots should therefore be read as numerical illustrations of the algorithms’ behavior, not as visualizations of the theoretical bounds; the dotted line of slope −1-1 indicates the O(1/K)O(1/K) reference rate and is not an upper bound on the curves.

The method and its analysis are in An accelerated primal–dual algorithm with backtracking for decentralized constrained optimization by Qiushui Xu, Necdet Serhat Aybat and Mert Gürbüzbalaban (Journal of Nonlinear and Variational Analysis 10(3), 2026, in the special issue in honor of Yurii Nesterov; arXiv:2512.07085): the reordering of the primal–dual updates that makes a local test possible, the test itself, the max-consensus synchronization of the momentum, the O(1/K) rates for suboptimality, infeasibility and consensus with the number of trials bounded, the convergence of the iterates, and experiments on QCQPs and SVM training on a network of twelve agents. The note A line search without a leader walks through the ideas; the wider thread is on the research page.

To reference this page:

@misc{gurbuzbalaban2026backtrackingplayground,
  title  = {Backtracking across a network, interactively},
  author = {G{\"u}rb{\"u}zbalaban, Mert},
  year   = {2026},
  howpublished = {\url{https://mert-g.org/playground/backtracking/}}
}