OpenRaiser/Intern-Atlas huggingface dataset:
Entropy bounds for grammar compression
Venue: arXiv cs.DS 2020
Year: 2020

Grammar compression represents a string as a context free grammar. Achieving compression requires encoding such grammar as a binary string; there are a few commonly used encodings. We bound the size of practically used encodings for several heuristical compression methods, including \RePair and \Greedy algorithms: the standard encoding of \RePair, which combines entropy coding and special encoding of a grammar, achieves $1.5|S|H_k(S)$, where $H_k(S)$ is $k$-th order entropy of $S$. We also show that by stopping after some iteration we can achieve $|S|H_k(S)$. This is particularly interesting, as it explains a phenomenon observed in practice: introducing too many nonterminals causes the bit-size to grow. We generalize our approach to other compression methods like \Greedy and a wide class of irreducible grammars as well as to other practically used bit encodings (including naive, which uses fixed-length codes). Our approach not only proves the bounds but also partially explains why \Greedy and \RePair are much better in practice than other grammar based methods. In some cases we argue that our estimations are optimal. The tools used in our analysis are of independent interest: we prove the new, optimal, bounds on the zeroth order entropy of parsing of a string.
Crossbar-Net: A Novel Convolutional Network for Kidney Tumor Segmentation in CT Images
Venue: arXiv cs.CV 2020
Year: 2020

Due to the irregular motion, similar appearance and diverse shape, accurate segmentation of kidney tumor in CT images is a difficult and challenging task. To this end, we present a novel automatic segmentation method, termed as Crossbar-Net, with the goal of accurate segmenting the kidney tumors. Firstly, considering that the traditional learning-based segmentation methods normally employ either whole images or squared patches as the training samples, we innovatively sample the orthogonal non-squared patches (namely crossbar patches), to fully cover the whole kidney tumors in either horizontal or vertical directions. These sampled crossbar patches could not only represent the detailed local information of kidney tumor as the traditional patches, but also describe the global appearance from either horizontal or vertical direction using contextual information. Secondly, with the obtained crossbar patches, we trained a convolutional neural network with two sub-models (i.e., horizontal sub-model and vertical sub-model) in a cascaded manner, to integrate the segmentation results from two directions (i.e., horizontal and vertical). This cascaded training strategy could effectively guarantee the consistency between sub-models, by feeding each other with the most difficult samples, for a better segmentation. In the experiment, we evaluate our method on a real CT kidney tumor dataset, collected from 94 different patients including 3,500 images. Compared with the state-of-the-art segmentation methods, the results demonstrate the superior results of our method on dice ratio score, true positive fraction, centroid distance and Hausdorff distance. Moreover, we have extended our crossbar-net to a different task: cardiac segmentation, showing the promising results for the better generalization.
Latency and Backlog Bounds in Time-Sensitive Networking with Credit Based Shapers and Asynchronous Traffic Shaping
Venue: arXiv cs.NI 2020
Year: 2020

We compute bounds on end-to-end worst-case latency and on nodal backlog size for a per-class deterministic network that implements Credit Based Shaper (CBS) and Asynchronous Traffic Shaping (ATS), as proposed by the Time-Sensitive Networking (TSN) standardization group. ATS is an implementation of the Interleaved Regulator, which reshapes traffic in the network before admitting it into a CBS buffer, thus avoiding burstiness cascades. Due to the interleaved regulator, traffic is reshaped at every switch, which allows for the computation of explicit delay and backlog bounds. Furthermore, we obtain a novel, tight per-flow bound for the response time of CBS, when the input is regulated, which is smaller than existing network calculus bounds. We also compute a per-flow bound on the response time of the interleaved regulator. Based on all the above results, we compute bounds on the per-class backlogs. Then, we use the newly computed delay bounds along with recent results on interleaved regulators from literature to derive tight end-to-end latency bounds and show that these are less than the sums of per-switch delay bounds.
Nonparametric Pricing Analytics with Customer Covariates
Venue: arXiv cs.LG 2020
Year: 2020

Personalized pricing analytics is becoming an essential tool in retailing. Upon observing the personalized information of each arriving customer, the firm needs to set a price accordingly based on the covariates such as income, education background, past purchasing history to extract more revenue. For new entrants of the business, the lack of historical data may severely limit the power and profitability of personalized pricing. We propose a nonparametric pricing policy to simultaneously learn the preference of customers based on the covariates and maximize the expected revenue over a finite horizon. The policy does not depend on any prior assumptions on how the personalized information affects consumers' preferences (such as linear models). It is adaptively splits the covariate space into smaller bins (hyper-rectangles) and clusters customers based on their covariates and preferences, offering similar prices for customers who belong to the same cluster trading off granularity and accuracy. We show that the algorithm achieves a regret of order $O(\log(T)^2 T^{(2+d)/(4+d)})$, where $T$ is the length of the horizon and $d$ is the dimension of the covariate. It improves the current regret in the literature \citep{slivkins2014contextual}, under mild technical conditions in the pricing context (smoothness and local concavity). We also prove that no policy can achieve a regret less than $O(T^{(2+d)/(4+d)})$ for a particular instance and thus demonstrate the near optimality of the proposed policy.
Private Sequential Learning
Venue: arXiv cs.LG 2020
Year: 2020

