Mert Gürbüzbalaban

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.

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 NN agents on a connected undirected graph G=(N,E)\mathcal G = (\mathcal N, \mathcal E). Agent ii holds a smooth convex loss fi:Rn→Rf_i: \mathbb R^n \to \mathbb R, a proper closed convex function ϕi\phi_i with an easy proximal map and a compact domain (the indicator of a compact simple set, or an ℓ1\ell_1 norm added to one; a bare ℓ1\ell_1 norm on all of Rn\mathbb R^n is outside the paper's assumptions), and a constraint gi(x)≤0g_i(x) \le 0 given by a convex map gi:Rn→Rmig_i: \mathbb R^n \to \mathbb R^{m_i} with Lipschitz Jacobian. (The paper allows −gi(x)∈Ki-g_i(x) \in \mathcal K_i for a closed convex cone Ki\mathcal K_i, which covers conic constraints; this note keeps to inequalities, the case Ki=R+mi\mathcal K_i = \mathbb R^{m_i}_+.) For a vector-valued constraint, ∇gi(x)=[∇gi,1(x),…,∇gi,mi(x)]∈Rn×mi\nabla g_i(x) = [\nabla g_{i,1}(x), \dots, \nabla g_{i,m_i}(x)] \in \mathbb R^{n \times m_i} denotes the matrix of component gradients, the transpose of the Jacobian, so that ∇gi(x) θi∈Rn\nabla g_i(x)\,\theta_i \in \mathbb R^n for a multiplier θi∈Rmi\theta_i \in \mathbb R^{m_i}; vector norms are Euclidean and matrix norms spectral. Writing φi=ϕi+fi\varphi_i = \phi_i + f_i, the network must solve

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

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 Rn\mathbb R^n across the edges of the graph and can compute the maximum of NN scalars, one held by each agent, so that every agent learns it. Each ϕi\phi_i has a compact domain, and each fif_i has an LfiL_{f_i}-Lipschitz gradient on that domain. Each gig_i is convex with a Jacobian that is LgiL_{g_i}-Lipschitz and bounded by CgiC_{g_i} on that domain. And a primal–dual solution (x⋆,θ⋆)(x^\star, \theta^\star) exists, with a known radius Bi>0B_i > 0 satisfying Bi≥2∥θi⋆∥B_i \ge 2\|\theta_i^\star\| for every ii whose gig_i is not affine. (The paper's assumption writes only the inequality; the radius must also be positive, because when θi⋆=0\theta_i^\star = 0 a zero radius would be allowed, and it pins the multiplier at zero. For example, take fi≡0f_i \equiv 0, ϕi\phi_i the indicator of [−2,2][-2, 2] and gi(x)=x2−1g_i(x) = x^2 - 1 at every agent, with Bi=0B_i = 0, every agent started at xi0=2x_i^0 = 2 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 22, and both increments are zero so every test passes; every iterate stays at 22 although gi(2)=3g_i(2) = 3. A positive radius leaves the margin Bi−∥θi⋆∥≥Bi/2B_i - \|\theta_i^\star\| \ge B_i/2 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 xi∈Rnx_i \in \mathbb R^n, stacked into x=(x1,…,xN)∈RnN\mathbf x = (x_1, \dots, x_N) \in \mathbb R^{nN}, and demanding xi=xjx_i = x_j across every edge, which reads Ax=0A\mathbf x = 0 for A=H⊗InA = H \otimes I_n with H∈R∣E∣×NH \in \mathbb R^{|\mathcal E| \times N} the oriented edge–node incidence matrix of the graph, turns this into a saddle-point problem: a Lagrangian with a multiplier θi∈R+mi\theta_i \in \mathbb R^{m_i}_+ for each agent's constraint and a multiplier λij∈Rn\lambda_{ij} \in \mathbb R^n for each edge's consensus constraint, stacked into λ∈Rn∣E∣\lambda \in \mathbb R^{n|\mathcal E|}. 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 θi\theta_i; the edge multipliers are updated from the disagreement between neighbors. Convergence requires the primal stepsize τi\tau_i, the dual stepsize σi\sigma_i and the consensus stepsize γ\gamma to satisfy inequalities involving LfiL_{f_i}, LgiL_{g_i}, CgiC_{g_i} and BiB_i. 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, ∥λk+1−λk∥2\|\lambda^{k+1} - \lambda^k\|^2, and in the standard update order λk+1=λk+γAxk+1\lambda^{k+1} = \lambda^k + \gamma A\mathbf x^{k+1} is computed from the new primal iterates. Expanded over the graph,

∥λk+1−λk∥2=γ2∑i∈N⟨xik+1, ∑j∈Ni(xik+1−xjk+1)⟩,\|\lambda^{k+1} - \lambda^k\|^2 = \gamma^2 \sum_{i \in \mathcal N} \Big\langle x_i^{k+1},\ \sum_{j \in \mathcal N_i} \big(x_i^{k+1} - x_j^{k+1}\big) \Big\rangle ,

so agent ii's test involves the neighbors' accepted candidates xjk+1x_j^{k+1}, which in turn depend on their tests, which involve xik+1x_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:

λk+1=λk+γkA((1+ηk) xk−ηkxk−1).\lambda^{k+1} = \lambda^k + \gamma^k A\big((1 + \eta^k)\,\mathbf x^k - \eta^k \mathbf x^{k-1}\big).

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 λk+1\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 sis_i with sik+1=sik+γk((1+ηk)xik−ηkxik−1)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 ∑j∈Ni(si−sj)\sum_{j \in \mathcal N_i}(s_i - s_j), which together with its own constraint's pull ∇gi(xi) θi\nabla g_i(x_i)\,\theta_i makes up the vector rir_i it extrapolates.

The test, and the one number the network shares

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

Eik(x~,θ~)≤−δτ~∥x~−xik∥2−δσ~∥θ~−θik∥2,E_i^k(\tilde x, \tilde\theta) \le -\frac{\delta}{\tilde\tau}\|\tilde x - x_i^k\|^2 - \frac{\delta}{\tilde\sigma}\|\tilde\theta - \theta_i^k\|^2 ,

where EikE_i^k adds up a descent-lemma term, 2(fi(x~)−fi(xik)−⟨∇fi(xik),x~−xik⟩)−1−cτ~∥x~−xik∥22\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 τ~≤(1−δ−c)/L\tilde\tau \le (1 - \delta - c)/L with LL the curvature in the direction of the step, and two terms that measure the constraint's Jacobian at the candidate, 2τ~cα∥∇gi(x~)(θ~−θik)∥2\tfrac{2\tilde\tau}{c_\alpha}\|\nabla g_i(\tilde x)(\tilde\theta - \theta_i^k)\|^2 and τ~cβ∥(∇gi(x~)−∇gi(xik)) θik∥2\tfrac{\tilde\tau}{c_\beta}\|(\nabla g_i(\tilde x) - \nabla g_i(x_i^k))\,\theta_i^k\|^2, against the dual progress 1σ~∥θ~−θik∥2\tfrac{1}{\tilde\sigma}\|\tilde\theta - \theta_i^k\|^2. Here δ,cα,cβ,cς>0\delta, c_\alpha, c_\beta, c_\varsigma > 0 are constants of the user's choosing with c=cα+cβ+cς<1−δc = c_\alpha + c_\beta + c_\varsigma < 1 - \delta, the dual stepsize is tied to the primal one by σ~=ζiτ~\tilde\sigma = \zeta_i \tilde\tau for a fixed ζi>0\zeta_i > 0, and if the test fails, τ~←ρτ~\tilde\tau \leftarrow \rho\tilde\tau for a fixed ρ∈(0,1)\rho \in (0, 1) 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 Bi>0B_i > 0, which must satisfy Bi≥2∥θi⋆∥B_i \ge 2\|\theta_i^\star\| when gig_i is not affine (an affine constraint needs none), appears in the method only as the radius of the ball onto which θi\theta_i 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 ii's search returns a factor ηi≥1\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 tkt_k that make the rates work are defined through t0=1t_0 = 1 and tk+1=tk/ηk+1t_{k+1} = t_k/\eta^{k+1}. So the network computes

ηk=max⁡i∈Nηi\eta^k = \max_{i \in \mathcal N} \eta_i

by a max-consensus, and every agent sets τik=τik−1/ηk\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 ηk\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 γk\gamma^k is set from ηk\eta^k and from τˉ=max⁡iτˉi\bar\tau = \max_i \bar\tau_i, the largest initial guess, as γk=cγτˉ(2cα+ηkcς)−1\gamma^k = \tfrac{c_\gamma}{\bar\tau}\big(\tfrac{2}{c_\alpha} + \tfrac{\eta^k}{c_\varsigma}\big)^{-1} with 0<cγ≤1/(2∣E∣)0 < c_\gamma \le 1/(2|\mathcal E|). 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 τ~\tilde\tau is below an explicit value τ^i\hat\tau_i built from the constants (a sufficient condition the paper proves). So agent ii only ever rejects trials above τ^i\hat\tau_i, each at most ρ\rho times the previous one: an agent whose initial guess is already at or below its threshold, τˉi≤τ^i\bar\tau_i \le \hat\tau_i, rejects nothing, and otherwise it rejects at most ⌈log⁡1/ρ(τˉi/τ^i)⌉\lceil \log_{1/\rho}(\bar\tau_i/\hat\tau_i) \rceil trials over the entire run. Its stepsize can still be pushed below ρτ^i\rho\hat\tau_i by cuts that other agents force through the synchronization; since all stepsizes shrink by the same factor, τik=τˉi/qk\tau_i^k = \bar\tau_i/q_k, and the common factor qkq_k only grows while some agent is above its own threshold, the floor is τik≥τˉimin⁡{1,ρmin⁡jτ^j/τˉj}\tau_i^k \ge \bar\tau_i \min\{1, \rho \min_j \hat\tau_j/\bar\tau_j\}: the individual ρτ^i\rho\hat\tau_i for the proportional start τˉi=20τ^i\bar\tau_i = 20\hat\tau_i, and min⁡{τˉ,ρmin⁡jτ^j}\min\{\bar\tau, \rho \min_j \hat\tau_j\} for a common start τˉ\bar\tau (the first branch when τˉ≤ρmin⁡jτ^j\bar\tau \le \rho\min_j \hat\tau_j, the second otherwise). It is a bound, not a prediction: a run in which no cut occurs keeps its stepsize at τˉ\bar\tau, 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 xˉiK=∑k=0K−1tkxik/∑k=0K−1tk\bar x_i^K = \sum_{k=0}^{K-1} t_k x_i^k \big/ \sum_{k=0}^{K-1} t_k, stacked into xˉK\bar{\mathbf x}^K, satisfy

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

for any initial stepsizes τˉi>0\bar\tau_i > 0, where (⋅)+(\cdot)_+ is the componentwise positive part (for a conic constraint the paper's statement has the distance to −Ki-\mathcal K_i in its place) 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 cc's, ρ\rho, a guess τˉi\bar\tau_i and, for nonlinear constraints, the dual radius BiB_i; it needs no Lipschitz constant. Without constraints (gi≡0g_i \equiv 0) the test loses its Jacobian terms, cβc_\beta is set to 00, 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 ii's loss is a quadratic 12(x−ai)⊤Qi(x−ai)\tfrac12(x - a_i)^\top Q_i (x - a_i) with its own minimizer aia_i and its own curvature; its ϕi\phi_i is the indicator of a box [−R,R]2[-R, R]^2; 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 x⋆x^\star 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 τˉ=1\bar\tau = 1 for every agent, with δ=cα=cβ=cς=0.1\delta = c_\alpha = c_\beta = c_\varsigma = 0.1 and ρ=0.9\rho = 0.9 as in the paper's experiments; D-APD runs with the safe stepsizes τ^i\hat\tau_i computed from the true constants, with the dual radius Bi=2φ(xs)/(−gi(xs))B_i = 2\varphi(x_s)/(-g_i(x_s)) taken from a Slater point xsx_s 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 xˉk=1N∑ixik\bar x^k = \tfrac1N \sum_i x_i^k, namely the relative suboptimality ∣φ(xˉk)−φ⋆∣/∣φ⋆∣|\varphi(\bar x^k) - \varphi^\star|/|\varphi^\star| with φ=∑iφi\varphi = \sum_i \varphi_i, 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 violation max⁡i(gi(xˉk))+\max_i (g_i(\bar x^k))_+, which is what one watches in practice; the theorem above bounds different quantities, the weighted temporal averages xˉiK\bar x_i^K and the multiplier-weighted residuals, and the playground spells out the relation between the two.

Left: the plane with twelve faint ellipses whose intersection is shaded, the level sets of the total loss around its unconstrained minimizer, twelve plus marks for the agents' own minimizers, and the agents' trails converging from scattered starts to a point marked x* on the boundary of the feasible region. Right: three log-log plots against iterations, of relative suboptimality, consensus error and constraint violation, for D-APDB, D-APD and the untested fixed step; the untested step loses stability after about nine hundred iterations, D-APDB descends first and D-APD overtakes it after about 250 iterations.
The playground's opening instance. Left: the agents' ellipses, their intersection, the level sets of the total loss, the agents' own minimizers (+), and D-APDB's trails from the starting points (rings) to x*. Right: the paper's three measures for the network average, over 3,000 iterations.

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 11 to 0.210.21, 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.

Left: on log-log axes, the stepsizes of twelve agents against iterations for an unconstrained problem with curvatures spread over a factor of a hundred; dashed horizontal lines mark each agent's safe stepsize; thin red lines, started at twenty times the safe values, are cut once at the start and stay about twice the safe values in proportion; a thick line started from a common value ten is cut three times and ends below most of the safe values. Right: relative suboptimality against iterations for D-APDB started from 0.3, 1, 3 and 10, all of which end at a stepsize near 0.21, and for D-APD; the run from 0.3 is the fastest, the ones from 3 and 10 stall near 0.1.
Left: what the line search settles on, in the unconstrained variant with curvatures spread over a factor 100. Right: four D-APDB runs on the constrained instance that differ only in the start τ̄, and D-APD; every D-APDB run ends near the same stepsize (0.197 to 0.225), and the runs differ mainly through the consensus stepsize γ.

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, 0.650.65, 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 min⁡{τˉ,ρmin⁡jτ^j}=0.32\min\{\bar\tau, \rho\min_j \hat\tau_j\} = 0.32 here). The right panel shows the price of the start. Four runs from τˉ=0.3,1,3,10\bar\tau = 0.3, 1, 3, 10 end at τ=0.197,0.206,0.215,0.225\tau = 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, 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 γk∝1/τˉ\gamma^k \propto 1/\bar\tau: the scale of the consensus stepsize is fixed from the initial guess (γk\gamma^k itself only changes with ηk\eta^k, and after the last cut equals cγ/(τˉ(2/cα+1/cς))c_\gamma/(\bar\tau(2/c_\alpha + 1/c_\varsigma))), 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 τˉ\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.30.3, 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 R=5,10,20R = 5, 10, 20 the safe stepsizes have medians 0.060.06, 0.050.05, 0.0250.025, the dual radius binding at the small box and the Jacobian bound at the larger ones, while D-APDB's 0.210.21 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 10−410^{-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. 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 O(1/K)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.

Comments and corrections are welcome by email. More notes on the notes index, or subscribe via RSS.