Sample Complexity of Linear Regression Models for Opinion Formation in Networks

We consider a fixed set $V=\{1,2,\cdots,n\}$ of agents (also referred to as nodes) connected by a network $G=(V,E)$. Let $N(i)$ denote the set of neighbors, and $d_{i}$ the degree of agent $i$. We assume every agent $i$ in a given network $G$ has a dataset $S_{i}=\{(x_{i}^{j},y_{i}^{j})\}_{j\in[m_{i}]}$ allocated by a market-designer, where $m_{i}$ is the number of samples at $i$, and $x_{i}^{j}\in\mathbb{R}^{k},\,\,\forall j\in[m_{i}]$, and are independently drawn from a fixed distribution $D$ with dimension $k$. Each agent $i$ learns an initial model $\bar{\theta}_{i}$ (known as internal opinion); $\bar{\theta}_{i}$ need not be a fixed number (as in (Bindel, Kleinberg, and Oren 2015)), but can be learned through a machine learning approach, similar as (Haghtalab, Jackson, and Procaccia 2021). We assume that these datasets are allocated by a system designer and that $m_{i}\geq k$ (i.e., $S_{i}$ has at least $k$ samples), which ensures everyone has enough basic knowledge to form their own opinion before learning over the social network. Our full paper (Liu et al. 2023) includes a table of all notations.

Agent $i$’s goal is to find a model $\theta_{i}$ that is close to its internal opinion, as well as to that of its neighbors, denoted by $N(i)$; i.e. compute $\theta_{i}$ that minimizes the loss function $\|\theta_{i}-\bar{\theta}_{i}\|^{2}+\sum_{j\in N(i)}v_{ij}\|\theta_{i}-\theta_{j}\|^{2}$, where $v_{ij}\geq 0$ measures the influence of a neighboring agent $j$ to agent $i$. We refer to $\boldsymbol{v}$, where $[\boldsymbol{v}]_{ij}=v_{ij}$, as the influence factor matrix. In Lemma 1, we show that the unique Nash equilibrium of this game is $(\theta^{eq}_{1},\cdots,\theta^{eq}_{n})^{T}=W^{-1}(\bar{\theta}_{1},\cdots,\bar{\theta}_{n})^{T}$ where $W=\mathcal{L}+I$ and $\mathcal{L}$ is the weighted Laplacian matrix of $G$.

We define the total sample complexity, $TSC(G,\boldsymbol{v},k,\epsilon)$, as the minimum number of total samples, $\sum_{i}m_{i}$, subject to the constraint $m_{i}\geq k$, so that the expected square loss of $\theta_{i}^{eq}$ is at most $\epsilon$ for all $i$; here $m_{i}=|S_{i}|$. In the special case where the influence is uniform, i.e., $v_{ij}=\alpha,\forall i,j$, we use $TSC(G,\alpha,k,\epsilon)$ to denote the total sample complexity.

Let $\widetilde{M}(k,\epsilon)$ denote the minimum number of samples that any agent $i$ would need to ensure that the best model $\bar{\theta}_{i}$ learned using only their samples ensures that the expected error is at most some target $\epsilon$; if there is no interaction between the agents, a total of $n\widetilde{M}(k,\epsilon)$ samples would be needed to ensure that $\bar{\theta}_{i}$ has low error for each agent. Since every agent has at least $k$ samples, we refer to

the ratio of the additional samples needed to achieve error of $\epsilon$ for every agent under social learning to that needed under independent learning, as the network gain of $G$. We will show that for linear regression $\widetilde{M}(k,\epsilon)=\Theta(\frac{k}{\epsilon})$ (Theorem 2). We assume $\widetilde{M}(k,\epsilon)>k$ and the network gain can be infinite when $TSC(G,\boldsymbol{v},k,\epsilon)=nk$.

