OpenRaiser/Intern-Atlas huggingface dataset:
Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces
Venue: arXiv cs.CG 2021
Year: 2021

The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. Among the challenges that it poses is to expand the currently limited range of random polynomials that we can handle. Despite important recent progress, the available tools cannot handle random sparse polynomials and Gaussian polynomials, that is polynomials whose coefficients are i.i.d. Gaussian random variables. We initiate a condition-based complexity framework based on the norm of the cube that is a step in this direction. We present this framework for real hypersurfaces and univariate polynomials. We demonstrate its capabilities in two problems, under very mild probabilistic assumptions. On the one hand, we show that the average run-time of the Plantinga-Vegter algorithm is polynomial in the degree for random sparse (alas a restricted sparseness structure) polynomials and random Gaussian polynomials. On the other hand, we study the size of the subdivision tree for Descartes' solver and run-time of the solver by Jindal and Sagraloff (arXiv:1704.06979). In both cases, we provide a bound that is polynomial in the size of the input (size of the support plus the logarithm of the degree) not only for the average but also for all higher moments.
Precoder Design and Power Allocation for Downlink MIMO-NOMA via Simultaneous Triangularization
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we consider the downlink precoder design for two-user power-domain multiple-input multiple-output (MIMO) non-orthogonal multiple access (NOMA) systems. The proposed precoding scheme is based on simultaneous triangularization and decomposes the MIMO-NOMA channels of the two users into multiple single-input single-output NOMA channels, assuming low-complexity self-interference cancellation at the users. In contrast to the precoding schemes based on simultaneous diagonalization (SD), the proposed scheme avoids inverting the MIMO channels of the users, thereby enhancing the ergodic rate performance. Furthermore, we develop a power allocation algorithm based on the convex-concave procedure, and exploit it to obtain the ergodic achievable rate region of the proposed MIMO-NOMA scheme. Our results illustrate that the proposed scheme outperforms baseline precoding schemes based on SD and orthogonal multiple access for a wide range of user rates and performs close to the dirty paper coding upper bound. The ergodic rate region can further be improved by utilizing a hybrid scheme based on time sharing between the proposed MIMO-NOMA scheme and point-to-point MIMO.
Picket: Guarding Against Corrupted Data in Tabular Data during Learning and Inference
Venue: arXiv cs.LG 2021
Year: 2021

Data corruption is an impediment to modern machine learning deployments. Corrupted data can severely bias the learned model and can also lead to invalid inferences. We present, Picket, a simple framework to safeguard against data corruptions during both training and deployment of machine learning models over tabular data. For the training stage, Picket identifies and removes corrupted data points from the training data to avoid obtaining a biased model. For the deployment stage, Picket flags, in an online manner, corrupted query points to a trained machine learning model that due to noise will result in incorrect predictions. To detect corrupted data, Picket uses a self-supervised deep learning model for mixed-type tabular data, which we call PicketNet. To minimize the burden of deployment, learning a PicketNet model does not require any human-labeled data. Picket is designed as a plugin that can increase the robustness of any machine learning pipeline. We evaluate Picket on a diverse array of real-world data considering different corruption models that include systematic and adversarial noise during both training and testing. We show that Picket consistently safeguards against corrupted data during both training and deployment of various models ranging from SVMs to neural networks, beating a diverse array of competing methods that span from data quality validation models to robust outlier-detection models.
SoK: Attacks on Industrial Control Logic and Formal Verification-Based Defenses
Venue: arXiv cs.CR 2021
Year: 2021

Programmable Logic Controllers (PLCs) play a critical role in the industrial control systems. Vulnerabilities in PLC programs might lead to attacks causing devastating consequences to the critical infrastructure, as shown in Stuxnet and similar attacks. In recent years, we have seen an exponential increase in vulnerabilities reported for PLC control logic. Looking back on past research, we found extensive studies explored control logic modification attacks, as well as formal verification-based security solutions. We performed systematization on these studies, and found attacks that can compromise a full chain of control and evade detection. However, the majority of the formal verification research investigated ad-hoc techniques targeting PLC programs. We discovered challenges in every aspect of formal verification, rising from (1) the ever-expanding attack surface from evolved system design, (2) the real-time constraint during the program execution, and (3) the barrier in security evaluation given proprietary and vendor-specific dependencies on different techniques. Based on the knowledge systematization, we provide a set of recommendations for future research directions, and we highlight the need of defending security issues besides safety issues.
Detection of Makeup Presentation Attacks based on Deep Face Representations
Venue: arXiv cs.CV 2021
Year: 2021

