Research map / Learning theory and algorithms / Sample complexity
Sample Complexity of Linear Regression Models for Opinion Formation in Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies total sample complexity for opinion formation games on networks where each agent's opinion is a linear regression model, deriving polynomial-time (SOCP) computation of TSC and network gain bounds for cliques, stars, hypercubes, and regular graphs.
Problem
How many samples must be distributed across a social network so that, at the Nash equilibrium of a data-driven opinion formation game, every agent's final model has low generalization error, and how much does networked learning reduce sample needs relative to isolated learning?
Approach
Treats each agent's opinion as a linear regression model learned from local samples and combines them via the DeGroot-style opinion formation game equilibrium (W^{-1} weights); derives error as a sum of squared equilibrium weights over sample sizes, yielding an optimization for total sample complexity and network gain.
Key results
- Network gain for clique is Omega(n) and for random d-regular graphs is Omega(min{d^2, n}); star graphs give only O(1) gain.
- Optimal sample allocation satisfies sum_i 1/(alpha d_i+1)^2 <= TSC-scaled sum m_i <= sum_i (alpha+1)/(alpha d_i+1), implying samples should be allocated inversely to degree.
- Empirical relative errors of the general-influence TSC bounds are small (e.g., err_u/err_l of 6.6%/1.3% on Econ and 41%/36% on 130bit).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Collaborate through opinion formation on a clique rather than learn independently | Linear regression opinion formation · Clique | network gain: $\Omega(n)$ | Helped |
| Use a star network for opinion formation rather than learn independently | Linear regression opinion formation · Star | network gain: $O(1)$ | No clear effect |
| Collaborate through opinion formation on a hypercube rather than learn independently | Linear regression opinion formation · Hypercube | network gain: $\Omega(d^2)$ | Helped |
| Collaborate through opinion formation on a random d-regular graph rather than learn independently | Linear regression opinion formation · Random d-regular graph | network gain: $\Omega(\min\{d^2, n\})$ | Helped |
| Allocate samples inversely to node degree | Opinion formation sample allocation · Networks with uniform influence factors | total sample complexity: $TSC(G, \alpha, k, \epsilon) = \Theta(\sum_{i \in [n]} m_i^* + nk)$ | Helped |
| Use opinion formation on a random d-regular graph with degree ranging from 2 to 10 | Opinion formation · Random d-regular graphs | network gain: $\Theta(d^2)$ | Helped |
| Use degree 11 in the random d-regular graph setup | Opinion formation · Random d-regular graph, degree 11 | network gain: infinity | Helped |
| Use the derived bounds for general influence factors | TSC estimation · Scale-free, Erdős-Rényi, random d-regular, and real-world networks | relative error of TSC bounds | Helped |
| Increase the influence factor | Opinion formation sample allocation · Networks with general influence factors | tightness of TSC bounds | Hurt |
Surprising findings
- Low-degree nodes need more samples, contrary to influence-maximization intuition that high-degree nodes are most valuable.
- A star graph gives almost no network gain over isolated learning.
Limitations
- Analysis restricted to (generalized) linear regression with unbiased noise and small-ball/non-degeneracy assumptions.
- Upper bound on network gain and general-influence bounds are not fully tight in theory; some bounds rely on empirical tightness.
Experimental setup
Datasets: ego-Facebook econ-mahindas email-Eu-core 130bit
Metrics: total sample complexity network gain relative error of TSC bounds
Builds on: DeGroot model fine-grained federated learning opinion formation game
Closest papers by meaning
- Learning Opinions in Social Networks (ICML 2020 · similarity 0.89)
- Game Theory Based Community-Aware Opinion Dynamics (AAAI 2026 · similarity 0.88)
- Opinion Maximization in Social Networks by Modifying Internal Opinions (NeurIPS 2025 · similarity 0.88)
- Majority Opinion Diffusion in Social Networks: An Adversarial Approach (AAAI 2021 · similarity 0.87)
- Reaching a Consensus in Predictive Loops (NeurIPS 2026 · similarity 0.85)
- Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.