OpenRaiser/Intern-Atlas huggingface dataset:
Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Stochastic gradient descent with a large initial learning rate is widely used for training modern neural net architectures. Although a small initial learning rate allows for faster training and better test performance initially, the large learning rate achieves better generalization soon after the learning rate is annealed. Towards explaining this phenomenon, we devise a setting in which we can prove that a two layer network trained with large initial learning rate and annealing provably generalizes better than the same network trained with a small learning rate from the start. The key insight in our analysis is that the order of learning different types of patterns is crucial: because the small learning rate model first memorizes easy-to-generalize, hard-to-fit patterns, it generalizes worse on hard-to-generalize, easier-to-fit patterns than its large learning rate counterpart. This concept translates to a larger-scale setting: we demonstrate that one can add a small patch to CIFAR-10 images that is immediately memorizable by a model with small initial learning rate, but ignored by the model with large learning rate until after annealing. Our experiments show that this causes the small learning rate model's accuracy on unmodified images to suffer, as it relies too much on the patch early on.
Computing Minimal Persistent Cycles: Polynomial and Hard Cases
Venue: arXiv cs.CG 2020
Year: 2020

Persistent cycles, especially the minimal ones, are useful geometric features functioning as augmentations for the intervals in a purely topological persistence diagram (also termed as barcode). In our earlier work, we showed that computing minimal 1-dimensional persistent cycles (persistent 1-cycles) for finite intervals is NP-hard while the same for infinite intervals is polynomially tractable. In this paper, we address this problem for general dimensions with $\mathbb{Z}_2$ coefficients. In addition to proving that it is NP-hard to compute minimal persistent d-cycles (d>1) for both types of intervals given arbitrary simplicial complexes, we identify two interesting cases which are polynomially tractable. These two cases assume the complex to be a certain generalization of manifolds which we term as weak pseudomanifolds. For finite intervals from the d-th persistence diagram of a weak (d+1)-pseudomanifold, we utilize the fact that persistent cycles of such intervals are null-homologous and reduce the problem to a minimal cut problem. Since the same problem for infinite intervals is NP-hard, we further assume the weak (d+1)-pseudomanifold to be embedded in $\mathbb{R}^{d+1}$ so that the complex has a natural dual graph structure and the problem reduces to a minimal cut problem. Experiments with both algorithms on scientific data indicate that the minimal persistent cycles capture various significant features of the data.
Time-aware uniformization of winning strategies
Venue: arXiv cs.GT 2020
Year: 2020

Two-player win/lose games of infinite duration are involved in several disciplines including computer science and logic. If such a game has deterministic winning strategies, one may ask how simple such strategies can get. The answer may help with actual implementation, or to win despite imperfect information, or to conceal sensitive information especially if the game is repeated. Given a concurrent two-player win/lose game of infinite duration, this article considers equivalence relations over histories of played actions. A classical restriction used here is that equivalent histories have equal length, hence \emph{time awareness}. A sufficient condition is given such that if a player has winning strategies, she has one that prescribes the same action at equivalent histories, hence \emph{uniformization}. The proof is fairly constructive and preserves finiteness of strategy memory, and counterexamples show relative tightness of the result. Several corollaries follow for games with states and colors.
On the Optimality of Trees Generated by ID3
Venue: arXiv cs.LG 2020
Year: 2020

Since its inception in the 1980s, ID3 has become one of the most successful and widely used algorithms for learning decision trees. However, its theoretical properties remain poorly understood. In this work, we introduce a novel metric of a decision tree algorithm's performance, called mean iteration statistical consistency (MIC), which measures optimality of trees generated by ID3. As opposed to previous metrics, MIC can differentiate between different decision tree algorithms and compare their performance. We provide theoretical and empirical evidence that the TopDown variant of ID3, introduced by Kearns and Mansour (1996), has near-optimal MIC in various settings for learning read-once DNFs under product distributions. In contrast, another widely used variant of ID3 has MIC which is not near-optimal. We show that the MIC analysis predicts well the performance of these algorithms in practice. Our results present a novel view of decision tree algorithms which may lead to better and more practical guarantees for these algorithms.
Towards a Verified Model of the Algorand Consensus Protocol in Coq
Venue: arXiv cs.CR 2020
Year: 2020