Facial cosmetics have the ability to substantially alter the facial appearance, which can negatively affect the decisions of a face recognition. In addition, it was recently shown that the application of makeup can be abused to launch so-called makeup presentation attacks. In such attacks, the attacker might apply heavy makeup in order to achieve the facial appearance of a target subject for the purpose of impersonation. In this work, we assess the vulnerability of a COTS face recognition system to makeup presentation attacks employing the publicly available Makeup Induced Face Spoofing (MIFS) database. It is shown that makeup presentation attacks might seriously impact the security of the face recognition system. Further, we propose an attack detection scheme which distinguishes makeup presentation attacks from genuine authentication attempts by analysing differences in deep face representations obtained from potential makeup presentation attacks and corresponding target face images. The proposed detection system employs a machine learning-based classifier, which is trained with synthetically generated makeup presentation attacks utilizing a generative adversarial network for facial makeup transfer in conjunction with image warping. Experimental evaluations conducted using the MIFS database reveal a detection equal error rate of 0.7% for the task of separating genuine authentication attempts from makeup presentation attacks.
audino: A Modern Annotation Tool for Audio and Speech
Venue: arXiv cs.SD 2021
Year: 2021

In this paper, we introduce a collaborative and modern annotation tool for audio and speech: audino. The tool allows annotators to define and describe temporal segmentation in audios. These segments can be labelled and transcribed easily using a dynamically generated form. An admin can centrally control user roles and project assignment through the admin dashboard. The dashboard also enables describing labels and their values. The annotations can easily be exported in JSON format for further analysis. The tool allows audio data and their corresponding annotations to be uploaded and assigned to a user through a key-based API. The flexibility available in the annotation tool enables annotation for Speech Scoring, Voice Activity Detection (VAD), Speaker Diarisation, Speaker Identification, Speech Recognition, Emotion Recognition tasks and more. The MIT open source license allows it to be used for academic and commercial projects.
Mathematical Theory of Atomic Norm Denoising In Blind Two-Dimensional Super-Resolution (Extended Version)
Venue: arXiv cs.IT 2021
Year: 2021

This paper develops a new mathematical framework for denoising in blind two-dimensional (2D) super-resolution upon using the atomic norm. The framework denoises a signal that consists of a weighted sum of an unknown number of time-delayed and frequency-shifted unknown waveforms from its noisy measurements. Moreover, the framework also provides an approach for estimating the unknown parameters in the signal. We prove that when the number of the observed samples satisfies certain lower bound that is a function of the system parameters, we can estimate the noise-free signal, with very high accuracy, upon solving a regularized least-squares atomic norm minimization problem. We derive the theoretical mean-squared error of the estimator, and we show that it depends on the noise variance, the number of unknown waveforms, the number of samples, and the dimension of the low-dimensional space where the unknown waveforms lie. Finally, we verify the theoretical findings of the paper by using extensive simulation experiments.
Are weighted games sufficiently good for binary voting?
Venue: arXiv cs.GT 2021
Year: 2021

Binary yes-no decisions in a legislative committee or a shareholder meeting are commonly modeled as a weighted game. However, there are noteworthy exceptions. E.g., the voting rules of the European Council according to the Treaty of Lisbon use a more complicated construction. Here we want to study the question if we lose much from a practical point of view, if we restrict ourselves to weighted games. To this end, we invoke power indices that measure the influence of a member in binary decision committees. More precisely, we compare the achievable power distributions of weighted games with those from a reasonable superset of weighted games. It turns out that the deviation is relatively small.
Self-supervised Learning from a Multi-view Perspective
Venue: arXiv cs.LG 2021
Year: 2021

As a subset of unsupervised representation learning, self-supervised representation learning adopts self-defined signals as supervision and uses the learned representation for downstream tasks, such as object detection and image captioning. Many proposed approaches for self-supervised learning follow naturally a multi-view perspective, where the input (e.g., original images) and the self-supervised signals (e.g., augmented images) can be seen as two redundant views of the data. Building from this multi-view perspective, this paper provides an information-theoretical framework to better understand the properties that encourage successful self-supervised learning. Specifically, we demonstrate that self-supervised learned representations can extract task-relevant information and discard task-irrelevant information. Our theoretical framework paves the way to a larger space of self-supervised learning objective design. In particular, we propose a composite objective that bridges the gap between prior contrastive and predictive learning objectives, and introduce an additional objective term to discard task-irrelevant information. To verify our analysis, we conduct controlled experiments to evaluate the impact of the composite objectives. We also explore our framework's empirical generalization beyond the multi-view perspective, where the cross-view redundancy may not be clearly observed.
Continuous Action Reinforcement Learning from a Mixture of Interpretable Experts
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning (RL) has demonstrated its ability to solve high dimensional tasks by leveraging non-linear function approximators. However, these successes are mostly achieved by 'black-box' policies in simulated domains. When deploying RL to the real world, several concerns regarding the use of a 'black-box' policy might be raised. In order to make the learned policies more transparent, we propose in this paper a policy iteration scheme that retains a complex function approximator for its internal value predictions but constrains the policy to have a concise, hierarchical, and human-readable structure, based on a mixture of interpretable experts. Each expert selects a primitive action according to a distance to a prototypical state. A key design decision to keep such experts interpretable is to select the prototypical states from trajectory data. The main technical contribution of the paper is to address the challenges introduced by this non-differentiable prototypical state selection procedure. Experimentally, we show that our proposed algorithm can learn compelling policies on continuous action deep RL benchmarks, matching the performance of neural network based policies, but returning policies that are more amenable to human inspection than neural network or linear-in-feature policies.
Perceiving Music Quality with GANs
Venue: arXiv cs.SD 2021
Year: 2021

