OpenRaiser/Intern-Atlas huggingface dataset:
Mismatched Estimation of rank-one symmetric matrices under Gaussian noise
Venue: arXiv cs.IT 2021
Year: 2021

We consider the estimation of an n-dimensional vector s from the noisy element-wise measurements of $\mathbf{s}\mathbf{s}^T$, a generic problem that arises in statistics and machine learning. We study a mismatched Bayesian inference setting, where some of the parameters are not known to the statistician. We derive the full exact analytic expression of the asymptotic mean squared error (MSE) in the large system size limit for the particular case of Gaussian priors and additive noise. From our formulas, we see that estimation is still possible in the mismatched case; and also that the minimum MSE (MMSE) can be achieved if the statistician chooses suitable parameters. Our technique relies on the asymptotics of the spherical integrals and can be applied as long as the statistician chooses a rotationally invariant prior.
A Tree Search Approach for Maximum-Likelihood Decoding of Reed-Muller Codes
Venue: arXiv cs.IT 2021
Year: 2021

A low-complexity tree search approach is presented that achieves the maximum-likelihood (ML) decoding performance of Reed-Muller (RM) codes. The proposed approach generates a bit-flipping tree that is traversed to find the ML decoding result by performing successive-cancellation decoding after each node visit. A depth-first search (DFS) and a breadth-first search (BFS) scheme are developed and a log-likelihood-ratio-based bit-flipping metric is utilized to avoid redundant node visits in the tree. Several enhancements to the proposed algorithm are presented to further reduce the number of node visits. Simulation results confirm that the BFS scheme provides a lower average number of node visits than the existing tree search approach to decode RM codes.
Code and Structure Editing for Teaching: A Case Study in using Bibliometrics to Guide Computer Science Research
Venue: arXiv cs.HC 2021
Year: 2021

Structure or projectional editors are a well-studied concept among researchers and some practitioners. They have the huge advantage of preventing syntax and in some cases type errors, and aid the discovery of syntax by users unfamiliar with a language. This begs the question: why are they not widely used in education? To answer this question we performed a systematic review of 57 papers and performed a bibliometric analysis which extended to 381 papers. From these we generated two hypotheses: (1) a lack of empirical evidence prevents educators from committing to this technology, and (2) existing tools have not been designed based on actual user needs as they would be if human-centered design principles were used. Given problems we encountered with existing resources to support a systematic review, and the role of bibliometric tools in overcoming those obstacles, we also detail our methods so that they may be used as a guide for researchers or graduate students unfamiliar with bibliometrics. In particular, we report on which tools provide reliable and plentiful information in the field of computer science, and which have insufficient coverage and interoperability issues.
A New Clustering-Based Technique for the Acceleration of Deep Convolutional Networks
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning and especially the use of Deep Neural Networks (DNNs) provides impressive results in various regression and classification tasks. However, to achieve these results, there is a high demand for computing and storing resources. This becomes problematic when, for instance, real-time, mobile applications are considered, in which the involved (embedded) devices have limited resources. A common way of addressing this problem is to transform the original large pre-trained networks into new smaller models, by utilizing Model Compression and Acceleration (MCA) techniques. Within the MCA framework, we propose a clustering-based approach that is able to increase the number of employed centroids/representatives, while at the same time, have an acceleration gain compared to conventional, $k$-means based approaches. This is achieved by imposing a special structure to the employed representatives, which is enabled by the particularities of the problem at hand. Moreover, the theoretical acceleration gains are presented and the key system hyper-parameters that affect that gain, are identified. Extensive evaluation studies carried out using various state-of-the-art DNN models trained in image classification, validate the superiority of the proposed method as compared for its use in MCA tasks.
Isolated loops
Venue: arXiv cs.DM 2021
Year: 2021

Many bureaucratic and industrial processes involve decision points where an object can be sent to a variety of different stations based on certain preconditions. Consider for example a visa application that has needs to be checked at various stages, and move to different stations based on the outcomes of said checks. While the individual decision points in these processes are well defined, in a complicated system, it is hard to understand the redundancies that can be introduced globally by composing a number of these decisions locally. In this paper, we model these processes as Eulerian paths and give an algorithm for calculating a measure of these redundancies, called isolated loops, as a type of loop count on Eulerian paths, and give a bound on this quantity.
Cross-Lingual BERT Contextual Embedding Space Mapping with Isotropic and Isometric Conditions
Venue: arXiv cs.CL 2021
Year: 2021

