OpenRaiser/Intern-Atlas huggingface dataset:
Channel Shortening by Large Multiantenna Precoding in OFDM
Venue: arXiv cs.IT 2021
Year: 2021

A channel delay spread larger than the cyclic prefix (CP) creates inter-carrier/symbol interference (ISI/ICI) in orthogonal frequency-division multiplexing (OFDM). Recent interests in low-latency applications have motivated the usage of shorter OFDM symbols where one can either downscale the CP at the cost of interference, or maintain it but with larger overhead. Alternatively, this paper studies channel shortening methods exploiting the properties of large multi-antenna precoding in order to steer the transmitted signal energy toward channel paths inside an insufficient CP. It is shown that ISI/ICI can asymptotically be canceled by conventional subcarrier-based precoding with an infinite number of antennas. This is achieved by introducing time-delay selectivity inside frequency-selective precoders in order to remove undesired delayed signals, providing a trade-off between interference mitigation and multi-path combining gains, and leading to subsequent gains in high SNR. This frequency-domain precoding method, coined time-frequency (TF) precoding, is compared to time-reversal (TR) filtering whose asymptotic rate is optimal but introduces post-modulation processing with channel-dependent signal distortion. In addition to maintain the legacy precoded multi-antenna OFDM structure, finite-size analysis shows that TF-precoding converges faster to its asymptotic rate than TR-filtering, so that TF-precoding can outperform TRfiltering in the high-SNR regime with not-so-many antennas.
Layer Flexible Adaptive Computational Time
Venue: arXiv cs.LG 2021
Year: 2021

Deep recurrent neural networks perform well on sequence data and are the model of choice. However, it is a daunting task to decide the structure of the networks, i.e. the number of layers, especially considering different computational needs of a sequence. We propose a layer flexible recurrent neural network with adaptive computation time, and expand it to a sequence to sequence model. Different from the adaptive computation time model, our model has a dynamic number of transmission states which vary by step and sequence. We evaluate the model on a financial data set and Wikipedia language modeling. Experimental results show the performance improvement of 7\% to 12\% and indicate the model's ability to dynamically change the number of layers along with the computational steps.
A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks
Venue: arXiv cs.DS 2021
Year: 2021

Answering exact shortest path distance queries is a fundamental task in graph theory. Despite a tremendous amount of research on the subject, there is still no satisfactory solution that can scale to billion-scale complex networks. Labelling-based methods are well-known for rendering fast response time to distance queries; however, existing works can only construct labelling on moderately large networks (million-scale) and cannot scale to large networks (billion-scale) due to their prohibitively large space requirements and very long preprocessing time. In this work, we present novel techniques to efficiently construct distance labelling and process exact shortest path distance queries for complex networks with billions of vertices and billions of edges. Our method is based on two ingredients: (i) a scalable labelling algorithm for constructing minimal distance labelling, and (ii) a querying framework that supports fast distance-bounded search on a sparsified graph. Thus, we first develop a novel labelling algorithm that can scale to graphs at the billion-scale. Then, we formalize a querying framework for exact distance queries, which combines our proposed highway cover distance labelling with distance-bounded searches to enable fast distance computation. To speed up the labelling construction process, we further propose a parallel labelling method that can construct labelling simultaneously for multiple landmarks. We evaluated the performance of the proposed methods on 12 real-world networks. The experiments show that the proposed methods can not only handle networks with billions of vertices, but also be up to 70 times faster in constructing labelling and save up to 90\% of labelling space. In particular, our method can answer distance queries on a billion-scale network of around 8B edges in less than 1ms, on average.
Solvability = Typability + Inhabitation
Venue: arXiv cs.LO 2021
Year: 2021

We extend the classical notion of solvability to a lambda-calculus equipped with pattern matching. We prove that solvability can be characterized by means of typability and inhabitation in an intersection type system P based on non-idempotent types. We show first that the system P characterizes the set of terms having canonical form, i.e. that a term is typable if and only if it reduces to a canonical form. But the set of solvable terms is properly contained in the set of canonical forms. Thus, typability alone is not sufficient to characterize solvability, in contrast to the case for the lambda-calculus. We then prove that typability, together with inhabitation, provides a full characterization of solvability, in the sense that a term is solvable if and only if it is typable and the types of all its arguments are inhabited. We complete the picture by providing an algorithm for the inhabitation problem of P.
Graph Neural Networks: A Review of Methods and Applications
Venue: arXiv cs.LG 2021
Year: 2021

Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics systems, learning molecular fingerprints, predicting protein interface, and classifying diseases demand a model to learn from graph inputs. In other domains such as learning from non-structural data like texts and images, reasoning on extracted structures (like the dependency trees of sentences and the scene graphs of images) is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are neural models that capture the dependence of graphs via message passing between the nodes of graphs. In recent years, variants of GNNs such as graph convolutional network (GCN), graph attention network (GAT), graph recurrent network (GRN) have demonstrated ground-breaking performances on many deep learning tasks. In this survey, we propose a general design pipeline for GNN models and discuss the variants of each component, systematically categorize the applications, and propose four open problems for future research.
Analysis of contagion maps on a class of networks that are spatially embedded in a torus
Venue: arXiv cs.SI 2021
Year: 2021

