Deep neural networks (DNNs) often need to be reduced in size for implementation in customized hardware for applications and products. The fact that DNNs are almost always significantly overparameterized means that there is much room to reduce the size of these networks without adversely impacting their overall performance for most tasks. In this paper, we study whether pruning of DNNs introduces bias in the classification task above and beyond the trained but unpruned model and if it does, when and how to eliminate it. We define bias as the relative classification error frequency of each class before and after pruning, as measured by a χ2homogeneity test. To illustrate our methodology, we focus on the image classification task using popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 using high-performance DNNs such as VGG11, AlexNet, Transformers, customized CNNs and fully-connected networks and compare the error frequencies before and after pruning using the categorical χ2test. We observe that standard pruning schemes, even when they maintain the overall accuracies of the full DNN, can introduce bias. We show that it is possible to reduce such bias to small and negligible values using the framework of a truncated lottery ticket scheme, which we introduce and evaluate.

New deep learning models are massively over-parametrized, e.g., GPT-3 and Turing-NLG exceed 100Bs of parameters. Naturally, model reduction techniques such as pruning, quantization, and distillation have been proposed and deployed. In the pruning literature, the Lottery Ticket Hypothesis (LTH) is amongst the most cited. LTH provides a recipe for reducing the free parameters of a deep network by eliminating a large fraction of its edges by 1) remembering and reusing only the edges on the highest-traffic input-output paths and 2) resetting remaining parameters to their initial values after each round of elimination. Here, we extend this idea two steps further. We add a random buildup phase, starting from a small percentage of parameters to reach a predefined accuracy, often needing fewer than 50% of the parameters of a full network. Then we eliminate parameters using an LTH-like procedure combined with a binary search. We demonstrate the efficiency of the proposed technique using three well-known image data sets by sparsifying three standard deep nets. We exceed the elimination power of LTH (over 98% pruned) and effectively match the performance of full networks. We conclude that for both reducing computation and maintaining a sparse network for inference, the proposed scheme is effective and practical.

A hybrid approach based on the combination of saliency-based neural pruning and regularization-based sparsification is proposed. We propose using a graph diffusion process for determining the neuron importance for pruning. Then, we use a regularization loss based on weighted $L_{1}-$norm and $L_{2}-$norm during fine-tuning to recover the lost performance. This is followed by a threshold step to further impose sparsification. We demonstrate such a hybrid approach achieves significantly better performance in comparison to purely regularization-based sparsification for large neural networks. To this end, we assessed our proposed method on three tasks, including: image classification (3 network architectures), audio classification and image compression.

Clustering mixtures of Gaussian distributions is a fundamental and challenging problem. State-of-the-art theoretical work on learning Gaussian mixture models has mostly focused on estimating the mixture parameters, where clustering is given as a byproduct. These methods have focused mostly on improving separation bounds for different mixture classes, and doing so in polynomial time and sample complexity. Less emphasis has been given to aligning these algorithms to the challenges of big data. In this paper, we focus on clustering $n$ samples from an arbitrary mixture of $c$-separated Gaussians in $\mathbb{R}^p$ in time that is linear in $p$ and $n$, and sample complexity that is independent of $p$. Our analysis suggests that for sufficiently separated Gaussians after $o(\log{p})$ random projections a good direction is found that yields a small clustering error. Specifically, for a user-specified error $e$, the expected number of such projections is small and bounded by $o(\ln p)$ when $\gamma\leq c\sqrt{\ln{\ln{p}}}$ and $\gamma=Q^{-1}(e)$ is the separation of the Gaussians with $Q$ as the tail distribution function of the normal distribution. Consequently, the expected overall running time of the algorithm is linear in $n$ and quasi-linear in $p$ at $o(\ln{p})O(np)$, and the sample complexity is independent of $p$. Unlike the methods that are based on $k$-means, our analysis is applicable to any mixture class (spherical or non-spherical). Finally, an extension to $k>2$ components is also provided.