Several methods have been developed to assess the perceptual quality of audio under transforms like lossy compression. However, they require paired reference signals of the unaltered content, limiting their use in applications where references are unavailable. This has hindered progress in audio generation and style transfer, where a no-reference quality assessment method would allow more reproducible comparisons across methods. We propose training a GAN on a large music library, and using its discriminator as a no-reference quality assessment measure of the perceived quality of music. This method is unsupervised, needs no access to degraded material and can be tuned for various domains of music. In a listening test with 448 human subjects, where participants rated professionally produced music tracks degraded with different levels and types of signal degradations such as waveshaping distortion and low-pass filtering, we establish a dataset of human rated material. By using the human rated dataset we show that the discriminator score correlates significantly with the subjective ratings, suggesting that the proposed method can be used to create a no-reference musical audio quality assessment measure.
The development and deployment of formal methods in the UK
Venue: arXiv cs.SE 2021
Year: 2021

UK researchers have made major contributions to the technical ideas underpinning formal approaches to the specification and development of computer systems. Perhaps as a consequence of this, some of the significant attempts to deploy theoretical ideas into practical environments have taken place in the UK. The authors of this paper have been involved in formal methods for many years and both have tracked a significant proportion of the whole story. This paper both lists key ideas and indicates where attempts were made to use the ideas in practice. Not all of these deployment stories have been a complete success and an attempt is made to tease out lessons that influence the probability of long-term impact.
TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation
Venue: arXiv cs.LG 2021
Year: 2021

Thompson sampling has become a ubiquitous approach to online decision problems with bandit feedback. The key algorithmic task for Thompson sampling is drawing a sample from the posterior of the optimal action. We propose an alternative arm selection rule we dub TS-UCB, that requires negligible additional computational effort but provides significant performance improvements relative to Thompson sampling. At each step, TS-UCB computes a score for each arm using two ingredients: posterior sample(s) and upper confidence bounds. TS-UCB can be used in any setting where these two quantities are available, and it is flexible in the number of posterior samples it takes as input. TS-UCB achieves materially lower regret on a comprehensive suite of synthetic and real-world datasets, including a personalized article recommendation dataset from Yahoo! and a suite of benchmark datasets from a deep bandit suite proposed in Riquelme et al. (2018). Finally, from a theoretical perspective, we establish optimal regret guarantees for TS-UCB for both the K-armed and linear bandit models.
Revisiting Explicit Regularization in Neural Networks for Well-Calibrated Predictive Uncertainty
Venue: arXiv cs.LG 2021
Year: 2021

From the statistical learning perspective, complexity control via explicit regularization is a necessity for improving the generalization of over-parameterized models. However, the impressive generalization performance of neural networks with only implicit regularization may be at odds with this conventional wisdom. In this work, we revisit the importance of explicit regularization for obtaining well-calibrated predictive uncertainty. Specifically, we introduce a probabilistic measure of calibration performance, which is lower bounded by the log-likelihood. We then explore explicit regularization techniques for improving the log-likelihood on unseen samples, which provides well-calibrated predictive uncertainty. Our findings present a new direction to improve the predictive probability quality of deterministic neural networks, which can be an efficient and scalable alternative to Bayesian neural networks and ensemble methods.
Attentive WaveBlock: Complementarity-enhanced Mutual Networks for Unsupervised Domain Adaptation in Person Re-identification and Beyond
Venue: arXiv cs.CV 2021
Year: 2021

