OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Training of Convolutional Neural Nets on Large Distributed Systems
Venue: arXiv cs.DC 2017
Year: 2017

Deep Neural Networks (DNNs) have achieved im- pressive accuracy in many application domains including im- age classification. Training of DNNs is an extremely compute- intensive process and is solved using variants of the stochastic gradient descent (SGD) algorithm. A lot of recent research has focussed on improving the performance of DNN training. In this paper, we present optimization techniques to improve the performance of the data parallel synchronous SGD algorithm using the Torch framework: (i) we maintain data in-memory to avoid file I/O overheads, (ii) we present a multi-color based MPI Allreduce algorithm to minimize communication overheads, and (iii) we propose optimizations to the Torch data parallel table framework that handles multi-threading. We evaluate the performance of our optimizations on a Power 8 Minsky cluster with 32 nodes and 128 NVidia Pascal P100 GPUs. With our optimizations, we are able to train 90 epochs of the ResNet-50 model on the Imagenet-1k dataset using 256 GPUs in just 48 minutes. This significantly improves on the previously best known performance of training 90 epochs of the ResNet-50 model on the same dataset using 256 GPUs in 65 minutes. To the best of our knowledge, this is the best known training performance demonstrated for the Imagenet- 1k dataset.
Crossing Behaviour of Social Groups: Insights from Observations at Non-signalized Intersection
Venue: arXiv cs.MA 2017
Year: 2017

Environmental, demographical and psychological factors have a demonstrated impact on risky crossing behaviour. In this work we focus on the potential influence of social factors on the considered phenomenon (i.e. group crossing decision). We present the results of a video-recorded observation about the crossing behaviour of singles and dyads at non-signalized intersections. Results showed that crossing behaviour is characterized by three distinct phases: (i) approaching, (ii) appraising (decision making) and (iii) crossing. Dyads walk slower than single pedestrians in all phases. The crossing behaviour of dyads is characterized by the emergence of a leader who takes the decision to cross first, followed by the companion. However, there is no difference between the accepted safety gap of singles and dyads. Understanding factors influencing the crossing decision of social groups represents an important result supporting the development of agent-based simulations of pedestrian-vehicle interactions.
REAP: An Efficient Incentive Mechanism for Reconciling Aggregation Accuracy and Individual Privacy in Crowdsensing
Venue: arXiv cs.GT 2017
Year: 2017

Incentive mechanism plays a critical role in privacy-aware crowdsensing. Most previous studies on co-design of incentive mechanism and privacy preservation assume a trustworthy fusion center (FC). Very recent work has taken steps to relax the assumption on trustworthy FC and allows participatory users (PUs) to add well calibrated noise to their raw sensing data before reporting them, whereas the focus is on the equilibrium behavior of data subjects with binary data. Making a paradigm shift, this paper aim to quantify the privacy compensation for continuous data sensing while allowing FC to directly control PUs. There are two conflicting objectives in such scenario: FC desires better quality data in order to achieve higher aggregation accuracy whereas PUs prefer adding larger noise for higher privacy-preserving levels (PPLs). To achieve a good balance therein, we design an efficient incentive mechanism to REconcile FC's Aggregation accuracy and individual PU's data Privacy (REAP). Specifically, we adopt the celebrated notion of differential privacy to measure PUs' PPLs and quantify their impacts on FC's aggregation accuracy. Then, appealing to Contract Theory, we design an incentive mechanism to maximize FC's aggregation accuracy under a given budget. The proposed incentive mechanism offers different contracts to PUs with different privacy preferences, by which FC can directly control PUs. It can further overcome the information asymmetry, i.e., the FC typically does not know each PU's precise privacy preference. We derive closed-form solutions for the optimal contracts in both complete information and incomplete information scenarios. Further, the results are generalized to the continuous case where PUs' privacy preferences take values in a continuous domain. Extensive simulations are provided to validate the feasibility and advantages of our proposed incentive mechanism.
An Optimal Choice Dictionary
Venue: arXiv cs.DS 2017
Year: 2017

