Backtracking across a network

The stepsize a first-order method is allowed to take is dictated by constants (Lipschitz constants of the gradient and of the constraints, bounds on dual variables) that are seldom known and, when known, are worst-case. On one machine a line search removes the need for them. On a network of agents who each hold part of the problem and talk only to their neighbors, a line search is not local: the agents share a momentum parameter, and a stepsize one agent rejects changes the step every other agent must take. This page runs 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, where every agent, every constraint and every stepsize can be watched. For reference it also runs the same iteration with the fixed stepsizes the paper’s analysis certifies from the constants, and with D-APDB’s initial stepsize left untested.

What is being computed

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

\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 $Q_i, A_i \succ 0$ . The network has to solve

\begin{gathered} \varphi^\star = \min_{x \in \mathbb R^2}\ \sum_{i \in \mathcal N} \big(\phi_i(x) + f_i(x)\big) \\ \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^\star$ , although no agent sees another agent’s loss or constraint. In the plane the data can be drawn: $a_i$ is the minimizer of agent $i$ ’s own loss (the $+$ marks), $g_i \le 0$ is the interior of an ellipse, and the feasible region is the intersection of the $N$ ellipses. The instances are built so that the losses pull in roughly one direction and $x^\star$ lies on the boundary of the feasible region, with one constraint active. 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^\star$ , $\varphi^\star$ and the multipliers $\theta_i^\star$ are computed by a log-barrier interior-point method on the centralized problem, to high accuracy.

Instance generator. $Q_i = L_{f_i}\, R_i\,\mathrm{diag}(1, \omega_i)\, R_i^\top$ with a uniformly random rotation $R_i$ , $\omega_i$ uniform in $[0.1, 0.5]$ , and $L_{f_i} = 0.1\, s^{\,u_i - 1/2}$ , $u_i$ uniform in $[0,1]$ , where $s$ is the curvature spread: the agents’ smoothness constants range over a factor $s$ around $0.1$ . The minimizers $a_i = c + r_i(\cos\psi_i, \sin\psi_i)$ with $c = (0.5, 0.5)$ , $r_i$ uniform in $[3.2, 4.0]$ and $\psi_i$ within $\pm 0.6$ rad of a direction common to the instance. $A_i$ has a uniformly random orientation and eigenvalues uniform in $[0.12, 0.4]$ (semi-axes between 2.2 and 4.1); its center $\bar x_i$ is within $\pm 0.5$ of $c$ in each coordinate, so $c$ is a Slater point. Starting points $x_i^0$ are uniform in $[-4, 4]^2$ , independently for each agent, and $\theta_i^0 = 0$ . New instance redraws everything.

The iteration. Agent $i$ keeps a copy $x_i$ of the decision variable, a multiplier $\theta_i \ge 0$ for its own constraint, a vector $s_i$ that encodes the multipliers of the consensus constraints $x_i = x_j$ , $(i, j) \in \mathcal E$ (the paper shows that the agents never need these multipliers themselves), and its stepsize $\tau_i$ . From its neighbors it needs only the vector

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 $x_i$ . Given a trial stepsize $\tilde\tau$ and a momentum factor $\eta$ , the step is

\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 projection onto the box, the dual stepsize is $\sigma = \zeta\tau$ with a fixed $\zeta > 0$ , and $B_i \ge \theta_i^\star$ is a bound on the optimal multiplier (the paper’s bounded-dual-domain assumption). 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. 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) starts every agent from an initial stepsize $\bar\tau_i$ and runs each iteration $k$ in two phases.

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

