Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs

1 INTRODUCTION

• Centralized data collection carries infrastructure, security, privacy, and user-control risks, while communication is a major bottleneck in decentralized collaboration.User-specificity can also increase model complexity and size.Source: §1 · p. 1
• Users’ distinct behaviors motivate learning personalized models alongside a sparse graph that connects sufficiently similar tasks.The graph also serves as an overlay restricting communication to pairs whose tasks appear sufficiently similar.Source: §1 · p. 2
• The method alternates personalized-model updates given the graph with graph updates given the models, using controlled sparsity.Model updates greedily add one base predictor at a time and are sent only to direct neighbors; graph updates use small random peer subsets.Source: §1 · p. 2
• For strongly convex graph regularizers, the algorithm has fast convergence, with peer-sampling size trading off communication against convergence speed.The model-learning procedure has communication costs linear in graph edges and logarithmic in the number of base classifiers.Source: §1 · p. 2
• The approach reports better personalized models at lower communication costs than existing methods on several datasets.The collaboration graph is learned jointly with the models.Source: §1 · p. 2

2 RELATED WORK

• The closest cited federated approach jointly learns personalized linear models and task similarities, but updates similarities centrally and does not produce a typically sparse valid weighted graph.Central updates require regular access to all task models, creating communication and computation bottlenecks when task counts are large.Source: §2 · pp. 2–3
• Unlike decentralized methods that learn a single global model, this approach learns personalized models using task similarities.In global-model methods, the graph encodes communication topology and affects convergence speed, but has no semantic meaning.Source: §2 · p. 3
• Existing decentralized personalized-model methods require a relevant graph as input, whereas this approach learns the graph along with the models.The learned-graph procedure can also be combined with several of those methods in alternating optimization.Source: §2 · p. 3
• The boosting-based approach learns nonlinear models with logarithmic communication cost, unlike cited personalized decentralized methods restricted to linear models with per-iteration cost linear in data dimension.The authors present it as an alternative for high-dimensional problems or complex decision boundaries.Source: §2 · p. 3

3 PROBLEM SETTING AND NOTATIONS

• Each user has a personal supervised task and local dataset, and local-only training may generalize poorly when data is scarce.Users share a hypothesis class; confidence is treated as proportional to dataset size and is set in practice to the normalized dataset size.Source: §3 · p. 3
• The collaboration graph is a weighted, undirected semantic overlay: users message direct neighbors, and disconnected components can represent unrelated user clusters.The graph is not known beforehand and evolves alongside model learning, with sparsity controlled.Source: §3 · p. 3
• The joint objective combines confidence- and degree-weighted local losses, graph-weighted model similarity, and graph regularization.Larger datasets can give users more influence on neighbors while small-data users can rely more on information from others; the graph regularizer controls structural properties such as sparsity.Source: §3 · p. 4
• The graph regularization trade-off ranges from a shared model within each connected component to independent local models, with intermediate settings retaining personalized models regularized by connected users.These extremes correspond to µ1 → +∞ and µ1 = 0, respectively.Source: §3 · p. 4
• Because the joint problem is typically bi-convex, the approach alternates decentralized optimization of model parameters and graph weights.The paper introduces separate procedures for greedy boosting-style model learning and sparse graph learning.Source: §3 · p. 4

4 DECENTRALIZED COLLABORATIVE BOOSTING OF PERSONALIZED MODELS

• Personal classifiers combine real-valued base predictors, while an l1 constraint controls model sparsity and the loss remains convex and differentiable.The parameter domain is compact and convex.Source: §4 · p. 4

4.1 Decentralized Algorithm

• Frank–Wolfe selects predictors that perform well on reweighted local samples, with an added bias toward predictors popular among graph neighbors, scaled by user confidence.The local gradient emphasizes poorly classified training points.Source: §4.1 · p. 5
• Users update from their local data and direct neighbors’ models, then send updates to those neighbors, allowing parallel updates over typically small neighborhoods.Each user retains its personal dataset locally.Source: §4.1 · p. 5

4.2 Convergence Analysis, Communication and Memory Costs

• The cited result states that the algorithm achieves an O(1/t) convergence rate, and directs readers to the supplementary material for the proof of that convergence-rate result.Source: §4.2 · p. 5
• Communication and memory to reach an ε-approximate solution scale linearly with graph edges and logarithmically with base predictors; with constant decision stumps per feature, dimensional cost is logarithmic.The authors report significantly better complexities than the state of the art for this stump setting.Source: §4.2 · pp. 5–6