A choice dictionary is a data structure that can be initialized with a parameter $n\in\{1,2,\ldots\}$ and subsequently maintains an initially empty subset $S$ of $\{1,\ldots,n\}$ under insertion, deletion, membership queries and an operation 'choice' that returns an arbitrary element of $S$. The choice dictionary is fundamental in space-efficient computing and has numerous applications. The best previous choice dictionary can be initialized with $n$ and a second parameter $t\in\{1,2,\ldots\}$ in constant time and subsequently executes all operations in $O(t)$ time and occupies $n+O(n({t/w})^t+\log n)$ bits on a word RAM with a word length of $w=Ω(\log n)$ bits. We describe a new choice dictionary that, following a constant-time initialization, executes all operations in constant time and, in addition to the space needed to store $n$, occupies only $n+1$ bits, which is shown to be optimal if $w=o(n)$. Allowed $\lceil\log_2(n+1)\rceil$ bits of additional space, the new data structure also supports iteration over the set $S$ in constant time per element.
Minor-free graphs have light spanners
Venue: arXiv cs.DS 2017
Year: 2017

We show that every $H$-minor-free graph has a light $(1+ε)$-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung. Our lightness bound is \[O\left(\frac{σ_H}{ε^3}\log \frac{1}ε\right)\] where $σ_H = |V(H)|\sqrt{\log |V(H)|}$ is the sparsity coefficient of $H$-minor-free graphs. That is, it has a practical dependency on the size of the minor $H$. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in $H$-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is $2^{O_H\left(\frac{1}{ε^4}\log \frac{1}ε\right)}n^{O(1)}$ where $O_H$ ignores dependencies on the size of $H$. Our techniques significantly deviate from existing lines of research on spanners for $H$-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs.
Using Deep Learning to Examine the Association between the Built Environment and Neighborhood Adult Obesity Prevalence
Venue: arXiv cs.CY 2017
Year: 2017

More than one-third of the adult population in the United States is obese. Obesity has been linked to factors such as, genetics, diet, physical activity and the environment. However, evidence indicating associations between the built environment and obesity has varied across studies and geographical contexts. Here, we used deep learning and approximately 150,000 high resolution satellite images to extract features of the built environment. We then developed linear regression models to consistently quantify the association between the extracted features and obesity prevalence at the census tract level for six cities in the United States. The extracted features of the built environment explained 72% to 90% of the variation in obesity prevalence across cities. Outof-sample predictions were considerably high with correlations greater than 80% between predicted and true obesity prevalence across all census tracts. This study supports a strong association between the built environment and obesity prevalence. Additionally, it also illustrates that features of the built environment extracted from satellite images can be useful for studying health indicators, such as obesity. Understanding the association between specific features of the built environment and obesity prevalence can lead to structural changes that could encourage physical activity and decreases in obesity prevalence.
Weight-Based Variable Ordering in the Context of High-Level Consistencies
Venue: arXiv cs.AI 2017
Year: 2017

Dom/wdeg is one of the best performing heuristics for dynamic variable ordering in backtrack search [Boussemart et al., 2004]. As originally defined, this heuristic increments the weight of the constraint that causes a domain wipeout (i.e., a dead-end) when enforcing arc consistency during search. "The process of weighting constraints with dom/wdeg is not defined when more than one constraint lead to a domain wipeout [Vion et al., 2011]." In this paper, we investigate how weights should be updated in the context of two high-level consistencies, namely, singleton (POAC) and relational consistencies (RNIC). We propose, analyze, and empirically evaluate several strategies for updating the weights. We statistically compare the proposed strategies and conclude with our recommendations.
Deep Reinforcement Learning for Resource Allocation in V2V Communications
Venue: arXiv cs.IT 2017
Year: 2017

