PaperlayerView exact revision on arXiv

Source-linked AI summary

Cordial Learning: Distributed Training with Correlated Data

Sarah Shitrit, Ilai Bistritz

arXiv:2610.03330v1cs.LGcs.AI

TL;DR

Distributed learning often ignores correlated data, even when agents’ labels depend on peers’ inputs. Cordial learning shares embedded outputs and trains coordination layers to use peers’ information. Under a linear model it converges to optimal models, and the paper reports effective performance on multi-digit MNIST beyond that theoretical setting.

  • Problem

    Distributed-learning methods do not account for correlated data from shared environments, while centralized training can require raw-data sharing and substantial communication.

    Source: §1 · pp. 1–2, §3.1 · p. 7

  • Method

    Cordial learning shares embedded outputs and trains local coordination layers to extract useful information from other agents’ outputs.

    Source: §4 · p. 8

  • Results

    Under the linear model, cordial learning converges to models minimizing the sum of agents’ losses, and multi-digit MNIST experiments show it performs well beyond that theoretical model.

    Source: §1 · p. 3, §7 · p. 29

  • Takeaways & Limitations

    Cordial learning offers a distributed approach for agents to benefit from correlated data while sharing outputs rather than explicit datapoints.

    Source: §4 · p. 8, §7 · p. 29

    A key open problem is designing cordial learning that compresses transmitted information according to receiving agents’ loss functions.

    Source: §7 · p. 29

Abstract

from arXiv · show

We consider a distributed learning task with agents that have correlated data. Specifically, the label of an agent depends on the input of other agents for the same sample, and these inputs are also correlated. Correlated data is the reality when agents share the same environment. Existing decentralized methods, such as federated learning, ignore the structure of the problem and perform poorly on correlated data. On the other hand, centralized approaches are infeasible due to privacy and communication constraints. We introduce cordial (correlated and distributed) learning to address this gap by sharing only low-dimensional outputs between the agents while training local models to extract informative signals from peers. This distributed learning induces a game in which the loss function of each agent depends on the models of others. Assuming a linear model, we prove that cordial learning converges with probability one to a globally optimal solution, despite the nonconvex global objective. Experiments on structured multi-digit MNIST tasks demonstrate that cordial learning remains highly effective even in highly nonlinear settings.

1. Introduction

Cordial learning addresses distributed learning with correlated data, where one agent’s label can depend on other agents’ inputs. It shares compact embedded outputs and trains coordination layers to use peers’ information while seeking low communication overhead.

1. Introduction

  • Existing distributed and federated learning assumes agents face the same task and does not account for the correlated-data structure described here.The paper contrasts this with cordial learning, where each device has a private dataset but corresponding datapoints across devices are correlated.Source: §1 · pp. 1–2
  • Cordial learning targets shared-environment data where agents’ inputs and labels are correlated, including cases where one agent’s label depends on other agents’ inputs.Examples include dependent handwritten digits, nearby patients with correlated health outcomes, remote sensors, and interacting vehicles.Source: §1 · pp. 1–2
  • The approach seeks close-to-optimal performance with low communication overhead, measured by the sum of agents’ losses.The paper argues that centralized training entails substantial communication and can compromise privacy, while distributed task structure can make a distributed architecture more data-efficient.Source: §1 · pp. 2–3
  • Cordial learning shares low-dimensional embedded outputs, then trains coordination layers to extract useful information from peers’ inputs for the same sample.The embedded output is processed before the agent’s softmax output, which is computed after incorporating information from other agents.Source: §1 · p. 3
  • Because each agent’s model affects other agents’ losses through shared information, the induced global objective is nonconvex even for linear regression.Agents train their own neural networks alongside coordination layers that process peers’ inputs.Source: §1 · p. 3
  • With coordination layers learning more slowly than embedding layers, the linear-model analysis guarantees convergence to globally optimal agent models despite local agents optimizing only their own losses.The paper presents this as a scalable distributed method with little communication overhead.Source: §1 · p. 3