Our focus here is to estimate the $TSC(G,\boldsymbol{v},k,\epsilon)$, and the network gain $\mu(G,\boldsymbol{v},k,\epsilon)$, and characterize the distribution of the optimal $m_{i}$s across the network. Most proofs are presented in our full paper (Liu et al. 2023).

From Table 1, we can see a well-connected network offers a substantial reduction in TSC (high network gain), whereas a star graph provides almost no gain compared to individual learning. We also demonstrate that the lower bounds on network gain in Table 1 are tight. More detailed results for specific networks can be found in Table 2.

Finally, we consider general influence factors and derive upper and lower bounds on TSC for arbitrary graphs (Theorem 7). We find that these bounds are empirically tight.

Sample complexity of collaborative learning. Building on Blum et al. (2017), a series of papers (Chen, Zhang, and Zhou 2018; Nguyen and Zakynthinou 2018; Blum et al. 2021; Haghtalab, Jordan, and Zhao 2022) studied the minimum number of samples to ensure every agent has a low-error model in collaborative learning. In this setting, there is a center that can iteratively draw samples from different mixtures of agents’ data distributions, and dispatch the final model to each agent. In contrast, we use the well-established decentralized opinion formation framework to describe the model exchange game; the final model of every agent is given by the equilibrium of this game.

Our formulation is similar to (Blum et al. 2021), which also considers the sample complexity of equilibrium, ensuring every agent has a sufficient utility guarantee. However, (Blum et al. 2021) study this problem in an incentive-aware setting without networks, which mainly focuses on the stability and fairness of the equilibrium. In contrast, our research is centered on the network effect of the equilibrium generated by the opinion formation model. Moreover, (Blum et al. 2021) assumes the agents’ utility has certain structures that are not derived from error bounds while we directly minimize the generalization error of agents’ final models.

(Haddadan, Xin, and Gao 2024) is another related paper which also considers learning on networks under opinion dynamic process. However, they study selecting $K$ agents to correct their prediction to maximize the overall accuracy in the entire network, rather than the sample complexity bound to ensure individual learner has a good model as our paper.

We first define the error for initial opinion as

To quantify the upper bound of $L(\bar{\theta}_{i})$, we additionally consider the following assumption on data distribution.

Given Assumption 1, $\Sigma_{i}$ is guaranteed to be invertible. Assumption 2 ensures $\Sigma_{i}^{-\frac{1}{2}}x$ is not too close to any fixed hyperplane, which is introduced in (Mourtada 2022) and is a variant of the small-ball condition in (Koltchinskii and Mendelson 2015; Mendelson 2015; Lecué and Mendelson 2016). From Proposition 5 in (Mourtada 2022) (see also Theorem 1.2 in (Rudelson and Vershynin 2015)), if every coordinate of $D$ are independent and have bounded density ratio, then Assumption 2 holds. More discussions on this assumption could be found in Section 3.3 in (Mourtada 2022).

For certain data distributions, tighter closed-form bounds have been derived. For instance, if $D$ is a $k$-dimensional multivariate Gaussian distribution with zero mean, then $L(\bar{\theta}_{i})=\frac{\sigma^{2}k}{m_{i}-k-1}$ (Anderson et al. 1958; Breiman and Freedman 1983; Donahue and Kleinberg 2021). For mean estimation, $L(\bar{\theta}_{i})=\frac{\sigma^{2}}{m_{i}}$ (Donahue and Kleinberg 2021). Theorem 2 shows that $L(\bar{\theta}_{i})$ scales with $\frac{k}{m_{i}}$, assuming the data distributions satisfy non-degeneracy and the small-ball condition. Thus, $\widetilde{M}(k,\epsilon)=\Theta(\frac{k}{\epsilon})$ samples suffice for a single agent learning a model with error $\epsilon$.

We next present our main technique for bounding the generalization error of an equilibrium model, which uses Theorem 2 to express the error as a function of the matrix $W$ and the number of samples at each agent.

