OpenRaiser/Intern-Atlas huggingface dataset:
Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
Venue: arXiv cs.NE 2020
Year: 2020

Several recent trends in machine learning theory and practice, from the design of state-of-the-art Gaussian Process to the convergence analysis of deep neural nets (DNNs) under stochastic gradient descent (SGD), have found it fruitful to study wide random neural networks. Central to these approaches are certain scaling limits of such networks. We unify these results by introducing a notion of a straightline \emph{tensor program} that can express most neural network computations, and we characterize its scaling limit when its tensors are large and randomized. From our framework follows (1) the convergence of random neural networks to Gaussian processes for architectures such as recurrent neural networks, convolutional neural networks, residual networks, attention, and any combination thereof, with or without batch normalization; (2) conditions under which the \emph{gradient independence assumption} -- that weights in backpropagation can be assumed to be independent from weights in the forward pass -- leads to correct computation of gradient dynamics, and corrections when it does not; (3) the convergence of the Neural Tangent Kernel, a recently proposed kernel used to predict training dynamics of neural networks under gradient descent, at initialization for all architectures in (1) without batch normalization. Mathematically, our framework is general enough to rederive classical random matrix results such as the semicircle and the Marchenko-Pastur laws, as well as recent results in neural network Jacobian singular values. We hope our work opens a way toward design of even stronger Gaussian Processes, initialization schemes to avoid gradient explosion/vanishing, and deeper understanding of SGD dynamics in modern architectures.
Space-Efficient Data Structures for Lattices
Venue: arXiv cs.DS 2020
Year: 2020

A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity. Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in $O(n^{3/4})$ time, where $n$ is the number of elements in the lattice. It occupies $O(n^{3/2}\log n)$ bits of space, which is only a $Θ(\log n)$ factor from the $Θ(n^{3/2})$-bit lower bound for storing lattices. The preprocessing time is $O(n^2)$. This structure admits a simple space-time tradeoff so that, for any $c \in [\frac{1}{2}, 1]$, the data structure supports meet and join queries in $O(n^{1-c/2})$ time, occupies $O(n^{1+c}\log n)$ bits of space, and can be constructed in $O(n^2 + n^{1+3c/2})$ time. Our second data structure uses $O(n^{3/2}\log n)$ bits of space and supports meet and join in $O(d \frac{\log n}{\log d})$ time, where $d$ is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements. This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.
Local Media and Geo-situated Responses to Brexit: A Quantitative Analysis of Twitter, News and Survey Data
Venue: arXiv cs.CY 2020
Year: 2020

Societal debates and political outcomes are subject to news and social media influences, which are in turn subject to commercial and other forces. Local press are in decline, creating a ``news gap''. Research shows a contrary relationship between UK regions' economic dependence on EU membership and their voting in the 2016 UK EU membership referendum, raising questions about local awareness. We draw on a corpus of Twitter data which has been annotated for user location and Brexit vote intent, allowing us to investigate how location, topics of concern and Brexit stance are related. We compare this with a large corpus of articles from local and national news outlets, as well as survey data, finding evidence of a distinctly different focus in local reporting. National press focused more on terrorism and immigration than local press in most areas. Some Twitter users focused on immigration. Local press focused on trade, unemployment, local politics and agriculture. We find that remain voters shared interests more in keeping with local press on a per-region basis.
Quantifying the effects of data augmentation and stain color normalization in convolutional neural networks for computational pathology
Venue: arXiv cs.CV 2020
Year: 2020

Stain variation is a phenomenon observed when distinct pathology laboratories stain tissue slides that exhibit similar but not identical color appearance. Due to this color shift between laboratories, convolutional neural networks (CNNs) trained with images from one lab often underperform on unseen images from the other lab. Several techniques have been proposed to reduce the generalization error, mainly grouped into two categories: stain color augmentation and stain color normalization. The former simulates a wide variety of realistic stain variations during training, producing stain-invariant CNNs. The latter aims to match training and test color distributions in order to reduce stain variation. For the first time, we compared some of these techniques and quantified their effect on CNN classification performance using a heterogeneous dataset of hematoxylin and eosin histopathology images from 4 organs and 9 pathology laboratories. Additionally, we propose a novel unsupervised method to perform stain color normalization using a neural network. Based on our experimental results, we provide practical guidelines on how to use stain color augmentation and stain color normalization in future computational pathology applications.
Link Prediction via Higher-Order Motif Features
Venue: arXiv cs.SI 2020
Year: 2020

