Decentralized Multitask Learning over Learned Task Graphs

Zirui Wan; Stefan Vlaski

Source-linked AI summary

Decentralized Multitask Learning over Learned Task Graphs

Zirui Wan, Stefan Vlaski

arXiv:2608.26989v1Aug 27, 2026cs.LGeess.SPeess.SY

TL;DR

The paper tackles decentralized multitask learning when inter-task relationships are unknown. It proposes a two-phase GMRF-based strategy that estimates a generalized graph Laplacian from noisy non-cooperative iterates before using it for cooperative multitask diffusion learning. The analysis and simulations show that learned-graph cooperation improves over non-cooperative learning and approaches the true-graph benchmark as stepsizes decrease.

Problem
Existing graph-regularized multitask methods commonly assume known task relationships, while decentralized settings require inferring them from distributed data without centralized covariance estimation.
Method
A fully decentralized two-phase method estimates a GMRF-constrained generalized graph Laplacian from noisy non-cooperative local-model iterates, then uses it in multitask diffusion learning.
Results
The learned graph improves performance over non-cooperative learning and approaches the true-Laplacian benchmark as stepsizes decrease, with steady-state effects of orders O(µ′) and O(µ).
Takeaways & Limitations
The framework provides decentralized joint graph and multitask learning with finite-sample estimation guarantees and analysis of graph-error propagation.

Abstract

from arXiv · show

This paper investigates decentralized multitask learning over networks when the underlying task relationships are unknown. While existing graph-regularized multitask frameworks typically assume a known structure, practical settings often require learning inter-task dependencies directly from distributed data. We propose a decentralized two-phase strategy that first estimates a generalized graph Laplacian from noisy non-cooperative stochastic gradient iterates, and subsequently exploits the learned graph to enable cooperative multitask diffusion learning. This framework is motivated by a Gaussian Markov random field prior, which gives rise to a decentralized maximum likelihood estimator for the graph Laplacian. The analysis quantifies the Laplacian estimation error and its propagation to the steady-state performance of the multitask diffusion recursion, and introduces a topology sensitivity index to capture the effect of network heterogeneity. Simulation results corroborate the theoretical findings and demonstrate that cooperation enabled by the learned task graph significantly improves performance over non-cooperative learning, while approaching the true-graph baseline when the estimation stepsize is sufficiently small.

I. INTRODUCTION

The paper addresses decentralized multitask learning when task relationships are unknown by learning a graph from distributed noisy iterates and using it for cooperative adaptation. It develops an end-to-end framework with error analysis and simulations showing improved performance over non-cooperative learning.

Multitask regularization: Graph Laplacian regularization encourages related agents to learn similar parameter vectors while preserving local adaptability.Under the GMRF interpretation, the Laplacian acts as a precision matrix governing conditional task dependencies.
Motivation: Existing graph-based multitask methods often assume task connectivity and edge weights are known, although these relationships may be implicit, data-driven, or evolving.This motivates inferring task relationships directly from available distributed data.
Relation to existing studies: Unlike centralized graph-learning approaches and implicit personalization methods, the framework jointly infers task relationships and learns local models through decentralized interactions.The approach avoids requiring prior knowledge of graph weights while retaining performance guarantees.
Proposed framework: The proposed two-phase framework first learns task relationships non-cooperatively, then performs graph-regularized multitask adaptation using only local connectivity information.The learned graph is modeled through a GMRF-constrained generalized graph Laplacian and incorporated into cooperative learning.
Results: The learned graph improves performance over non-cooperative learning and approaches the known-graph baseline as the relevant stepsizes decrease.The framework analyzes both stochastic error and Laplacian-induced bias in the resulting multitask diffusion algorithm.
Graph learning: The method estimates a Laplacian from noisy non-cooperative stochastic iterates and establishes finite-sample error bounds for the estimated graph.The analysis also quantifies how network heterogeneity affects estimation quality through topology sensitivity.

C. Notation

The paper models task relationships with a generalized graph Laplacian under a GMRF prior and formulates decentralized stochastic multitask learning using local gradient information and Laplacian regularization.