Graph objective

• The graph objective uses separable penalties on edge weights and node degrees, a structure that supports efficient decentralized updates using local communication.The component functions are convex and smooth, and the objective is convex in the graph weights.Source: §5 · p. 6

Decentralized algorithm

• Each graph update samples κ other users at random, requests their models, loss values, and degrees, updates the associated weights, then sends those weights to the sampled users.κ is typically much smaller than the total number of users.Source: §5 · p. 6
• No global information is needed for weight updates, so they can run asynchronously and in parallel.Source: §5 · p. 6

Convergence, communication and memory

• For σ-strongly convex g, expected suboptimality contracts geometrically by ρ^T; for general convex g, convergence is O(1/T).The authors note the strongly convex graph-update rate is typically faster than the boosting subproblem’s rate.Source: §5 · p. 6

Proposed regularizer

• The experimental regularizer’s smaller λ concentrates each user’s weights on peers with closer models, trading model-update accuracy against communication; a variable-pruning heuristic has negligible quality impact in sparse regimes.The heuristic retains zero weights for users whose models are most different.Source: §5 · p. 7

Real data

• The evaluation includes four real user-level datasets and compares boosting and linear methods across global, local, and collaborative settings.Hyperparameters were tuned with three-fold cross-validation, and reported accuracies were averaged over users.Source: §6 · pp. 7–8

Synthetic data

• On Moons, Dada-Oracle and Dada-Learned reduce Local-boost overfitting and achieve higher test accuracy than Global-boost.Dada-Oracle outperforms Dada-Learned, while Dada-Learned compensates for lacking ground-truth task relationships.Source: Figure 1 · p. 7, §6 · p. 8
• Dada-Learned’s graph remains sparser than the oracle graph and approximately recovers the ground-truth cluster structure.The figure visualizes graph weights and the learned graph, with darker edges indicating higher weights.Source: §6 · p. 8, Figure 2 · p. 8

Real data

• On real datasets, Dada-Learned and Perso-lin-Learned achieve the best performance among the compared methods.The results support using graph learning with Perso-lin when no prior collaboration graph is available.Source: §6 · p. 8
• Under limited communication budgets, Dada-Learned achieves higher accuracy, especially on higher-dimensional data.The comparison is reported for real datasets at fixed communication budgets.Source: §6 · p. 8, Table 2 · p. 8

Future work

• The authors plan to extend the approach to functional gradient boosting, where graph regularization would apply to an infinite set of base predictors.Source: §7 · pp. 8–9
• The authors describe privacy guarantees and extension to functional boosting as future work, not established capabilities of the present method.Source: §7 · pp. 8–9
• They also propose differential privacy to formally guarantee that personal datasets cannot be inferred from information sent by users.The authors expect sparse communication may offer a better privacy–accuracy trade-off than that known for linear models.Source: §7 · p. 9

SUPPLEMENTARY MATERIAL

• The supplement outlines convergence analyses, complexity discussion, and additional experimental results beyond the main text.Source: SUPPLEMENTARY MATERIAL · p. 11

A PROOF OF THEOREM 1

• The proof of Theorem 1 sets up the classifier optimization over block-structured parameters and defines the feasible domain and update notation.The feasible domain is formed from the per-user parameter sets, with updates expressed using a step size γ.Source: A PROOF OF THEOREM 1 · p. 11

A.1 Curvature Bound

• The curvature analysis bounds each block’s curvature using the partial-gradient Lipschitz constant and the squared diameter of its feasible domain.The proof first establishes objective smoothness over the feasible domain.Source: §A.1 · p. 11

A.2 Convergence Analysis

• The expected sub-optimality gap decreases at O(1/t), implying convergence of the model-update algorithm to an optimal solution.Source: §A.2 · p. 13

B PROOF OF THEOREM 2

• The graph-learning convergence analysis assumes a smooth, strongly convex term and a convex, nonsmooth, coordinate-separable nonnegativity term.The appendix frames the graph-learning analysis as a proximal block coordinate descent procedure.Source: §B.1 · p. 13, B PROOF OF THEOREM 2 · p. 13

B.1 Interpretation as Proximal Coordinate Descent

• The graph update is proximal block coordinate descent over a randomly selected coordinate block, with the nonnegative constraint yielding the thresholding update max(0, w).Source: §B.1 · pp. 13–14

B.2 Convergence Analysis