2. Previous Work

The paper distinguishes cordial learning from prior approaches by its treatment of correlated samples, cooperative distributed agents, and private local tasks. Related methods instead address independent data, shared tasks, centralized training, or different interaction structures.

2. Previous Work

  • Federated learning addresses independent datasets for a shared task and requires devices to use the same architecture for weight averaging, unlike cordial learning’s correlated data and heterogeneous architectures.Communication reduction in federated learning and distributed SGD is also recognized as important.Source: §2 · p. 3
  • Distributed distillation shares softmax outputs on common unlabeled data, whereas cordial learning shares embedded outputs for the same sample agents are learning from.The prior scheme supports different architectures and avoids explicit data disclosure (Bistritz et al., 2020).Source: §2 · p. 4
  • Learning-in-games work studies distributed players seeking rewards and equilibria, while cordial learning uses a cooperative game to help agents learn.The paper contrasts its cooperative players with zero-sum GAN games (Goodfellow et al., 2020; Bistritz and Bambos, 2020).Source: §2 · p. 4
  • Performative prediction studies games where learners’ actions affect others’ risk scores and data distributions, seeking equilibria in selfish behavior; in Narang et al. (2023), datapoints are independent given the distribution and players observe one another’s actions.Source: §2 · p. 4
  • Vertical federated learning has correlated inputs but one label and one learning task, making it a special case of cordial learning when labels are identical and one agent orchestrates learning.Cordial learning gives each agent its own local task and label.Source: §2 · p. 4
  • Multitask learning trains a centralized architecture on asynchronous tasks, whereas cordial learning coordinates distributed agents learning from synchronous correlated datapoints.Successive-classification pipelines share a feature backbone and compute sequentially, unlike cordial learning’s distributed agents and bidirectional information flow.Source: §2 · pp. 4–5

3. Problem Formulation

The formulation treats corresponding agent datapoints as statistically dependent while each agent observes only local data. It defines a coupled sum-of-losses objective and a linear model in which agents’ labels mix inputs across agents, then motivates cordial learning as a distributed route to its global optimum.

3. Problem Formulation

  • Corresponding datapoints across agents are statistically dependent, although each agent observes its own local training data and learning task.The formulation treats the agents’ inputs as parts of a larger distributed feature vector.Source: §3 · p. 6
  • The ideal empirical-risk objective sums the agents’ losses, while training each agent independently ignores cross-agent effects and is suboptimal.A centralized model can attain minimal training loss, but requires sharing data and real-time server processing, with communication and privacy costs.Source: §3 · p. 6, §3.1 · pp. 6–7

3.1 Linear Mean-Squared Error Model

  • For analysis, the paper assumes a linear model in which each agent’s random label is a linear mixture of all agents’ inputs, with zero-mean noise of finite variance.The linear model is adopted to analyze guarantees for a scenario where general ML losses may be nonconvex and intractable.Source: §3.1 · p. 6
  • Cordial learning has each agent process other agents’ outputs through dedicated coordination layers to improve on isolated training without centralized data sharing.The algorithm’s stated goal is to bypass centralized-training issues while improving performance over the naive isolated scheme.Source: §3.1 · p. 7
  • Because each agent’s loss depends on other agents’ models, the distributed training procedure induces a game in which improving one agent’s own loss can worsen others’.The game is not generally a potential game, and the sum of losses is nonconvex.Source: §3.1 · pp. 7–8
  • Assumption 1 requires the optimal linear estimator of an agent’s label from its own input to retain enough information to represent that agent’s effect on peers.The paper says cordial learning can work without Assumption 1, but its optimality result depends on it.Source: §3.1 · pp. 7–8
  • Under the stated conditions, the residualized variables yield a globally optimal solution, although the nonconvex sum of losses prevents a general guarantee from centralized gradient descent.Each agent’s loss is convex only in its own parameters when other agents’ embedding matrices are fixed.Source: §3.1 · p. 8