Armed with Theorem 3, we initiate the study of total sample complexity of opinion convergence. Recall that we want to ensure that at the equilibrium, every node on the network has a model with a small generalization error. Specifically, we want to ensure $L(\theta_{i}^{eq})\leq\epsilon$ for any $i\in[n]$ and a given $\epsilon>0$. Theorem 3 precisely gives us the mechanism to achieve a desired error bound.

From Theorem 4, $TSC(G,\boldsymbol{v},k,\epsilon)$ has order $\sum_{i=1}^{n}m_{i}^{*}+nk$ and assigning $\max\left\{\lceil m_{i}^{*}\rceil,k\right\}$ samples to agent $i$ is sufficient to solve the TSC problem up to some constant. Thus, we only need to focus on the solution of Equation B.2, $m_{i}^{*},\forall i\in[n]$. In the following sections, we will characterize properties of $m_{i}^{*},\forall i\in[n]$ and use it to prove network gain for different graphs.

We model uniform influence factors by setting $v_{ij}=\alpha$ for every agent $i$ and neighbor $j$ of $i$, for a given real $\alpha\geq 0$. Let $TSC(G,\alpha,k,\epsilon)$ be the solution of the optimization in Theorem 4 for this case. Theorem 5 provides interpretable bounds for $TSC(G,\alpha,k,\epsilon)$ related to degree, and serves as the first step to derive tight bounds for specific graph classes. The proof of Theorem 5 leverages the dual form of Equation B.2, together with a careful analysis of matrix $W$ defined in Lemma 1. Detailed proof can be found in (Liu et al. 2023).

Theorem 5 suggests that it is sufficient to allocate samples inversely proportional to the node degrees. This has interesting policy implications; in contrast to other social network models, e.g., the classic work on influence maximization (Kempe, Kleinberg, and Tardos 2003), our result advocates that allocating more resources to low-connectivity agents benefit the network at large. We provide empirical validation of this phenomenon in Section 5.

With the help of Theorem 5, we could derive the bounds of network gain for any graph in Corollary 6.

For small $\epsilon$, Corollary 6 demonstrates that the network gain is at least $\Omega\left(\frac{n}{\sum_{i\in[n]}\frac{1}{d_{i}}}\right)$, implying that networks with more high-degree nodes result in higher network gain, but the gain is limited to $O\left(\min\left\{\frac{n}{\sum_{i\in[n]}\frac{1}{d_{i}^{2}}},n\right\}\right)$.

Now we are ready to analyze the tight network gain for special graphs classes. Our main results are shown in Table 2, with detailed lemmas and proofs deferred to (Liu et al. 2023). The third column of Table 2 gives $\sum_{i\in[n]}m_{i}^{*}$, which suffices to characterize total sample complexity (TSC) because $TSC(G,\alpha,k,\epsilon)=\Theta\left(\sum_{i\in[n]}m_{i}^{*}+nk\right)$ from Theorem 4. The last column indicates the number of samples required for each agent to ensure that all constraints of the TSC problem are satisfied. For each kind of graph, if the sample size for every agent is the maximum of $k$ and the term in the last column, it is sufficient to guarantee $L(\theta^{eq}_{i})\leq\epsilon,\,\,\forall i$. To prove the results in Table 2, we leverage the spectral properties of graph Laplacian $\mathcal{L}$ for different networks, together with the lower bound in Theorem 5. Note that the lower bound in Table 2 does not require any constraint on $\epsilon$. This contrasts with the bounds in Corrollary 6 and requires a more refined analysis. On the other hand, there is no general upper bound for the network gain because it can be infinite.

