Decentralized Quasi-Newton Methods

II. PROBLEM FORMULATION

• Distributed optimization assumes agents can compute local gradient components using their own and neighboring variables, enabling neighborhood-based updates.Consensus problems can be reformulated to obtain distributedly computable gradients, including through penalties or dual-domain gradient ascent.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

• The paper introduces D-BFGS, a gradient-based curvature approximation that can operate synchronously or asynchronously without computing Hessians.It proves convergence for convex functions and linear convergence for strongly convex functions in both formulations.Source: §I · p. 1
• The asynchronous formulation lets nodes use possibly outdated local-memory values, avoiding the synchronization cost of three exchanges per synchronous iteration.Its convergence analysis assumes a bound on how many iterations information takes to reach neighbors’ local memories.Source: §I · pp. 1–2

A. Gradient descent and BFGS

• Gradient descent methods can converge slowly, while distributed Hessian use requires problem-specific assumptions and challenges.Approximate Newton methods can converge faster, but the Hessian inverse needed for Newton’s method is generally not locally computable.Source: §I · p. 1, A. Gradient descent and BFGS · p. 2
• Standard BFGS chooses curvature updates to satisfy a secant condition using successive variable and gradient differences.The condition is motivated by the Hessian’s behavior for small variable changes; a positive definite update requires v(t)^T r(t) > 0, which holds for strongly convex objectives.Source: A. Gradient descent and BFGS · p. 2
• Standard BFGS is not directly distributable because its curvature matrices lack suitable sparsity and its update requires a global inner product.D-BFGS modifies the curvature approximation to make the descent direction distributedly computable.Source: A. Gradient descent and BFGS · pp. 2–3

III. DECENTRALIZED BFGS

• Each node locally approximates the curvature of its own and neighboring cost functions to compute its descent direction.The update maintains a secant condition while allowing decentralized computation.Source: §III · p. 3
• Modified neighborhood variable and gradient variations let each node update a local Hessian approximation using information accessible through its neighbors.The variable variation is normalized, and the gradient variation subtracts γ times that modified variable variation.Source: §III · p. 3
• The local curvature update regularizes the secant condition, with the log-determinant formulation enforcing eigenvalues greater than γ.A feasible update requires the modified variable and gradient variations to have positive inner product.Source: §III · p. 3
• At each iteration, nodes exchange descent components, update local variables and gradients, then compute neighborhood variations for the next curvature estimate.Each node combines its locally computed descent component with components received from neighbors.Source: §III · p. 3
• The algorithm uses neighborhood curvature matrices and gradients to form descent directions, sending each neighbor the component intended for that node.Figure 1 depicts variable and gradient exchanges used to build curvature estimates and compute these descent components.Source: Figure 1 · p. 4, §III · p. 4

A. Secant condition in D-BFGS

• The aggregate descent matrix H(t) satisfies the global secant condition, preserving the condition used by centralized BFGS.The local matrices are selected so the overall update meets that condition.Source: A. Secant condition in D-BFGS · p. 4
• Each node’s sparse global representation combines its neighborhood curvature approximation, and summing these local relations yields the overall secant relation.The proof represents each neighborhood approximation as a block-sparse matrix before combining the node-level relations.Source: A. Secant condition in D-BFGS · p. 4
• The regularized update modifies gradient and variable variations to compensate for γI, preserving the secant condition after regularization.Γ is used to prevent stalling if eigenvalues of the inverse local approximation become too small.Source: A. Secant condition in D-BFGS · p. 4
• A local update requires a positive inner product between neighborhood variations, so the method may skip an update when this condition fails.The paper notes that this requirement restricts the functions handled by D-BFGS.Source: A. Secant condition in D-BFGS · p. 4

IV. ASYNCHRONOUS D-BFGS