Unsupervised domain adaptation (UDA) for person re-identification is challenging because of the huge gap between the source and target domain. A typical self-training method is to use pseudo-labels generated by clustering algorithms to iteratively optimize the model on the target domain. However, a drawback to this is that noisy pseudo-labels generally cause trouble in learning. To address this problem, a mutual learning method by dual networks has been developed to produce reliable soft labels. However, as the two neural networks gradually converge, their complementarity is weakened and they likely become biased towards the same kind of noise. This paper proposes a novel light-weight module, the Attentive WaveBlock (AWB), which can be integrated into the dual networks of mutual learning to enhance the complementarity and further depress noise in the pseudo-labels. Specifically, we first introduce a parameter-free module, the WaveBlock, which creates a difference between features learned by two networks by waving blocks of feature maps differently. Then, an attention mechanism is leveraged to enlarge the difference created and discover more complementary features. Furthermore, two kinds of combination strategies, i.e. pre-attention and post-attention, are explored. Experiments demonstrate that the proposed method achieves state-of-the-art performance with significant improvements on multiple UDA person re-identification tasks. We also prove the generality of the proposed method by applying it to vehicle re-identification and image classification tasks. Our codes and models are available at https://github.com/WangWenhao0716/Attentive-WaveBlock.
Cumulant GAN
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we propose a novel loss function for training Generative Adversarial Networks (GANs) aiming towards deeper theoretical understanding as well as improved stability and performance for the underlying optimization problem. The new loss function is based on cumulant generating functions giving rise to \emph{Cumulant GAN}. Relying on a recently-derived variational formula, we show that the corresponding optimization problem is equivalent to R{é}nyi divergence minimization, thus offering a (partially) unified perspective of GAN losses: the R{é}nyi family encompasses Kullback-Leibler divergence (KLD), reverse KLD, Hellinger distance and $χ^2$-divergence. Wasserstein GAN is also a member of cumulant GAN. In terms of stability, we rigorously prove the linear convergence of cumulant GAN to the Nash equilibrium for a linear discriminator, Gaussian distributions and the standard gradient descent ascent algorithm. Finally, we experimentally demonstrate that image generation is more robust relative to Wasserstein GAN and it is substantially improved in terms of both inception score and Fréchet inception distance when both weaker and stronger discriminators are considered.
Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks
Venue: arXiv cs.SI 2021
Year: 2021

Decision-making about pandemic mitigation often relies upon simulation modelling. Models of disease transmission through networks of contacts--between individuals or between population centres--are increasingly used for these purposes. Real-world contact networks are rich in structural features that influence infection transmission, such as tightly-knit local communities that are weakly connected to one another. In this paper, we propose a new flow-based edge-betweenness centrality method for detecting bottleneck edges that connect nodes in contact networks. In particular, we utilize convex optimization formulations based on the idea of diffusion with p-norm network flow. Using simulation models of COVID-19 transmission through real network data at both individual and county levels, we demonstrate that targeting bottleneck edges identified by the proposed method reduces the number of infected cases by up to 10% more than state-of-the-art edge-betweenness methods. Furthermore, the proposed method is orders of magnitude faster than existing methods.
Shared Experience Actor-Critic for Multi-Agent Reinforcement Learning
Venue: arXiv cs.MA 2021
Year: 2021

Exploration in multi-agent reinforcement learning is a challenging problem, especially in environments with sparse rewards. We propose a general method for efficient exploration by sharing experience amongst agents. Our proposed algorithm, called Shared Experience Actor-Critic (SEAC), applies experience sharing in an actor-critic framework. We evaluate SEAC in a collection of sparse-reward multi-agent environments and find that it consistently outperforms two baselines and two state-of-the-art algorithms by learning in fewer steps and converging to higher returns. In some harder environments, experience sharing makes the difference between learning to solve the task and not learning at all.
Ensemble Distillation for Robust Model Fusion in Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Federated Learning (FL) is a machine learning setting where many devices collaboratively train a machine learning model while keeping the training data decentralized. In most of the current training schemes the central model is refined by averaging the parameters of the server model and the updated parameters from the client side. However, directly averaging model parameters is only possible if all models have the same structure and size, which could be a restrictive constraint in many scenarios. In this work we investigate more powerful and more flexible aggregation schemes for FL. Specifically, we propose ensemble distillation for model fusion, i.e. training the central classifier through unlabeled data on the outputs of the models from the clients. This knowledge distillation technique mitigates privacy risk and cost to the same extent as the baseline FL algorithms, but allows flexible aggregation over heterogeneous client models that can differ e.g. in size, numerical precision or structure. We show in extensive empirical experiments on various CV/NLP datasets (CIFAR-10/100, ImageNet, AG News, SST2) and settings (heterogeneous models/data) that the server model can be trained much faster, requiring fewer communication rounds than any existing FL technique so far.