A line search without a leader

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 $N$ agents on a connected graph $\mathcal G = (\mathcal N, \mathcal E)$. Agent $i$ holds a smooth convex loss $f_i$, a convex function $\phi_i$ with an easy proximal map (an indicator of a simple set, an $\ell_1$ norm), and a constraint $g_i(x) \le 0$ given by a convex map with Lipschitz Jacobian. The network must solve

Giving every agent its own copy $x_i$ and demanding $x_i = x_j$ across every edge turns this into a saddle-point problem: a Lagrangian with a multiplier $\theta_i$ for each agent's constraint and a multiplier $\lambda_{ij}$ for each edge's consensus constraint. 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 $\eta$, and then takes a dual ascent step on $\theta_i$; the edge multipliers are updated from the disagreement between neighbors. Convergence requires the primal stepsize $\tau_i$, the dual stepsize $\sigma_i$ and the consensus stepsize $\gamma$ to satisfy inequalities involving $L_{f_i}$, $L_{g_i}$, a bound $C_{g_i}$ on the Jacobian of $g_i$ over the domain, and a bound $B_i$ on $\theta_i^\star$. 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, $\|\lambda^{k+1} - \lambda^k\|^2$, and in the standard update order $\lambda^{k+1} = \lambda^k + \gamma A\mathbf x^{k+1}$ is computed from the new primal iterates. Expanded over the graph,

so agent $i$'s test involves the neighbors' accepted candidates $x_j^{k+1}$, which in turn depend on their tests, which involve $x_i^{k+1}$. 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 $\lambda^{k+1}$ 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 $\lambda$ at all. Each keeps a vector $s_i$ with $s_i^{k+1} = s_i^k + \gamma^k((1+\eta^k) x_i^k - \eta^k x_i^{k-1})$, exchanges it with its neighbors, and the only thing it needs from the edge multipliers is the pull $\sum_{j \in \mathcal N_i}(s_i - s_j)$, which together with its own constraint's pull $\nabla g_i(x_i)\,\theta_i$ makes up the vector $r_i$ it extrapolates.

The test, and the one number the network shares

With that order fixed, agent $i$ at iteration $k$ tries the stepsize $\tilde\tau = \tau_i^{k-1}$ it used last time, with momentum $\eta_i = \tau_i^{k-1}/\tilde\tau$, computes the candidate pair $(\tilde x, \tilde\theta)$, and accepts it if

where $E_i^k$ adds up a descent-lemma term, $2\big(f_i(\tilde x) - f_i(x_i^k) - \langle \nabla f_i(x_i^k), \tilde x - x_i^k\rangle\big) - \tfrac{1-c}{\tilde\tau}\|\tilde x - x_i^k\|^2$, which a quadratic passes as soon as $\tilde\tau \le (1 - \delta - c)/L$ with $L$ the curvature in the direction of the step, and two terms that measure the constraint's Jacobian at the candidate, $\tfrac{2\tilde\tau}{c_\alpha}\|\nabla g_i(\tilde x)(\tilde\theta - \theta_i^k)\|^2$ and $\tfrac{\tilde\tau}{c_\beta}\|(\nabla g_i(\tilde x) - \nabla g_i(x_i^k))\,\theta_i^k\|^2$, against the dual progress $\tfrac{1}{\tilde\sigma}\|\tilde\theta - \theta_i^k\|^2$. Here $c = c_\alpha + c_\beta + c_\varsigma$ and $\delta$ are small constants of the user's choosing with $\delta + c < 1$, and $\tilde\sigma = \zeta\tilde\tau$. If the test fails, $\tilde\tau \leftarrow \rho\tilde\tau$ 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 bound $B_i$ appears in the method only as the radius onto which $\theta_i$ is projected; a loose bound leaves the iterates untouched there, whereas in the fixed-step method it enters the stepsize.

Now the coupling. Agent $i$'s search returns a factor $\eta_i \ge 1$ 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 $t_k$ that make the rates work are defined through $t_{k+1} = t_k/\eta^{k+1}$. So the network computes