The Algorand blockchain is a secure and decentralized public ledger based on pure proof of stake rather than proof of work. At its core it is a novel consensus protocol with exactly one block certified in each round: that is, the protocol guarantees that the blockchain does not fork. In this paper, we report on our effort to model and formally verify the Algorand consensus protocol in the Coq proof assistant. Similar to previous consensus protocol verification efforts, we model the protocol as a state transition system and reason over reachable global states. However, in contrast to previous work, our model explicitly incorporates timing issues (e.g., timeouts and network delays) and adversarial actions, reflecting a more realistic environment faced by a public blockchain. Thus far, we have proved asynchronous safety of the protocol: two different blocks cannot be certified in the same round, even when the adversary has complete control of message delivery in the network. We believe that our model is sufficiently general and other relevant properties of the protocol such as liveness can be proved for the same model.
Generative Modeling by Estimating Gradients of the Data Distribution
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a new generative model where samples are produced via Langevin dynamics using gradients of the data distribution estimated with score matching. Because gradients can be ill-defined and hard to estimate when the data resides on low-dimensional manifolds, we perturb the data with different levels of Gaussian noise, and jointly estimate the corresponding scores, i.e., the vector fields of gradients of the perturbed data distribution for all noise levels. For sampling, we propose an annealed Langevin dynamics where we use gradients corresponding to gradually decreasing noise levels as the sampling process gets closer to the data manifold. Our framework allows flexible model architectures, requires no sampling during training or the use of adversarial methods, and provides a learning objective that can be used for principled model comparisons. Our models produce samples comparable to GANs on MNIST, CelebA and CIFAR-10 datasets, achieving a new state-of-the-art inception score of 8.87 on CIFAR-10. Additionally, we demonstrate that our models learn effective representations via image inpainting experiments.
Adversarial Lipschitz Regularization
Venue: arXiv cs.LG 2020
Year: 2020

Generative adversarial networks (GANs) are one of the most popular approaches when it comes to training generative models, among which variants of Wasserstein GANs are considered superior to the standard GAN formulation in terms of learning stability and sample quality. However, Wasserstein GANs require the critic to be 1-Lipschitz, which is often enforced implicitly by penalizing the norm of its gradient, or by globally restricting its Lipschitz constant via weight normalization techniques. Training with a regularization term penalizing the violation of the Lipschitz constraint explicitly, instead of through the norm of the gradient, was found to be practically infeasible in most situations. Inspired by Virtual Adversarial Training, we propose a method called Adversarial Lipschitz Regularization, and show that using an explicit Lipschitz penalty is indeed viable and leads to competitive performance when applied to Wasserstein GANs, highlighting an important connection between Lipschitz regularization and adversarial training.
Intersection Types for the Computational lambda-Calculus
Venue: arXiv cs.LO 2020
Year: 2020

We study polymorphic type assignment systems for untyped lambda-calculi with effects, based on Moggi's monadic approach. Moving from the abstract definition of monads, we introduce a version of the call-by-value computational lambda-calculus based on Wadler's variant with unit and bind combinators, and without let. We define a notion of reduction for the calculus and prove it confluent, and also we relate our calculus to the original work by Moggi showing that his untyped metalanguage can be interpreted and simulated in our calculus. We then introduce an intersection type system inspired to Barendregt, Coppo and Dezani system for ordinary untyped lambda-calculus, establishing type invariance under conversion, and provide models of the calculus via inverse limit and filter model constructions and relate them. We prove soundness and completeness of the type system, together with subject reduction and expansion properties. Finally, we introduce a notion of convergence, which is precisely related to reduction, and characterize convergent terms via their types.
ACTNET: end-to-end learning of feature activations and multi-stream aggregation for effective instance image retrieval
Venue: arXiv cs.CV 2020
Year: 2020

We propose a novel CNN architecture called ACTNET for robust instance image retrieval from large-scale datasets. Our key innovation is a learnable activation layer designed to improve the signal-to-noise ratio (SNR) of deep convolutional feature maps. Further, we introduce a controlled multi-stream aggregation, where complementary deep features from different convolutional layers are optimally transformed and balanced using our novel activation layers, before aggregation into a global descriptor. Importantly, the learnable parameters of our activation blocks are explicitly trained, together with the CNN parameters, in an end-to-end manner minimising triplet loss. This means that our network jointly learns the CNN filters and their optimal activation and aggregation for retrieval tasks. To our knowledge, this is the first time parametric functions have been used to control and learn optimal aggregation. We conduct an in-depth experimental study on three non-linear activation functions: Sine-Hyperbolic, Exponential and modified Weibull, showing that while all bring significant gains the Weibull function performs best thanks to its ability to equalise strong activations. The results clearly demonstrate that our ACTNET architecture significantly enhances the discriminative power of deep features, improving significantly over the state-of-the-art retrieval results on all datasets.
Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphs
Venue: arXiv cs.DS 2020
Year: 2020

