Edgeworth expansions for network moments

• URL: http://arxiv.org/abs/2004.06615v2
• Date: Mon, 4 Jan 2021 05:08:25 GMT
• Title: Edgeworth expansions for network moments
• Authors: Yuan Zhang, Dong Xia
• Abstract summary: We present the first higher-order accurate approximation to the sampling CDF of a studentized network moment by Edgeworth expansion. For sparse networks, our theory shows a simple normal approximation achieves a gradually depreciating Berry-Esseen bound as the network becomes sparser.
• Score: 20.058158445038824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Network method of moments arXiv:1202.5101 is an important tool for nonparametric network inference. However, there has been little investigation on accurate descriptions of the sampling distributions of network moment statistics. In this paper, we present the first higher-order accurate approximation to the sampling CDF of a studentized network moment by Edgeworth expansion. In sharp contrast to classical literature on noiseless U-statistics, we show that the Edgeworth expansion of a network moment statistic as a noisy U-statistic can achieve higher-order accuracy without non-lattice or smoothness assumptions but just requiring weak regularity conditions. Behind this result is our surprising discovery that the two typically-hated factors in network analysis, namely, sparsity and edge-wise observational errors, jointly play a blessing role, contributing a crucial self-smoothing effect in the network moment statistic and making it analytically tractable. Our assumptions match the minimum requirements in related literature. For sparse networks, our theory shows a simple normal approximation achieves a gradually depreciating Berry-Esseen bound as the network becomes sparser. This result also refines the best previous theoretical result. For practitioners, our empirical Edgeworth expansion is highly accurate, fast and easy to implement. We demonstrate the clear advantage of our method by comprehensive simulation studies. We showcase three applications of our results in network inference. We prove, to our knowledge, the first theoretical guarantee of higher-order accuracy for some network bootstrap schemes, and moreover, the first theoretical guidance for selecting the sub-sample size for network sub-sampling. We also derive one-sample test and Cornish-Fisher confidence interval for a given moment with higher-order accurate controls of confidence level and type I error, respectively.

Related papers

• Quantifying lottery tickets under label noise: accuracy, calibration, and complexity [6.232071870655069]
  Pruning deep neural networks is a widely used strategy to alleviate the computational burden in machine learning. We use the sparse double descent approach to identify univocally and characterise pruned models associated with classification tasks.
  arXiv  Detail & Related papers  (2023-06-21T11:35:59Z)
• ZigZag: Universal Sampling-free Uncertainty Estimation Through Two-Step Inference [54.17205151960878]
  We introduce a sampling-free approach that is generic and easy to deploy. We produce reliable uncertainty estimates on par with state-of-the-art methods at a significantly lower computational cost.
  arXiv  Detail & Related papers  (2022-11-21T13:23:09Z)
• CNN-based Prediction of Network Robustness With Missing Edges [0.9239657838690227]
  We investigate the performance of CNN-based approaches for connectivity and controllability prediction, when partial network information is missing. A threshold is explored that if a total amount of more than 7.29% information is lost, the performance of CNN-based prediction will be significantly degenerated.
  arXiv  Detail & Related papers  (2022-08-25T03:36:20Z)
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks [79.74580058178594]
  We analyze the performance of training a pruned neural network by analyzing the geometric structure of the objective function. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned.
  arXiv  Detail & Related papers  (2021-10-12T01:11:07Z)
• How much pre-training is enough to discover a good subnetwork? [10.699603774240853]
  We mathematically analyze the amount of dense network pre-training needed for a pruned network to perform well. We find a simple theoretical bound in the number of gradient descent pre-training iterations on a two-layer, fully-connected network. Experiments with larger datasets require more pre-training forworks obtained via pruning to perform well.
  arXiv  Detail & Related papers  (2021-07-31T15:08:36Z)
• Robustness to Pruning Predicts Generalization in Deep Neural Networks [29.660568281957072]
  We introduce prunability: the smallest emphfraction of a network's parameters that can be kept while pruning without adversely affecting its training loss. We show that this measure is highly predictive of a model's generalization performance across a large set of convolutional networks trained on CIFAR-10.
  arXiv  Detail & Related papers  (2021-03-10T11:39:14Z)
• Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracy [42.15969584135412]
  Neural network pruning is a popular technique used to reduce the inference costs of modern networks. We evaluate whether the use of test accuracy alone in the terminating condition is sufficient to ensure that the resulting model performs well. We find that pruned networks effectively approximate the unpruned model, however, the prune ratio at which pruned networks achieve commensurate performance varies significantly across tasks.
  arXiv  Detail & Related papers  (2021-03-04T13:22:16Z)
• S2-BNN: Bridging the Gap Between Self-Supervised Real and 1-bit Neural Networks via Guided Distribution Calibration [74.5509794733707]
  We present a novel guided learning paradigm from real-valued to distill binary networks on the final prediction distribution. Our proposed method can boost the simple contrastive learning baseline by an absolute gain of 5.515% on BNNs. Our method achieves substantial improvement over the simple contrastive learning baseline, and is even comparable to many mainstream supervised BNN methods.
  arXiv  Detail & Related papers  (2021-02-17T18:59:28Z)
• Neural Pruning via Growing Regularization [82.9322109208353]
  We extend regularization to tackle two central problems of pruning: pruning schedule and weight importance scoring. Specifically, we propose an L2 regularization variant with rising penalty factors and show it can bring significant accuracy gains. The proposed algorithms are easy to implement and scalable to large datasets and networks in both structured and unstructured pruning.
  arXiv  Detail & Related papers  (2020-12-16T20:16:28Z)
• Towards Practical Lottery Ticket Hypothesis for Adversarial Training [78.30684998080346]
  We show there exists a subset of the aforementioned sub-networks that converge significantly faster during the training process. As a practical application of our findings, we demonstrate that such sub-networks can help in cutting down the total time of adversarial training.
  arXiv  Detail & Related papers  (2020-03-06T03:11:52Z)
• Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networks [65.24701908364383]
  We show that a sufficient condition for a uncertainty on a ReLU network is "to be a bit Bayesian calibrated" We further validate these findings empirically via various standard experiments using common deep ReLU networks and Laplace approximations.
  arXiv  Detail & Related papers  (2020-02-24T08:52:06Z)

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.