A spreading process on a network is influenced by the network's underlying spatial structure, and it is insightful to study the extent to which a spreading process follows such structure. We consider a threshold contagion model on a network whose nodes are embedded in a manifold and which has both `geometric edges', which respect the geometry of the underlying manifold, and `nongeometric edges' that are not constrained by that geometry. Building on ideas from Taylor et al. \cite{Taylor2015}, we examine when a contagion propagates as a wave along a network whose nodes are embedded in a torus and when it jumps via long nongeometric edges to remote areas of the network. We build a `contagion map' for a contagion spreading on such a `noisy geometric network' to produce a point cloud; and we study the dimensionality, geometry, and topology of this point cloud to examine qualitative properties of this spreading process. We identify a region in parameter space in which the contagion propagates predominantly via wavefront propagation. We consider different probability distributions for constructing nongeometric edges -- reflecting different decay rates with respect to the distance between nodes in the underlying manifold -- and examine the effect of such choices on the qualitative properties of the spreading dynamics. Our work generalizes the analysis in Taylor et al. and consolidates contagion maps both as a tool for investigating spreading behavior on spatial networks and as a technique for manifold learning.
Efficiently list-edge coloring multigraphs asymptotically optimally
Venue: arXiv cs.DM 2021
Year: 2021

We give polynomial time algorithms for the seminal results of Kahn, who showed that the Goldberg-Seymour and List-Coloring conjectures for (list-)edge coloring multigraphs hold asymptotically. Kahn's arguments are based on the probabilistic method and are non-constructive. Our key insight is to show that the main result of Achlioptas, Iliopoulos and Kolmogorov for analyzing local search algorithms can be used to make constructive applications of a powerful version of the so-called Lopsided Lovasz Local Lemma. In particular, we use it to design algorithms that exploit the fact that correlations in the probability spaces on matchings used by Kahn decay with distance.
Secure Modulo Sum via Multiple Access Channel
Venue: arXiv cs.IT 2021
Year: 2021

We discuss secure computation of modular sum when multiple access channel from distinct players $A_1, \ldots, A_c$ to a third party (Receiver) is given. Then, we define the secure modulo sum capacity as the supremum of the transmission rate of modulo sum without information leakage of other information. We derive its useful lower bound, which is numerically calculated under a realistic model that can be realizable as a Gaussian multiple access channel (MAC).
Convex Polygons in Cartesian Products
Venue: arXiv cs.CG 2021
Year: 2021

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, \emph{grid}). First, we prove that every such grid contains $Ω(\log n)$ points in convex position and that this bound is tight up to a constant factor. We generalize this result to $d$ dimensions (for a fixed $d\in \mathbb{N}$), and obtain a tight lower bound of $Ω(\log^{d-1}n)$ for the maximum number of points in convex position in a $d$-dimensional grid. Second, we present polynomial-time algorithms for computing the longest $x$- or $y$-monotone convex polygonal chain in a grid that contains no two points with the same $x$- or $y$-coordinate. We show that the maximum size of a convex polygon with such unique coordinates can be efficiently approximated up to a factor of $2$. Finally, we present exponential bounds on the maximum number of point sets in convex position in such grids, and for some restricted variants. These bounds are tight up to polynomial factors.
List Decoding Random Euclidean Codes and Infinite Constellations
Venue: arXiv cs.IT 2021
Year: 2021

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $ P $ and $ N $ respectively, the list decoding capacity is equal to $ \frac{1}{2}\log\frac{P}{N} $. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain number-theoretic conjecture is true, then the list size grows as a polynomial function of the gap-to-capacity.
Spectral estimation for detecting low-dimensional structure in networks using arbitrary null models
Venue: arXiv cs.SI 2021
Year: 2021