Link prediction requires predicting which new links are likely to appear in a graph. Being able to predict unseen links with good accuracy has important applications in several domains such as social media, security, transportation, and recommendation systems. A common approach is to use features based on the common neighbors of an unconnected pair of nodes to predict whether the pair will form a link in the future. In this paper, we present an approach for link prediction that relies on higher-order analysis of the graph topology, well beyond common neighbors. We treat the link prediction problem as a supervised classification problem, and we propose a set of features that depend on the patterns or motifs that a pair of nodes occurs in. By using motifs of sizes 3, 4, and 5, our approach captures a high level of detail about the graph topology within the neighborhood of the pair of nodes, which leads to a higher classification accuracy. In addition to proposing the use of motif-based features, we also propose two optimizations related to constructing the classification dataset from the graph. First, to ensure that positive and negative examples are treated equally when extracting features, we propose adding the negative examples to the graph as an alternative to the common approach of removing the positive ones. Second, we show that it is important to control for the shortest-path distance when sampling pairs of nodes to form negative examples, since the difficulty of prediction varies with the shortest-path distance. We experimentally demonstrate that using off-the-shelf classifiers with a well constructed classification dataset results in up to 10 percentage points increase in accuracy over prior topology-based and feature learning methods.
Inference from Auction Prices
Venue: arXiv cs.GT 2020
Year: 2020

Econometric inference allows an analyst to back out the values of agents in a mechanism from the rules of the mechanism and bids of the agents. This paper gives an algorithm to solve the problem of inferring the values of agents in a dominant-strategy mechanism from the social choice function implemented by the mechanism and the per-unit prices paid by the agents (the agent bids are not observed). For single-dimensional agents, this inference problem is a multi-dimensional inversion of the payment identity and is feasible only if the payment identity is uniquely invertible. The inversion is unique for single-unit proportional weights social choice functions (common, for example, in bandwidth allocation); and its inverse can be found efficiently. This inversion is not unique for social choice functions that exhibit complementarities. Of independent interest, we extend a result of Rosen (1965), that the Nash equilbria of "concave games" are unique and pure, to an alternative notion of concavity based on Gale and Nikaido (1965).
On the Analysis of EM for truncated mixtures of two Gaussians
Venue: arXiv cs.LG 2020
Year: 2020

Motivated by a recent result of Daskalakis et al. 2018, we analyze the population version of Expectation-Maximization (EM) algorithm for the case of \textit{truncated} mixtures of two Gaussians. Truncated samples from a $d$-dimensional mixture of two Gaussians $\frac{1}{2} \mathcal{N}(\vecμ, \vecΣ)+ \frac{1}{2} \mathcal{N}(-\vecμ, \vecΣ)$ means that a sample is only revealed if it falls in some subset $S \subset \mathbb{R}^d$ of positive (Lebesgue) measure. We show that for $d=1$, EM converges almost surely (under random initialization) to the true mean (variance $σ^2$ is known) for any measurable set $S$. Moreover, for $d>1$ we show EM almost surely converges to the true mean for any measurable set $S$ when the map of EM has only three fixed points, namely $-\vecμ, \vec{0}, \vecμ$ (covariance matrix $\vecΣ$ is known), and prove local convergence if there are more than three fixed points. We also provide convergence rates of our findings. Our techniques deviate from those of Daskalakis et al. 2017, which heavily depend on symmetry that the untruncated problem exhibits. For example, for an arbitrary measurable set $S$, it is impossible to compute a closed form of the update rule of EM. Moreover, arbitrarily truncating the mixture, induces further correlations among the variables. We circumvent these challenges by using techniques from dynamical systems, probability and statistics; implicit function theorem, stability analysis around the fixed points of the update rule of EM and correlation inequalities (FKG).
On approximate pure Nash equilibria in weighted congestion games with polynomial latencies
Venue: arXiv cs.GT 2020
Year: 2020

We study natural improvement dynamics in weighted congestion games with polynomial latencies of maximum degree $d\geq 1$. We focus on two problems regarding the existence and efficiency of approximate pure Nash equilibria, with a reasonable small approximation factor, in these games. By exploiting a simple technique, we firstly show that such a game always admits a $d$-approximate potential function. This implies that every sequence of $d$-approximate improvement moves by the players leads to a $d$-approximate pure Nash equilibrium. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, the game always admits a constant approximate potential function. Secondly, using a simple potential function argument, we are able to show that a $(d+δ)$-approximate pure Nash equilibrium of cost at most $(d+1)/(d+δ)$ times the cost of an optimal state always exists, for $δ\in [0,1]$.
LipschitzLR: Using theoretically computed adaptive learning rates for fast convergence
Venue: arXiv cs.LG 2020
Year: 2020