by a max-consensus, and every agent sets $\tau_i^k = \tau_i^{k-1}/\eta^k$. An agent whose own test had passed now takes a smaller step than it needed to, and recomputes its update with the common $\eta^k$; 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 $\gamma^k$ is set from $\eta^k$ and from $\bar\tau = \max_i \bar\tau_i$, the largest initial guess, as $\gamma^k = \tfrac{c_\gamma}{\bar\tau}\big(\tfrac{2}{c_\alpha} + \tfrac{\eta^k}{c_\varsigma}\big)^{-1}$ with $c_\gamma \le 1/(2|\mathcal E|)$. That is the whole synchronization: one scalar per iteration, on top of the one vector exchange with the neighbors that the fixed-step method needs anyway.

Two consequences follow from the stepsizes never increasing. First, the line search cannot run away: the test is guaranteed to pass once $\tilde\tau$ is below an explicit value $\hat\tau_i$ built from the constants (a sufficient condition the paper proves), so $\tau_i^k \ge \rho\,\hat\tau_i$ forever, and the number of trials agent $i$ rejects over the entire run is at most $\log_{1/\rho}\lceil \bar\tau_i/\hat\tau_i \rceil + 1$. Second, the theory for the fixed-step method goes through with the adaptive stepsizes (the paper's main theorem): the weighted ergodic averages $\bar x_i^K = \sum_{k<K} t_k x_i^k / \sum_{k<K} t_k$ satisfy

for any initial stepsizes $\bar\tau_i > 0$, where $d_{-\mathcal K_i}$ is the distance to the constraint cone (for a scalar inequality, the positive part of $g_i$) and $\lambda^\star$ an optimal multiplier of the consensus constraints; and the iterates themselves converge to a primal–dual solution. The method the agents run needs $\delta$, the $c$'s, $\rho$ and a guess $\bar\tau_i$; it needs no Lipschitz constant. Without constraints ($g_i \equiv 0$) the test loses its Jacobian terms 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 $i$'s loss is a quadratic $\tfrac12(x - a_i)^\top Q_i (x - a_i)$ with its own minimizer $a_i$ and its own curvature; its $\phi_i$ is the indicator of a box $[-R, R]^2$; its constraint is an ellipse. The feasible region is the intersection of the twelve ellipses, the agents' minimizers lie outside it, and the solution $x^\star$ sits on the boundary where one agent's constraint binds. Every agent starts from a different random point. D-APDB is started from the same guess $\bar\tau = 1$ for every agent, with $\delta = c_\alpha = c_\beta = c_\varsigma = 0.1$ and $\rho = 0.9$ as in the paper's experiments; D-APD runs with the safe stepsizes $\hat\tau_i$ computed from the true constants, with the dual bound taken from a Slater point 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.

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; it cuts the stepsize once, from $1$ to $0.21$, and never again, and from then on every agent runs with a step three to five times the safe one, which the first two 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 thirty random instances the picture is the same: one failed test per run, final stepsizes two to four times the safe ones, D-APDB ahead at iteration 100 in all but one instance and D-APD ahead at iteration 3,000 in most. 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 end at the stiffest agent's value, because the synchronization makes every agent share the worst cut. The right panel shows the price of the start. Four runs from $\bar\tau = 0.3, 1, 3, 10$ all end at $\tau$ between $0.20$ and $0.23$: the test finds the same stepsize whatever the guess. 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 $\gamma^k \propto 1/\bar\tau$: the consensus stepsize is fixed from the initial guess, and 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 $\bar\tau$ costs more in consensus than it gains in the primal step. The safe steps of D-APD, being small, come with a large $\gamma$, which is why D-APD finishes ahead in the first figure; started from $0.3$, D-APDB finishes ahead of D-APD in most 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 $R = 5, 10, 20$ the safe stepsizes have medians $0.10$, $0.05$, $0.025$, while D-APDB's $0.21$ does not move). 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 $10^{-4}$ 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, and it grows with the dimension.

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 that runs without any Lipschitz constant or dual bound entering the stepsizes, keeps the $O(1/K)$ 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 $\bar\tau$, 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.