The universal approximation theorem states that any regular function can be approximated closely using a single hidden layer neural network. Some recent work has shown that, for some special functions, the number of nodes in such an approximation could be exponentially reduced with multi-layer neural networks. In this work, we extend this idea to a rich class of functions, namely the discriminant functions that arise in optimal Bayesian classification of Gaussian mixture models (GMMs) in $\mathds{R}^n$. We show that such functions can be approximated with arbitrary precision using $O(n)$ nodes in a neural network with two hidden layers (deep neural network), while in contrast, a neural network with a single hidden layer (shallow neural network) would require at least $O(\exp(n))$ nodes or exponentially large coefficients. Given the universality of the Gaussian distribution in the feature spaces of data, e.g., in speech, image and text, our results shed light on the observed efficiency of deep neural networks in practical classification problems.

We present a method of extracting figures and images from the pages of scanned documents, especially from technical research articles. Our approach is novel in two key ways. First, we treat this as a computer vision problem, and train convolutional neural networks to recognize figures in scanned pages. Second, we generate our training data from 'born-digital' structured documents, allowing us to automatically produce labels for our training set using PDF figure extractors. This avoids the otherwise tedious task of hand-labelling thousands of document pages. Our convolutional neural networks achieve precision and recall of close to 85% in identifying figures from a test set consisting of modern journal papers and conference proceedings, and obtain precision and recall above 80% on an application data set comprised of historical technical documents scanned from the Bell Labs Records. Our results show that models trained on digital documents transfer very well to historical scans. Finally, it is easy to extend our models to identify other document elements such as tables and captions.

Through detailed analysis of scores of publicly available data sets corresponding to a wide range of large-scale networks, from communication and road networks to various forms of social networks, we explore a little-studied geometric characteristic of real-life networks, namely their hyperbolicity. We provide strong evidence that large-scale communication and social networks exhibit this fundamental property, and through extensive computations we quantify the degree of hyperbolicity of each network in comparison to its diameter. By contrast, and as evidence of the validity of the methodology, applying the same technique to graphs of road networks shows that they are not hyperbolic, which is as expected. Finally, we present practical computational means for detection of hyperbolicity and show how the test itself may be scaled to much larger graphs than those we examined via renormalization group methodology.

Motivated by challenging resource allocation issues arising in large-scale wireless and wireline communication networks, we study distributed network utility maximization problems with a mixture of concave (e.g., best-effort throughputs) and nonconcave (e.g., voice/video streaming rates) utilities. In the first part of the paper, we develop our methodological framework in the context of a locally coupled networked system, where nodes represent agents that control a discrete local state. Each node has a possibly nonconcave local objective function, which depends on the local state of the node and the local states of its neighbors. The goal is to maximize the sum of the local objective functions of all nodes. We devise an iterative randomized algorithm, whose convergence and optimality properties follow from the classical framework of Markov Random Fields and Gibbs Measures via a judiciously selected neighborhood structure. The proposed algorithm is distributed, asynchronous, requires limited computational effort per node/iteration, and yields provable convergence in the limit. In order to demonstrate the scope of the proposed methodological framework, in the second part of the paper we show how the method can be applied to two different problems for which no distributed algorithm with provable convergence and optimality properties is available. Specifically, we describe how the proposed methodology provides a distributed mechanism for solving nonconcave utility maximization problems: 1) arising in OFDMA cellular networks, through power allocation and user assignment; 2) arising in multihop wireline networks, through explicit rate allocation. Several numerical experiments are presented to illustrate the convergence speed and performance of the proposed method.

Cloud providers may operate large-scale data centers in a few locations. We argue that deploying many small-scale data centers at network edge can significantly improve user experience in terms of latency. Small-scale data centers, however, may not be able to provide elastic services. In this paper, we investigate distributed small-scale data centers with load reallocation where jobs that cannot be suitably processed locally will be reallocated to remote data centers. We formulate an optimization problem for load reallocation in distributed data centers, provide performance comparisons among different alternatives and offer insights on handling multiple job types. We develop online optimization algorithms that can be operated in a decentralized and measurement-based fashion to dynamically reallocate load in response to sudden load surges. The experimental results demonstrate that elasticity can be practically provided by small-scale data centers enhanced with effective load reallocation techniques.