The network alignment (or graph matching) problem refers to recovering the node-to-node correspondence between two correlated networks. In this paper, we propose a network alignment algorithm which works without using a seed set of pre-matched node pairs or any other auxiliary information (e.g., node or edge labels) as an input. The algorithm assigns structurally innovative features to nodes based on the tail of empirical degree distribution of their neighbor nodes. Then, it matches the nodes according to these features. We evaluate the performance of proposed algorithm on both synthetic and real networks. For synthetic networks, we generate Erdos-Renyi graphs in the regions of $Θ(\log(n)/n)$ and $Θ(\log^{2}(n)/n)$, where a previous work theoretically showed that recovering is feasible in sparse Erdos-Renyi graphs if and only if the probability of having an edge between a pair of nodes in one of the graphs and also between the corresponding nodes in the other graph is in the order of $Ω(\log(n)/n)$, where $n$ is the number of nodes. Experiments on both real and synthetic networks show that it outperforms previous works in terms of probability of correct matching.
Reliability-Latency Performance of Frameless ALOHA with and without Feedback
Venue: arXiv cs.IT 2020
Year: 2020

This paper presents a finite length analysis of multi-slot type frameless ALOHA based on a dynamic programming approach. The analysis is exact, but its evaluation is only feasible for moderate number of users due to the computational complexity. The analysis is then extended to derive continuous approximations of its key parameters, which, apart from providing an insight into the decoding process, make it possible to estimate the packet error rate with very low computational complexity. Finally, a feedback scheme is presented in which the slot access scheme is dynamically adapted according to the approximate analysis in order to minimize the packet error rate. The results indicate that the introduction of feedback can substantially improve the performance of frameless ALOHA
Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
Venue: arXiv cs.DS 2020
Year: 2020