4. Cordial Learning Algorithm and Performance

Cordial learning trains agents through shared embedded outputs and local coordination layers, with each agent optimizing its own loss. Under the theorem’s conditions, the algorithm converges with probability one to a global minimum of the sum of agent losses.

4. Cordial Learning Algorithm and Performance

  • Agents share embedded outputs rather than datapoints, while coordination layers process information received from peers.Source: §4 · p. 8
  • Each agent computes gradients over its local parameters and uses information sent by other agents, avoiding the need for centralized gradients of other agents’ losses.Source: §4 · pp. 8–9

End

  • Two independent batches separate gradient computation from covariance estimation, yielding unbiased stochastic gradients.Source: End · p. 11
  • Agents can use common sample ordering during training and communicate online using coordination layers and covariance estimates learned from training samples.Source: End · p. 11
  • With probability 1, cordial learning converges to a global minimum of the sum of all agents’ losses.Source: End · p. 11
  • The convergence theorem assumes independent samples across iterations and a slower update timescale for coordination layers than for embedding layers.Source: End · p. 11

5. Convergence Analysis

The analysis separates embedding updates from coordination-layer updates by constructing local variables that remove input correlations. It uses embedding convergence to establish coordination convergence and bound stochastic-gradient variance.

5. Convergence Analysis

  • Subtracting the component correlated with X_i makes the expected gradient for M_i independent of coordination parameters and other agents’ models.Source: §5 · pp. 12–13
  • The expected gradient for M_i is 2(M_i − A*_i), suggesting noiseless convergence to A*_i; the global-objective gradient instead adds N−1 peer terms.Source: §5 · p. 12
  • Coordination layers reach minimal error only as peers’ embeddings approach A*_j, and their convergence reduces the variance of M_i’s stochastic gradient.Source: §5 · p. 12
  • With no perfectly redundant input dimensions, effective coordination errors converge to zero with probability one across agents.Source: §5 · pp. 15–16
  • The stochastic-gradient variance upper bound decreases to an error floor determined by label noise and covariance estimation.Source: §5 · p. 16

6. Experiments

The experiments test cordial learning (CL) in a linear model and on multi-digit MNIST tasks, comparing it with isolated and centralized training. CL performs strongly when agents’ digits are correlated, although its advantage depends on the strength of that dependence and the amount of data.

6. Experiments

  • The linear simulations use correlated Gaussian or Laplacian inputs, while MNIST experiments test deterministic Pairwise-10 and probabilistic common-cause digit dependencies.The MNIST experiments use separate image pools for training, validation, and testing.Source: §6 · p. 17, §6.1 · p. 17, §6.2 · p. 18

6.1 Linear Model Simulations

  • After 20,000 iterations, the median ratio of cordial to isolated loss ranges from 0.36% to 1.4%, and is below 2.4% in every run.From iteration 140 onward, cordial loss is lower in all 600 runs and continues decreasing toward the global minimum.Source: §6.1 · p. 18, Figure 3 · p. 19

6.2 MNIST-Based Multi-Agent Simulations

  • MNIST composites give each agent one digit; cordial agents exchange 10-dimensional embedded outputs through coordination layers, alongside isolated and centralized CNN baselines.The centralized CNN receives the full composite image, while isolated agents do not communicate.Source: §6.2 · pp. 18–20

6.2.1 The Pairwise-10 Dataset

  • In Pairwise-10, CL has lower test loss than isolated training in every setting; at P = 500, its losses are 0.008, 0.0009, and less than 10−4.At P = 25, its median accuracy for 2, 4, and 6 agents rises from 0.88, 0.91, and 0.91 to 0.94, 0.996, and 1.000.Source: §6.2.1 · p. 22, Figure 5 · p. 23, Table 2 · p. 24