In this article, we develop a decentralized resource allocation mechanism for vehicle-to-vehicle (V2V) communication systems based on deep reinforcement learning. Each V2V link is considered as an agent, making its own decisions to find optimal sub-band and power level for transmission. Since the proposed method is decentralized, the global information is not required for each agent to make its decisions, hence the transmission overhead is small. From the simulation results, each agent can learn how to satisfy the V2V constraints while minimizing the interference to vehicle-to-infrastructure (V2I) communications.
Cost-Efficient and Robust On-Demand Video Transcoding Using Heterogeneous Cloud Services
Venue: arXiv cs.DC 2017
Year: 2017

Video streams usually have to be transcoded to match the characteristics of viewers' devices. Streaming providers have to store numerous transcoded versions of a given video to serve various display devices. Given the fact that viewers' access pattern to video streams follows a long tail distribution, for the video streams with low access rate, we propose to transcode them in an on-demand manner using cloud computing services. The challenge in utilizing cloud services for on-demand video transcoding is to maintain a robust QoS for viewers and cost-efficiency for streaming service providers. To address this challenge, we present the Cloud-based Video Streaming Services (CVS2) architecture. It includes a QoS-aware scheduling that maps transcoding tasks to the VMs by considering the affinity of the transcoding tasks with the allocated heterogeneous VMs. To maintain robustness in the presence of varying streaming requests, the architecture includes a cost-efficient VM Provisioner. This component provides a self- configurable cluster of heterogeneous VMs. The cluster is reconfigured dynamically to maintain the maximum affinity with the arriving workload. Results obtained under diverse workload conditions demonstrate that CVS2 architecture can maintain a robust QoS for viewers while reducing the incurred cost of the streaming service provider up to 85%
Sparsity, variance and curvature in multi-armed bandits
Venue: arXiv cs.LG 2017
Year: 2017

In (online) learning theory the concepts of sparsity, variance and curvature are well-understood and are routinely used to obtain refined regret and generalization bounds. In this paper we further our understanding of these concepts in the more challenging limited feedback scenario. We consider the adversarial multi-armed bandit and linear bandit settings and solve several open problems pertaining to the existence of algorithms with favorable regret bounds under the following assumptions: (i) sparsity of the individual losses, (ii) small variation of the loss sequence, and (iii) curvature of the action set. Specifically we show that (i) for $s$-sparse losses one can obtain $\tilde{O}(\sqrt{s T})$-regret (solving an open problem by Kwon and Perchet), (ii) for loss sequences with variation bounded by $Q$ one can obtain $\tilde{O}(\sqrt{Q})$-regret (solving an open problem by Kale and Hazan), and (iii) for linear bandit on an $\ell_p^n$ ball one can obtain $\tilde{O}(\sqrt{n T})$-regret for $p \in [1,2]$ and one has $\tildeΩ(n \sqrt{T})$-regret for $p>2$ (solving an open problem by Bubeck, Cesa-Bianchi and Kakade). A key new insight to obtain these results is to use regularizers satisfying more refined conditions than general self-concordance
Compressing Word Embeddings via Deep Compositional Code Learning
Venue: arXiv cs.CL 2017
Year: 2017

Natural language processing (NLP) models often require a massive number of parameters for word embeddings, resulting in a large storage or memory footprint. Deploying neural NLP models to mobile devices requires compressing the word embeddings without any significant sacrifices in performance. For this purpose, we propose to construct the embeddings with few basis vectors. For each word, the composition of basis vectors is determined by a hash code. To maximize the compression rate, we adopt the multi-codebook quantization approach instead of binary coding scheme. Each code is composed of multiple discrete numbers, such as (3, 2, 1, 8), where the value of each component is limited to a fixed range. We propose to directly learn the discrete codes in an end-to-end neural network by applying the Gumbel-softmax trick. Experiments show the compression rate achieves 98% in a sentiment analysis task and 94% ~ 99% in machine translation tasks without performance loss. In both tasks, the proposed method can improve the model performance by slightly lowering the compression rate. Compared to other approaches such as character-level segmentation, the proposed method is language-independent and does not require modifications to the network architecture.
k-server via multiscale entropic regularization
Venue: arXiv cs.DS 2017
Year: 2017