Typically, a linearly orthogonal transformation mapping is learned by aligning static type-level embeddings to build a shared semantic space. In view of the analysis that contextual embeddings contain richer semantic features, we investigate a context-aware and dictionary-free mapping approach by leveraging parallel corpora. We illustrate that our contextual embedding space mapping significantly outperforms previous multilingual word embedding methods on the bilingual dictionary induction (BDI) task by providing a higher degree of isomorphism. To improve the quality of mapping, we also explore sense-level embeddings that are split from type-level representations, which can align spaces in a finer resolution and yield more precise mapping. Moreover, we reveal that contextual embedding spaces suffer from their natural properties -- anisotropy and anisometry. To mitigate these two problems, we introduce the iterative normalization algorithm as an imperative preprocessing step. Our findings unfold the tight relationship between isotropy, isometry, and isomorphism in normalized contextual embedding spaces.
Hardness of Detecting Abelian and Additive Square Factors in Strings
Venue: arXiv cs.DS 2021
Year: 2021

We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in a string. In particular, we conclude conditional optimality of the state-of-the-art algorithms for finding such factors. Overall, we show 3SUM-hardness of (a) detecting an Abelian square factor of an odd half-length, (b) computing centers of all Abelian square factors, (c) detecting an additive square factor in a length-$n$ string of integers of magnitude $n^{\mathcal{O}(1)}$, and (d) a problem of computing a double 3-term arithmetic progression (i.e., finding indices $i \ne j$ such that $(x_i+x_j)/2=x_{(i+j)/2}$) in a sequence of integers $x_1,\dots,x_n$ of magnitude $n^{\mathcal{O}(1)}$. Problem (d) is essentially a convolution version of the AVERAGE problem that was proposed in a manuscript of Erickson. We obtain a conditional lower bound for it with the aid of techniques recently developed by Dudek et al. [STOC 2020]. Problem (d) immediately reduces to problem (c) and is a step in reductions to problems (a) and (b). In conditional lower bounds for problems (a) and (b) we apply an encoding of Amir et al. [ICALP 2014] and extend it using several string gadgets that include arbitrarily long Abelian-square-free strings. Our reductions also imply conditional lower bounds for detecting Abelian squares in strings over a constant-sized alphabet. We also show a subquadratic upper bound in this case, applying a result of Chan and Lewenstein [STOC 2015].
Understanding Gender and Racial Disparities in Image Recognition Models
Venue: arXiv cs.CV 2021
Year: 2021

Large scale image classification models trained on top of popular datasets such as Imagenet have shown to have a distributional skew which leads to disparities in prediction accuracies across different subsections of population demographics. A lot of approaches have been made to solve for this distributional skew using methods that alter the model pre, post and during training. We investigate one such approach - which uses a multi-label softmax loss with cross-entropy as the loss function instead of a binary cross-entropy on a multi-label classification problem on the Inclusive Images dataset which is a subset of the OpenImages V6 dataset. We use the MR2 dataset, which contains images of people with self-identified gender and race attributes to evaluate the fairness in the model outcomes and try to interpret the mistakes by looking at model activations and suggest possible fixes.
Follow Your Path: a Progressive Method for Knowledge Distillation
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks often have a huge number of parameters, which posts challenges in deployment in application scenarios with limited memory and computation capacity. Knowledge distillation is one approach to derive compact models from bigger ones. However, it has been observed that a converged heavy teacher model is strongly constrained for learning a compact student network and could make the optimization subject to poor local optima. In this paper, we propose ProKT, a new model-agnostic method by projecting the supervision signals of a teacher model into the student's parameter space. Such projection is implemented by decomposing the training objective into local intermediate targets with an approximate mirror descent technique. The proposed method could be less sensitive with the quirks during optimization which could result in a better local optimum. Experiments on both image and text datasets show that our proposed ProKT consistently achieves superior performance compared to other existing knowledge distillation methods.
LENS: Layer Distribution Enabled Neural Architecture Search in Edge-Cloud Hierarchies
Venue: arXiv cs.LG 2021
Year: 2021

Edge-Cloud hierarchical systems employing intelligence through Deep Neural Networks (DNNs) endure the dilemma of workload distribution within them. Previous solutions proposed to distribute workloads at runtime according to the state of the surroundings, like the wireless conditions. However, such conditions are usually overlooked at design time. This paper addresses this issue for DNN architectural design by presenting a novel methodology, LENS, which administers multi-objective Neural Architecture Search (NAS) for two-tiered systems, where the performance objectives are refashioned to consider the wireless communication parameters. From our experimental search space, we demonstrate that LENS improves upon the traditional solution's Pareto set by 76.47% and 75% with respect to the energy and latency metrics, respectively.
IoTDataBench: Extending TPCx-IoT for Compression and Scalability
Venue: arXiv cs.DB 2021
Year: 2021