• Nodes update when available using locally stored neighbor information, which can reflect earlier variable and gradient states.The model bounds how many iterations it takes for information to reach neighbors’ local memory.Source: §IV · pp. 4–5
• At each available update, a node applies received descent directions, updates its variable and gradient, then computes its next local D-BFGS quantities and direction.The local update matrices follow the same formulas as in the synchronous setting.Source: §IV · p. 5
• Asynchronous D-BFGS uses one communication round per time iteration, removing the coordination required by the synchronous algorithm’s three rounds.The computation order is rearranged for the asynchronous setting.Source: §IV · p. 5
• The virtual global update is algorithmically equivalent to the physical updates performed by all nodes.It accounts for descent directions that have finished computing, even when a receiving node is busy.Source: §IV · p. 5

V. CONVERGENCE ANALYSIS

• A twice-differentiable objective with nonnegative Hessian eigenvalues bounded above by L is convex and has an L-Lipschitz gradient.The analysis uses this condition for its convex-function convergence case.Source: §V · p. 6
• When Hessian eigenvalues are bounded between positive μ and L, the objective is strongly convex and stronger convergence properties can be established.The paper identifies this as a separate assumption for the strongly convex case.Source: §V · p. 6
• The analysis assumes positive inner products between modified neighborhood variable and gradient variations, a condition required for well-defined local Hessian approximations.The authors note this condition may not hold in practice, but use it to simplify the analysis.Source: §V · p. 6

A. Synchronous convergence

• Synchronous analysis bounds the eigenvalues of the regularized Hessian inverse approximation, H(t) + ΓI, uniformly.H(t) is built from the nodes' local Hessian inverse approximations; its positive semidefinite components yield a lower bound, while γ bounds the local matrices above.Source: A. Synchronous convergence · p. 6
• For convex, non-strongly-convex objectives, synchronous D-BFGS reduces the objective error at least at rate o(1/t) under Assumptions 1 and 3 and a suitable stepsize.The stepsize must satisfy ǫ(t) < 2Γ/(L∆2).Source: A. Synchronous convergence · p. 6
• Under Assumptions 2 and 3 and a suitable stepsize, synchronous D-BFGS converges at least linearly for strongly convex objectives.The stepsize must satisfy ǫ(t) < 2Γ/(L∆2).Source: A. Synchronous convergence · pp. 6–7

B. Asynchronous convergence

• Under Assumptions 1, 3, and 4, asynchronous D-BFGS admits a stepsize for which the gradient converges to zero.Assumption 4 bounds the asynchronicity: nodes are at most B iterations out of sync and communication delays are bounded by B.Source: B. Asynchronous convergence · p. 7
• With Assumptions 2, 3, and 4 and a suitable stepsize, asynchronous D-BFGS converges linearly; its gradient error is bounded in terms of stale information.The error bound is proportional to the maximum distance between the optimum and earlier variable states.Source: B. Asynchronous convergence · p. 7

VI. CONSENSUS OPTIMIZATION

• The shared-variable objective, with each local function available at one node, is reformulated using local variables constrained to agree across nodes.A matrix Z = W ⊗ I_p encodes the agreement constraint through (I − Z)x = 0, given the stated properties of W.Source: §VI · p. 7
• The agreement constraint can be handled either by a primal-domain penalty or by ascending in the dual domain.The paper develops these two routes to obtain the structure needed for decentralized optimization.Source: §VI · p. 8

A. Primal domain penalty methods

• The primal penalty is quadratic and pushes the solution toward the feasible agreement space; the penalized and constrained solutions differ by order α.α is the penalty coefficient.Source: A. Primal domain penalty methods · p. 8
• Neighbor exchanges make the penalty gradients locally computable, supporting synchronous or asynchronous quasi-Newton implementations.The resulting method uses local curvature estimation, which the passage says yields faster convergence.Source: A. Primal domain penalty methods · p. 8

B. Dual ascent methods

• D-BFGS uses the dual-function gradient, locally computable from neighboring variables, in synchronous and asynchronous quasi-Newton dual ascent.The dual gradient is the constraint slack evaluated at the Lagrangian minimizers.Source: B. Dual ascent methods · p. 8

A. Synchronous algorithms

