OpenRaiser/Intern-Atlas huggingface dataset:
Statistical physics approaches to Unique Games
Venue: arXiv cs.DS 2019
Year: 2019

We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture.
Verifying Visibility-Based Weak Consistency
Venue: arXiv cs.LO 2019
Year: 2019

Multithreaded programs generally leverage efficient and thread-safe concurrent objects like sets, key-value maps, and queues. While some concurrent-object operations are designed to behave atomically, each witnessing the atomic effects of predecessors in a linearization order, others forego such strong consistency to avoid complex control and synchronization bottlenecks. For example, contains (value) methods of key-value maps may iterate through key-value entries without blocking concurrent updates, to avoid unwanted performance bottlenecks, and consequently overlook the effects of some linearization-order predecessors. While such weakly-consistent operations may not be atomic, they still offer guarantees, e.g., only observing values that have been present. In this work we develop a methodology for proving that concurrent object implementations adhere to weak-consistency specifications. In particular, we consider (forward) simulation-based proofs of implementations against relaxed-visibility specifications, which allow designated operations to overlook some of their linearization-order predecessors, i.e., behaving as if they never occurred. Besides annotating implementation code to identify linearization points, i.e., points at which operations' logical effects occur, we also annotate code to identify visible operations, i.e., operations whose effects are observed; in practice this annotation can be done automatically by tracking the writers to each accessed memory location. We formalize our methodology over a general notion of transition systems, agnostic to any particular programming language or memory model, and demonstrate its application, using automated theorem provers, by verifying models of Java concurrent object implementations.
Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties
Venue: arXiv cs.CG 2019
Year: 2019

Data analysts commonly utilize statistics to summarize large datasets. While it is often sufficient to explore only the summary statistics of a dataset (e.g., min/mean/max), Anscombe's Quartet demonstrates how such statistics can be misleading. We consider a similar problem in the context of graph mining. To study the relationships between different graph properties, we examine low-order non-isomorphic graphs and provide a simple visual analytics system to explore correlations across multiple graph properties. However, for larger graphs, studying the entire space quickly becomes intractable. We use different random graph generation methods to further look into the distribution of graph properties for higher order graphs and investigate the impact of various sampling methodologies. We also describe a method for generating many graphs that are identical over a number of graph properties and statistics yet are clearly different and identifiably distinct.
On the Importance of Location Privacy for Users of Location Based Applications
Venue: arXiv cs.DB 2019
Year: 2019

Do people care about their location privacy while using location-based service apps? This paper aims to answer this question and several other hypotheses through a survey, and review the privacy preservation techniques. Our results indicate that privacy is indeed an influential factor in the selection of location-based apps by users.
Congestion Analysis of Convolutional Neural Network-Based Pedestrian Counting Methods on Helicopter Footage
Venue: arXiv cs.CV 2019
Year: 2019

Over the past few years, researchers have presented many different applications for convolutional neural networks, including those for the detection and recognition of objects from images. The desire to understand our own nature has always been an important motivation for research. Thus, the visual recognition of humans is among the most important issues facing machine learning today. Most solutions for this task have been developed and tested by using several publicly available datasets. These datasets typically contain images taken from street-level closed-circuit television cameras offering a low-angle view. There are major differences between such images and those taken from the sky. In addition, aerial images are often very congested, containing hundreds of targets. These factors may have significant impact on the quality of the results. In this paper, we investigate state-of-the-art methods for counting pedestrians and the related performance of aerial footage. Furthermore, we analyze this performance with respect to the congestion levels of the images.
Towards Optimal and Efficient Best Arm Identification in Linear Bandits
Venue: arXiv cs.LG 2019
Year: 2019

We give a new algorithm for best arm identification in linearly parameterised bandits in the fixed confidence setting. The algorithm generalises the well-known LUCB algorithm of Kalyanakrishnan et al. (2012) by playing an arm which minimises a suitable notion of geometric overlap of the statistical confidence set for the unknown parameter, and is fully adaptive and computationally efficient as compared to several state-of-the methods. We theoretically analyse the sample complexity of the algorithm for problems with two and three arms, showing optimality in many cases. Numerical results indicate favourable performance over other algorithms with which we compare.
Fourth Industrial Revolution for Development: The Relevance of Cloud Federation in Healthcare Support
Venue: arXiv cs.DC 2019
Year: 2019

