OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Mini-batch SGD for Elastic Distributed Training: Learning in the Limbo of Resources
Venue: arXiv cs.LG 2019
Year: 2019

With an increasing demand for training powers for deep learning algorithms and the rapid growth of computation resources in data centers, it is desirable to dynamically schedule different distributed deep learning tasks to maximize resource utilization and reduce cost. In this process, different tasks may receive varying numbers of machines at different time, a setting we call elastic distributed training. Despite the recent successes in large mini-batch distributed training, these methods are rarely tested in elastic distributed training environments and suffer degraded performance in our experiments, when we adjust the learning rate linearly immediately with respect to the batch size. One difficulty we observe is that the noise in the stochastic momentum estimation is accumulated over time and will have delayed effects when the batch size changes. We therefore propose to smoothly adjust the learning rate over time to alleviate the influence of the noisy momentum estimation. Our experiments on image classification, object detection and semantic segmentation have demonstrated that our proposed Dynamic SGD method achieves stabilized performance when varying the number of GPUs from 8 to 128. We also provide theoretical understanding on the optimality of linear learning rate scheduling and the effects of stochastic momentum.
Authenticated Key-Value Stores with Hardware Enclaves
Venue: arXiv cs.CR 2019
Year: 2019

Authenticated data storage on an untrusted platform is an important computing paradigm for cloud applications ranging from big-data outsourcing, to cryptocurrency and certificate transparency log. These modern applications increasingly feature update-intensive workloads, whereas existing authenticated data structures (ADSs) designed with in-place updates are inefficient to handle such workloads. In this paper, we address this issue and propose a novel authenticated log-structured merge tree (eLSM) based key-value store by leveraging Intel SGX enclaves. We present a system design that runs the code of eLSM store inside enclave. To circumvent the limited enclave memory (128 MB with the latest Intel CPUs), we propose to place the memory buffer of the eLSM store outside the enclave and protect the buffer using a new authenticated data structure by digesting individual LSM-tree levels. We design protocols to support query authentication in data integrity, completeness (under range queries), and freshness. The proof in our protocol is made small by including only the Merkle proofs at selective levels. We implement eLSM on top of Google LevelDB and Facebook RocksDB with minimal code change and performance interference. We evaluate the performance of eLSM under the YCSB workload benchmark and show a performance advantage of up to 4.5X speedup.
A Novel Fuzzy Search Approach over Encrypted Data with Improved Accuracy and Efficiency
Venue: arXiv cs.CR 2019
Year: 2019

As cloud computing becomes prevalent in recent years, more and more enterprises and individuals outsource their data to cloud servers. To avoid privacy leaks, outsourced data usually is encrypted before being sent to cloud servers, which disables traditional search schemes for plain text. To meet both end of security and searchability, search-supported encryption is proposed. However, many previous schemes suffer severe vulnerability when typos and semantic diversity exist in query requests. To overcome such flaw, higher error-tolerance is always expected for search-supported encryption design, sometimes defined as 'fuzzy search'. In this paper, we propose a new scheme of multi-keyword fuzzy search over encrypted and outsourced data. Our approach introduces a new mechanism to map a natural language expression into a word-vector space. Compared with previous approaches, our design shows higher robustness when multiple kinds of typos are involved. Besides, our approach is enhanced with novel data structures to improve search efficiency. These two innovations can work well for both accuracy and efficiency. Moreover, these designs will not hurt the fundamental security. Experiments on a real-world dataset demonstrate the effectiveness of our proposed approach, which outperforms currently popular approaches focusing on similar tasks.
A Socio-Informatic Approach to Automated Account Classification on Social Media
Venue: arXiv cs.SI 2019
Year: 2019

Automated accounts on social media have become increasingly problematic. We propose a key feature in combination with existing methods to improve machine learning algorithms for bot detection. We successfully improve classification performance through including the proposed feature.
Asymptotic Analysis of RZF over Double Scattering Channels with MMSE Estimation
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies the ergodic rate performance of regularized zero-forcing (RZF) precoding in the downlink of a multi-user multiple-input single-output (MISO) system, where the channel between the base station (BS) and each user is modeled by the double scattering model. This non-Gaussian channel model is a function of both the antenna correlation and the structure of scattering in the propagation environment. This paper makes the preliminary contribution of deriving the minimum-mean-square-error (MMSE) channel estimate for this model. Then under the assumption that the users are divided into groups of common correlation matrices, this paper derives deterministic approximations of the signal-to-interference-plus-noise ratio (SINR) and the ergodic rate, which are almost surely tight in the limit that the number of BS antennas, the number of users and the number of scatterers in each group grow infinitely large. The derived results are expressed in a closed-form for the special case of multi-keyhole channels. Simulation results confirm the close match provided by the asymptotic analysis for moderate system dimensions. We show that the maximum number of users that can be supported simultaneously, while realizing large-scale MIMO gains, is equal to the number of scatterers.
A Practical Analysis of Rust's Concurrency Story
Venue: arXiv cs.DC 2019
Year: 2019