We formulate a private learning model to study an intrinsic tradeoff between privacy and query complexity in sequential learning. Our model involves a learner who aims to determine a scalar value, $v^*$, by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes the learner's queries, though not the responses, and tries to infer from them the value of $v^*$. The objective of the learner is to obtain an accurate estimate of $v^*$ using only a small number of queries, while simultaneously protecting her privacy by making $v^*$ provably difficult to learn for the adversary. Our main results provide tight upper and lower bounds on the learner's query complexity as a function of desired levels of privacy and estimation accuracy. We also construct explicit query strategies whose complexity is optimal up to an additive constant.
Understanding Reuse, Performance, and Hardware Cost of DNN Dataflows: A Data-Centric Approach Using MAESTRO
Venue: arXiv cs.DC 2020
Year: 2020

The data partitioning and scheduling strategies used by DNN accelerators to leverage reuse and perform staging are known as dataflow, and they directly impact the performance and energy efficiency of DNN accelerator designs. An accelerator microarchitecture dictates the dataflow(s) that can be employed to execute a layer or network. Selecting an optimal dataflow for a layer shape can have a large impact on utilization and energy efficiency, but there is a lack of understanding on the choices and consequences of dataflows, and of tools and methodologies to help architects explore the co-optimization design space. In this work, we first introduce a set of data-centric directives to concisely specify the space of DNN dataflows in a compilerfriendly form. We then show how these directives can be analyzed to infer various forms of reuse and to exploit them using hardware capabilities. We codify this analysis into an analytical cost model, MAESTRO (Modeling Accelerator Efficiency via Spatio-Temporal Reuse and Occupancy), that estimates various cost-benefit tradeoffs of a dataflow including execution time and energy efficiency for a DNN model and hardware configuration. We demonstrate the use of MAESTRO to drive a hardware design space exploration (DSE) experiment, which searches across 480M designs to identify 2.5M valid designs at an average rate of 0.17M designs per second, including Pareto-optimal throughput- and energy-optimized design points.
Almost Global Problems in the LOCAL Model
Venue: arXiv cs.DC 2020
Year: 2020

The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges: - There are lots of problems with time complexities of $Θ(\log^* n)$ or $Θ(\log n)$. - It is not possible to have a problem with complexity between $ω(\log^* n)$ and $o(\log n)$. - In general graphs, we can construct LCL problems with infinitely many complexities between $ω(\log n)$ and $n^{o(1)}$. - In trees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are LCL problems with complexities of the form $Θ(n^α)$ for any rational $0 < α\le 1/2$, while for trees only complexities of the form $Θ(n^{1/k})$ are known. No LCL problem with complexity between $ω(\sqrt{n})$ and $o(n)$ is known, and neither are there results that would show that such problems do not exist. We show that: - In general graphs, we can construct LCL problems with infinitely many complexities between $ω(\sqrt{n})$ and $o(n)$. - In trees, problems with such complexities do not exist. Put otherwise, we show that any LCL with a complexity $o(n)$ can be solved in time $O(\sqrt{n})$ in trees, while the same is not true in general graphs.
Gradient-Leaks: Understanding and Controlling Deanonymization in Federated Learning
Venue: arXiv cs.CR 2020
Year: 2020

Federated Learning (FL) systems are gaining popularity as a solution to training Machine Learning (ML) models from large-scale user data collected on personal devices (e.g., smartphones) without their raw data leaving the device. At the core of FL is a network of anonymous user devices sharing training information (model parameter updates) computed locally on personal data. However, the type and degree to which user-specific information is encoded in the model updates is poorly understood. In this paper, we identify model updates encode subtle variations in which users capture and generate data. The variations provide a strong statistical signal, allowing an adversary to effectively deanonymize participating devices using a limited set of auxiliary data. We analyze resulting deanonymization attacks on diverse tasks on real-world (anonymized) user-generated data across a range of closed- and open-world scenarios. We study various strategies to mitigate the risks of deanonymization. As random perturbation methods do not offer convincing operating points, we propose data-augmentation strategies which introduces adversarial biases in device data and thereby, offer substantial protection against deanonymization threats with little effect on utility.
Systematic encoders for generalized Gabidulin codes and the $q$-analogue of Cauchy matrices
Venue: arXiv cs.IT 2020
Year: 2020