Optimizing deep neural networks is largely thought to be an empirical process, requiring manual tuning of several hyper-parameters, such as learning rate, weight decay, and dropout rate. Arguably, the learning rate is the most important of these to tune, and this has gained more attention in recent works. In this paper, we propose a novel method to compute the learning rate for training deep neural networks with stochastic gradient descent. We first derive a theoretical framework to compute learning rates dynamically based on the Lipschitz constant of the loss function. We then extend this framework to other commonly used optimization algorithms, such as gradient descent with momentum and Adam. We run an extensive set of experiments that demonstrate the efficacy of our approach on popular architectures and datasets, and show that commonly used learning rates are an order of magnitude smaller than the ideal value.
Spatially-Adaptive Filter Units for Compact and Efficient Deep Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks excel in a number of computer vision tasks. One of their most crucial architectural elements is the effective receptive field size, that has to be manually set to accommodate a specific task. Standard solutions involve large kernels, down/up-sampling and dilated convolutions. These require testing a variety of dilation and down/up-sampling factors and result in non-compact representations and excessive number of parameters. We address this issue by proposing a new convolution filter composed of displaced aggregation units (DAU). DAUs learn spatial displacements and adapt the receptive field sizes of individual convolution filters to a given problem, thus eliminating the need for hand-crafted modifications. DAUs provide a seamless substitution of convolutional filters in existing state-of-the-art architectures, which we demonstrate on AlexNet, ResNet50, ResNet101, DeepLab and SRN-DeblurNet. The benefits of this design are demonstrated on a variety of computer vision tasks and datasets, such as image classification (ILSVRC 2012), semantic segmentation (PASCAL VOC 2011, Cityscape) and blind image de-blurring (GOPRO). Results show that DAUs efficiently allocate parameters resulting in up to four times more compact networks at similar or better performance.
A systematic mapping study of developer social network research
Venue: arXiv cs.SE 2020
Year: 2020

Developer social networks (DSNs) are a tool for the analysis of community structures and collaborations between developers in software projects and software ecosystems. Within this paper, we present the results of a systematic mapping study on the use of DSNs in software engineering research. We identified 255 primary studies on DSNs. We mapped the primary studies to research directions, collected information about the data sources and the size of the studies, and conducted a bibliometric assessment. We found that nearly half of the research investigates the structure of developer communities. Other frequent topics are prediction systems build using DSNs, collaboration behavior between developers, and the roles of developers. Moreover, we determined that many publications use a small sample size regarding the number of projects, which could be problematic for the external validity of the research. Our study uncovered several open issues in the state of the art, e.g., studying inter-company collaborations, using multiple information sources for DSN research, as well as general lack of reporting guidelines or replication studies.
Perceptual Quality-preserving Black-Box Attack against Deep Learning Image Classifiers
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks provide unprecedented performance in all image classification problems, taking advantage of huge amounts of data available for training. Recent studies, however, have shown their vulnerability to adversarial attacks, spawning an intense research effort in this field. With the aim of building better systems, new countermeasures and stronger attacks are proposed by the day. On the attacker's side, there is growing interest for the realistic black-box scenario, in which the user has no access to the neural network parameters. The problem is to design efficient attacks which mislead the neural network without compromising image quality. In this work, we propose to perform the black-box attack along a low-distortion path, so as to improve both the attack efficiency and the perceptual quality of the adversarial image. Numerical experiments on real-world systems prove the effectiveness of the proposed approach, both in benchmark classification tasks and in key applications in biometrics and forensics.
SMART: Secure Magnetoelectric AntifeRromagnet-Based Tamper-Proof Non-Volatile Memory
Venue: arXiv cs.ET 2020
Year: 2020

The storage industry is moving toward emerging non-volatile memories (NVMs), including the spin-transfer torque magnetoresistive random-access memory (STT-MRAM) and the phase-change memory (PCM), owing to their high density and low-power operation. In this paper, we demonstrate, for the first time, circuit models and performance benchmarking for the domain wall (DW) reversal-based magnetoelectric-antiferromagnetic random access memory (ME-AFMRAM) at cell-level and at array-level. We also provide perspectives for coherent rotation-based memory switching with topological insulator-driven anomalous Hall read-out. In the coherent rotation regime, the ultra-low power magnetoelectric switching coupled with the terahertz-range antiferromagnetic dynamics result in substantially lower energy-per-bit and latency metrics for the ME-AFMRAM compared to other NVMs including STTMRAM and PCM. After characterizing the novel ME-AFMRAM, we leverage its unique properties to build a dense, on-chip, secure NVM platform, called SMART: A Secure Magnetoelectric Antiferromagnet- Based Tamper-Proof Non-Volatile Memory. New NVM technologies open up challenges and opportunities from a data-security perspective. For example, their sensitivity to magnetic fields and temperature fluctuations, and their data remanence after power-down make NVMs vulnerable to data theft and tampering attacks. The proposed SMART memory is not only resilient against data confidentiality attacks seeking to leak sensitive information but also ensures data integrity and prevents Denial-of-Service (DoS) attacks on the memory. It is impervious to particular power side-channel (PSC) attacks which exploit asymmetric read/write signatures for 0 and 1 logic levels, and photonic side-channel attacks which monitor photo-emission signatures from the chip backside.
Wasserstein Adversarial Examples via Projected Sinkhorn Iterations
Venue: arXiv cs.LG 2020
Year: 2020