GMRF prior: The GMRF prior models each agent parameter as a Gaussian random vector whose dependencies follow a connected, undirected weighted graph.Edge weights represent agent similarity, and each node's neighborhood includes itself and its connected neighbors.
GMRF prior: The generalized graph Laplacian is symmetric and positive definite, combining weighted adjacency, degree, and nonnegative diagonal self-loop matrices.Its self-loop terms control local-model variance under the GMRF interpretation.
Multitask formulation: Under the GMRF prior, the MAP estimator becomes a Laplacian-regularized multitask optimization problem.The regularization strength η controls coupling across agents.
Decentralized learning: Because exact risks and gradients are unavailable, agents use stochastic gradient approximations in a diffusion-type recursion that remains decentralized through Laplacian sparsity.The unknown true Laplacian is replaced by an estimate in the learning recursion.

C. Non-Cooperative Phase for Laplacian Estimation

The non-cooperative phase estimates local Laplacian blocks from noisy independent model iterates, using neighborhood covariances and local maximum likelihood optimization before assembling a sparse symmetric graph estimate.

Local estimation: Each agent independently runs stochastic gradient descent without access to the unknown Laplacian to generate local model estimates for graph learning.The recursion uses a constant stepsize µ and only each agent's own data.
Local estimation: Laplacian sparsity makes the first row and column of each local inverse covariance coincide with the corresponding neighborhood Laplacian block.Thus, local covariance information suffices to recover the parameters needed for decentralized graph learning.
Local graph inference: Each node solves a convex MML problem using its local sample covariance, equivalent to the global maximum likelihood estimator while avoiding centralized processing.The local covariance is a principal submatrix and can be estimated directly from locally stacked iterates.
Graph assembly: The local estimates are assembled according to known connectivity, preserving sparsity and enforcing symmetry through local averaging.The resulting local Laplacian encodes the edge weights on each agent's neighborhood.
Motivation: Finite-sample error bounds are needed because noisy samples invalidate direct application of classical asymptotic consistency arguments.The paper analyzes how these estimation errors affect decentralized multitask learning.
Algorithm: The phase is organized within a two-phase algorithm whose inputs include neighborhoods, data, initialization, stepsizes, regularization, and iteration counts.Phase II subsequently uses cooperative learning after the non-cooperative estimation stage.

III. ESTIMATION QUALITY ANALYSIS

The estimation-quality analysis relies on regularity assumptions for local costs and conditional gradient noise, with examples including quadratic and logistic objectives.

Scope: These assumptions are commonly satisfied by learning and adaptation objectives such as quadratic and logistic costs.
Assumptions: The analysis assumes local cost functions are convex, twice differentiable, and have bounded Hessians.The Hessians are also required to satisfy a Lipschitz condition.
Assumptions: The gradient-noise assumptions specify conditional behavior relative to the filtration of all past iterates across agents.They include a conditional covariance condition for the stochastic gradient process.

A. Laplacian Estimation Error

The Laplacian error analysis separates finite-dimensional covariance fluctuations from stepsize-induced bias and quantifies how topology affects estimation quality.

Laplacian estimation error: Theorem 1 bounds Laplacian estimation error for sufficiently small µ and sufficiently large M.The theorem introduces constants including ζ, ρ, τ, and Φ in the bound.
Error decomposition: The covariance-concentration component reflects finite-dimensional statistical fluctuations and vanishes as M →∞.It decays with increasing dimension according to the theorem's bound.
Error decomposition: The noise-induced bias from non-cooperative stochastic-gradient steady-state error behaves as O(µ) and can be reduced with a decaying stepsize.This bias propagates into downstream graph-based learning tasks.
Topology sensitivity: The topology sensitivity index TSI(L) measures how network structure influences Laplacian estimation error.Larger values reflect stronger amplification of local covariance perturbations, with heterogeneous hub networks tending to have larger sensitivity.

B. Laplacian-Induced Error in Multitask Learning

The analysis separates steady-state multitask diffusion error into stochastic gradient-noise effects and deterministic bias from estimating the task graph. Both effects vanish as dimension grows and stepsizes decrease, recovering the true-Laplacian optimum asymptotically.

The Laplacian-induced bias measures deviation between the optimal solutions associated with the true and estimated Laplacians.Its expectation is taken over randomness in the estimated Laplacian.
Theorem 2 characterizes steady-state deviation when multitask diffusion uses an estimated Laplacian.
The steady-state error decomposes into stochastic error of order O(µ′) and Laplacian-induced bias of order O(µ).The stochastic term arises from gradient noise, while the deterministic bias stems from graph-estimation errors.
As M grows and µ, µ′ decrease, both error components vanish and diffusion asymptotically recovers the true-Laplacian optimum.The true-Laplacian optimum also carries a maximum a posteriori interpretation.

IV. NUMERICAL EXPERIMENTS