We present an $O((\log k)^2)$-competitive randomized algorithm for the $k$-server problem on hierarchically separated trees (HSTs). This is the first $o(k)$-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy. When combined with Bartal's static HST embedding reduction, this leads to an $O((\log k)^2 \log n)$-competitive algorithm on any $n$-point metric space. We give a new dynamic HST embedding that yields an $O((\log k)^3 \log Δ)$-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most $Δ$.
Spintronics based Stochastic Computing for Efficient Bayesian Inference System
Venue: arXiv cs.ET 2017
Year: 2017

Bayesian inference is an effective approach for solving statistical learning problems especially with uncertainty and incompleteness. However, inference efficiencies are physically limited by the bottlenecks of conventional computing platforms. In this paper, an emerging Bayesian inference system is proposed by exploiting spintronics based stochastic computing. A stochastic bitstream generator is realized as the kernel components by leveraging the inherent randomness of spintronics devices. The proposed system is evaluated by typical applications of data fusion and Bayesian belief networks. Simulation results indicate that the proposed approach could achieve significant improvement on inference efficiencies in terms of power consumption and inference speed.
Two Error Bounds of Imperfect Binary Search
Venue: arXiv cs.DS 2017
Year: 2017

Suppose we know that an object is in a sorted table and we want to determine the index of that object. To achieve this goal we could perform a binary search. However, suppose it is time-consuming to determine the relative position of that object to any other objects in the table. In this scenario, we might want to resort to an incomplete solution: we could device an algorithm that quickly predicts the result of comparing two objects, and replace the actual comparison with this algorithm during a binary search. The question then is how far away are the results yielded by the imperfect binary search from the correct answers. We present two quick lemmas that answer this question.
Uplink Performance Analysis of a Drone Cell in a Random Field of Ground Interferers
Venue: arXiv cs.NI 2017
Year: 2017

Aerial base stations are a promising technology to increase the capabilities of the existing communication networks. However, the existing analytical frameworks do not sufficiently characterize the impact of ground interferers on the aerial base stations. In order to address this issue, we model the effect of interference coming from the coexisting ground networks on the aerial link, which could be the uplink of an aerial cell served by a drone base station. By considering a Poisson field of ground interferers, we characterize the aggregate interference experienced by the drone. This result includes the effect of the drone antenna pattern, the height-dependent shadowing, and various types of environment. We show that the benefits that a drone obtains from a better line-of-sight (LoS) at high altitudes is counteracted by a high vulnerability to the interference coming from the ground. However, by deriving the link coverage probability and transmission rate we show that a drone base station is still a promising technology if the overall system is properly dimensioned according to the given density and transmission power of the interferers. Particularly, our results illustrate how the benefits of such network is maximized by defining the optimal drone altitude and signal-to- interference (SIR) requirement.
On constant multi-commodity flow-cut gaps for directed minor-free graphs
Venue: arXiv cs.DS 2017
Year: 2017