\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 $\Lambda_i(x) = f_i(x) - f_i(x_i^k) - \langle \nabla f_i(x_i^k), x - x_i^k \rangle$ , $c = c_\alpha + c_\beta + c_\varsigma$ , and user constants $\delta, c_\alpha, c_\beta, c_\varsigma > 0$ with $\delta + c < 1$ ; otherwise it sets $\tilde\tau \leftarrow \rho\,\tilde\tau$ and tries again. (The paper writes the coefficients of $E_i^k$ through auxiliary sequences $\alpha_i^k = c_\alpha/\tau_i^{k-1}$ , $\beta_i^k = c_\beta/\tau_i^{k-1}$ , $\tilde\varsigma_i^{k+1} = c_\varsigma/\tilde\tau$ and so on; with those definitions the coefficients collapse to the ones shown.) Term by term, the test is the paper’s sufficient condition for a safe stepsize with every global constant replaced by its local counterpart: the first two terms require $\tilde\tau \le (1 - \delta - c)/L$ where $L$ is the curvature of $f_i$ along the step actually taken (for a quadratic, $\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. The network computes one scalar, $\eta^k = \max_i \eta_i$ , by max-consensus, and every agent sets $\tau_i^k = \tau_i^{k-1}/\eta^k$ , so the stepsizes never increase and all shrink by the same factor; it then updates

\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 $\bar\tau = \max_i \bar\tau_i$ and $c_\gamma \le 1/(2|\mathcal E|)$ . If $\eta^k > 1$ , every agent recomputes $(x_i^{k+1}, \theta_i^{k+1})$ with $\tau_i^k$ and $\eta^k$ (for the agent that set the maximum this reproduces its accepted candidate); otherwise the candidates are kept. Each agent then exchanges $s_i^{k+1}$ with its neighbors and forms $r_i^{k+1}$ . The communication per iteration is one vector exchange with the neighbors and one max-consensus of a scalar. Without constraints ( $g_i \equiv 0$ , $c_\beta = 0$ ) the test reduces to $\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 $\delta = c_\alpha = c_\beta = c_\varsigma = 0.1$ , $\zeta = 1$ and $c_\gamma = 1/(2|\mathcal E|)$ , as in the paper’s experiments; the chips set the shrink factor $\rho$ and the start $\bar\tau_i$ , either one value $\bar\tau$ for every agent or, as in the paper’s experiments, twenty times each agent’s safe stepsize defined next.

The safe stepsizes, and the two fixed-step runs. The paper proves (its sufficient condition for the line search) that agent $i$ ’s test passes for every $\tilde\tau \le \hat\tau_i$ , where

\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), \end{gathered}

in terms of the smoothness constant $L_{f_i} = \|Q_i\|$ , the Lipschitz constant $L_{g_i} = \|A_i\|$ of $\nabla g_i$ , the bound $C_{g_i} = \max_{x \in [-R,R]^2} \|\nabla g_i(x)\|$ over the whole box, and the dual bound $B_i$ (for $g_i \equiv 0$ the paper takes $\tau_i' = (1 - \delta - c)/(2L_{f_i})$ ). Since stepsizes only decrease by the factor $\rho$ and only when a test fails, no stepsize ever falls below $\rho\,\hat\tau_i$ , and the number of trials agent $i$ rejects over the whole run is at most $\log_{1/\rho}\lceil \bar\tau_i/\hat\tau_i\rceil + 1$ .

D-APD, the benchmark of the paper, is the same iteration with $\tau_i \equiv \hat\tau_i$ , $\eta \equiv 1$ and $\gamma$ from the same formula with $\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 $L_{f_i}$ , $L_{g_i}$ and $C_{g_i}$ exactly, and compute $B_i$ the way one would in practice, from the Slater point $x_s = c$ and weak duality: since every $f_i \ge 0$ , $\theta_i^\star \le \varphi(x_s)/(-g_i(x_s)) =: B_i$ . D-APDB uses the same $B_i$ , but only as the radius of the projection of $\theta_i$ , where a loose bound leaves the iterates untouched; in $\hat\tau_i$ a loose bound shrinks the step. The third run, fixed $\bar\tau$ , no test, takes D-APDB’s initial stepsize, with D-APDB’s $\gamma$ , and never tests it.

How to read the comparison. D-APD is not a competitor on equal terms: it is handed the constants, and D-APDB is not. The paper’s claim is that D-APDB keeps D-APD’s guarantees without that information, at the price of a bounded number of extra trials and one max-consensus per iteration, 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 below). 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 why the untested start is not an option.

The measures. For the network average $\bar x^k = \tfrac1N \sum_i x_i^k$ the panels plot, on logarithmic axes, the three quantities of the paper’s experiments: the relative suboptimality $|\varphi(\bar x^k) - \varphi^\star| / |\varphi^\star|$ with $\varphi = \sum_i f_i$ (the iterates stay in the box, so the indicators contribute nothing), the consensus error $\sum_i \|x_i^k - \bar x^k\|^2 / (N \|\bar x^k\|^2)$ , and the constraint violation $\max_i\, (g_i(\bar x^k))_+$ , shown unnormalized because $\bar x^0$ can be feasible here (the paper divides by the initial violation and plots $\log(1 + \cdot)$ of the suboptimality). The paper’s guarantee (its main theorem) concerns the weighted ergodic averages $\bar x_i^K = \sum_{k < K} t_k x_i^k / \sum_{k < K} t_k$ with $t_0 = 1$ , $t_{k+1} = t_k/\eta^{k+1}$ : for any initial stepsizes $\bar\tau_i > 0$ ,

\begin{gathered} \Big|\sum_i \varphi_i(\bar x_i^K) - \varphi^\star\Big| = O(1/K), \\ \sum_i \theta_i^\star\,\big(g_i(\bar x_i^K)\big)_+ + \|\lambda^\star\|\,\|A\bar{\mathbf x}^K\| = O(1/K), \end{gathered}