The experiments evaluate decentralized Laplacian estimation under different data, stepsize, dimension, and topology settings. They show the predicted O(µ) behavior and that degree heterogeneity, especially hub dominance, increases estimation error.

General Settings: The simulations use streaming linear-regression data over a connected, undirected network with stationary, independent regressors and noise.The graph contains K = 10 nodes with maximum degree 8 in the main weighted-topology experiment.
Impacts of stepsize µ and dimension M: At M = 800, halving µ reduces Laplacian estimation error by approximately one-half, or about 3 dB, consistent with O(µ).The error is averaged over 100 Monte Carlo realizations of the non-cooperative iterates.
Impacts of stepsize µ and dimension M: When µ is very small and M is insufficiently large, covariance concentration dominates the estimation error.For µ = 10^-2, the error curve nearly overlaps the true-parameter GML benchmark before M = 800.
Impacts of topologies: Among graphs with identical node counts and average degree, the hub-dominated topology produces the largest Laplacian estimation error.The analysis attributes this to its high-degree hub and larger topology sensitivity index TSI(L).
Impacts of topologies: Highly uneven connectivity significantly amplifies decentralized Laplacian estimation error even when average connectivity remains constant.

C. Steady-State Performance under Diffusion and Learned Laplacians

The experiments examine steady-state diffusion performance with true and learned Laplacians, then evaluate two-phase and multi-phase joint learning. Learned graphs improve over non-cooperative learning and approach the true-Laplacian benchmark when estimation stepsizes are small, while topology and stability constrain performance.

Topology and stability: Hub-dominated topologies yield the largest Laplacian estimation error despite having the same average degree as regular and Erdős–Rényi graphs.The paper attributes this to high-degree hubs amplifying covariance perturbations through increased topology sensitivity.
True-Laplacian diffusion: With the true Laplacian, steady-state MSD decreases monotonically as the multitask stepsize µ′ decreases.The observed scaling agrees with the theoretical O(µ′) diffusion-error prediction.
Learned-Laplacian diffusion: Smaller Laplacian-learning stepsizes µ produce lower steady-state MSD with estimated Laplacians.When µ is sufficiently small, performance approaches the true-Laplacian benchmark, indicating that the remaining gap is primarily estimation error.
Two-phase learning: The two-phase strategy lowers steady-state MSD after switching from non-cooperative to cooperative learning with the learned graph.The gain is particularly pronounced for larger µ, where Phase-I stochastic gradient noise is more significant.
Multi-phase learning: Multi-phase learning achieves nearly the same steady-state MSD across Laplacian update intervals {5000, 2500, 1000, 10}.Shorter intervals slightly slow the transient because updates use noisier iterates, whereas larger intervals closely match the two-phase benchmark.
Topology and stability: Stability depends on regularization strength η and task smoothness; strong regularization with weakly correlated parameters can amplify errors and cause MSD divergence.Very short update intervals can further corrupt the Laplacian estimate through transient error.

APPENDIX PROOF OF THEOREM 1

The appendix establishes stability and steady-state performance properties for diffusion with learned Laplacians. It uses Gaussian approximations, bounded-Hessian assumptions, norm inequalities, and Lyapunov analysis to control the error recursion.

Steady-state approximation: The steady-state estimator admits an asymptotically Gaussian approximation for sufficiently small constant µ as i →∞.The appendix introduces an exact Gaussian model to facilitate subsequent covariance analysis.
Steady-state approximation: The steady-state error covariance scales as µΠ, where Π is symmetric positive semidefinite and independent of µ.The covariance structure is characterized through a continuous Lyapunov equation.
Covariance analysis: Element-wise stacking transforms the iterates so their Gaussian approximation can be expressed through the transformed covariance Φ and its marginal covariance Φ_m.The transformation is defined by W^e_i = P W_i.
Laplacian-error bounds: The proof bounds Laplacian estimation error by combining covariance concentration, inverse perturbation, local reconstruction, and symmetrization arguments.The local error uses the Schur complement identity and non-expansiveness of the relevant operators.
Proof setting: The analysis requires a symmetric positive definite Laplacian, so earlier arguments for combinatorial Laplacians do not apply directly.A modified proof is therefore provided for the present setting.
Stability analysis: For sufficiently small µ′, the diffusion error recursion is stable because its contraction factor satisfies γmax ≤ 1 and 0 < ∥B∥ < 1.The contraction analysis uses the bounded-Hessian assumption and the expansion associated with γmax.