We now give a more detailed discussion of the results in Table 2 as follows. (1) For a clique, the network gain is $\Omega(n)$ and $TSC(G,\alpha,k,\epsilon)=\Theta\left(\frac{k}{\epsilon}+nk\right)$. From Corollary 6, this is the best lower bound of network gain for any graph. (2) For a star, when $\epsilon$ is less than some constant, the network gain is $O(1)$ and $TSC(G,\alpha,k,\epsilon)=\Theta\left(\frac{nk}{\epsilon}\right)$. This implies a star graph almost cannot get any gain compared with learning individually. (3) For a hypercube, when $\alpha\geq\frac{3}{8}$, the network gain is $\Omega(d^{2})$ and $TSC(G,\alpha,k,\epsilon)=\Theta\left(\frac{nk}{d^{2}\epsilon}+nk\right)$. (4) For a random d-regular graph, with high probability, the network gain is $\Omega(d^{2})$ when $d\leq\sqrt{n}$ while it is $\Omega(n)$ when $d>\sqrt{n}$. The total sample complexity is $TSC(G,\alpha,k,\epsilon)=\Theta\left(\frac{nk}{\min\{d^{2},n\}\epsilon}+nk\right)$. (5) For a $d$-regular graph $G$, the edge expansion $\tau(G)$ equals $\min\limits_{|S|:|S|\leq n/2}\frac{|\partial S|}{d|S|}$, where $\partial S$ is the set $\{(u,v)\in E:u\in S,v\in V\setminus S\}$. Edge expansion measures graph connectivity and can be viewed as a lower bound on the probability that a randomly chosen edge from any subset of vertices $S$ has one endpoint outside $S$. A $d$-expander denotes a $d$-regular graph with edge expansion $\tau(G)$. For this kind of graph, the network gain is $\Omega(\min\{d^{2}\tau(G)^{4},n\})$ and $TSC(G,\alpha,k,\epsilon)=\Theta(\frac{nk}{\min\{d^{2}\tau(G)^{4},n\}\epsilon}+nk)$. Note that the $\Omega\left(\min\{d^{2},n\}\right)$ lower bound is also optimal for these $d-$regular graphs from the upper bound in Corollary 6.

It follows from Table 2 and Corollary 6 that both random and expander $d$-regular graphs (with constant $\tau(G)$) have the optimal lower bound for network gain. Interestingly, this property also holds for the hypercube, which has regular degree $d=\log n$, even though its expansion is $O(\frac{1}{\log n})=o(1)$. A natural open question is to characterize other degree-bounded network families which also achieve near-optimal network gains.

Going beyond uniform influence factors, we investigate the total sample complexity of opinion convergence with general influence factors. The non-uniformity of the influence factors implies that the sample complexity is not just dependent on the network structure, but also on how each individual agent weighs the influence of its neighbors. A trivial bound is $\Omega\left(\frac{k}{\epsilon}\right)\leq TSC(G,\boldsymbol{v},k,\epsilon)\leq O\left(\frac{nk}{\epsilon}\right)$ which means learning through the game is always more beneficial than learning individually but needs at least the samples for one agent to learn a good model.

To derive more sophisticated and tighter bounds, we need to analyze the matrix $W$ with general weights, which captures both the network topology and influence factors. Since $W^{-1}$ is positive-definite, from the Schur product theorem, $(W^{-1})\circ(W^{-1})$ is also positive-definite where $\circ$ is the Hadamard product (element-wise product). Define $B=((W^{-1})\circ(W^{-1}))^{-1}$ and $[B]_{ij}=b_{ij}$. Theorem 7 establishes a bound for graphs with general influence factors, which is empirically tight from our experiments in Section 5. The proof for the upper bound utilizes a thorough analysis of the property of $b_{ij}$s, and the lower bound is derived based on the dual form of Equation B.2 with general weights. We refer the reader to (Liu et al. 2023) for the whole proof.

Although the above two bounds give good empirical estimations to the TSC, deriving closed-form solution for Equation B.2 is still interesting, and is investigated in Lemma 8 under a certain condition.

It is easy to verify that the condition in Lemma 8 holds for cliques, but beyond cliques, we have yet to identify other instances where it holds. Characterizing the graphs that meet this condition remains an interesting open problem