Good clustering can provide critical insight into potential locations where congestion in a network may occur. A natural measure of congestion for a collection of nodes in a graph is its Cheeger ratio, defined as the ratio of the size of its boundary to its volume. Spectral methods provide effective means to estimate the smallest Cheeger ratio via the spectral gap of the graph Laplacian. Here, we compute the spectral gap of the truncated graph Laplacian, with the so-called Dirichlet boundary condition, for the graphs of a dozen communication networks at the IP-layer, which are subgraphs of the much larger global IP-layer network. We show that i) the Dirichlet spectral gap of these networks is substantially larger than the standard spectral gap and is therefore a better indicator of the true expansion properties of the graph, ii) unlike the standard spectral gap, the Dirichlet spectral gaps of progressively larger subgraphs converge to that of the global network, thus allowing properties of the global network to be efficiently obtained from them, and (iii) the (first two) eigenvectors of the Dirichlet graph Laplacian can be used for spectral clustering with arguably better results than standard spectral clustering. We first demonstrate these results analytically for finite regular trees. We then perform spectral clustering on the IP-layer networks using Dirichlet eigenvectors and show that it yields cuts near the network core, thus creating genuine single-component clusters. This is much better than traditional spectral clustering where several disjoint fragments near the network periphery are liable to be misleadingly classified as a single cluster. Since congestion in communication networks is known to peak at the core due to large-scale curvature and geometry, identification of core congestion and its localization are important steps in analysis and improved engineering of networks. Thus, spectral clustering with Dirichlet boundary condition is seen to be more effective at finding bona-fide bottlenecks and congestion than standard spectral clustering.

We consider data networks in which real-time/near real-time applications require not only successful transmission of packets from source to destination, but also specific end-to-end delay bounds, such as voice over IP. Although there is a well-developed general theory for control of best-effort packet traffic in data networks (elastic traffic), little is known about decentralized control mechanisms that ensure end-to-end performance bounds (inelastic traffic). In this paper we propose and analyze a simple, distributed and self-stabilizing rate control scheme that uses only end-to-end delay feedback to ensure QoS while using the network resources efficiently. In particular, we show that while for short paths (up to two hops long) the proposed scheme guarantees end-to-end delay budgets for all node pairs and also maximizes the total network throughput, when there are long paths in the network the resulting solution, even though still self-stabilizing and QoS-compliant, can deviate from the global network throughput. We present numerical results and conclude with a discussion of possible implementations of the proposed scheme in multi-service networks involving a mixture of best-effort and QoS-constrained services.

We study the problem of jointly performing scheduling and congestion control in mobile ad-hoc networks so that network queues remain bounded and the resulting flow rates satisfy an associated network utility maximization problem. In recent years a number of papers have presented theoretical solutions to this problem that are based on combining differential-backlog scheduling algorithms with utility-based congestion control. However, this work typically does not address a number of issues such as how signaling should be performed and how the new algorithms interact with other wireless protocols. In this paper we address such issues. In particular: ldr We define a specific network utility maximization problem that we believe is appropriate for mobile adhoc networks. ldr We describe a wireless greedy primal dual (wGPD) algorithm for combined congestion control and scheduling that aims to solve this problem. ldr We show how the wGPD algorithm and its associated signaling can be implemented in practice with minimal disruption to existing wireless protocols. ldr We show via OPNET simulation that wGPD significantly outperforms standard protocols such as 802.11 operating in conjunction with TCP. This work was supported by the DARPA CBMANET program.