Discovering low-dimensional structure in real-world networks requires a suitable null model that defines the absence of meaningful structure. Here we introduce a spectral approach for detecting a network's low-dimensional structure, and the nodes that participate in it, using any null model. We use generative models to estimate the expected eigenvalue distribution under a specified null model, and then detect where the data network's eigenspectra exceed the estimated bounds. On synthetic networks, this spectral estimation approach cleanly detects transitions between random and community structure, recovers the number and membership of communities, and removes noise nodes. On real networks spectral estimation finds either a significant fraction of noise nodes or no departure from a null model, in stark contrast to traditional community detection methods. Across all analyses, we find the choice of null model can strongly alter conclusions about the presence of network structure. Our spectral estimation approach is therefore a promising basis for detecting low-dimensional structure in real-world networks, or lack thereof.
A Generic Transformation for Optimal Node Repair in MDS Array Codes over $\mathbf{F}_2$
Venue: arXiv cs.IT 2021
Year: 2021

For high-rate linear systematic maximum distance separable (MDS) codes, most early constructions could initially optimally repair all the systematic nodes but not all the parity nodes. Fortunately, this issue was first solved by Li et al. in (IEEE Trans. Inform. Theory, 64(9), 6257-6267, 2018), where a transformation that can convert any nonbinary MDS array code into another one with desired properties was proposed. However, the transformation does not work for binary MDS array codes. In this paper, we address this issue by proposing another generic transformation that can convert any $[n, k]$ binary MDS array code into a new one, which endows any $r=n-k\ge2$ chosen nodes with optimal repair bandwidth and optimal rebuilding access properties, and at the same time, preserves the normalized repair bandwidth/rebuilding access for the remaining $k$ nodes under some conditions. As two immediate applications, we show that 1) by applying the transformation multiple times, any binary MDS array code can be converted into one with optimal rebuilding access for all nodes, 2) any binary MDS array code with optimal repair bandwidth or optimal rebuilding access for the systematic nodes can be converted into one with the corresponding optimality property for all nodes.
Fundamental limits of many-user MAC with finite payloads and fading
Venue: arXiv cs.IT 2021
Year: 2021

Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links. Each user has a fixed number $k$ of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading). In this paper we consider the many-user asymptotics of Chen-Chen-Guo'2017, where the number of users grows linearly with the blocklength. Differently, though, we adopt a per-user probability of error (PUPE) criterion (as opposed to classical joint-error probability criterion). Under PUPE the finite energy-per-bit communication is possible, and we are able to derive bounds on the tradeoff between energy and spectral efficiencies. We reconfirm the curious behaviour (previously observed for non-fading MAC) of the possibility of almost perfect multi-user interference (MUI) cancellation for user densities below a critical threshold. Further, we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e., TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection). Notably, the problem treated here can be seen as a variant of support recovery in compressed sensing for the unusual definition of sparsity with one non-zero entry per each contiguous section of $2^k$ coordinates. This identifies our problem with that of the sparse regression codes (SPARCs) and hence our results can be equivalently understood in the context of SPARCs with sections of length $2^{100}$. Finally, we discuss the relation of the almost perfect MUI cancellation property and the replica-method predictions.
Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
Venue: arXiv cs.DC 2021
Year: 2021

We consider the distributed optimization problem, the goal of which is to minimize the sum of local objective functions over a directed network. Though it has been widely studied recently, most of the existing algorithms are designed for synchronized or randomly activated implementation, which may create deadlocks in practice. In sharp contrast, we propose a \emph{fully} asynchronous push-pull gradient algorithm (APPG) where each node updates without waiting for any other node by using (possibly stale) information from neighbors. Thus, it is both deadlock-free and robust to any bounded communication delay. Moreover, we construct two novel augmented networks to theoretically evaluate its performance from the worst-case point of view and show that if local functions have Lipschitz-continuous gradients and their sum satisfies the Polyak-Łojasiewicz condition (convexity is not required), each node of APPG converges to the same optimal solution at a linear rate of $\mathcal{O}(λ^k)$, where $λ\in(0,1)$ and the virtual counter $k$ increases by one no matter which node updates. This largely elucidates its linear speedup efficiency and shows its advantage over the synchronous version. Finally, the performance of APPG is numerically validated via a logistic regression problem on the \emph{Covertype} dataset.
Learning Interpretable Models with Causal Guarantees
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning has shown much promise in helping improve the quality of medical, legal, and financial decision-making. In these applications, machine learning models must satisfy two important criteria: (i) they must be causal, since the goal is typically to predict individual treatment effects, and (ii) they must be interpretable, so that human decision makers can validate and trust the model predictions. There has recently been much progress along each direction independently, yet the state-of-the-art approaches are fundamentally incompatible. We propose a framework for learning interpretable models from observational data that can be used to predict individual treatment effects (ITEs). In particular, our framework converts any supervised learning algorithm into an algorithm for estimating ITEs. Furthermore, we prove an error bound on the treatment effects predicted by our model. Finally, in an experiment on real-world data, we show that the models trained using our framework significantly outperform a number of baselines.
A Framework for Understanding Sources of Harm throughout the Machine Learning Life Cycle
Venue: arXiv cs.LG 2021
Year: 2021

