OpenRaiser/Intern-Atlas huggingface dataset:
Privacy Preserving Multi-Server k-means Computation over Horizontally Partitioned Data
Venue: arXiv cs.CR 2019
Year: 2019

The k-means clustering is one of the most popular clustering algorithms in data mining. Recently a lot of research has been concentrated on the algorithm when the dataset is divided into multiple parties or when the dataset is too large to be handled by the data owner. In the latter case, usually some servers are hired to perform the task of clustering. The dataset is divided by the data owner among the servers who together perform the k-means and return the cluster labels to the owner. The major challenge in this method is to prevent the servers from gaining substantial information about the actual data of the owner. Several algorithms have been designed in the past that provide cryptographic solutions to perform privacy preserving k-means. We provide a new method to perform k-means over a large set using multiple servers. Our technique avoids heavy cryptographic computations and instead we use a simple randomization technique to preserve the privacy of the data. The k-means computed has exactly the same efficiency and accuracy as the k-means computed over the original dataset without any randomization. We argue that our algorithm is secure against honest but curious and passive adversary.
PAC Battling Bandits in the Plackett-Luce Model
Venue: arXiv cs.LG 2019
Year: 2019

We introduce the probably approximately correct (PAC) \emph{Battling-Bandit} problem with the Plackett-Luce (PL) subset choice model--an online learning framework where at each trial the learner chooses a subset of $k$ arms from a fixed set of $n$ arms, and subsequently observes a stochastic feedback indicating preference information of the items in the chosen subset, e.g., the most preferred item or ranking of the top $m$ most preferred items etc. The objective is to identify a near-best item in the underlying PL model with high confidence. This generalizes the well-studied PAC \emph{Dueling-Bandit} problem over $n$ arms, which aims to recover the \emph{best-arm} from pairwise preference information, and is known to require $O(\frac{n}{ε^2} \ln \frac{1}δ)$ sample complexity \citep{Busa_pl,Busa_top}. We study the sample complexity of this problem under various feedback models: (1) Winner of the subset (WI), and (2) Ranking of top-$m$ items (TR) for $2\le m \le k$. We show, surprisingly, that with winner information (WI) feedback over subsets of size $2 \leq k \leq n$, the best achievable sample complexity is still $O\left( \frac{n}{ε^2} \ln \frac{1}δ\right)$, independent of $k$, and the same as that in the Dueling Bandit setting ($k=2$). For the more general top-$m$ ranking (TR) feedback model, we show a significantly smaller lower bound on sample complexity of $Ω\bigg( \frac{n}{mε^2} \ln \frac{1}δ\bigg)$, which suggests a multiplicative reduction by a factor ${m}$ owing to the additional information revealed from preferences among $m$ items instead of just $1$. We also propose two algorithms for the PAC problem with the TR feedback model with optimal (upto logarithmic factors) sample complexity guarantees, establishing the increase in statistical efficiency from exploiting rank-ordered feedback.
Faster deterministic parameterized algorithm for k-Path
Venue: arXiv cs.DS 2019
Year: 2019

In the k-Path problem, the input is a directed graph $G$ and an integer $k\geq 1$, and the goal is to decide whether there is a simple directed path in $G$ with exactly $k$ vertices. We give a deterministic algorithm for k-Path with time complexity $O^*(2.554^k)$. This improves the previously best deterministic algorithm for this problem of Zehavi [ESA 2015] whose time complexity is $O^*(2.597^k)$. The technique used by our algorithm can also be used to obtain faster deterministic algorithms for k-Tree, r-Dimensional k-Matching, Graph Motif, and Partial Cover.
Covering Tours and Cycle Covers with Turn Costs: Hardness and Approximation
Venue: arXiv cs.CG 2019
Year: 2019

We investigate a variety of problems of finding tours and cycle covers with minimum turn cost. Questions of this type have been studied in the past, with complexity and approximation results as well as open problems dating back to work by Arkin et al. in 2001. A wide spectrum of practical applications have renewed the interest in these questions, and spawned variants: for full coverage, every point has to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring an individual penalty. We make a number of contributions. We first show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O'Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. On the positive side, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants, making use of LP/IP techniques. For full coverage in more general grid graphs (e.g., hexagonal grids), our approximation factors are better than the combinatorial ones of Arkin et al. Our approach can also be extended to other geometric variants, such as scenarios with obstacles and linear combinations of turn and distance costs.
Motion Feasibility Conditions for Multi-Agent Control Systems on Lie Groups
Venue: arXiv cs.SY 2019
Year: 2019