We consider the problem of traffic anomaly detection in IP networks. Traffic anomalies typically arise when there is focused overload or when a network element fails and it is desired to infer these purely from the measured traffic. We derive new general formulae for the variance of the cumulative traffic over a fixed time interval and show how the derived analytical expression simplifies for the case of voice over IP traffic, the focus of this paper. To detect load anomalies, we show it is sufficient to consider cumulative traffic over relatively long intervals such as 5 min. We also propose simple anomaly detection tests including detection of over/underload. This approach substantially extends the current practice in IP network management where only the first-order statistics and fixed thresholds are used to identify abnormal behavior. We conclude with the application of the scheme to field data from an operational network.

We consider meshed optical transport networks having multiple levels of hierarchy whereby cross-connects in different levels perform multiplexing and demultiplexing functions at different granularities. We present a traffic grooming approach that can be implemented in a centralized or distributed fashion, based on the novel design that takes advantage of algorithm efficiency and a simple threshold mechanism to decide when grooming is economical. Our approach allows nodes to perform grooming and degrooming automatically, which is desired in the next-generation optical network where circuits are setup and torn-down dynamically through signaling. We present several experiments using different network topologies. The results indicate that the flow pattern influences the port requirement behavior, and that the flow thickness influences the optimal value of the threshold.

A time-domain wavelength interleaved network (TWIN) (Widjaja, I. et al., IEEE Commun. Mag., vol.41, 2003) is an optical network with an ultrafast tunable laser and a fixed receiver at each node. We consider the problem of scheduling bursts of data in a TWIN. Due to the high data rates employed on the optical links, the burst transmissions typically last for very short times compared with the round trip propagation times between source-destination pairs. A good schedule should ensure that: 1) there are no transmit/receive conflicts; 2) propagation delays are observed; 3) throughput is maximized (schedule length is minimized). We formulate the scheduling problem with periodic demand as a generalization of the well-known crossbar switch scheduling. We prove that even in the presence of propagation delays, there exist a class of computationally viable scheduling algorithms which asymptotically achieve the maximum throughput obtainable without propagation delays. We also show that any schedule can be rearranged to achieve a factor-two approximation of the maximum throughput even without asymptotic limits. However, the delay/throughput performance of these schedules is limited in practice. We consequently propose a scheduling algorithm that exhibits near optimal (on average within ∼7% of optimum) delay/throughput performance in realistic network examples.

Recent measurement and simulation studies have revealed that wide area network traffic has complex statistical, possibly multifractal, characteristics on short timescales, and is self-similar on long timescales. In this paper, using measured TCP traces and queueing simulations, we show that the fine timescale features can affect performance substantially at low and intermediate utilizations, while the coarse timescale self-similarity is important at intermediate and high utilizations. We outline an analytical method for estimating performance for traffic that is self-similar on coarse timescales and multi-fractal on fine timescales, and show that the engineering problem of setting safe operating points for planning or admission control can be significantly affected by fine timescale fluctuations in network traffic.

This paper provides a very simple two-approximation algorithm for two NP-hard problems that arise in electronic circuit design. To our knowledge, this is the best approximation bound known for these problems. In addition, the simplicity of the proposed algorithm makes it attractive for real-time applications for similar problems in areas such as telecommunications and parallel processing.

The results of a traffic study undertaken to determine if a 64 kb/s common-signalling channel is sufficiently fast to meet the present and future call-processing needs of integrated digital loop-carrier (IDLC) systems are presented. Bell Communications Research (Bellcore) has proposed the use of such a 64 kb/s common signalling channel in a requirement document, technical reference TR-TSY-000303, to satisfy call-processing needs across the IDLC generic interface, whenever out-of-band signalling is used. The IDLC call-processing traffic on this message-oriented common-signalling channel is characterized, and associated design requirements in TR-303 under certain modelling assumptions (Poisson arrivals and exponential service time) are examined. Under worst-case conditions, it is concluded that a critical message requiring a response within 100 ms would practically always meet that delay criterion. Critical messages requiring a response within 40 ms would fail once every 10 busy hours. Since no specific signalling response requirement of 40 ms has been found, the authors conclude that a 64 kb/s common-signalling-channel for IDLC system is sufficiently fast to achieve required signalling response times.>