As machine learning (ML) increasingly affects people and society, awareness of its potential unwanted consequences has also grown. To anticipate, prevent, and mitigate undesirable downstream consequences, it is critical that we understand when and how harm might be introduced throughout the ML life cycle. In this paper, we provide a framework that identifies seven distinct potential sources of downstream harm in machine learning, spanning data collection, development, and deployment. In doing so, we aim to facilitate more productive and precise communication around these issues, as well as more direct, application-grounded ways to mitigate them.
On checkable codes in group algebras
Venue: arXiv cs.IT 2021
Year: 2021

We classify, in terms of the structure of the finite group G, all group algebras KG for which all right ideals are right annihilators of principal left ideals. This means in the language of coding theory that we classify code-checkable group algebras KG which have been considered so far only for abelian groups G. Optimality of checkable codes and asymptotic results are discussed.
Semi-Supervised Ordinal Regression Based on Empirical Risk Minimization
Venue: arXiv cs.LG 2021
Year: 2021

Ordinal regression is aimed at predicting an ordinal class label. In this paper, we consider its semi-supervised formulation, in which we have unlabeled data along with ordinal-labeled data to train an ordinal regressor. There are several metrics to evaluate the performance of ordinal regression, such as the mean absolute error, mean zero-one error, and mean squared error. However, the existing studies do not take the evaluation metric into account, have a restriction on the model choice, and have no theoretical guarantee. To overcome these problems, we propose a novel generic framework for semi-supervised ordinal regression based on the empirical risk minimization principle that is applicable to optimizing all of the metrics mentioned above. Besides, our framework has flexible choices of models, surrogate losses, and optimization algorithms without the common geometric assumption on unlabeled data such as the cluster assumption or manifold assumption. We further provide an estimation error bound to show that our risk estimator is consistent. Finally, we conduct experiments to show the usefulness of our framework.
Optimal Nonparametric Inference via Deep Neural Network
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural network is a state-of-art method in modern science and technology. Much statistical literature have been devoted to understanding its performance in nonparametric estimation, whereas the results are suboptimal due to a redundant logarithmic sacrifice. In this paper, we show that such log-factors are not necessary. We derive upper bounds for the $L^2$ minimax risk in nonparametric estimation. Sufficient conditions on network architectures are provided such that the upper bounds become optimal (without log-sacrifice). Our proof relies on an explicitly constructed network estimator based on tensor product B-splines. We also derive asymptotic distributions for the constructed network and a relating hypothesis testing procedure. The testing procedure is further proven as minimax optimal under suitable network architectures.
Non-cooperatively assembling large structures: a 2D pumping lemma cannot be as powerful as its 1D counterpart
Venue: arXiv cs.CC 2021
Year: 2021

We show the first asymptotically efficient constructions in the so-called "noncooperative planar tile assembly" model. Algorithmic self-assembly is the study of the local, distributed, asynchronous algorithms ran by molecules to self-organise, in particular during crystal growth. The general cooperative model, also called "temperature 2", uses synchronisation to simulate Turing machines, build shapes using the smallest possible amount of tile types, and other algorithmic tasks. However, in the non-cooperative ("temperature 1") model, the growth process is entirely asynchronous, and mostly relies on geometry. Even though the model looks like a generalisation of finite automata to two dimensions, its 3D generalisation is capable of performing arbitrary (Turing) computation, and of universal simulations, whereby a single 3D non-cooperative tileset can simulate the dynamics of all possible 3D non-cooperative systems, up to a constant scaling factor. However, it was shown that the original 2D non-cooperative model is not capable of universal simulations, and the question of its computational power is still widely open. Here, we show an unexpected result, namely that this model can reliably grow assemblies of size Omega(n log n) with only n tile types, which is the first asymptotically efficient positive construction.