Impact of Community Structure on Consensus Machine Learning

• URL: http://arxiv.org/abs/2011.01334v1
• Date: Mon, 2 Nov 2020 21:41:35 GMT
• Title: Impact of Community Structure on Consensus Machine Learning
• Authors: Bao Huynh, Haimonti Dutta, Dane Taylor
• Abstract summary: We study consensus machine learning over networks drawn from block models. We find that there exists a critical level of community structure at which $tau_epsilon$ reaches a lower bound.
• Score: 0.17188280334580192
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consensus dynamics support decentralized machine learning for data that is distributed across a cloud compute cluster or across the internet of things. In these and other settings, one seeks to minimize the time $\tau_\epsilon$ required to obtain consensus within some $\epsilon>0$ margin of error. $\tau_\epsilon$ typically depends on the topology of the underlying communication network, and for many algorithms $\tau_\epsilon$ depends on the second-smallest eigenvalue $\lambda_2\in[0,1]$ of the network's normalized Laplacian matrix: $\tau_\epsilon\sim\mathcal{O}(\lambda_2^{-1})$. Here, we analyze the effect on $\tau_\epsilon$ of network community structure, which can arise when compute nodes/sensors are spatially clustered, for example. We study consensus machine learning over networks drawn from stochastic block models, which yield random networks that can contain heterogeneous communities with different sizes and densities. Using random matrix theory, we analyze the effects of communities on $\lambda_2$ and consensus, finding that $\lambda_2$ generally increases (i.e., $\tau_\epsilon$ decreases) as one decreases the extent of community structure. We further observe that there exists a critical level of community structure at which $\tau_\epsilon$ reaches a lower bound and is no longer limited by the presence of communities. We support our findings with empirical experiments for decentralized support vector machines.

Related papers

• Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
  We show at a physics level of rigor that Bayesian inference with a fully connected neural network is solvable. We provide techniques to compute the model evidence and posterior to arbitrary order in $1/N$ and at arbitrary temperature.
  arXiv  Detail & Related papers  (2024-05-26T17:08:04Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  We show that for any fixed $epsilon>0$ and depth $i$, there is a poly-time algorithm that learns random Xavier networks of depth $i$. The algorithm runs in time and sample complexity of $(bard)mathrmpoly(epsilon-1)$, where $bar d$ is the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to $(bard)mathrmpolylog(eps
  arXiv  Detail & Related papers  (2023-05-25T22:27:42Z)
• Learning the Structure of Large Networked Systems Obeying Conservation Laws [5.86054250638667]
  Conservation laws in networked systems may be modeled as balance equations of the form $X = B* Y$. In several practical systems, the network structure is often unknown and needs to be estimated from data. We propose a new $ell_1$-regularized maximum likelihood estimator for this problem in the high-dimensional regime.
  arXiv  Detail & Related papers  (2022-06-14T18:16:52Z)
• Distributed Sparse Feature Selection in Communication-Restricted Networks [6.9257380648471765]
  We propose and theoretically analyze a new distributed scheme for sparse linear regression and feature selection. In order to infer the causal dimensions from the whole dataset, we propose a simple, yet effective method for information sharing in the network.
  arXiv  Detail & Related papers  (2021-11-02T05:02:24Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)
• Maximizing Influence of Leaders in Social Networks [15.05158252504978]
  We consider the edge addition problem for the DeGroot model of opinion dynamics in a social network with $n$ nodes and $m$ edges. We show that our algorithm is efficient and effective, which scales to large networks with more than a million nodes.
  arXiv  Detail & Related papers  (2021-06-11T02:31:46Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  We consider the dynamic of descent for learning a two-layer neural network. We show that an over-parametrized two-layer neural network can provably learn with gradient loss at most ground with Tangent samples.
  arXiv  Detail & Related papers  (2020-07-09T07:09:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.