Correct concurrent programs are difficult to write; when multiple threads mutate shared data, they may lose writes, corrupt data, or produce erratic program behavior. While many of the data-race issues with concurrency can be avoided by the placing of locks throughout the code, these often serialize program execution, and can significantly slow down performance-critical applications. Programmers also make mistakes, and often forget locks in less-executed code paths, which leads to programs that misbehave only in rare situations. Rust is a recent programming language from Mozilla that attempts to solve these intertwined issues by detecting data-races at compile time. Rust's type system encodes a data-structure's ability to be shared between threads in the type system, which in turn allows the compiler to reject programs where threads directly mutate shared state without locks or other protection mechanisms. In this work, we examine how this aspect of Rust's type system impacts the development and refinement of a concurrent data structure, as well as its ability to adapt to situations where correctness is guaranteed by lower-level invariants (e.g., in lock-free algorithms) that are not directly expressible in the type system itself. We detail the implementation of a concurrent lock-free hashmap in order to describe these traits of the Rust language. Our code is publicly available at https://github.com/saligrama/concache and is one of the fastest concurrent hashmaps for the Rust language, which leads to mitigating bottlenecks in concurrent programs.
Analysis of reaction and timing attacks against cryptosystems based on sparse parity-check codes
Venue: arXiv cs.IT 2019
Year: 2019

In this paper we study reaction and timing attacks against cryptosystems based on sparse parity-check codes, which encompass low-density parity-check (LDPC) codes and moderate-density parity-check (MDPC) codes. We show that the feasibility of these attacks is not strictly associated to the quasi-cyclic (QC) structure of the code but is related to the intrinsically probabilistic decoding of any sparse parity-check code. So, these attacks not only work against QC codes, but can be generalized to broader classes of codes. We provide a novel algorithm that, in the case of a QC code, allows recovering a larger amount of information than that retrievable through existing attacks and we use this algorithm to characterize new side-channel information leakages. We devise a theoretical model for the decoder that describes and justifies our results. Numerical simulations are provided that confirm the effectiveness of our approach.
A computational model for analytic column stores
Venue: arXiv cs.DB 2019
Year: 2019

This work presents an abstract model for the computations performed by analytic column stores or columnar query processors. The model is based on circuits whose wires carry columns rather than scalar values, and whose nodes apply operators with column inputs and outputs. This model allows expression of most of the architectural features of existing column-store DBMSes through columnar execution plans, rather than such features being implemented sui-generis, and without the column store maintaining significant out-of-plan data. A strict adherence to columnarity allows for a relatively simple and robust model; enabling extensive and intensive optimization of almost all aspects of query processing; and also enabling massive uniform parallelization of query process on modern hardware. Moreover, the computational model's expressivity makes it useful also as an \emph{analytical} tool for considering design aspects and features of existing column stores, individually and comparatively. To achieve the model's wide expressiveness, much of this work develops representation schemes of relevant data structures as combinations of plain columns, with columnar circuits used as scheme encoders and decoders. A particular focus is given to schemes which also compress the data, and their use in query execution --- as an integral part of the computation: Subcircuits of larger columnar circuits, not black boxes. Decoder and encoder circuits are thus also composed to form more elaborate schemes. Such formulation allows both for an alternative view of well-known compression schemes, and for the development of new columnar compression schemes with useful features; these should be of independent interest irrespective of column store systems.
A process algebraic form to represent extensive games
Venue: arXiv cs.GT 2019
Year: 2019

In this paper, we introduce an agent-based representation of games, in order to propose a compact representation for multi-party games in game theory. Our method is inspired by concepts in process theory and process algebra. In addition, we introduce an algorithm whose input is a game in the form of process algebra (proposed in this paper) and as an output, finds the Nash equilibrium of the game in linear space complexity.
Analysis of Confident-Classifiers for Out-of-distribution Detection
Venue: arXiv cs.LG 2019
Year: 2019