Inefficient healthcare is a major concern among many African nations and can be mitigated by building world-class infrastructure connecting different medical facilities for collaboration and resource sharing. Such infrastructure should support collection and exchange of medical data for the purpose of accessing expertise not available locally. It should be equipped with modern technologies of the fourth industrial revolution, providing decision support to doctors thereby enabling African nations leapfrog from poorly equipped to medically prepared. Sadly, world-class healthcare infrastructure are a missing piece in the African public health ecosystem. Medical facilities are either non-existent or prohibitively expensive when they exist. Federated cloud computing can provide a solution to this challenge. Being a model that allows collaboration between multiple Cloud service providers through resources pooling; it allows for the execution of tasks on computing resources flexibly and cost efficiently. This paper aims to connect unconnected medical facilities in Africa by proposing a Cloud federation for healthcare using cooperative and competitive collaboration models. Simulations were carried out to test the efficacy of these models using five different workload allocation schemes: First-Fit-Descending (FFD), Best-Fit-Descending (BFD), Binary-Search-Best-Fit (BSBF); Genetic Algorithm meta-heuristic and Stable Roommate Allocation economic model for both light and heavy workloads. Results of simulations revealed that the cooperative model resulted in lower delays but higher resource utilisation; while the competitive provided faster service delivery and better quality of service. BSBF and BFD resulted in the best resources utilisation and energy conservation. Finally, deployment considerations and potential business models for federated Cloud for African healthcare were presented.
Enhancing the Privacy of Federated Learning with Sketching
Venue: arXiv cs.LG 2019
Year: 2019

In response to growing concerns about user privacy, federated learning has emerged as a promising tool to train statistical models over networks of devices while keeping data localized. Federated learning methods run training tasks directly on user devices and do not share the raw user data with third parties. However, current methods still share model updates, which may contain private information (e.g., one's weight and height), during the training process. Existing efforts that aim to improve the privacy of federated learning make compromises in one or more of the following key areas: performance (particularly communication cost), accuracy, or privacy. To better optimize these trade-offs, we propose that \textit{sketching algorithms} have a unique advantage in that they can provide both privacy and performance benefits while maintaining accuracy. We evaluate the feasibility of sketching-based federated learning with a prototype on three representative learning models. Our initial findings show that it is possible to provide strong privacy guarantees for federated learning without sacrificing performance or accuracy. Our work highlights that there exists a fundamental connection between privacy and communication in distributed settings, and suggests important open problems surrounding the theoretical understanding, methodology, and system design of practical, private federated learning.
Breaking the Hidden Irreducible Polynomials Scheme
Venue: arXiv cs.CR 2019
Year: 2019

In 2019 Gómez described a new public key cryptography scheme based on ideas from multivariate public key cryptography using hidden irreducible polynomials. We show that the scheme's design has a flaw which lets an attacker recover the private key directly from the public key.
Fully Dynamic Matching: Beating 2-Approximation in $Δ^ε$ Update Time
Venue: arXiv cs.DS 2019
Year: 2019

In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a $2-Ω(1)$ approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant $ε> 0$, there is a randomized algorithm that with high probability maintains a $2-Ω(1)$ approximate maximum matching of a fully-dynamic general graph in worst-case update time $O(Δ^ε+\text{polylog } n)$, where $Δ$ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had $O(m^{1/4})$ update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time $O(n^ε)$ was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].
Biconditional Generative Adversarial Networks for Multiview Learning with Missing Views
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we present a conditional GAN with two generators and a common discriminator for multiview learning problems where observations have two views, but one of them may be missing for some of the training samples. This is for example the case for multilingual collections where documents are not available in all languages. Some studies tackled this problem by assuming the existence of view generation functions to approximately complete the missing views; for example Machine Translation to translate documents into the missing languages. These functions generally require an external resource to be set and their quality has a direct impact on the performance of the learned multiview classifier over the completed training set. Our proposed approach addresses this problem by jointly learning the missing views and the multiview classifier using a tripartite game with two generators and a discriminator. Each of the generators is associated to one of the views and tries to fool the discriminator by generating the other missing view conditionally on the corresponding observed view. The discriminator then tries to identify if for an observation, one of its views is completed by one of the generators or if both views are completed along with its class. Our results on a subset of Reuters RCV1/RCV2 collections show that the discriminator achieves significant classification performance; and that the generators learn the missing views with high quality without the need of any consequent external resource.
Reducing audio membership inference attack accuracy to chance: 4 defenses
Venue: arXiv cs.CR 2019
Year: 2019

