Optimally Improving Cooperative Learning in a Social Setting

Published in 41st International Conference on Machine Learning (ICML), 2024

Abstract

We study cooperative learning where networked agents, each owning a classifier for the same task, update predictions via communication or observation. If highly influential vertices rely on erroneous classifiers, accuracy degrades for the whole network. We ask how to optimally fix a few classifiers to maximize overall accuracy. We propose aggregate and egalitarian objectives, give a polynomial-time algorithm for the aggregate objective, prove the egalitarian objective is NP-hard, and design approximation algorithms for that setting. Mathematical analysis and experiments on synthetic and real data validate the approach.

Methodology

We model the network using DeGroot and Friedkin-Johnsen dynamics where agents update beliefs based on neighbors. We define two optimization problems:

Aggregate Improvement: Maximize the total accuracy of the network. We prove this can be solved in polynomial time by selecting nodes with the highest “influence scores” derived from the network topology.
Egalitarian Improvement: Maximize the accuracy of the worst-performing agents (or count of improved agents). We prove this is NP-hard via reduction from Set Cover. We propose a greedy algorithm (EgalAlg) with a $(1-1/e)$ approximation guarantee.

Experimental Results

We tested our algorithms on synthetic graphs (Erdős-Rényi, Barabási-Albert) and real-world networks (Facebook, Wiki). Our greedy approach (EgalAlg) consistently outperforms heuristics like random selection or degree-based selection.

Table 1: Number of modified nodes required to achieve >90% accuracy (Lower is better)

Dataset	Random	Degree Heuristic	EgalAlg (Ours)
Erdős-Rényi (ER)	>100	>100	55
Barabási-Albert (PA)	7	4	1
Facebook (FB)	94	93	9
Wiki	22	26	2

Key Contributions

Framework: Defined “Cooperative Learning in a Social Setting” where agents share predictions rather than parameters.
Algorithms: Provided an exact polynomial-time algorithm for aggregate improvement and an approximation algorithm for the NP-hard egalitarian objective.
Theoretical Guarantees: Rigorous proofs for hardness and approximation ratios.
Impact: Demonstrated that intervening on a small set of influential nodes can drastically improve network-wide consensus and accuracy.

BibTeX Citation

@inproceedings{haddadan2024optimally,
  title={Optimally Improving Cooperative Learning in a Social Setting},
  author={Shahrzad Haddadan and Cheng Xin and Jie Gao},
  booktitle={International Conference on Machine Learning (ICML)},
  year={2024},
  url={[http://jackal092927.github.io/files/social_learning_arxiv.pdf](http://jackal092927.github.io/files/social_learning_arxiv.pdf)}
}

Cheng Xin