• Each graph-update block overlaps others because an edge weight can be updated from either endpoint, requiring convergence analysis adapted to this update structure.The proof adapts the technique of Wright (2015) to overlapping blocks.Source: §B.2 · p. 14

C SMOOTHNESS AND STRONG CONVEXITY OF GRAPH LEARNING FORMULATION

• The graph objective is strongly convex, while its block smoothness grows linearly with block size; the log-degree term makes this dependence tight and its convergence effect mild.The analysis gives σ = 2µ1λ for strong convexity.Source: C SMOOTHNESS AND STRONG CONVEXITY OF… · p. 17

D.1 Learning Models: A Logarithmic Communication and Memory Cost

• Single-coordinate Frank–Wolfe updates send a coordinate index and value; network memory is linear in M, K, and n, with sparse models reducing dependence on n to logarithmic.The sparse representation stores at most t_k nonzero elements after t_k updates.Source: §D.1 · p. 18

D COMMUNICATION AND MEMORY

• Model-learning communication is logarithmic in the number of base predictors under the stated failure-free system assumption.For a constant number of simple decision stumps per feature, the passage says this yields logarithmic cost in data dimensionality.Source: §D.1 · pp. 17–18

D.2 Learning the Collaboration Graph: Communication vs. Convergence

• Each graph update requests selected peers’ degrees, models, and local losses, then sends them their updated edge weights; its expected communication cost depends on κ and model sparsity.The per-iteration cost is given in terms of κ, Z, the expected number of nonzero model entries, and log n.Source: §D.2 · p. 18
• Larger κ raises per-iteration communication linearly but has a mild convergence-rate effect; intermediate values can balance communication and rounds, while larger values suit high precision or fewer rounds.For moderate precision, κ = 1 is suggested to minimize total communication; balancing communication and rounds calls for values much smaller than K.Source: §D.2 · pp. 18–19

D.2.1 Refined communication complexity analysis

• When users cache the models and losses of peers they contact, communication depends on how many selected peers are new, and the expected number of new peers decreases exponentially with iterations.The refined analysis gives a proposition for the expected number of new nodes after T iterations.Source: §D.2.1 · p. 19

E.1 Details on Experimental Setting

• Experiments pair a four-cluster, 100-user Moons benchmark with four real datasets, while hyperparameters are selected by three-fold cross-validation.The real datasets are Harws, Vehicle Sensor, Computer Buyers, and School.Source: §E.1 · p. 20

E.2 Effect of the Block Size κ

• At κ=1, graph learning minimizes total communication at about 5 × 10^5 bits, while larger κ reduces communication rounds; moderate κ balances rounds, cost, and variance.Sending all weights to all users once requires 1.6 × 10^7 bits.Source: §E.2 · pp. 20–21, Figure 3 · p. 21

E.3 Test Accuracy with respect to Local Dataset Size

• On Moons, both Dada variants outperform Local-boost, especially for small datasets; Dada-Oracle closes size-related accuracy gaps, while Dada-Learned nearly matches it except for the smallest sets.On Harws, Dada-Learned generally improves on Local-boost, with more variability across user-task groups.Source: Figure 4 · p. 21, §E.3 · p. 21

E.4 Test Accuracy with respect to Communication Cost

• Dada-Learned generally reaches higher test accuracy with less communication than Perso-lin-Learned, especially on high-dimensional Harws.Figure 5 reports average test accuracy against communication cost.Source: §E.4 · pp. 21–22, Figure 5 · p. 22

E.5 Standard Deviations due to Random Sampling

• Across three random runs, decentralized methods vary with random user selection, whereas global and local methods have zero standard deviation.The appendix reports means and standard deviations of test accuracy.Source: §E.5 · p. 22

• Moons100 uses 100 rotated-user tasks, 3–20 training points and 100 test points per user, with 5% training-label noise in 20 dimensions.Source: §E.6 · pp. 22–23
• Dada-Oracle and Dada-Learned reduce Local-boost overfitting and achieve higher test accuracy than Global-boost and Perso-lin; the learned graph recovers performance without ground-truth similarities.Figure 6 tracks training and test accuracy over iterations.Source: Figure 6 · p. 23, §E.6 · p. 23
• The learned graph averages 42.64 neighbors versus 60.86 for the ground-truth graph; lower λ sparsifies it, while denser graphs can improve accuracy at higher communication cost.As λ approaches zero, accuracy tends toward Local-boost.Source: Figure 7 · p. 23, §E.6 · p. 23