A rapidly growing area of work has studied the existence of adversarial examples, datapoints which have been perturbed to fool a classifier, but the vast majority of these works have focused primarily on threat models defined by $\ell_p$ norm-bounded perturbations. In this paper, we propose a new threat model for adversarial attacks based on the Wasserstein distance. In the image classification setting, such distances measure the cost of moving pixel mass, which naturally cover "standard" image manipulations such as scaling, rotation, translation, and distortion (and can potentially be applied to other settings as well). To generate Wasserstein adversarial examples, we develop a procedure for projecting onto the Wasserstein ball, based upon a modified version of the Sinkhorn iteration. The resulting algorithm can successfully attack image classification models, bringing traditional CIFAR10 models down to 3% accuracy within a Wasserstein ball with radius 0.1 (i.e., moving 10% of the image mass 1 pixel), and we demonstrate that PGD-based adversarial training can improve this adversarial accuracy to 76%. In total, this work opens up a new direction of study in adversarial robustness, more formally considering convex metrics that accurately capture the invariances that we typically believe should exist in classifiers. Code for all experiments in the paper is available at https://github.com/locuslab/projected_sinkhorn.
Mitigating Metaphors: A Comprehensible Guide to Recent Nature-Inspired Algorithms
Venue: arXiv cs.NE 2020
Year: 2020

In recent years, a plethora of new metaheuristic algorithms have explored different sources of inspiration within the biological and natural worlds. This nature-inspired approach to algorithm design has been widely criticised. A notable issue is the tendency for authors to use terminology that is derived from the domain of inspiration, rather than the broader domains of metaheuristics and optimisation. This makes it difficult to both comprehend how these algorithms work and understand their relationships to other metaheuristics. This paper attempts to address this issue, at least to some extent, by providing accessible descriptions of the most cited nature-inspired algorithms published in the last twenty years. It also discusses commonalities between these algorithms and more classical nature-inspired metaheuristics such as evolutionary algorithms and particle swarm optimisation, and finishes with a discussion of future directions for the field.
Topology of Learning in Artificial Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Understanding how neural networks learn remains one of the central challenges in machine learning research. From random at the start of training, the weights of a neural network evolve in such a way as to be able to perform a variety of tasks, like classifying images. Here we study the emergence of structure in the weights by applying methods from topological data analysis. We train simple feedforward neural networks on the MNIST dataset and monitor the evolution of the weights. When initialized to zero, the weights follow trajectories that branch off recurrently, thus generating trees that describe the growth of the effective capacity of each layer. When initialized to tiny random values, the weights evolve smoothly along two-dimensional surfaces. We show that natural coordinates on these learning surfaces correspond to important factors of variation.
An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
Venue: arXiv cs.LG 2020
Year: 2020

The choice of batch-size in a stochastic optimization algorithm plays a substantial role for both optimization and generalization. Increasing the batch-size used typically improves optimization but degrades generalization. To address the problem of improving generalization while maintaining optimal convergence in large-batch training, we propose to add covariance noise to the gradients. We demonstrate that the learning performance of our method is more accurately captured by the structure of the covariance matrix of the noise rather than by the variance of gradients. Moreover, over the convex-quadratic, we prove in theory that it can be characterized by the Frobenius norm of the noise matrix. Our empirical studies with standard deep learning model-architectures and datasets shows that our method not only improves generalization performance in large-batch training, but furthermore, does so in a way where the optimization performance remains desirable and the training duration is not elongated.
A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
Venue: arXiv cs.LG 2020
Year: 2020

We consider the decomposition of a data matrix assumed to be a superposition of a low-rank matrix and a component which is sparse in a known dictionary, using a convex demixing method. We consider two sparsity structures for the sparse factor of the dictionary sparse component, namely entry-wise and column-wise sparsity, and provide a unified analysis, encompassing both undercomplete and the overcomplete dictionary cases, to show that the constituent matrices can be successfully recovered under some relatively mild conditions on incoherence, sparsity, and rank. We leverage these results to localize targets of interest in a hyperspectral (HS) image based on their spectral signature(s) using the a priori known characteristic spectral responses of the target. We corroborate our theoretical results and analyze target localization performance of our approach via experimental evaluations and comparisons to related techniques.