We characterize the generator matrix in standard form of generalized Gabidulin codes. The parametrization we get for the non-systematic part of this matrix coincides with the $q$-analogue of generalized Cauchy matrices, leading to the definition of $q$-Cauchy matrices. These matrices can be represented very conveniently and their representation allows to define new interesting subfamilies of generalized Gabidulin codes whose generator matrix is a structured matrix. In particular, as an application, we construct Gabidulin codes whose generator matrix is the concatenation of an identity block and a Toeplitz/Hankel matrix. In addition, our results allow to give a new efficient criterion to verify whether a rank metric code of dimension $k$ and length $n$ is a generalized Gabidulin code. This criterion is only based on the computation of the rank of one matrix and on the verification of the linear independence of two sets of elements and it requires $\mathcal O(m\cdot F(k,n))$ field operations, where $F(k,n)$ is the cost of computing the reduced row echelon form of a $k \times n$ matrix. Moreover, we also provide a characterization of the generator matrix in standard form of general MRD codes.
Norm-Preservation: Why Residual Networks Can Become Extremely Deep?
Venue: arXiv cs.CV 2020
Year: 2020

Augmenting neural networks with skip connections, as introduced in the so-called ResNet architecture, surprised the community by enabling the training of networks of more than 1,000 layers with significant performance gains. This paper deciphers ResNet by analyzing the effect of skip connections, and puts forward new theoretical results on the advantages of identity skip connections in neural networks. We prove that the skip connections in the residual blocks facilitate preserving the norm of the gradient, and lead to stable back-propagation, which is desirable from optimization perspective. We also show that, perhaps surprisingly, as more residual blocks are stacked, the norm-preservation of the network is enhanced. Our theoretical arguments are supported by extensive empirical evidence. Can we push for extra norm-preservation? We answer this question by proposing an efficient method to regularize the singular values of the convolution operator and making the ResNet's transition layers extra norm-preserving. Our numerical investigations demonstrate that the learning dynamics and the classification performance of ResNet can be improved by making it even more norm preserving. Our results and the introduced modification for ResNet, referred to as Procrustes ResNets, can be used as a guide for training deeper networks and can also inspire new deeper architectures.
Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a new concept, data irrecoverability, and show that the well-studied concept of data privacy is sufficient but not necessary for data irrecoverability. We show that there are several regularized loss minimization problems that can use perturbed data with theoretical guarantees of generalization, i.e., loss consistency. Our results quantitatively connect the convergence rates of the learning problems to the impossibility for any adversary for recovering the original data from perturbed observations. In addition, we show several examples where the convergence rates with perturbed data only increase the convergence rates with original data within a constant factor related to the amount of perturbation, i.e., noise.
A universal framework for learning the elliptical mixture model
Venue: arXiv cs.LG 2020
Year: 2020

Mixture modelling using elliptical distributions promises enhanced robustness, flexibility and stability over the widely employed Gaussian mixture model (GMM). However, existing studies based on the elliptical mixture model (EMM) are restricted to several specific types of elliptical probability density functions, which are not supported by general solutions or systematic analysis frameworks; this significantly limits the rigour and the power of EMMs in applications. To this end, we propose a novel general framework for estimating and analysing the EMMs, achieved through Riemannian manifold optimisation. First, we investigate the relationships between Riemannian manifolds and elliptical distributions, and the so established connection between the original manifold and a reformulated one indicates a mismatch between those manifolds, the major cause of failure of the existing optimisation for solving general EMMs. We next propose a universal solver which is based on the optimisation of a re-designed cost and prove the existence of the same optimum as in the original problem; this is achieved in a simple, fast and stable way. We further calculate the influence functions of the EMM as theoretical bounds to quantify robustness to outliers. Comprehensive numerical results demonstrate the ability of the proposed framework to accommodate EMMs with different properties of individual functions in a stable way and with fast convergence speed. Finally, the enhanced robustness and flexibility of the proposed framework over the standard GMM are demonstrated both analytically and through comprehensive simulations.
Classifier-agnostic saliency map extraction
Venue: arXiv cs.LG 2020
Year: 2020

Currently available methods for extracting saliency maps identify parts of the input which are the most important to a specific fixed classifier. We show that this strong dependence on a given classifier hinders their performance. To address this problem, we propose classifier-agnostic saliency map extraction, which finds all parts of the image that any classifier could use, not just one given in advance. We observe that the proposed approach extracts higher quality saliency maps than prior work while being conceptually simple and easy to implement. The method sets the new state of the art result for localization task on the ImageNet data, outperforming all existing weakly-supervised localization techniques, despite not using the ground truth labels at the inference time. The code reproducing the results is available at https://github.com/kondiz/casme . The final version of this manuscript is published in Computer Vision and Image Understanding and is available online at https://doi.org/10.1016/j.cviu.2020.102969 .
Sphere Decoder with Box Optimization for FTN Non-orthogonal FDM System
Venue: arXiv cs.IT 2020
Year: 2020