Discriminatively trained neural classifiers can be trusted, only when the input data comes from the training distribution (in-distribution). Therefore, detecting out-of-distribution (OOD) samples is very important to avoid classification errors. In the context of OOD detection for image classification, one of the recent approaches proposes training a classifier called "confident-classifier" by minimizing the standard cross-entropy loss on in-distribution samples and minimizing the KL divergence between the predictive distribution of OOD samples in the low-density regions of in-distribution and the uniform distribution (maximizing the entropy of the outputs). Thus, the samples could be detected as OOD if they have low confidence or high entropy. In this paper, we analyze this setting both theoretically and experimentally. We conclude that the resulting confident-classifier still yields arbitrarily high confidence for OOD samples far away from the in-distribution. We instead suggest training a classifier by adding an explicit "reject" class for OOD samples.
The Ideal Versus the Real: Revisiting the History of Virtual Machines and Containers
Venue: arXiv cs.NI 2019
Year: 2019

The common perception in both academic literature and the industry today is that virtual machines offer better security, while containers offer better performance. However, a detailed review of the history of these technologies and the current threats they face reveals a different story. This survey covers key developments in the evolution of virtual machines and containers from the 1950s to today, with an emphasis on countering modern misperceptions with accurate historical details and providing a solid foundation for ongoing research into the future of secure isolation for multitenant infrastructures, such as cloud and container deployments.
Differentiable Visual Computing
Venue: arXiv cs.GR 2019
Year: 2019

Derivatives of computer graphics, image processing, and deep learning algorithms have tremendous use in guiding parameter space searches, or solving inverse problems. As the algorithms become more sophisticated, we no longer only need to differentiate simple mathematical functions, but have to deal with general programs which encode complex transformations of data. This dissertation introduces three tools for addressing the challenges that arise when obtaining and applying the derivatives for complex graphics algorithms. Traditionally, practitioners have been constrained to composing programs with a limited set of operators, or hand-deriving derivatives. We extend the image processing language Halide with reverse-mode automatic differentiation, and the ability to automatically optimize the gradient computations. This enables automatic generation of the gradients of arbitrary Halide programs, at high performance, with little programmer effort. In 3D rendering, the gradient is required with respect to variables such as camera parameters, geometry, and appearance. However, computing the gradient is challenging because the rendering integral includes visibility terms that are not differentiable. We introduce, to our knowledge, the first general-purpose differentiable ray tracer that solves the full rendering equation, while correctly taking the geometric discontinuities into account. Finally, we demonstrate that the derivatives of light path throughput can also be useful for guiding sampling in forward rendering. Simulating light transport in the presence of multi-bounce glossy effects and motion in 3D rendering is challenging due to the hard-to-sample high-contribution areas. We present a Markov Chain Monte Carlo rendering algorithm that extends Metropolis Light Transport by automatically and explicitly adapting to the local integrand, thereby increasing sampling efficiency.
E-Gotsky: Sequencing Content using the Zone of Proximal Development
Venue: arXiv cs.HC 2019
Year: 2019

Vygotsky's notions of Zone of Proximal Development and Dynamic Assessment emphasize the importance of personalized learning that adapts to the needs and abilities of the learners and enables more efficient learning. In this work we introduce a novel adaptive learning engine called E-gostky that builds on these concepts to personalize the learning path within an e-learning system. E-gostky uses machine learning techniques to select the next content item that will challenge the student but will not be overwhelming, keeping students in their Zone of Proximal Development. To evaluate the system, we conducted an experiment where hundreds of students from several different elementary schools used our engine to learn fractions for five months. Our results show that using E-gostky can significantly reduce the time required to reach similar mastery. Specifically, in our experiment, it took students who were using the adaptive learning engine $17\%$ less time to reach a similar level of mastery as of those who didn't. Moreover, students made greater efforts to find the correct answer rather than guessing and class teachers reported that even students with learning disabilities showed higher engagement.
Requirements variability specification for data intensive software
Venue: arXiv cs.SE 2019
Year: 2019

Nowadays, the use of feature modeling technique, in software requirements specification, increased the variation support in Data Intensive Software Product Lines (DISPLs) requirements modeling. It is considered the easiest and the most efficient way to express commonalities and variability among different products requirements. Several recent works, in DISPLs requirements, handled data variability by different models which are far from real world concepts. This,leaded to difficulties in analyzing, designing, implementing, and maintaining this variability. However, this work proposes a software requirements specification methodology based on concepts more close to the nature and which are inspired from genetics. This bio-inspiration has carried out important results in DISPLs requirements variability specification with feature modeling, which were not approached by the conventional approaches.The feature model was enriched with features and relations, facilitating the requirements variation management, not yet considered in the current relevant works.The use of genetics-based methodology seems to be promising in data intensive software requirements variability specification.
Compact Fenwick trees for dynamic ranking and selection
Venue: arXiv cs.DS 2019
Year: 2019