We present a record-breaking result and lessons learned in practicing TPCx-IoT benchmarking for a real-world use case. We find that more system characteristics need to be benchmarked for its application to real-world use cases. We introduce an extension to the TPCx-IoT benchmark, covering fundamental requirements of time-series data management for IoT infrastructure. We characterize them as data compression and system scalability. To evaluate these two important features of IoT databases, we propose IoTDataBench and update four aspects of TPCx-IoT, i.e., data generation, workloads, metrics and test procedures. Preliminary evaluation results show systems that fail to effectively compress data or flexibly scale can negatively affect the redesigned metrics, while systems with high compression ratios and linear scalability are rewarded in the final metrics. Such systems have the ability to scale up computing resources on demand and can thus save dollar costs.
Self-Supervised Domain Adaptation for Diabetic Retinopathy Grading using Vessel Image Reconstruction
Venue: arXiv cs.CV 2021
Year: 2021

This paper investigates the problem of domain adaptation for diabetic retinopathy (DR) grading. We learn invariant target-domain features by defining a novel self-supervised task based on retinal vessel image reconstructions, inspired by medical domain knowledge. Then, a benchmark of current state-of-the-art unsupervised domain adaptation methods on the DR problem is provided. It can be shown that our approach outperforms existing domain adaption strategies. Furthermore, when utilizing entire training data in the target domain, we are able to compete with several state-of-the-art approaches in final classification accuracy just by applying standard network architectures and using image-level labels.
Maximizing the Set Cardinality of Users Scheduled for Ultra-dense uRLLC Networks
Venue: arXiv cs.IT 2021
Year: 2021

Ultra-reliability and low latency communication has long been an important but challenging task in the fifth and sixth generation wireless communication systems. Scheduling as many users as possible to serve on the limited time-frequency resource is one of a crucial topic, subjecting to the maximum allowable transmission power and the minimum rate requirement of each user. We address it by proposing a mixed integer programming model, with the goal of maximizing the set cardinality of users instead of maximizing the system sum rate or energy efficiency. Mathematical transformations and successive convex approximation are combined to solve the complex optimization problem. Numerical results show that the proposed method achieves a considerable performance compared with exhaustive search method, but with lower computational complexity.
Algorithm Selection on a Meta Level
Venue: arXiv cs.LG 2021
Year: 2021

The problem of selecting an algorithm that appears most suitable for a specific instance of an algorithmic problem class, such as the Boolean satisfiability problem, is called instance-specific algorithm selection. Over the past decade, the problem has received considerable attention, resulting in a number of different methods for algorithm selection. Although most of these methods are based on machine learning, surprisingly little work has been done on meta learning, that is, on taking advantage of the complementarity of existing algorithm selection methods in order to combine them into a single superior algorithm selector. In this paper, we introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors. We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework, essentially combining ideas of meta learning and ensemble learning. In an extensive experimental evaluation, we demonstrate that ensembles of algorithm selectors can significantly outperform single algorithm selectors and have the potential to form the new state of the art in algorithm selection.
The role of IT ambidexterity, digital dynamic capability and knowledge processes as enablers of patient agility: an empirical study
Venue: arXiv cs.CY 2021
Year: 2021

There is a limited understanding of IT's role as a crucial enabler of patient agility and the department's ability to respond to patient's needs and wishes adequately. This study's objective is to contribute to the insights of the validity of the hypothesized relationship between IT resources, practices and capabilities, and hospital departments' knowledge processes and the department's ability to adequately sense and respond to patient needs and wishes, i.e., patient agility. This study conveniently sampled data from 107 clinical hospital departments in the Netherlands and uses structural equation modeling for model assessment. IT ambidexterity positively enhances the development of a digital dynamic capability. Likewise, IT ambidexterity also positively impacts the hospital department's knowledge processes. Both digital dynamic capability and knowledge processes positively influence patient agility. IT ambidexterity promotes taking advantage of IT resources and experiments to reshape patient services and enhance patient agility.
Combinatorial Gap Theorem and Reductions between Promise CSPs
Venue: arXiv cs.CC 2021
Year: 2021