• D-BFGS reaches average error 3×10^-4 by iteration 200, versus 0.06 for ADMM and 0.6 for DD; its exchange-time advantage over ADMM grows from 2× to 10× as condition number rises from 1 to 100.D-BFGS requires twice as many communications per iteration as ADMM and DD.Source: A. Synchronous algorithms · p. 9, Figure 2 · p. 9, Figure 3 · p. 9
• D-BFGS reaches average error 0.015 by iteration 100, while DGD reaches 0.32 by iteration 200; across 1,000 realizations, exchange-time differences are about 5× for both tested condition numbers.D-BFGS requires three local information exchanges per iteration, compared with one for DGD.Source: A. Synchronous algorithms · p. 9, Figure 4 · p. 9, Figure 5 · p. 9

B. Logistic regression

• D-BFGS reaches gradient magnitude 1.3×10^-6 before iteration 200, compared with 9.1×10^-5 for DGD, on the simulated logistic-regression problem.The data are generated to be linearly separable, with 100 samples assigned to each node.Source: B. Logistic regression · p. 10, Figure 6 · p. 10

C. Asynchronous algorithms

• At σ = 0.01, asynchronous D-BFGS reaches average error 2.4×10−3 by iteration 200, versus 5.1×10−2 for DD; at σ = 0.3, larger drift does not substantially change either method’s convergence time.Source: C. Asynchronous algorithms · p. 10

VIII. CONCLUSIONS

• The paper concludes that D-BFGS approximates each node's and its neighbors' curvature, with analytical results for synchronous and asynchronous versions and numerical improvements over alternatives on two consensus optimization problems.The reported numerical evaluations use both dual and primal domains.Source: §VIII · p. 10

APPENDIX A: PROOF OF THEOREM 1

• The convex-case proof combines a descent inequality with convexity and distance-to-minimizer bounds to establish the objective-error result.The proof refers to Proposition 1.3.3 in for the final sequence argument.Source: Appendix A · pp. 10–11
• For the convex case, the proof concludes that the objective error satisfies e(t) = o(1/t).The argument assumes a stepsize satisfying Γ − ǫL∆²/2 > 0.Source: Appendix A · pp. 10–11

APPENDIX B: PROOF OF THEOREM 2

• Under strong convexity, the proof uses a stepsize below 2Γ/(L∆²) to obtain the linear-rate result of Theorem 2.The argument bounds the gradient norm using the objective suboptimality and strong convexity.Source: Appendix B · p. 11

APPENDIX C: PROOF OF THEOREM 3

• The analysis bounds the asynchronous-gradient discrepancy using gradient Lipschitz continuity and eigenvalue bounds on the curvature matrices.It also bounds terms using the triangle and Cauchy-Schwarz inequalities.Source: Appendix C · p. 11
• The proof assumes an asynchronicity bound B limiting the time between a neighbor's information timestamp and the current time.This bounds the difference between the global and asynchronous variables.Source: Appendix C · p. 11
• With the stated stepsize condition, the proof concludes that the global virtual variable and all local variables converge, with the global gradient tending to zero.It uses the partial asynchronicity assumption to extend the result to local variables.Source: Appendix C · p. 12

• It bounds the error terms using their definitions and previously established bounds, including alternative bounds for ∥δnk(t)∥.Source: Appendix D · p. 12
• Triangle inequalities, Lipschitz continuity, and maxima over τ−B≤l≤τ are used to bound the remaining terms.Source: Appendix D · p. 12
• The proof obtains (37) by extending the maximum to t−2B≤l≤t−1 and summing B times.Source: Appendix D · p. 12

• At the active node, it adds and subtracts the true gradient and uses eigenvalue, Cauchy–Schwarz, strong-convexity, and gradient-norm bounds.Source: Appendix E · pp. 12–13
• The proof substitutes the gradient error bound from (37) into (82) to derive the function-gap recurrence.Source: Appendix E · p. 13
• The convergence argument follows the sequence lemma cited as [31, Lemma 3].Source: Appendix E · p. 13
• The recurrence bounds V(t+1) using V(t) and the maximum over the delayed interval t−d(t)≤l≤t.Source: Appendix E · p. 13
• Choosing ε so that p+q<1 yields linear convergence under the bounded-delay condition.Source: Appendix E · p. 13