The Fenwick tree is a classical implicit data structure that stores an array in such a way that modifying an element, accessing an element, computing a prefix sum and performing a predecessor search on prefix sums all take logarithmic time. We introduce a number of variants which improve the classical implementation of the tree: in particular, we can reduce its size when an upper bound on the array element is known, and we can perform much faster predecessor searches. Our aim is to use our variants to implement an efficient dynamic bit vector: our structure is able to perform updates, ranking and selection in logarithmic time, with a space overhead in the order of a few percents, outperforming existing data structures with the same purpose. Along the way, we highlight the pernicious interplay between the arithmetic behind the Fenwick tree and the structure of current CPU caches, suggesting simple solutions that improve performance significantly.
Dynamic Environment Prediction in Urban Scenes using Recurrent Representation Learning
Venue: arXiv cs.CV 2019
Year: 2019

A key challenge for autonomous driving is safe trajectory planning in cluttered, urban environments with dynamic obstacles, such as pedestrians, bicyclists, and other vehicles. A reliable prediction of the future environment, including the behavior of dynamic agents, would allow planning algorithms to proactively generate a trajectory in response to a rapidly changing environment. We present a novel framework that predicts the future occupancy state of the local environment surrounding an autonomous agent by learning a motion model from occupancy grid data using a neural network. We take advantage of the temporal structure of the grid data by utilizing a convolutional long-short term memory network in the form of the PredNet architecture. This method is validated on the KITTI dataset and demonstrates higher accuracy and better predictive power than baseline methods.
Adversarial Speaker Verification
Venue: arXiv cs.SD 2019
Year: 2019

The use of deep networks to extract embeddings for speaker recognition has proven successfully. However, such embeddings are susceptible to performance degradation due to the mismatches among the training, enrollment, and test conditions. In this work, we propose an adversarial speaker verification (ASV) scheme to learn the condition-invariant deep embedding via adversarial multi-task training. In ASV, a speaker classification network and a condition identification network are jointly optimized to minimize the speaker classification loss and simultaneously mini-maximize the condition loss. The target labels of the condition network can be categorical (environment types) and continuous (SNR values). We further propose multi-factorial ASV to simultaneously suppress multiple factors that constitute the condition variability. Evaluated on a Microsoft Cortana text-dependent speaker verification task, the ASV achieves 8.8% and 14.5% relative improvements in equal error rates (EER) for known and unknown conditions, respectively.
New Quantum MDS Codes over Finite Fields
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we present three new classes of $q$-ary quantum MDS codes utilizing generalized Reed-Solomon codes satisfying Hermitian self-orthogonal property. Among our constructions, the minimum distance of some $q$-ary quantum MDS codes can be bigger than $\frac{q}{2}+1$. Comparing to previous known constructions, the lengths of codes in our constructions are more flexible.
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
Venue: arXiv cs.FL 2019
Year: 2019

Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out that in practice they operate very slowly. On the other side there is the Zielonka's recursive algorithm, which is very simple, exponential in the worst case, and the fastest in practice. We combine these two approaches: we propose a small modification of the Zielonka's algorithm, which ensures that the running time is at most quasi-polynomial. In effect, we obtain a simple algorithm that solves parity games in quasi-polynomial time. We also hope that our algorithm, after further optimizations, can lead to an algorithm that shares the good performance of the Zielonka's algorithm on typical inputs, while reducing the worst-case complexity on difficult inputs.
Asymmetric Impurity Functions, Class Weighting, and Optimal Splits for Binary Classification Trees
Venue: arXiv cs.LG 2019
Year: 2019

We investigate how asymmetrizing an impurity function affects the choice of optimal node splits when growing a decision tree for binary classification. In particular, we relax the usual axioms of an impurity function and show how skewing an impurity function biases the optimal splits to isolate points of a particular class when splitting a node. We give a rigorous definition of this notion, then give a necessary and sufficient condition for such a bias to hold. We also show that the technique of class weighting is equivalent to applying a specific transformation to the impurity function, and tie all these notions together for a class of impurity functions that includes the entropy and Gini impurity. We also briefly discuss cost-insensitive impurity functions and give a characterization of such functions.