Networks are a useful representation for data on connections between units of interests, but the observed connections are often noisy and/or include missing values. One common approach to network analysis is to treat the network as a realization from a random graph model, and estimate the underlying edge probability matrix, which is sometimes referred to as network denoising. Here we propose a generalized linear model with low rank effects to model network edges. This model can be applied to various types of networks, including directed and undirected, binary and weighted, and it can naturally utilize additional information such as node and/or edge covariates. We develop an efficient projected gradient ascent algorithm to fit the model, establish asymptotic consistency, and demonstrate empirical performance of the method on both simulated and real networks.
Successful training of convolutional neural networks is often associated with the training of sufficiently deep architectures composed of high amounts of features while relying on a variety of regularization and pruning techniques to converge to less redundant states. We introduce an easy to compute metric, based on feature time evolution, to evaluate feature importance during training and demonstrate its potency in determining a networks effective capacity. In consequence we propose a novel algorithm to evolve fixed-depth architectures starting from just a single feature per layer to attain effective representational capacities needed for a specific task by greedily adding feature by feature. We revisit popular CNN architectures and demonstrate how evolved architectures not only converge to similar topologies that benefit from less parameters or improved accuracy, but furthermore exhibit systematic correspondence in representational complexity with the specified task. In contrast to conventional design patterns that typically have a monotonic increase in the amount of features with increased depth, we observe that CNNs perform better when there is a peak in learnable parameters in intermediate, with falloffs to earlier and later layers.
This paper studies the landscape of empirical risk of deep neural networks by theoretically analyzing its convergence behavior to the population risk as well as its stationary points and properties. For an $l$-layer linear neural network, we prove its empirical risk uniformly converges to its population risk at the rate of $\mathcal{O}(r^{2l}\sqrt{d\log(l)}/\sqrt{n})$ with training sample size of $n$, the total weight dimension of $d$ and the magnitude bound $r$ of weight of each layer. We then derive the stability and generalization bounds for the empirical risk based on this result. Besides, we establish the uniform convergence of gradient of the empirical risk to its population counterpart. We prove the one-to-one correspondence of the non-degenerate stationary points between the empirical and population risks with convergence guarantees, which describes the landscape of deep neural networks. In addition, we analyze these properties for deep nonlinear neural networks with sigmoid activation functions. We prove similar results for convergence behavior of their empirical risks as well as the gradients and analyze properties of their non-degenerate stationary points. To our best knowledge, this work is the first one theoretically characterizing landscapes of deep learning algorithms. Besides, our results provide the sample complexity of training a good deep neural network. We also provide theoretical understanding on how the neural network depth $l$, the layer width, the network size $d$ and parameter magnitude determine the neural network landscapes.