where $\lambda^\star$ is an optimal multiplier of the consensus constraints and $\|A\bar{\mathbf x}^K\|$ measures the disagreement across edges; moreover the iterates $(x_i^k, \theta_i^k)$ converge to a primal–dual solution. The panels show the last iterates, not the ergodic averages, as the paper’s experiments do, so the curves are not bound to lie under a $1/k$ line; the dotted guide of slope $-1$ only shows the scale of the guaranteed rate.

What to try

The page opens with twelve agents, ellipse constraints, the box $[-10, 10]^2$ , and D-APDB started from $\bar\tau = 1$ for every agent, with no constants. Six experiments, in order:

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^\star$ on the boundary of the feasible region. In panel B a single triangle at $k = 0$ marks the only failed test: 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 a handful of extra trial steps in 3,000 iterations. That is the entire cost of the line search on this instance, paid at the first 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 $\tilde\tau\tilde\sigma\,\|\nabla g_i(\tilde x)\|^2$ at $\tilde\tau = 1$ is far above $c_\alpha(1-\delta)/2$ , the local form of the condition behind $\tau_i''$ , while the curvature term alone would have accepted a stepsize of 1.
Why the test is needed. Switch the agents drawn to no test. The same stepsize with no test looks healthy for some 900 iterations, until the active constraint’s multiplier has built up; then the primal–dual coupling is unstable at this stepsize, the agents fly apart to the walls of the box, the active multiplier jumps to its bound, and the consensus error climbs by four orders of magnitude and never recovers. The test detected this at iteration 0, from local quantities, nine hundred iterations before any symptom.
What the safe stepsizes pay for. Step the box through 5, 10, 20. The dashed lines in panel B fall (their medians are about 0.10, 0.05, 0.025), because $C_{g_i}$ is a bound over the whole box, and D-APD’s curves slow down accordingly; D-APDB’s stepsize and curves do not move, because its test only sees the points the agents visit. The paper’s twenty-dimensional experiments are the extreme of this effect.
Early and late, and the role of $\gamma$ . With the default start D-APDB leads D-APD over the first few hundred iterations, in almost every instance, and D-APD ends ahead in most. Now set the start to 0.3: D-APDB ends at the same stepsize, about 0.2, but finishes well ahead of D-APD; set it to 3 or 10 and it stalls. The test finds the same primal stepsize from any start; what changes is $\gamma^k \propto 1/\bar\tau$ , the consensus stepsize, which the algorithm fixes from the initial guess and never revisits. The end-of-run ranking on this problem is decided by that consensus stepsize, not by the line search. In the method as analyzed, an optimistic guess is corrected in the primal step but remembered in the consensus step.
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\,\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 stiffest agent’s value. The single shared $\eta^k$ is what keeps the paper’s analysis intact; its price is that the most conservative agent sets the pace for all.
The shrink factor, and new instances. Set $\rho$ to 0.5: the first iteration needs two or three trials instead of eight, but the stepsize lands at about 0.125 instead of 0.2, since a coarse search overshoots by up to the factor $\rho$ . Then press new instance a few times: the number of failed tests, the ratio of the final stepsizes to the safe ones, and the early lead persist across instances, while the end-of-run comparison with D-APD depends on the instance and, as experiment 4 shows, on the start.

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 N

curvature spread

constraints

box ±R

D-APDB start τ̄

shrink ρ

methods

A The run: agents in the plane, and the three measures the paper bounds

agents of

k = 0 of 3,000

a line of slope −1 is the paper’s O(1/k) rate for the averaged iterates

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 average x̄ᵏ and × the solution. Right: the three measures of the paper for 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

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); the dashed lines are the safe stepsizes τ̂ᵢ that D-APD uses throughout, which the theory guarantees the line search never goes below by more than the factor ρ. Right: how many candidate steps the agents computed at each iteration, on average; one means the first trial passed.

Method	τᵢ at the end	backtracking	suboptimality	consensus	violation
D-APDB (backtracking)	0.21 from 1.0	1× at k = 0; 3,007 trial steps per agent	7.8e-4	3.4e-8	6.8e-4
D-APD, safe steps τ̂ᵢ	3.9e-2 – 6.4e-2	—	6.9e-5	4.6e-8	0
Fixed τ̄, no test	1.0	—	11	11	0

All rows run the same primal–dual iteration (defined above the playground) 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 C_gᵢ of its constraint’s gradient over the box, and the dual bound Bᵢ = 6.5 – 6.8 from a Slater point. The last three columns are the paper’s measures at the final iteration, for the network average x̄. A “trial step” is one candidate update, accepted or not; D-APDB’s trial steps beyond the 3,000 iterations are the price of the line search.

Each agent can test its own step against what it sees locally, and one shared number, the largest of the resulting shrink factors, is enough to keep the network’s primal–dual iteration consistent. The price is one max-consensus per iteration and a bounded number of extra trials; what is bought is a method with the paper’s O(1/K) guarantees and no Lipschitz constant or dual bound to know in advance.

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/}}
}