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]²
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.
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 end | backtracking (D-APDB) | suboptimality | consensus | violation |
|---|---|---|---|---|---|
| D-APDB (backtracking) | 0.21 from 1.0 | 1× at k = 0; 3,008 candidate updates 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 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.
The page opens with instance 7, twelve agents, ellipse constraints, curvature spread ×10, the box , , and D-APDB started from for every agent, with no constants. Three terms recur. The safe stepsize is the value the analysis certifies for agent 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.
- 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 on the boundary of the feasible region. In panel B a single triangle at 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 , 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 at is far above , the local form of the condition behind , while the curvature term alone would have accepted a stepsize of 1.
- 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.
- 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 , 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 moves with it.) The paper’s twenty-dimensional experiments are the extreme of this effect.
- Early and late, and the role of the consensus stepsize . 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 at 3,000, against D-APD’s and 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 of each start, so they are close but not equal). The difference is the consensus stepsize . After the cut it equals , inversely proportional to the start (factors 1/0.3, 1, 1/3, 1/10 relative to the start 1): the scale of is fixed from the initial guess and only the factor involving 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.
- 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 , 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 ). The single shared 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 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 . Then put 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 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 (, , , , ) are in ; the stacked primal vector is in and the edge multipliers in . is the Euclidean norm of a vector and the spectral norm of a matrix, , and is the set of neighbors of agent in the graph. The constants are the test parameters of the paper and throughout; the center of the instance is written to keep for that sum.
The problem. agents sit on a connected undirected graph , a random cycle through all agents with further random edges, so , as in the paper’s experiments. Agent privately holds a smooth convex loss, a simple set, and one constraint:
with , so and . Writing for the local composite objective, the network has to solve
every agent ending with the same solution , although no agent sees another agent’s loss or constraint. The feasible set is : the box, intersected with the filled ellipses (boundaries included). In the plane the data can be drawn: is the minimizer of agent ’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 () 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 , its value and the multipliers 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 there and the box faces within of it), in the unknowns with 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 (with and the outward normal of box face ), the positive parts of all ellipse values and of the four box inequalities , the negative parts of all multipliers, and all complementarity products and : it is accepted when that residual is below , 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 . The reference multipliers are not used by the distributed runs.
Instance generator. with a uniformly random rotation , uniform in , and , uniform in , where is the curvature spread: the agents’ smoothness constants range over a factor around . The minimizers with , uniform in and within rad of a direction common to the instance. has a uniformly random orientation and eigenvalues uniform in (semi-axes between 2.2 and 4.1); its center is within of in each coordinate. The Slater point used below is the centroid of the ellipses’ centers, , which lies strictly inside every ellipse by construction. Starting points are uniform in , 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 keeps a copy of the decision variable, a multiplier for its own constraint, a vector that encodes the multipliers of the consensus constraints , , and its stepsize . At each iteration it receives from its neighbors and forms, locally,
the pull of its constraint and of its neighbors on (the paper shows that the consensus multipliers themselves, with and an oriented edge–node incidence matrix of the graph, never need to be formed; is not to be confused with the ellipse matrices ). Given a trial stepsize and a momentum factor , the step is
where the prox of the box indicator is the coordinatewise projection onto , the dual stepsize is with a fixed , and is the radius of the dual projection, which the paper’s bounded-dual-domain assumption requires to satisfy for a non-affine (an affine constraint needs no such radius); the radius must also be positive, since a zero radius would pin 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
which makes the momentum and consensus updates at unambiguous. D-APDB and the two fixed-step methods below all take exactly this step and differ only in how and are chosen.
D-APDB (distributed accelerated primal–dual method with backtracking) takes initial stepsizes , a shrink factor , test parameters with , a dual ratio and , and runs each iteration in two phases.
Local line search. Agent tries with the local momentum , computes the candidate above, and accepts it if
with ; otherwise it sets and tries again. (The paper writes the coefficients of through auxiliary sequences , , and so on; with those definitions and 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 with , where is the curvature of along the step actually taken (for a quadratic, ); 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 by which its test made it shrink, the network computes the largest of them, , by max-consensus, and every agent sets . The stepsizes therefore never increase, all shrink by the same factor, and the agents keep their initial proportions: with a common factor . 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
with . If , every agent recomputes with and (for the agent that set the maximum this reproduces its accepted candidate); otherwise the candidates are kept. Each agent then sends to its neighbors and forms . 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 () the constraint terms are removed, , the test reduces to , and the method is D-APDB-0, Algorithm 2. On this page , with constraints and without, , and , 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 strictly below it, a technical point that bounding the incidence terms together rather than agent by agent ( for a connected graph with at least three agents) restores. The chips set and the start , either one value 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 ’s test passes for every , where
in terms of the smoothness constant , the Lipschitz constant of , the bound over the whole box (attained at a corner, since the norm of an affine map is convex), and the dual radius . The constraint-free line is the paper’s choice for (with , so ): half the uniform threshold that the smoothness constant certifies, conservative because a particular step passes at a larger value when its direction has lower curvature than . Two consequences. Agent can only reject a trial larger than , each of its rejections is at most times the previous one, and the first is at most , so over the whole run it rejects at most trials (none if ). And since the common factor only grows when some agent rejects, which requires that agent to still be above its own threshold, the factor never exceeds , which gives the floor
Note what this does and does not say: an agent’s own test never pushes it below , but a cut forced by another agent can, so the floor is a network quantity. With the proportional start it reduces to the individual ; with a common start the guaranteed lower bound on the common stepsize is , which equals when and otherwise. It is a bound, not the value the common stepsize settles on: a run in which no cut occurs keeps its stepsize at , which can exceed the bound (constraints: none, spread ×1, start 3, : every , 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 , and from the same formula with : the fixed stepsizes the analysis certifies as safe, which require every constant above. Here the agents are given , and exactly, and compute the way one would in practice, from the Slater point and weak duality: since every , any optimal multiplier satisfies with , so
meets the paper’s assumption. D-APDB uses the same , but only as the radius of the projection of , where a loose radius changes nothing as long as the projection stays inactive; in a loose radius shrinks the step. The third run, fixed , no test, keeps D-APDB’s initial stepsizes, sets , uses the constant consensus stepsize 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 , 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 of the current iterates the panels plot, on logarithmic axes, the three last-iterate diagnostics of the paper’s experiments: the relative suboptimality with (the iterates stay in the box, so the indicators contribute nothing), the consensus error , and the constraint violation , shown unnormalized because can be feasible here (the paper divides by the initial violation and plots of the suboptimality). In the code the two denominators are guarded as and ; the plots draw values below at and leave a gap where a value is exactly zero, and the table reports the unclamped values. The paper’s 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 of each agent, with , , stacked as , satisfy, for any initial stepsizes ,
where is an optimal multiplier of the consensus constraints and is the disagreement across edges; moreover the iterates 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 . 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 indicates the 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/}}
}