In 1975, the pioneering work of J. E. Mazo showed the potential faster-than-Nyquist (FTN) gain of single-carrier binary signal. If the inter-symbol interference is eliminated by an optimal detector, the FTN single-carrier binary signal can transmit 24.7% more bits than the Nyquist signal without any loss of bit error rate performance, which is known as the Mazo limit. In this paper, we apply sphere decoder (SD) with box optimization (BO) to reduce inter-carrier interference (ICI) in FTN non-orthogonal frequency division multiplexing (FTN-NOFDM) system. Compared with the conventional SD, SD with BO can achieve the same performance to reduce ICI, but its average number of expanded nodes in search process is significantly decreased especially for high-order modulation format, which can reduce the complexity of the receiver. When the bandwidth compression factor $α$ is set to 0.802, the transmission rate of QPSK-modulated FTN-NOFDM is 24.7% faster than the Nyquist rate, and it has almost the same performance as orthogonal frequency division multiplexing (OFDM), which agrees well with the Mazo limit. The QPSK-modulated FTN-NOFDM with $α$ equal to 0.5 (the spectral efficiency is 4 bit/s/Hz) outperforms 16QAM-modulated OFDM by about 1.5 dB. The 16QAM-modulated FTN-NOFDM with $α$ equal to 0.67 and 0.5 (the spectral efficiency is 6 bit/s/Hz and 8 bit/s/Hz, respectively) outperforms 64QAM-modulated and 256QAM-modulated OFDM by about 1.5 dB and 2 dB, respectively. Therefore, FTN-NOFDM will be a promising modulation scheme for the future bandwidth-limited wireless communications.
The effects of change decomposition on code review -- a controlled experiment
Venue: arXiv cs.SE 2020
Year: 2020

Background: Code review is a cognitively demanding and time-consuming process. Previous qualitative studies hinted at how decomposing change sets into multiple yet internally coherent ones would improve the reviewing process. So far, literature provided no quantitative analysis of this hypothesis. Aims: (1) Quantitatively measure the effects of change decomposition on the outcome of code review (in terms of number of found defects, wrongly reported issues, suggested improvements, time, and understanding); (2) Qualitatively analyze how subjects approach the review and navigate the code, building knowledge and addressing existing issues, in large vs. decomposed changes. Method: Controlled experiment using the pull-based development model involving 28 software developers among professionals and graduate students. Results: Change decomposition leads to fewer wrongly reported issues, influences how subjects approach and conduct the review activity (by increasing context-seeking), yet impacts neither understanding the change rationale nor the number of found defects. Conclusions: Change decomposition reduces the noise for subsequent data analyses but also significantly supports the tasks of the developers in charge of reviewing the changes. As such, commits belonging to different concepts should be separated, adopting this as a best practice in software engineering.
Cost Sharing Games for Energy-Efficient Multi-Hop Broadcast in Wireless Networks
Venue: arXiv cs.GT 2020
Year: 2020

We study multi-hop broadcast in wireless networks with one source node and multiple receiving nodes. The message flow from the source to the receivers can be modeled as a tree-graph, called broadcast-tree. The problem of finding the minimum-power broadcast-tree (MPBT) is NP-complete. Unlike most of the existing centralized approaches, we propose a decentralized algorithm, based on a non-cooperative cost-sharing game. In this game, every receiving node, as a player, chooses another node of the network as its respective transmitting node for receiving the message. Consequently, a cost is assigned to the receiving node based on the power imposed on its chosen transmitting node. In our model, the total required power at a transmitting node consists of (i) the transmit power and (ii) the circuitry power needed for communication hardware modules. We develop our algorithm using the marginal contribution (MC) cost-sharing scheme and show that the optimum broadcast-tree is always a Nash equilibrium (NE) of the game. Simulation results demonstrate that our proposed algorithm outperforms conventional algorithms for the MPBT problem. Besides, we show that the circuitry power, which is usually ignored by existing algorithms, significantly impacts the energy-efficiency of the network.
Supervised Learning Under Distributed Features
Venue: arXiv cs.MA 2020
Year: 2020

This work studies the problem of learning under both large datasets and large-dimensional feature space scenarios. The feature information is assumed to be spread across agents in a network, where each agent observes some of the features. Through local cooperation, the agents are supposed to interact with each other to solve an inference problem and converge towards the global minimizer of an empirical risk. We study this problem exclusively in the primal domain, and propose new and effective distributed solutions with guaranteed convergence to the minimizer with linear rate under strong convexity. This is achieved by combining a dynamic diffusion construction, a pipeline strategy, and variance-reduced techniques. Simulation results illustrate the conclusions.