A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and show that, for purely combinatorial reasons, a value of an unsolvable instance is bounded away from one; we call this fact a gap theorem. We show that the gap theorem implies NP-hardness of a gap version of the Layered Label Cover Problem. The same result can be derived from the PCP Theorem, but a full, self-contained proof of our reduction is quite short and the result can still provide PCP-free NP-hardness proofs for numerous problems. The simplicity of our reasoning also suggests that weaker versions of Unique-Games-type conjectures, e.g., the d-to-1 conjecture, might be accessible and serve as an intermediate step for proving these conjectures in their full strength. As the second, main application we provide a sufficient condition under which a fixed template Promise Constraint Satisfaction Problem (PCSP) reduces to another PCSP. The correctness of the reduction hinges on the gap theorem, but the reduction itself is very simple. As a consequence, we obtain that every CSP can be canonically reduced to most of the known NP-hard PCSPs, such as the approximate hypergraph coloring problem.
RankSRGAN: Super Resolution Generative Adversarial Networks with Learning to Rank
Venue: arXiv cs.CV 2021
Year: 2021

Generative Adversarial Networks (GAN) have demonstrated the potential to recover realistic details for single image super-resolution (SISR). To further improve the visual quality of super-resolved results, PIRM2018-SR Challenge employed perceptual metrics to assess the perceptual quality, such as PI, NIQE, and Ma. However, existing methods cannot directly optimize these indifferentiable perceptual metrics, which are shown to be highly correlated with human ratings. To address the problem, we propose Super-Resolution Generative Adversarial Networks with Ranker (RankSRGAN) to optimize generator in the direction of different perceptual metrics. Specifically, we first train a Ranker which can learn the behaviour of perceptual metrics and then introduce a novel rank-content loss to optimize the perceptual quality. The most appealing part is that the proposed method can combine the strengths of different SR methods to generate better results. Furthermore, we extend our method to multiple Rankers to provide multi-dimension constraints for the generator. Extensive experiments show that RankSRGAN achieves visually pleasing results and reaches state-of-the-art performance in perceptual metrics and quality. Project page: https://wenlongzhang0517.github.io/Projects/RankSRGAN
Edge of chaos as a guiding principle for modern neural network training
Venue: arXiv cs.LG 2021
Year: 2021

The success of deep neural networks in real-world problems has prompted many attempts to explain their training dynamics and generalization performance, but more guiding principles for the training of neural networks are still needed. Motivated by the edge of chaos principle behind the optimal performance of neural networks, we study the role of various hyperparameters in modern neural network training algorithms in terms of the order-chaos phase diagram. In particular, we study a fully analytical feedforward neural network trained on the widely adopted Fashion-MNIST dataset, and study the dynamics associated with the hyperparameters in back-propagation during the training process. We find that for the basic algorithm of stochastic gradient descent with momentum, in the range around the commonly used hyperparameter values, clear scaling relations are present with respect to the training time during the ordered phase in the phase diagram, and the model's optimal generalization power at the edge of chaos is similar across different training parameter combinations. In the chaotic phase, the same scaling no longer exists. The scaling allows us to choose the training parameters to achieve faster training without sacrificing performance. In addition, we find that the commonly used model regularization method - weight decay - effectively pushes the model towards the ordered phase to achieve better performance. Leveraging on this fact and the scaling relations in the other hyperparameters, we derived a principled guideline for hyperparameter determination, such that the model can achieve optimal performance by saturating it at the edge of chaos. Demonstrated on this simple neural network model and training algorithm, our work improves the understanding of neural network training dynamics, and can potentially be extended to guiding principles of more complex model architectures and algorithms.
FPT Approximation for Fair Minimum-Load Clustering
Venue: arXiv cs.CG 2021
Year: 2021

In this paper, we consider the Minimum-Load $k$-Clustering/Facility Location (MLkC) problem where we are given a set $P$ of $n$ points in a metric space that we have to cluster and an integer $k$ that denotes the number of clusters. Additionally, we are given a set $F$ of cluster centers in the same metric space. The goal is to select a set $C\subseteq F$ of $k$ centers and assign each point in $P$ to a center in $C$, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have a rich literature, the minimum-load objective is not studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [ACM Trans. Algo. 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is $O(k)$, even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017], which generalizes MLkC. Here the input points are colored by one of the $\ell$ colors denoting the group they belong to. MLkC is the special case with $\ell=1$. Considering this problem, we are able to obtain a $3$-approximation in $f(k,\ell)\cdot n^{O(1)}$ time. Also, our scheme leads to an improved $(1 + ε)$-approximation in case of Euclidean norm, and in this case, the running time depends only polynomially on the dimension $d$. Our results imply the same approximations for MLkC with running time $f(k)\cdot n^{O(1)}$, achieving the first constant approximations for this problem in general and Euclidean metric spaces.