6.2.2 The Common-Cause Datasets

  • At p = 0.8 and P ≥100, CL beats isolated agents in every setting; at p = 0.6 its gains depend on data, while centralized training is best at P = 500.For p = 0.6 and P = 25, CL is worse than isolated training with 4 agents and on two of three draws with 6 agents.Source: §6.2.2 · p. 25, Figure 6 · p. 26, Figure 7 · p. 27

7. Conclusions

Cordial learning (CL) shares embedded outputs so agents with correlated data can learn from one another; under a linear model and mild assumptions, it converges to models minimizing total loss. The paper also identifies open questions on convergence rates and recipient-aware output compression.

7. Conclusions

  • CL lets agents with correlated data learn from peers by sharing embedded outputs and training layers to extract useful information from those outputs.The paper studies linear labels formed from inputs across agents and reports deep-network experiments on multi-digit MNIST beyond that theoretical model.Source: §7 · p. 29
  • Under mild assumptions, CL converges to models minimizing the sum of agents’ losses for a linear model whose labels mix all agents’ inputs.The paper describes this as convergence to a global minimum despite the sum-of-losses objective being nonconvex.Source: §7 · p. 29
  • Convergence-rate analysis and optimal regret bounds for online learning remain open questions.The paper also calls for schemes that compress shared information according to receiving agents’ loss functions.Source: §7 · p. 29

Appendix A. Proof of Lemma 3

The proof derives gradients for the stochastic loss and uses independent batches to make covariance estimates unbiased. It also specifies leave-one-out and independent-batch calculations for the expected gradients.

Appendix A. Proof of Lemma 3

  • The proof begins with the stochastic loss and considers its gradient with respect to M_i.The passage identifies this as the gradient of agent i’s loss L_i.Source: Appendix A · pp. 29–30
  • Replacing the indicated factor with an independent-batch estimate makes the covariance estimates in each product independent and the estimator in (29) unbiased.The text points to (32) for the unbiasedness argument.Source: Appendix A · p. 30
  • The expected-gradient expressions use leave-one-out samples from B0 for the indicated estimate and independent batch B1 for the other estimate.The proof identifies these batch choices for the corresponding estimates.Source: Appendix A · pp. 30–31

Appendix B. Nonconvex Objective

A two-agent scalar example establishes nonconvexity by restricting the objective to an affine subspace where the resulting function has an indefinite Hessian.

Appendix B. Nonconvex Objective

  • The counterexample uses two scalar agents with zero-mean, unit-variance inputs having zero cross-covariance and noiseless labels Y1=Y2=X2.The setup states E[X1X2]=0 and uses the two-agent scalar case.Source: Appendix B · p. 31
  • On the affine restriction M1=0 and Λ2=0, the Hessian of h has determinant −4 and is indefinite.The proof uses this restricted function to show h is not convex.Source: Appendix B · p. 31
  • Because a convex function must remain convex on every affine subspace, the full objective in (7) is nonconvex.The passage explicitly draws this conclusion from the restricted example.Source: Appendix B · p. 31

Appendix C. Proof of Theorem 2

The proof uses Robbins–Siegmund arguments and continuity to establish almost-sure convergence of model parameters, then concludes that each agent’s loss reaches its global minimum.

Appendix C. Proof of Theorem 2

  • A Robbins–Siegmund argument shows that the squared distance from M_i(t) to its target converges to zero with probability one.The proof argues that any positive limiting distance would contradict the stated summability condition.Source: Appendix C · p. 32
  • A dense-subset argument and continuity extend the convergence result to every Λ_i* in S_i with probability one.The proof first takes a countable dense subset, then uses bounded subsequences and continuity to obtain the full-sequence result.Source: Appendix C · p. 36
  • Each agent’s loss L_i converges to its global minimum σ^2 with probability one.The passage states this conclusion after establishing convergence of the relevant parameters.Source: Appendix C · p. 36
Loading 2610.03330v1…