We consider the \emph{Budgeted} version of the classical \emph{Connected Dominating Set} problem (BCDS). Given a graph $G$ and a budget $k$, we seek a connected subset of at most $k$ vertices maximizing the number of dominated vertices in $G$. We improve over the previous $(1-1/e)/13$ approximation in [Khuller, Purohit, and Sarpatwar,\ \emph{SODA 2014}] by introducing a new method for performing tree decompositions in the analysis of the last part of the algorithm. This new approach provides a $(1-1/e)/12$ approximation guarantee. By generalizing the analysis of the first part of the algorithm, we are able to modify it appropriately and obtain a further improvement to $(1-e^{-7/8})/11$. On the other hand, we prove a $(1-1/e+ε)$ inapproximability bound, for any $ε> 0$. We also examine the \emph{edge-vertex domination} variant, where an edge dominates its endpoints and all vertices neighboring them. In \emph{Budgeted Edge-Vertex Domination} (BEVD), we are given a graph $G$, and a budget $k$, and we seek a, not necessarily connected, subset of $k$ edges such that the number of dominated vertices in $G$ is maximized. We prove there exists a $(1-1/e)$-approximation algorithm. Also, for any $ε> 0$, we present a $(1-1/e+ε)$-inapproximability result by a gap-preserving reduction from the \emph{maximum coverage} problem. Finally, we examine the "dual" \emph{Partial Edge-Vertex Domination} (PEVD) problem, where a graph $G$ and a quota $n'$ are given. The goal is to select a minimum-size set of edges to dominate at least $n'$ vertices in $G$. In this case, we present a $H(n')$-approximation algorithm by a reduction to the \emph{partial cover} problem.
An Inter-Layer Weight Prediction and Quantization for Deep Neural Networks based on a Smoothly Varying Weight Hypothesis
Venue: arXiv cs.LG 2020
Year: 2020

Due to a resource-constrained environment, network compression has become an important part of deep neural networks research. In this paper, we propose a new compression method, \textit{Inter-Layer Weight Prediction} (ILWP) and quantization method which quantize the predicted residuals between the weights in all convolution layers based on an inter-frame prediction method in conventional video coding schemes. Furthermore, we found a phenomenon \textit{Smoothly Varying Weight Hypothesis} (SVWH) which is that the weights in adjacent convolution layers share strong similarity in shapes and values, i.e., the weights tend to vary smoothly along with the layers. Based on SVWH, we propose a second ILWP and quantization method which quantize the predicted residuals between the weights in adjacent convolution layers. Since the predicted weight residuals tend to follow Laplace distributions with very low variance, the weight quantization can more effectively be applied, thus producing more zero weights and enhancing the weight compression ratio. In addition, we propose a new \textit{inter-layer loss} for eliminating non-texture bits, which enabled us to more effectively store only texture bits. That is, the proposed loss regularizes the weights such that the collocated weights between the adjacent two layers have the same values. Finally, we propose an ILWP with an inter-layer loss and quantization method. Our comprehensive experiments show that the proposed method achieves a much higher weight compression rate at the same accuracy level compared with the previous quantization-based compression methods in deep neural networks.
The Design of Global Correlation Quantifiers and Continuous Notions of Statistical Sufficiency
Venue: arXiv cs.IT 2020
Year: 2020

Using first principles from inference, we design a set of functionals for the purposes of \textit{ranking} joint probability distributions with respect to their correlations. Starting with a general functional, we impose its desired behaviour through the \textit{Principle of Constant Correlations} (PCC), which constrains the correlation functional to behave in a consistent way under statistically independent inferential transformations. The PCC guides us in choosing the appropriate design criteria for constructing the desired functionals. Since the derivations depend on a choice of partitioning the variable space into $n$ disjoint subspaces, the general functional we design is the $n$-partite information (NPI), of which the \textit{total correlation} and \textit{mutual information} are special cases. Thus, these functionals are found to be uniquely capable of determining whether a certain class of inferential transformations, $ρ\xrightarrow{*}ρ'$, preserve, destroy or create correlations. This provides conceptual clarity by ruling out other possible global correlation quantifiers. Finally, the derivation and results allow us to quantify non-binary notions of statistical sufficency. Our results express what percentage of the correlations are preserved under a given inferential transformation or variable mapping.
Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
Venue: arXiv cs.DS 2020
Year: 2020

Linear regression in $\ell_p$-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving $\ell_p$-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p > 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that is guaranteed to converge rapidly for p > 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any $p \in [2,\infty).$ Our algorithm is simple to implement and is guaranteed to find a $(1+\varepsilon)$-approximate solution in $O(p^{3.5} m^{\frac{p-2}{2(p-1)}} \log \frac{m}{\varepsilon}) \le O_p(\sqrt{m} \log \frac{m}{\varepsilon} )$ iterations. Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10--50x, and is the fastest among available implementations in the high-accuracy regime.
Caching as an Image Characterization Problem using Deep Convolutional Neural Networks
Venue: arXiv cs.NI 2020
Year: 2020

Caching of popular content closer to the mobile user can significantly increase overall user experience as well as network efficiency by decongesting backbone network segments in the case of congestion episodes. In order to find the optimal caching locations, many conventional approaches rely on solving a complex optimization problem that suffers from the curse of dimensionality, which may fail to support online decision making. In this paper we propose a framework to amalgamate model based optimization with data driven techniques by transforming an optimization problem to a grayscale image and train a convolutional neural network (CNN) to predict optimal caching location policies. The rationale for the proposed modelling comes from CNN's superiority to capture features in grayscale images reaching human level performance in image recognition problems. The CNN is trained with optimal solutions and numerical investigations reveal that the performance can increase by more than 400% compared to powerful randomized greedy algorithms. To this end, the proposed technique seems as a promising way forward to the holy grail aspect in resource orchestration which is providing high quality decision making in real time.
Recovering Purity with Comonads and Capabilities
Venue: arXiv cs.PL 2020
Year: 2020

In this paper, we take a pervasively effectful (in the style of ML) typed lambda calculus, and show how to extend it to permit capturing pure expressions with types. Our key observation is that, just as the pure simply-typed lambda calculus can be extended to support effects with a monadic type discipline, an impure typed lambda calculus can be extended to support purity with a comonadic type discipline. We establish the correctness of our type system via a simple denotational model, which we call the capability space model. Our model formalizes the intuition common to systems programmers that the ability to perform effects should be controlled via access to a permission or capability, and that a program is capability-safe if it performs no effects that it does not have a runtime capability for. We then identify the axiomatic categorical structure that the capability space model validates, and use these axioms to give a categorical semantics for our comonadic type system. We then give an equational theory (substitution and the call-by-value $β$ and $η$ laws) for the imperative lambda calculus, and show its soundness relative to this semantics. Finally, we give a translation of the pure simply-typed lambda calculus into our comonadic imperative calculus, and show that any two terms which are $βη$-equal in the STLC are equal in the equational theory of the comonadic calculus, establishing that pure programs can be mapped in an equation-preserving way into our imperative calculus.
Benchmarking Robustness in Object Detection: Autonomous Driving when Winter is Coming
Venue: arXiv cs.CV 2020
Year: 2020

The ability to detect objects regardless of image distortions or weather conditions is crucial for real-world applications of deep learning like autonomous driving. We here provide an easy-to-use benchmark to assess how object detection models perform when image quality degrades. The three resulting benchmark datasets, termed Pascal-C, Coco-C and Cityscapes-C, contain a large variety of image corruptions. We show that a range of standard object detection models suffer a severe performance loss on corrupted images (down to 30--60\% of the original performance). However, a simple data augmentation trick---stylizing the training images---leads to a substantial increase in robustness across corruption type, severity and dataset. We envision our comprehensive benchmark to track future progress towards building robust object detection models. Benchmark, code and data are publicly available.