A research note, October 2026; about 18 minutes to read
A line search without a leader
Every first-order method needs a stepsize, and the one the theory hands you is built from constants nobody knows. On one machine a line search fixes that. On a network of agents who share a momentum parameter and only talk to their neighbors, a stepsize one agent rejects changes everyone's step. The paper behind this note lets each agent run its own backtracking test and synchronizes the network with a single number per iteration, keeping the O(1/K) guarantees and dropping the constants.
An accelerated primal–dual algorithm with backtracking for decentralized constrained optimization (J. Nonlinear Var. Anal., 2026)
Take any gradient method and look at the condition under which it is proven to converge. It is an inequality on the stepsize, and on the other side of the inequality sits a constant: a Lipschitz constant of the gradient, and for constrained problems also a Lipschitz constant of the constraint map and a bound on the optimal multipliers. These constants exist, but one rarely knows them, and when one does know them they describe the worst point of the whole domain while the iterates spend their time somewhere much tamer. The standard remedy is a line search: try a stepsize, check an inequality that uses only quantities at the current and the candidate point, shrink and retry if it fails. The theory then charges a few extra function evaluations and gives back a method that adapts to the curvature it actually meets.
This note is about doing that on a network. In decentralized optimization the problem is split among agents who each hold their own loss and their own constraints, communicate only with their neighbors on a graph, and must all arrive at the same solution. The paper it accompanies, with Qiushui Xu and Serhat Aybat, builds a line search for an accelerated primal–dual method in this setting. The difficulty is not the inequality; it is that in a primal–dual method the agents are coupled through a shared momentum parameter and through multipliers that live on the edges of the graph, so a stepsize rejected by one agent is not that agent's private business. The playground runs the method on a small problem in the plane, where the agents, their constraints and their stepsizes can all be watched.
The problem and the method underneath
There are agents on a connected undirected graph . Agent holds a smooth convex loss , a proper closed convex function with an easy proximal map and a compact domain (the indicator of a compact simple set, or an norm added to one; a bare norm on all of is outside the paper's assumptions), and a constraint given by a convex map with Lipschitz Jacobian. (The paper allows for a closed convex cone , which covers conic constraints; this note keeps to inequalities, the case .) For a vector-valued constraint, denotes the matrix of component gradients, the transpose of the Jacobian, so that for a multiplier ; vector norms are Euclidean and matrix norms spectral. Writing , the network must solve
Everything quoted below is proved in the paper under its Assumptions 1–4, which are worth stating because the guarantees are only as general as they are. The agents can exchange vectors in across the edges of the graph and can compute the maximum of scalars, one held by each agent, so that every agent learns it. Each has a compact domain, and each has an -Lipschitz gradient on that domain. Each is convex with a Jacobian that is -Lipschitz and bounded by on that domain. And a primal–dual solution exists, with a known radius satisfying for every whose is not affine. (The paper's assumption writes only the inequality; the radius must also be positive, because when a zero radius would be allowed, and it pins the multiplier at zero. For example, take , the indicator of and at every agent, with , every agent started at and zero multiplier and consensus histories: the consensus pulls vanish because the agents agree, the projection onto the radius-zero ball keeps every multiplier at zero, the prox keeps , and both increments are zero so every test passes; every iterate stays at although . A positive radius leaves the margin through which the dual step can react to a violation.) The playground's problem below satisfies all of this through its box, its quadratic data and a Slater point, with radii that are positive by construction.
Giving every agent its own copy , stacked into , and demanding across every edge, which reads for with the oriented edge–node incidence matrix of the graph, turns this into a saddle-point problem: a Lagrangian with a multiplier for each agent's constraint and a multiplier for each edge's consensus constraint, stacked into . The method underneath is the accelerated primal–dual algorithm (APD) of Hamedani and Aybat, close to the decentralized form they gave it for strongly convex problems: each agent takes a proximal gradient step on its own loss against the pull of its multipliers, extrapolates that pull with a momentum factor , and then takes a dual ascent step on ; the edge multipliers are updated from the disagreement between neighbors. Convergence requires the primal stepsize , the dual stepsize and the consensus stepsize to satisfy inequalities involving , , and . The fixed-step method with the stepsizes those inequalities certify is called D-APD in the paper, and it is the benchmark: the same iteration, handed the constants.
Why the obvious line search does not decentralize
APD already has a line search in the centralized setting. The natural plan is to let every agent run it on its own block. Here is where it breaks. The test an agent would check contains the change of the consensus multipliers, , and in the standard update order is computed from the new primal iterates. Expanded over the graph,
so agent 's test involves the neighbors' accepted candidates , which in turn depend on their tests, which involve . Nobody can go first.
The paper's first move is to change the order. The consensus multipliers are updated before the primal step, from the two previous primal iterates, which are final:
The momentum term in this update is a by-product of the proof (it makes a duality-gap bound telescope), but the effect on the implementation is what matters: once depends only on points every agent already has, each agent's test can be written entirely in its own variables. In fact the agents never form at all. Each keeps a vector with , exchanges it with its neighbors, and the only thing it needs from the edge multipliers is the pull , which together with its own constraint's pull makes up the vector it extrapolates.
The test, and the one number the network shares
With that order fixed, agent at iteration tries the stepsize it used last time, with momentum , computes the candidate pair , and accepts it if
where adds up a descent-lemma term, , which a quadratic passes as soon as with the curvature in the direction of the step, and two terms that measure the constraint's Jacobian at the candidate, and , against the dual progress . Here are constants of the user's choosing with , the dual stepsize is tied to the primal one by for a fixed , and if the test fails, for a fixed and the agent tries again. Term by term this is the sufficient condition behind the fixed-step method with every global constant replaced by a local one: the Jacobian is evaluated where the iterate is, the multiplier is the one in hand, and the curvature is probed along the step taken. The dual radius , which must satisfy when is not affine (an affine constraint needs none), appears in the method only as the radius of the ball onto which is projected; a loose radius changes nothing there while the projection stays inactive, whereas in the fixed-step method it enters the stepsize.
Now the coupling. Agent 's search returns a factor by which it had to shrink. The analysis needs one momentum factor and one sequence of stepsize ratios for the whole network, because the ergodic weights that make the rates work are defined through and . So the network computes
by a max-consensus, and every agent sets . An agent whose own test had passed now takes a smaller step than it needed to, and recomputes its update with the common ; the analysis then controls the gap between the parameters each agent's test accepted and the smaller ones it is told to use. The consensus stepsize is set from and from , the largest initial guess, as with . That is the whole synchronization: the maximum of one scalar per iteration, on top of the one vector exchange with the neighbors that the fixed-step method needs anyway. The maximum is a collective operation, not a single exchange: computed by flooding, it takes as many neighbor-to-neighbor rounds as the graph's diameter, which is why the paper's communication model lists it as a separate primitive.
Two consequences follow from the stepsizes never increasing. First, the line search cannot run away: the test is guaranteed to pass once is below an explicit value built from the constants (a sufficient condition the paper proves). So agent only ever rejects trials above , each at most times the previous one: an agent whose initial guess is already at or below its threshold, , rejects nothing, and otherwise it rejects at most trials over the entire run. Its stepsize can still be pushed below by cuts that other agents force through the synchronization; since all stepsizes shrink by the same factor, , and the common factor only grows while some agent is above its own threshold, the floor is : the individual for the proportional start , and for a common start (the first branch when , the second otherwise). It is a bound, not a prediction: a run in which no cut occurs keeps its stepsize at , which can exceed it. Second, the theory for the fixed-step method goes through with the adaptive stepsizes (the paper's main theorem): the weighted ergodic averages , stacked into , satisfy
for any initial stepsizes , where is the componentwise positive part (for a conic constraint the paper's statement has the distance to in its place) and an optimal multiplier of the consensus constraints; and the iterates themselves converge to a primal–dual solution. The method the agents run needs , the 's, , a guess and, for nonlinear constraints, the dual radius ; it needs no Lipschitz constant. Without constraints () the test loses its Jacobian terms, is set to , and the paper calls the result D-APDB-0.
Twelve agents in the plane
The playground sets this up where it can be seen. Twelve agents sit on a random cycle with twelve random chords. Agent 's loss is a quadratic with its own minimizer and its own curvature; its is the indicator of a box ; its constraint is an ellipse. The feasible region is the intersection of the twelve ellipses with a box, the agents' minimizers lie outside it, and the solution sits on its boundary, where on this instance one agent's constraint binds (occasionally two do). Every agent starts from a different random point. D-APDB is started from the same guess for every agent, with and as in the paper's experiments; D-APD runs with the safe stepsizes computed from the true constants, with the dual radius taken from a Slater point by weak duality, the way one would in practice; and a third run takes D-APDB's initial stepsize and never tests it. The comparison with D-APD is not one between equals, since D-APD is given the constants and D-APDB is not; it is there to show what the local tests find relative to what the constants would certify, and what that costs and buys. One caution about the curves: they are last-iterate diagnostics of the network average , namely the relative suboptimality with , the consensus error and the violation , which is what one watches in practice; the theorem above bounds different quantities, the weighted temporal averages and the multiplier-weighted residuals, and the playground spells out the relation between the two.
Three things happen in the picture. The untested step, fifteen times the largest safe stepsize, looks healthy for some nine hundred iterations, until the active constraint's multiplier has built up; then the primal–dual coupling turns out to be unstable at that stepsize, the agents fly apart to the walls of the box, and the consensus error jumps by four orders of magnitude and never recovers. D-APDB rejects the same stepsize at iteration 0, through the constraint terms of its test and from local quantities only, nine hundred iterations before any symptom (a rejected sufficient condition does not by itself prove that a fixed stepsize must fail, and smaller untested stepsizes do converge here; on this instance the rejected one fails); it cuts the stepsize once, from to , and never again, and from then on every agent runs with a step three to five times the safe one, which the first hundred iterations show. And D-APD, started with the safe steps, is slower early and faster late, overtaking after about 250 iterations and finishing an order of magnitude ahead. Over the playground's instances 1–30 with its opening controls the picture is the same: the cutting happens in a single iteration in every run, D-APDB has the lower relative suboptimality at iteration 100 in 29 runs and D-APD has it at iteration 3,000 in 26, and the final stepsizes are approximately 1.2 to 5.3 times the safe ones. The last point has a specific cause, shown in the second figure.
The left panel shows the line search doing what it should. Started from twenty times the safe values, the agents' stepsizes are cut once and remain in proportion to their own curvatures, about twice the safe values; started from a common value, they are cut three times, at iterations 0, 9 and 73, each time because some agent's step turned into its stiff direction, and they all end at the value the agent that forced the last cut could accept, , below the safe stepsizes of nine of the twelve agents, because the synchronization makes every agent share the worst cut (the floor above only promises here). The right panel shows the price of the start. Four runs from end at : the accepted values lie on the geometric grid of each start, so they are close but not equal, and for these four starts the test lands near the same stepsize (a start below the value the test would accept is never raised, since stepsizes only decrease, so this cannot hold for arbitrarily small guesses). But they converge at very different speeds, and the one with the smallest start is fastest, the opposite of what a line search is meant to deliver. The reason is : the scale of the consensus stepsize is fixed from the initial guess ( itself only changes with , and after the last cut equals ), so an optimistic guess that the test corrects at the first iteration still leaves the agents pulling toward each other with a stepsize that is ten or thirty times smaller than it would otherwise be. On this problem that pull is the bottleneck, so a large costs more in consensus than it gains in the primal step. The safe steps of D-APD, being small, come with a large , which is why D-APD finishes ahead in the first figure; started from , D-APDB finishes ahead of D-APD in 22 of those 30 instances.
This is also why the comparison in the plane is close, while in the paper's experiments it is not. In two dimensions the constants are not very pessimistic: the Jacobian bound over the box and the Slater-point dual bound put the safe stepsize at about a quarter of what the line search finds (the box matters: at the safe stepsizes have medians , , , the dual radius binding at the small box and the Jacobian bound at the larger ones, while D-APDB's does not move on this instance). In the paper's twenty-dimensional QCQPs the dual bound and the Jacobian bound over a twenty-dimensional box enter the safe stepsize, and D-APDB, started from twenty times it, brings the consensus error and the constraint violation down to about within three thousand gradient calls per node while the fixed-step method is still oscillating orders of magnitude higher in consensus error (the paper's first figure). The mechanism is the same; the room between the certified constant and the local truth is what differs. That room can grow with the dimension, and between these two examples it does, because the constants are bounds over the whole box and over all admissible multipliers, and both loosen as the box acquires corners far from where the iterates travel; two examples illustrate the mechanism, they do not establish a law.
What to take from it
The construction has two parts that are worth remembering separately. Reordering the primal–dual updates so that the coupling multipliers are formed from finished iterates is what makes a local test possible at all; it is a change to the algorithm, and the rates keep their order. Synchronizing the momentum through the maximum of the agents' shrink factors is what makes the local tests add up to a convergent method; it costs one scalar consensus per iteration and makes every agent as conservative as the least fortunate one in that iteration. What is bought is an accelerated primal–dual method for constrained consensus problems whose stepsizes involve no Lipschitz constant and no dual bound (for nonlinear constraints a bound on the multipliers is still used, but only as the radius of the dual projection), which keeps the guarantees and provably wastes only a logarithmic number of trials. What is not bought, as the second figure shows, is freedom from the initial guess: in the analysis the consensus stepsize is tied to , and whether it can be allowed to follow the stepsizes the agents actually settle on is a question the playground makes easy to ask.
The same philosophy, a backtracking rule in place of a Lipschitz constant, with a complexity bound that counts the extra trials, appears in our stochastic gradient descent–ascent method with backtracking for nonconvex–concave minimax problems, on a single machine. The network is what makes the present case different, and the one number it shares per iteration is the difference.
Comments and corrections are welcome by email. More notes on the notes index, or subscribe via RSS.