It is critical to understand the privacy and robustness vulnerabilities of machine learning models, as their implementation expands in scope. In membership inference attacks, adversaries can determine whether a particular set of data was used in training, putting the privacy of the data at risk. Existing work has mostly focused on image related tasks; we generalize this type of attack to speaker identification on audio samples. We demonstrate attack precision of 85.9\% and recall of 90.8\% for LibriSpeech, and 78.3\% precision and 90.7\% recall for VOiCES (Voices Obscured in Complex Environmental Settings). We find that implementing defenses such as prediction obfuscation, defensive distillation or adversarial training, can reduce attack accuracy to chance.
A Comparative Analysis of XGBoost
Venue: arXiv cs.LG 2019
Year: 2019

XGBoost is a scalable ensemble technique based on gradient boosting that has demonstrated to be a reliable and efficient machine learning challenge solver. This work proposes a practical analysis of how this novel technique works in terms of training speed, generalization performance and parameter setup. In addition, a comprehensive comparison between XGBoost, random forests and gradient boosting has been performed using carefully tuned models as well as using the default settings. The results of this comparison may indicate that XGBoost is not necessarily the best choice under all circumstances. Finally an extensive analysis of XGBoost parametrization tuning process is carried out.
Dynamic Time Warp Convolutional Networks
Venue: arXiv cs.LG 2019
Year: 2019

Where dealing with temporal sequences it is fair to assume that the same kind of deformations that motivated the development of the Dynamic Time Warp algorithm could be relevant also in the calculation of the dot product ("convolution") in a 1-D convolution layer. In this work a method is proposed for aligning the convolution filter and the input where they are locally out of phase utilising an algorithm similar to the Dynamic Time Warp. The proposed method enables embedding a non-parametric warping of temporal sequences for increasing similarity directly in deep networks and can expand on the generalisation capabilities and the capacity of standard 1-D convolution layer where local sequential deformations are present in the input. Experimental results demonstrate the proposed method exceeds or matches the standard 1-D convolution layer in terms of the maximum accuracy achieved on a number of time series classification tasks. In addition the impact of different hyperparameters settings is investigated given different datasets and the results support the conclusions of previous work done in relation to the choice of DTW parameter values. The proposed layer can be freely integrated with other typical layers to compose deep artificial neural networks of an arbitrary architecture that are trained using standard stochastic gradient descent.
Efficiently Learning Structured Distributions from Untrusted Batches
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem, introduced by Qiao and Valiant, of learning from untrusted batches. Here, we assume $m$ users, all of whom have samples from some underlying distribution $p$ over $1, \ldots, n$. Each user sends a batch of $k$ i.i.d. samples from this distribution; however an $ε$-fraction of users are untrustworthy and can send adversarially chosen responses. The goal is then to learn $p$ in total variation distance. When $k = 1$ this is the standard robust univariate density estimation setting and it is well-understood that $Ω(ε)$ error is unavoidable. Suprisingly, Qiao and Valiant gave an estimator which improves upon this rate when $k$ is large. Unfortunately, their algorithms run in time exponential in either $n$ or $k$. We first give a sequence of polynomial time algorithms whose estimation error approaches the information-theoretically optimal bound for this problem. Our approach is based on recent algorithms derived from the sum-of-squares hierarchy, in the context of high-dimensional robust estimation. We show that algorithms for learning from untrusted batches can also be cast in this framework, but by working with a more complicated set of test functions. It turns out this abstraction is quite powerful and can be generalized to incorporate additional problem specific constraints. Our second and main result is to show that this technology can be leveraged to build in prior knowledge about the shape of the distribution. Crucially, this allows us to reduce the sample complexity of learning from untrusted batches to polylogarithmic in $n$ for most natural classes of distributions, which is important in many applications. To do so, we demonstrate that these sum-of-squares algorithms for robust mean estimation can be made to handle complex combinatorial constraints (e.g. those arising from VC theory), which may be of independent technical interest.
Secure Federated Submodel Learning
Venue: arXiv cs.LG 2019
Year: 2019

