OpenRaiser/Intern-Atlas huggingface dataset:
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
Venue: arXiv cs.LG 2017
Year: 2017

We describe a general technique that yields the first {\em Statistical Query lower bounds} for a range of fundamental high-dimensional learning problems involving Gaussian distributions. Our main results are for the problems of (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown Gaussian distribution. For each of these problems, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the computational complexity of {\em any} Statistical Query algorithm for the problem. Our SQ lower bound for Problem (1) is qualitatively matched by known learning algorithms for GMMs. Our lower bound for Problem (2) implies that the accuracy of the robust learning algorithm in~\cite{DiakonikolasKKLMS16} is essentially best possible among all polynomial-time SQ algorithms. Our SQ lower bounds are attained via a unified moment-matching technique that is useful in other contexts and may be of broader interest. Our technique yields nearly-tight lower bounds for a number of related unsupervised estimation problems. Specifically, for the problems of (3) robust covariance estimation in spectral norm, and (4) robust sparse mean estimation, we establish a quadratic {\em statistical--computational tradeoff} for SQ algorithms, matching known upper bounds. Finally, our technique can be used to obtain tight sample complexity lower bounds for high-dimensional {\em testing} problems. Specifically, for the classical problem of robustly {\em testing} an unknown mean (known covariance) Gaussian, our technique implies an information-theoretic sample lower bound that scales {\em linearly} in the dimension. Our sample lower bound matches the sample complexity of the corresponding robust {\em learning} problem and separates the sample complexity of robust testing from standard (non-robust) testing.
Improving Reliability of Word Similarity Evaluation by Redesigning Annotation Task and Performance Measure
Venue: arXiv cs.CL 2017
Year: 2017

We suggest a new method for creating and using gold-standard datasets for word similarity evaluation. Our goal is to improve the reliability of the evaluation, and we do this by redesigning the annotation task to achieve higher inter-rater agreement, and by defining a performance measure which takes the reliability of each annotation decision in the dataset into account.
Systematic Classification of Side-Channel Attacks: A Case Study for Mobile Devices
Venue: arXiv cs.CR 2017
Year: 2017

Side-channel attacks on mobile devices have gained increasing attention since their introduction in 2007. While traditional side-channel attacks, such as power analysis attacks and electromagnetic analysis attacks, required physical presence of the attacker as well as expensive equipment, an (unprivileged) application is all it takes to exploit the leaking information on modern mobile devices. Given the vast amount of sensitive information that are stored on smartphones, the ramifications of side-channel attacks affect both the security and privacy of users and their devices. In this paper, we propose a new categorization system for side-channel attacks, which is necessary as side-channel attacks have evolved significantly since their scientific investigations during the smart card era in the 1990s. Our proposed classification system allows to analyze side-channel attacks systematically, and facilitates the development of novel countermeasures. Besides this new categorization system, the extensive survey of existing attacks and attack strategies provides valuable insights into the evolving field of side-channel attacks, especially when focusing on mobile devices. We conclude by discussing open issues and challenges in this context and outline possible future research directions.
Designing Security-Aware Incentives for Computation Offloading via Device-to-Device Communication
Venue: arXiv cs.GT 2017
Year: 2017

Computation offloading via device-to-device (D2D) communication, or D2D offloading, has recently been proposed to enhance mobile computing performance by exploiting spare computing resources of nearby user devices. The success of D2D offloading relies on user participation in collaborative service provisioning, which incurs extra costs to users providing the service, thus mandating an incentive mechanism that can compensate for these costs. Although incentive mechanism design has been intensively studied in the literature, this paper considers a much more challenging yet less investigated problem in which selfish users are also facing interdependent security risks, such as infectious proximity-based attacks. Security cost is significantly different in nature from conventional service provisioning costs such as energy consumption, since security risks often depend on the collective behavior of all users. To this end, we build a novel mathematical framework by leveraging the combined power of game theory and epidemic theory to investigate the interplay between user incentives and interdependent security risks in D2D offloading, thereby enabling the design of security-aware incentive mechanisms. Our analysis discovers an interesting "less is more" phenomenon: although giving users more incentives promotes more participation, it may harm the network operator's utility. This is because too much participation may foster persistent security risks and as a result, the effective participation level does not improve. Our model and analysis shed new insights on the optimization of D2D offloading networks in the presence of interdependent security risks. Extensive simulations are carried out to verify our analytical conclusions.
The Optimal Placement Delivery Arrays
Venue: arXiv cs.IT 2017
Year: 2017

In wireless networks, coded caching is an effective technique to reduce network congestion during peak traffic times. Recently, a new concept called placement delivery array (PDA) was proposed to characterize the coded caching scheme. So far, only one class of PDAs by Maddah-Ali and Niesen is known to be optimal. In this paper, we mainly focus on constructing optimal PDAs. Firstly, we derive some lower bounds. Next, we present several infinite classes of PDAs, which are shown to be optimal with respect to the new bounds.
F-Score Driven Max Margin Neural Network for Named Entity Recognition in Chinese Social Media
Venue: arXiv cs.CL 2017
Year: 2017

We focus on named entity recognition (NER) for Chinese social media. With massive unlabeled text and quite limited labelled corpus, we propose a semi-supervised learning model based on B-LSTM neural network. To take advantage of traditional methods in NER such as CRF, we combine transition probability with deep learning in our model. To bridge the gap between label accuracy and F-score of NER, we construct a model which can be directly trained on F-score. When considering the instability of F-score driven method and meaningful information provided by label accuracy, we propose an integrated method to train on both F-score and label accuracy. Our integrated model yields 7.44\% improvement over previous state-of-the-art result.
Google's Multilingual Neural Machine Translation System: Enabling Zero-Shot Translation
Venue: arXiv cs.CL 2017
Year: 2017

We propose a simple solution to use a single Neural Machine Translation (NMT) model to translate between multiple languages. Our solution requires no change in the model architecture from our base system but instead introduces an artificial token at the beginning of the input sentence to specify the required target language. The rest of the model, which includes encoder, decoder and attention, remains unchanged and is shared across all languages. Using a shared wordpiece vocabulary, our approach enables Multilingual NMT using a single model without any increase in parameters, which is significantly simpler than previous proposals for Multilingual NMT. Our method often improves the translation quality of all involved language pairs, even while keeping the total number of model parameters constant. On the WMT'14 benchmarks, a single multilingual model achieves comparable performance for English$\rightarrow$French and surpasses state-of-the-art results for English$\rightarrow$German. Similarly, a single multilingual model surpasses state-of-the-art results for French$\rightarrow$English and German$\rightarrow$English on WMT'14 and WMT'15 benchmarks respectively. On production corpora, multilingual models of up to twelve language pairs allow for better translation of many individual pairs. In addition to improving the translation quality of language pairs that the model was trained with, our models can also learn to perform implicit bridging between language pairs never seen explicitly during training, showing that transfer learning and zero-shot translation is possible for neural translation. Finally, we show analyses that hints at a universal interlingua representation in our models and show some interesting examples when mixing languages.
Improved Handover Through Dual Connectivity in 5G mmWave Mobile Networks
Venue: arXiv cs.NI 2017
Year: 2017

The millimeter wave (mmWave) bands offer the possibility of orders of magnitude greater throughput for fifth generation (5G) cellular systems. However, since mmWave signals are highly susceptible to blockage, channel quality on any one mmWave link can be extremely intermittent. This paper implements a novel dual connectivity protocol that enables mobile user equipment (UE) devices to maintain physical layer connections to 4G and 5G cells simultaneously. A novel uplink control signaling system combined with a local coordinator enables rapid path switching in the event of failures on any one link. This paper provides the first comprehensive end-to-end evaluation of handover mechanisms in mmWave cellular systems. The simulation framework includes detailed measurement-based channel models to realistically capture spatial dynamics of blocking events, as well as the full details of MAC, RLC and transport protocols. Compared to conventional handover mechanisms, the study reveals significant benefits of the proposed method under several metrics.
Joint load balancing and interference mitigation in 5G HETNETS
Venue: arXiv cs.NI 2017
Year: 2017

We study the problem of joint load balancing and interference mitigation in heterogeneous networks (HetNets) in which massive multiple-input multiple-output (MIMO) macro cell base station (BS) equipped with a large number of antennas, overlaid with wireless self-backhauled small cells (SCs) are assumed. Self-backhauled SC BSs with full-duplex communication employing regular antenna arrays serve both macro users and SC users by using the wireless backhaul from macro BS in the same frequency band. We formulate the joint load balancing and interference mitigation problem as a network utility maximization subject to wireless backhaul constraints. Subsequently, leveraging the framework of stochastic optimization, the problem is decoupled into dynamic scheduling of macro cell users, backhaul provisioning of SCs, and offloading macro cell users to SCs as a function of interference and backhaul links. Via numerical results, we show the performance gains of our proposed framework under the impact of small cells density, number of base station antennas, and transmit power levels at low and high frequency bands. We further provide insights into the performance analysis and convergence of the proposed framework. The numerical results show that the proposed user association algorithm outperforms other baselines. Interestingly, we find that even at lower frequency band the performance of open access small cell is close to that of closed access at some operating points, the open access full- duplex small cell still yields higher gain as compared to the closed access at higher frequency bands. With increasing the small cell density or the wireless backhaul quality, the open access full- duplex small cells outperform and achieve a 5.6x gain in terms of cell-edge performance as compared to the closed access ones in ultra-dense networks with 350 small cell base stations per km2 .
Multi-Agent Motion Planning and Object Transportation under High Level Goals
Venue: arXiv cs.SY 2017
Year: 2017

This paper presents a hybrid control framework for the motion planning of a multi-agent system including N robotic agents and M objects, under high level goals. In particular, we design control protocols that allow the transition of the agents as well as the transportation of the objects by the agents, among predefined regions of interest in the workspace. This allows us to abstract the coupled behavior of the agents and the objects as a finite transition system and to design a high-level multi-agent plan that satisfies the agents' and the objects' specifications, given as temporal logic formulas. Simulation results verify the proposed framework.
Guidefill: GPU Accelerated, Artist Guided Geometric Inpainting for 3D Conversion
Venue: arXiv cs.CV 2017
Year: 2017

The conversion of traditional film into stereo 3D has become an important problem in the past decade. One of the main bottlenecks is a disocclusion step, which in commercial 3D conversion is usually done by teams of artists armed with a toolbox of inpainting algorithms. A current difficulty in this is that most available algorithms are either too slow for interactive use, or provide no intuitive means for users to tweak the output. In this paper we present a new fast inpainting algorithm based on transporting along automatically detected splines, which the user may edit. Our algorithm is implemented on the GPU and fills the inpainting domain in successive shells that adapt their shape on the fly. In order to allocate GPU resources as efficiently as possible, we propose a parallel algorithm to track the inpainting interface as it evolves, ensuring that no resources are wasted on pixels that are not currently being worked on. Theoretical analysis of the time and processor complexiy of our algorithm without and with tracking (as well as numerous numerical experiments) demonstrate the merits of the latter. Our transport mechanism is similar to the one used in coherence transport, but improves upon it by corrected a "kinking" phenomena whereby extrapolated isophotes may bend at the boundary of the inpainting domain. Theoretical results explaining this phenomena and its resolution are presented. Although our method ignores texture, in many cases this is not a problem due to the thin inpainting domains in 3D conversion. Experimental results show that our method can achieve a visual quality that is competitive with the state-of-the-art while maintaining interactive speeds and providing the user with an intuitive interface to tweak the results.
The ZipML Framework for Training Models with End-to-End Low Precision: The Cans, the Cannots, and a Little Bit of Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order of magnitude. We examine training at reduced precision, both from a theoretical and practical perspective, and ask: is it possible to train models at end-to-end low precision with provable guarantees? Can this lead to consistent order-of-magnitude speedups? We present a framework called ZipML to answer these questions. For linear models, the answer is yes. We develop a simple framework based on one simple but novel strategy called double sampling. Our framework is able to execute training at low precision with no bias, guaranteeing convergence, whereas naive quantization would introduce significant bias. We validate our framework across a range of applications, and show that it enables an FPGA prototype that is up to 6.5x faster than an implementation using full 32-bit precision. We further develop a variance-optimal stochastic quantization strategy and show that it can make a significant difference in a variety of settings. When applied to linear models together with double sampling, we save up to another 1.7x in data movement compared with uniform quantization. When training deep networks with quantized models, we achieve higher accuracy than the state-of-the-art XNOR-Net. Finally, we extend our framework through approximation to non-linear models, such as SVM. We show that, although using low-precision data induces bias, we can appropriately bound and control the bias. We find in practice 8-bit precision is often sufficient to converge to the correct solution. Interestingly, however, in practice we notice that our framework does not always outperform the naive rounding approach. We discuss this negative result in detail.
Probabilistic Rank and Matrix Rigidity
Venue: arXiv cs.CC 2017
Year: 2017

We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measures the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds, including: The Walsh-Hadamard Transform is Not Very Rigid. We give surprising upper bounds on the rigidity of a family of matrices whose rigidity has been extensively studied, and was conjectured to be highly rigid. For the $2^n \times 2^n$ Walsh-Hadamard transform $H_n$ (a.k.a. Sylvester matrices, or the communication matrix of Inner Product mod 2), we show how to modify only $2^{εn}$ entries in each row and make the rank drop below $2^{n(1-Ω(ε^2/\log(1/ε)))}$, for all $ε> 0$, over any field. That is, it is not possible to prove arithmetic circuit lower bounds on Hadamard matrices, via L. Valiant's matrix rigidity approach. We also show non-trivial rigidity upper bounds for $H_n$ with smaller target rank. Matrix Rigidity and Threshold Circuit Lower Bounds. We give new consequences of rigid matrices for Boolean circuit complexity. We show that explicit $n \times n$ Boolean matrices which maintain rank at least $2^{(\log n)^{1-δ}}$ after $n^2/2^{(\log n)^{δ/2}}$ modified entries would yield a function lacking sub-quadratic-size $AC^0$ circuits with two layers of arbitrary linear threshold gates. We also prove that explicit 0/1 matrices over $\mathbb{R}$ which are modestly more rigid than the best known rigidity lower bounds for sign-rank would imply strong lower bounds for the infamously difficult class $THR\circ THR$.
What Do Recurrent Neural Network Grammars Learn About Syntax?
Venue: arXiv cs.CL 2017
Year: 2017

Recurrent neural network grammars (RNNG) are a recently proposed probabilistic generative modeling family for natural language. They show state-of-the-art language modeling and parsing performance. We investigate what information they learn, from a linguistic perspective, through various ablations to the model and the data, and by augmenting the model with an attention mechanism (GA-RNNG) to enable closer inspection. We find that explicit modeling of composition is crucial for achieving the best performance. Through the attention mechanism, we find that headedness plays a central role in phrasal representation (with the model's latent attention largely agreeing with predictions made by hand-crafted head rules, albeit with some important differences). By training grammars without nonterminal labels, we find that phrasal representations depend minimally on nonterminals, providing support for the endocentricity hypothesis.
Lower bounds for 2-query LCCs over large alphabet
Venue: arXiv cs.CC 2017
Year: 2017

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates. We show that any {\em zero-error} $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to Σ^n$ that can correct a constant fraction of corrupted symbols must have $n \geq \exp(k/\log|Σ|)$. We say that an LCC is zero-error if there exists a non-adaptive corrector algorithm that succeeds with probability $1$ when the input is an uncorrupted codeword. All known constructions of LCCs are zero-error. Our result is tight upto constant factors in the exponent. The only previous lower bound on the length of 2-query LCCs over large alphabet was $Ω\left((k/\log|Σ|)^2\right)$ due to Katz and Trevisan (STOC 2000). Our bound implies that zero-error LCCs cannot yield $2$-server private information retrieval (PIR) schemes with sub-polynomial communication. Since there exists a $2$-server PIR scheme with sub-polynomial communication (STOC 2015) based on a zero-error $2$-query locally decodable code (LDC), we also obtain a separation between LDCs and LCCs over large alphabet. For our proof of the result, we need a new decomposition lemma for directed graphs that may be of independent interest. Given a dense directed graph $G$, our decomposition uses the directed version of Szemerédi regularity lemma due to Alon and Shapira (STOC 2003) to partition almost all of $G$ into a constant number of subgraphs which are either edge-expanding or empty.
Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
Venue: arXiv cs.LG 2017
Year: 2017

We look at the eigenvalues of the Hessian of a loss function before and after training. The eigenvalue distribution is seen to be composed of two parts, the bulk which is concentrated around zero, and the edges which are scattered away from zero. We present empirical evidence for the bulk indicating how over-parametrized the system is, and for the edges that depend on the input data.
Deep Convolutional Neural Networks with Merge-and-Run Mappings
Venue: arXiv cs.CV 2017
Year: 2017

A deep residual network, built by stacking a sequence of residual blocks, is easy to train, because identity mappings skip residual branches and thus improve information flow. To further reduce the training difficulty, we present a simple network architecture, deep merge-and-run neural networks. The novelty lies in a modularized building block, merge-and-run block, which assembles residual branches in parallel through a merge-and-run mapping: Average the inputs of these residual branches (Merge), and add the average to the output of each residual branch as the input of the subsequent residual branch (Run), respectively. We show that the merge-and-run mapping is a linear idempotent function in which the transformation matrix is idempotent, and thus improves information flow, making training easy. In comparison to residual networks, our networks enjoy compelling advantages: they contain much shorter paths, and the width, i.e., the number of channels, is increased. We evaluate the performance on the standard recognition tasks. Our approach demonstrates consistent improvements over ResNets with the comparable setup, and achieves competitive results (e.g., $3.57\%$ testing error on CIFAR-$10$, $19.00\%$ on CIFAR-$100$, $1.51\%$ on SVHN).