The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide \& conquer algorithms, and has been extensively studied for various classes of undirected graphs. It has been shown by Linial, London and Rabinovich \cite{linial1994geometry} and by Aumann and Rabani \cite{aumann1998log} that for general $n$-vertex graphs it is bounded by $O(\log n)$ and the Gupta-Newman-Rabinovich-Sinclair conjecture \cite{gupta2004cuts} asserts that it is $O(1)$ for any family of graphs that excludes some fixed minor. The flow-cut gap is poorly understood for the case of directed graphs. We show that for uniform demands it is $O(1)$ on directed series-parallel graphs, and on directed graphs of bounded pathwidth. These are the first constant upper bounds of this type for some non-trivial family of directed graphs. We also obtain $O(1)$ upper bounds for the general multi-commodity flow-cut gap on directed trees and cycles. These bounds are obtained via new embeddings and Lipschitz quasipartitions for quasimetric spaces, which generalize analogous results form the metric case, and could be of independent interest. Finally, we discuss limitations of methods that were developed for undirected graphs, such as random partitions, and random embeddings.
Joint Power Allocation and Beamforming for Non-Orthogonal Multiple Access (NOMA) in 5G Millimeter-Wave Communications
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we explore non-orthogonal multiple access (NOMA) in millimeter-wave (mmWave) communications (mmWave-NOMA). In particular, we consider a typical problem, i.e., maximization of the sum rate of a 2-user mmWave-NOMA system. In this problem, we need to find the beamforming vector to steer towards the two users simultaneously subject to an analog beamforming structure, while allocating appropriate power to them. As the problem is non-convex and may not be converted to a convex problem with simple manipulations, we propose a suboptimal solution to this problem. The basic idea is to decompose the original joint beamforming and power allocation problem into two sub-problems which are relatively easy to solve: one is a power and beam gain allocation problem, and the other is a beamforming problem under a constant-modulus constraint. Extension of the proposed solution from 2-user mmWave-NOMA to more-user mmWave-NOMA is also discussed. Extensive performance evaluations are conducted to verify the rational of the proposed solution, and the results also show that the proposed sub-optimal solution achieve close-to-bound sum-rate performance, which is significantly better than that of time-division multiple access (TDMA).
Game theoretic path selection to support security in device-to-device communications
Venue: arXiv cs.GT 2017
Year: 2017

Device-to-Device (D2D) communication is expected to be a key feature supported by 5G networks, especially due to the proliferation of Mobile Edge Computing (MEC), which has a prominent role in reducing network stress by shifting computational tasks from the Internet to the mobile edge. Apart from being part of MEC, D2D can extend cellular coverage allowing users to communicate directly when telecommunication infrastructure is highly congested or absent. This significant departure from the typical cellular paradigm imposes the need for decentralised network routing protocols. Moreover, enhanced capabilities of mobile devices and D2D networking will likely result in proliferation of new malware types and epidemics. Although the literature is rich in terms of D2D routing protocols that enhance quality-of-service and energy consumption, they provide only basic security support, e.g., in the form of encryption. Routing decisions can, however, contribute to collaborative detection of mobile malware by leveraging different kinds of anti-malware software installed on mobile devices. Benefiting from the cooperative nature of D2D communications, devices can rely on each other's contributions to detect malware. The impact of our work is geared towards having more malware-free D2D networks. To achieve this, we designed and implemented a novel routing protocol for D2D communications that optimises routing decisions for explicitly improving malware detection. The protocol identifies optimal network paths, in terms of malware mitigation and energy spent for malware detection, based on a game theoretic model. Diverse capabilities of network devices running different types of anti-malware software and their potential for inspecting messages relayed towards an intended destination device are leveraged using game theoretic tools. An optimality analysis of both Nash and Stackelberg security games is undertaken, including both zero and non-zero sum variants, and the Defender's equilibrium strategies. By undertaking network simulations, theoretical results obtained are illustrated through randomly generated network scenarios showing how our protocol outperforms conventional routing protocols, in terms of expected payoff, which consists of: security damage in inflicted by malware and malware detection cost.
Learning Word Embeddings from Speech
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we propose a novel deep neural network architecture, Sequence-to-Sequence Audio2Vec, for unsupervised learning of fixed-length vector representations of audio segments excised from a speech corpus, where the vectors contain semantic information pertaining to the segments, and are close to other vectors in the embedding space if their corresponding segments are semantically similar. The design of the proposed model is based on the RNN Encoder-Decoder framework, and borrows the methodology of continuous skip-grams for training. The learned vector representations are evaluated on 13 widely used word similarity benchmarks, and achieved competitive results to that of GloVe. The biggest advantage of the proposed model is its capability of extracting semantic information of audio segments taken directly from raw speech, without relying on any other modalities such as text or images, which are challenging and expensive to collect and annotate.