Federated learning was proposed with an intriguing vision of achieving collaborative machine learning among numerous clients without uploading their private data to a cloud server. However, the conventional framework requires each client to leverage the full model for learning, which can be prohibitively inefficient for resource-constrained clients and large-scale deep learning tasks. We thus propose a new framework, called federated submodel learning, where clients download only the needed parts of the full model, namely submodels, and then upload the submodel updates. Nevertheless, the "position" of a client's truly required submodel corresponds to her private data, and its disclosure to the cloud server during interactions inevitably breaks the tenet of federated learning. To integrate efficiency and privacy, we have designed a secure federated submodel learning scheme coupled with a private set union protocol as a cornerstone. Our secure scheme features the properties of randomized response, secure aggregation, and Bloom filter, and endows each client with a customized plausible deniability, in terms of local differential privacy, against the position of her desired submodel, thus protecting her private data. We further instantiated our scheme with the e-commerce recommendation scenario in Alibaba, implemented a prototype system, and extensively evaluated its performance over 30-day Taobao user data. The analysis and evaluation results demonstrate the feasibility and scalability of our scheme from model accuracy and convergency, practical communication, computation, and storage overheads, as well as manifest its remarkable advantages over the conventional federated learning framework.
Average Age-of-Information with a Backup Information Source
Venue: arXiv cs.IT 2019
Year: 2019

Data collected and transmitted by Internet of things (IoT) devices are typically used for control and monitoring purposes; and hence, their timely delivery is of utmost importance for the underlying applications. However, IoT devices operate with very limited energy sources, severely reducing their ability for timely collection and processing of status updates. IoT systems make up for these limitations by employing multiple low-power low-complexity devices that can monitor the same signal, possibly with different quality observations and different energy costs, to create diversity against the limitations of individual nodes. We investigate policies to minimize the average age of information (AoI) in a monitoring system that collects data from two sources of information denoted as primary and backup sources, respectively. We assume that each source offers a different trade-off between the AoI and the energy cost. The monitoring node is equipped with a finite size battery and harvests ambient energy. For this setup, we formulate the scheduling of status updates from the two sources as a Markov decision process (MDP), and obtain a policy that decides on the optimal action to take (i.e., which source to query or remain idle) depending on the current energy level and AoI. The performance of the obtained policy is compared with an aggressive policy for different system parameters. We identify few types of optimal solution structures and discuss the benefits of having a backup source of information in the system.
AIM 2019 Challenge on Image Demoireing: Dataset and Study
Venue: arXiv cs.CV 2019
Year: 2019

This paper introduces a novel dataset, called LCDMoire, which was created for the first-ever image demoireing challenge that was part of the Advances in Image Manipulation (AIM) workshop, held in conjunction with ICCV 2019. The dataset comprises 10,200 synthetically generated image pairs (consisting of an image degraded by moire and a clean ground truth image). In addition to describing the dataset and its creation, this paper also reviews the challenge tracks, competition, and results, the latter summarizing the current state-of-the-art on this dataset.
Metrics Induced by Jensen-Shannon and Related Divergences on Positive Definite Matrices
Venue: arXiv cs.IT 2019
Year: 2019

We study metric properties of symmetric divergences on Hermitian positive definite matrices. In particular, we prove that the square root of these divergences is a distance metric. As a corollary we obtain a proof of the metric property for Quantum Jensen-Shannon-(Tsallis) divergences (parameterized by $α\in [0,2]$), which in turn (for $α=1$) yields a proof of the metric property of the Quantum Jensen-Shannon divergence that was conjectured by Lamberti \emph{et al.} a decade ago (\emph{Metric character of the quantum Jensen-Shannon divergence}, Phy.\ Rev.\ A, \textbf{79}, (2008).) A somewhat more intricate argument also establishes metric properties of Jensen-Rényi divergences (for $α\in (0,1)$), and outlines a technique that may be of independent interest.
Towards the Use of Neural Networks for Influenza Prediction at Multiple Spatial Resolutions
Venue: arXiv cs.LG 2019
Year: 2019

We introduce the use of a Gated Recurrent Unit (GRU) for influenza prediction at the state- and city-level in the US, and experiment with the inclusion of real-time flu-related Internet search data. We find that a GRU has lower prediction error than current state-of-the-art methods for data-driven influenza prediction at time horizons of over two weeks. In contrast with other machine learning approaches, the inclusion of real-time Internet search data does not improve GRU predictions.