We study the problem of motion feasibility for multiagent control systems on Lie groups with collision avoidance constraints. We first consider the problem for kinematic left invariant control systems and next, for dynamical control systems given by a left-trivialized Lagrangian function. Solutions of the kinematic problem give rise to linear combinations of the control inputs in a linear subspace annihilating the collision avoidance constraints. In the dynamical problem, motion feasibility conditions are obtained by using techniques from variational calculus on manifolds, given by a set of equations in a vector space, and Lagrange multipliers annihilating the constraint force that prevents deviation of solutions from a constraint submanifold.
Sea of Lights: Practical Device-to-Device Security Bootstrapping in the Dark
Venue: arXiv cs.NI 2019
Year: 2019

Practical solutions to bootstrap security in today's information and communication systems critically depend on centralized services for authentication as well as key and trust management. This is particularly true for mobile users. Identity providers such as Google or Facebook have active user bases of two billion each, and the subscriber number of mobile operators exceeds five billion unique users as of early 2018. If these centralized services go completely `dark' due to natural or man made disasters, large scale blackouts, or country-wide censorship, the users are left without practical solutions to bootstrap security on their mobile devices. Existing distributed solutions, for instance, the so-called web-of-trust are not sufficiently lightweight. Furthermore, they support neither cross-application on mobile devices nor strong protection of key material using hardware security modules. We propose Sea of Lights(SoL), a practical lightweight scheme for bootstrapping device-to-device security wirelessly, thus, enabling secure distributed self-organized networks. It is tailored to operate `in the dark' and provides strong protection of key material as well as an intuitive means to build a lightweight web-of-trust. SoL is particularly well suited for local or urban operation in scenarios such as the coordination of emergency response, where it helps containing/limiting the spreading of misinformation. As a proof of concept, we implement SoL in the Android platform and hence test its feasibility on real mobile devices. We further evaluate its key performance aspects using simulation.
GestureGAN for Hand Gesture-to-Gesture Translation in the Wild
Venue: arXiv cs.CV 2019
Year: 2019

Hand gesture-to-gesture translation in the wild is a challenging task since hand gestures can have arbitrary poses, sizes, locations and self-occlusions. Therefore, this task requires a high-level understanding of the mapping between the input source gesture and the output target gesture. To tackle this problem, we propose a novel hand Gesture Generative Adversarial Network (GestureGAN). GestureGAN consists of a single generator $G$ and a discriminator $D$, which takes as input a conditional hand image and a target hand skeleton image. GestureGAN utilizes the hand skeleton information explicitly, and learns the gesture-to-gesture mapping through two novel losses, the color loss and the cycle-consistency loss. The proposed color loss handles the issue of "channel pollution" while back-propagating the gradients. In addition, we present the Fréchet ResNet Distance (FRD) to evaluate the quality of generated images. Extensive experiments on two widely used benchmark datasets demonstrate that the proposed GestureGAN achieves state-of-the-art performance on the unconstrained hand gesture-to-gesture translation task. Meanwhile, the generated images are in high-quality and are photo-realistic, allowing them to be used as data augmentation to improve the performance of a hand gesture classifier. Our model and code are available at https://github.com/Ha0Tang/GestureGAN.
Google Scholar, Web of Science, and Scopus: a systematic comparison of citations in 252 subject categories
Venue: arXiv cs.DL 2019
Year: 2019

Despite citation counts from Google Scholar (GS), Web of Science (WoS), and Scopus being widely consulted by researchers and sometimes used in research evaluations, there is no recent or systematic evidence about the differences between them. In response, this paper investigates 2,448,055 citations to 2,299 English-language highly-cited documents from 252 GS subject categories published in 2006, comparing GS, the WoS Core Collection, and Scopus. GS consistently found the largest percentage of citations across all areas (93%-96%), far ahead of Scopus (35%-77%) and WoS (27%-73%). GS found nearly all the WoS (95%) and Scopus (92%) citations. Most citations found only by GS were from non-journal sources (48%-65%), including theses, books, conference papers, and unpublished materials. Many were non-English (19%-38%), and they tended to be much less cited than citing sources that were also in Scopus or WoS. Despite the many unique GS citing sources, Spearman correlations between citation counts in GS and WoS or Scopus are high (0.78-0.99). They are lower in the Humanities, and lower between GS and WoS than between GS and Scopus. The results suggest that in all areas GS citation data is essentially a superset of WoS and Scopus, with substantial extra coverage.
A Framework for Automated Cellular Network Tuning with Reinforcement Learning
Venue: arXiv cs.NI 2019
Year: 2019

Tuning cellular network performance against always occurring wireless impairments can dramatically improve reliability to end users. In this paper, we formulate cellular network performance tuning as a reinforcement learning (RL) problem and provide a solution to improve the performance for indoor and outdoor environments. By leveraging the ability of Q-learning to estimate future performance improvement rewards, we propose two algorithms: (1) closed loop power control (PC) for downlink voice over LTE (VoLTE) and (2) self-organizing network (SON) fault management. The VoLTE PC algorithm uses RL to adjust the indoor base station transmit power so that the signal to interference plus noise ratio (SINR) of a user equipment (UE) meets the target SINR. It does so without the UE having to send power control requests. The SON fault management algorithm uses RL to improve the performance of an outdoor base station cluster by resolving faults in the network through configuration management. Both algorithms exploit measurements from the connected users, wireless impairments, and relevant configuration parameters to solve a non-convex performance optimization problem using RL. Simulation results show that our proposed RL based algorithms outperform the industry standards today in realistic cellular communication environments.
Cross-view image synthesis using geometry-guided conditional GANs
Venue: arXiv cs.CV 2019
Year: 2019

We address the problem of generating images across two drastically different views, namely ground (street) and aerial (overhead) views. Image synthesis by itself is a very challenging computer vision task and is even more so when generation is conditioned on an image in another view. Due the difference in viewpoints, there is small overlapping field of view and little common content between these two views. Here, we try to preserve the pixel information between the views so that the generated image is a realistic representation of cross view input image. For this, we propose to use homography as a guide to map the images between the views based on the common field of view to preserve the details in the input image. We then use generative adversarial networks to inpaint the missing regions in the transformed image and add realism to it. Our exhaustive evaluation and model comparison demonstrate that utilizing geometry constraints adds fine details to the generated images and can be a better approach for cross view image synthesis than purely pixel based synthesis methods.
Perfect $L_p$ Sampling in a Data Stream
Venue: arXiv cs.DS 2019
Year: 2019

In this paper, we resolve the one-pass space complexity of $L_p$ sampling for $p \in (0,2)$. Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector $f \in \mathbb{R}^n$, a perfect $L_p$ sampler must output an index $i$ with probability $|f_i|^p/\|f\|_p^p$, and is allowed to fail with some probability $δ$. So far, for $p > 0$ no algorithm has been shown to solve the problem exactly using $\text{poly}( \log n)$-bits of space. In 2010, Monemizadeh and Woodruff introduced an approximate $L_p$ sampler, which outputs $i$ with probability $(1 \pm ν)|f_i|^p /\|f\|_p^p$, using space polynomial in $ν^{-1}$ and $\log(n)$. The space complexity was later reduced by Jowhari, Sağlam, and Tardos to roughly $O(ν^{-p} \log^2 n \log δ^{-1})$ for $p \in (0,2)$, which tightly matches the $Ω(\log^2 n \log δ^{-1})$ lower bound in terms of $n$ and $δ$, but is loose in terms of $ν$. Given these nearly tight bounds, it is perhaps surprising that no lower bound exists in terms of $ν$---not even a bound of $Ω(ν^{-1})$ is known. In this paper, we explain this phenomenon by demonstrating the existence of an $O(\log^2 n \log δ^{-1})$-bit perfect $L_p$ sampler for $p \in (0,2)$. This shows that $ν$ need not factor into the space of an $L_p$ sampler, which closes the complexity of the problem for this range of $p$. For $p=2$, our bound is $O(\log^3 n \log δ^{-1})$-bits, which matches the prior best known upper bound in terms of $n,δ$, but has no dependence on $ν$. For $p<2$, our bound holds in the random oracle model, matching the lower bounds in that model. Moreover, we show that our algorithm can be derandomized with only a $O((\log \log n)^2)$ blow-up in the space (and no blow-up for $p=2$). Our derandomization technique is general, and can be used to derandomize a large class of linear sketches.
Wrangling Rogues: Managing Experimental Post-Moore Architectures
Venue: arXiv cs.AR 2019
Year: 2019

The Rogues Gallery is a new experimental testbed that is focused on tackling "rogue" architectures for the Post-Moore era of computing. While some of these devices have roots in the embedded and high-performance computing spaces, managing current and emerging technologies provides a challenge for system administration that are not always foreseen in traditional data center environments. We present an overview of the motivations and design of the initial Rogues Gallery testbed and cover some of the unique challenges that we have seen and foresee with upcoming hardware prototypes for future post-Moore research. Specifically, we cover the networking, identity management, scheduling of resources, and tools and sensor access aspects of the Rogues Gallery and techniques we have developed to manage these new platforms.
The Deconfounded Recommender: A Causal Inference Approach to Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

The goal of recommendation is to show users items that they will like. Though usually framed as a prediction, the spirit of recommendation is to answer an interventional question---for each user and movie, what would the rating be if we "forced" the user to watch the movie? To this end, we develop a causal approach to recommendation, one where watching a movie is a "treatment" and a user's rating is an "outcome." The problem is there may be unobserved confounders, variables that affect both which movies the users watch and how they rate them; unobserved confounders impede causal predictions with observational data. To solve this problem, we develop the deconfounded recommender, a way to use classical recommendation models for causal recommendation. Following Wang & Blei [23], the deconfounded recommender involves two probabilistic models. The first models which movies the users watch; it provides a substitute for the unobserved confounders. The second one models how each user rates each movie; it employs the substitute to help account for confounders. This two-stage approach removes bias due to confounding. It improves recommendation and enjoys stable performance against interventions on test sets.
The Influence of Down-Sampling Strategies on SVD Word Embedding Stability
Venue: arXiv cs.CL 2019
Year: 2019

The stability of word embedding algorithms, i.e., the consistency of the word representations they reveal when trained repeatedly on the same data set, has recently raised concerns. We here compare word embedding algorithms on three corpora of different sizes, and evaluate both their stability and accuracy. We find strong evidence that down-sampling strategies (used as part of their training procedures) are particularly influential for the stability of SVDPPMI-type embeddings. This finding seems to explain diverging reports on their stability and lead us to a simple modification which provides superior stability as well as accuracy on par with skip-gram embeddings.
Neural Architecture Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Automatic neural architecture design has shown its potential in discovering powerful neural network architectures. Existing methods, no matter based on reinforcement learning or evolutionary algorithms (EA), conduct architecture search in a discrete space, which is highly inefficient. In this paper, we propose a simple and efficient method to automatic neural architecture design based on continuous optimization. We call this new approach neural architecture optimization (NAO). There are three key components in our proposed approach: (1) An encoder embeds/maps neural network architectures into a continuous space. (2) A predictor takes the continuous representation of a network as input and predicts its accuracy. (3) A decoder maps a continuous representation of a network back to its architecture. The performance predictor and the encoder enable us to perform gradient based optimization in the continuous space to find the embedding of a new architecture with potentially better accuracy. Such a better embedding is then decoded to a network by the decoder. Experiments show that the architecture discovered by our method is very competitive for image classification task on CIFAR-10 and language modeling task on PTB, outperforming or on par with the best results of previous architecture search methods with a significantly reduction of computational resources. Specifically we obtain 1.93% test set error rate for CIFAR-10 image classification task and 56.0 test set perplexity of PTB language modeling task. Furthermore, combined with the recent proposed weight sharing mechanism, we discover powerful architecture on CIFAR-10 (with error rate 2.93%) and on PTB (with test set perplexity 56.6), with very limited computational resources (less than 10 GPU hours) for both tasks.
Everybody Dance Now
Venue: arXiv cs.GR 2019
Year: 2019

This paper presents a simple method for "do as I do" motion transfer: given a source video of a person dancing, we can transfer that performance to a novel (amateur) target after only a few minutes of the target subject performing standard moves. We approach this problem as video-to-video translation using pose as an intermediate representation. To transfer the motion, we extract poses from the source subject and apply the learned pose-to-appearance mapping to generate the target subject. We predict two consecutive frames for temporally coherent video results and introduce a separate pipeline for realistic face synthesis. Although our method is quite simple, it produces surprisingly compelling results (see video). This motivates us to also provide a forensics tool for reliable synthetic content detection, which is able to distinguish videos synthesized by our system from real data. In addition, we release a first-of-its-kind open-source dataset of videos that can be legally used for training and motion transfer.
Asymptotic Soft Filter Pruning for Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Deeper and wider Convolutional Neural Networks (CNNs) achieve superior performance but bring expensive computation cost. Accelerating such over-parameterized neural network has received increased attention. A typical pruning algorithm is a three-stage pipeline, i.e., training, pruning, and retraining. Prevailing approaches fix the pruned filters to zero during retraining, and thus significantly reduce the optimization space. Besides, they directly prune a large number of filters at first, which would cause unrecoverable information loss. To solve these problems, we propose an Asymptotic Soft Filter Pruning (ASFP) method to accelerate the inference procedure of the deep neural networks. First, we update the pruned filters during the retraining stage. As a result, the optimization space of the pruned model would not be reduced but be the same as that of the original model. In this way, the model has enough capacity to learn from the training data. Second, we prune the network asymptotically. We prune few filters at first and asymptotically prune more filters during the training procedure. With asymptotic pruning, the information of the training set would be gradually concentrated in the remaining filters, so the subsequent training and pruning process would be stable. Experiments show the effectiveness of our ASFP on image classification benchmarks. Notably, on ILSVRC-2012, our ASFP reduces more than 40% FLOPs on ResNet-50 with only 0.14% top-5 accuracy degradation, which is higher than the soft filter pruning (SFP) by 8%.
Cookie Clicker
Venue: arXiv cs.GT 2019
Year: 2019

Cookie Clicker is a popular online incremental game where the goal of the game is to generate as many cookies as possible. In the game you start with an initial cookie generation rate, and you can use cookies as currency to purchase various items that increase your cookie generation rate. In this paper, we analyze strategies for playing Cookie Clicker optimally. While simple to state, the game gives rise to interesting analysis involving ideas from NP-hardness, approximation algorithms, and dynamic programming.