N-gram models remain a fundamental component of language modeling. In data-scarce regimes, they are a strong alternative to neural models. Even when not used as-is, recent work shows they can regularize neural models. Despite this success, the effectiveness of one of the best N-gram smoothing methods, the one suggested by Kneser and Ney (1995), is not fully understood. In the hopes of explaining this performance, we study it through the lens of competitive distribution estimation: the ability to perform as well as an oracle aware of further structure in the data. We first establish basic competitive properties of Kneser-Ney smoothing. We then investigate the nature of its backoff mechanism and show that it emerges from first principles, rather than being an assumption of the model. We do this by generalizing the Good-Turing estimator to the contextual setting. This exploration leads us to a powerful generalization of Kneser-Ney, which we conjecture to have even stronger competitive properties. Empirically, it significantly improves performance on language modeling, even matching feed-forward neural models. To show that the mechanisms at play are not restricted to language modeling, we demonstrate similar gains on the task of predicting attack types in the Global Terrorism Database.

Maximum selection under probabilistic queries \emph{(probabilistic maximization)} is a fundamental algorithmic problem arising in numerous theoretical and practical contexts. We derive the first query-optimal sequential algorithm for probabilistic-maximization. Departing from previous assumptions, the algorithm and performance guarantees apply even for infinitely many items, hence in particular do not require a-priori knowledge of the number of items. The algorithm has linear query complexity, and is optimal also in the streaming setting. To derive these results we consider a probabilistic setting where several candidates for a position are asked multiple questions with the goal of finding who has the highest probability of answering interview questions correctly. Previous work minimized the total number of questions asked by alternating back and forth between the best performing candidates, in a sense, inviting them to multiple interviews. We show that the same order-wise selection accuracy can be achieved by querying the candidates sequentially, never returning to a previously queried candidate. Hence one interview is enough!

With the eventual goal of better understanding learning rates of general continuous distributions, we derive the first essentially min-max optimal estimators and learning rates for several natural classes of parametric non-smooth continuous distributions under KL divergence. In particular, we show that unlike the folk theorem of 1/2n learning-rate increase per distribution parameter, non-smooth distribution exhibit a wide range of learning rates.

We present a comprehensive understanding of three important problems in PAC preference learning: maximum selection (maxing), ranking, and estimating all pairwise preference probabilities, in the adaptive setting. With just Weak Stochastic Transitivity, we show that maxing requires $\Omega(n^2)$ comparisons and with slightly more restrictive Medium Stochastic Transitivity, we present a linear complexity maxing algorithm. With Strong Stochastic Transitivity and Stochastic Triangle Inequality, we derive a ranking algorithm with optimal $\mathcal{O}(n\log n)$ complexity and an optimal algorithm that estimates all pairwise preference probabilities.

The problem of estimating an unknown discrete distribution from its samples is a fundamental tenet of statistical learning. Over the past decade, it attracted significant research effort and has been solved for a variety of divergence measures. Surprisingly, an equally important problem, estimating an unknown Markov chain from its samples, is still far from understood. We consider two problems related to the min-max risk (expected loss) of estimating an unknown k-state Markov chain from its n sequential samples: predicting the conditional distribution of the next sample with respect to the KL-divergence, and estimating the transition matrix with respect to a natural loss induced by KL or a more general f-divergence measure. For the first measure, we determine the min-max prediction risk to within a linear factor in the alphabet size, showing it is \Omega(k\log\log n/n) and O(k^2\log\log n/n). For the second, if the transition probabilities can be arbitrarily small, then only trivial uniform risk upper bounds can be derived. We therefore consider transition probabilities that are bounded away from zero, and resolve the problem for essentially all sufficiently smooth f-divergences, including KL-, L_2-, Chi-squared, Hellinger, and Alpha-divergences.

We consider $(\epsilon,\delta)$-PAC maximum-selection and ranking using pairwise comparisons for general probabilistic models whose comparison probabilities satisfy strong stochastic transitivity and stochastic triangle inequality. Modifying the popular knockout tournament, we propose a simple maximum-selection algorithm that uses $\mathcal{O}\left(\frac{n}{\epsilon^2} \left(1+\log \frac1{\delta}\right)\right)$ comparisons, optimal up to a constant factor. We then derive a general framework that uses noisy binary search to speed up many ranking algorithms, and combine it with merge sort to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac n{\epsilon^2}\log n(\log \log n)^3\right)$ comparisons for $\delta=\frac1n$, optimal up to a $(\log \log n)^3$ factor.

PAC maximum selection (maxing) and ranking of $n$ elements via random pairwise comparisons have diverse applications and have been studied under many models and assumptions. With just one simple natural assumption: strong stochastic transitivity, we show that maxing can be performed with linearly many comparisons yet ranking requires quadratically many. With no assumptions at all, we show that for the Borda-score metric, maximum selection can be performed with linearly many comparisons and ranking can be performed with $\mathcal{O}(n\log n)$ comparisons.

Categorical models are a natural fit for many problems. When learning the distribution of categories from samples, high-dimensionality may dilute the data. Minimax optimality is too pessimistic to remedy this issue. A serendipitously discovered estimator, absolute discounting, corrects empirical frequencies by subtracting a constant from observed categories, which it then redistributes among the unobserved. It outperforms classical estimators empirically, and has been used extensively in natural language modeling. In this paper, we rigorously explain the prowess of this estimator using less pessimistic notions. We show that (1) absolute discounting recovers classical minimax KL-risk rates, (2) it is \emph{adaptive} to an effective dimension rather than the true dimension, (3) it is strongly related to the Good-Turing estimator and inherits its \emph{competitive} properties. We use power-law distributions as the cornerstone of these results. We validate the theory via synthetic data and an application to the Global Terrorism Database.

Estimating the number of defective elements of a set has various biological applications including estimating the prevalence of a disease or disorder. Group testing has been shown to be more efficient than scrutinizing each element separately for defectiveness. In group testing, we query a subset of elements and the result of the query will be defective if the subset contains at least one defective element. We present an adaptive, randomized group-testing algorithm to estimate the number of defective elements with near-optimal number of queries. Our algorithm uses at most 2 log log d + O(1/δ2log 1/ε) queries and estimates the number of defective elements d up to a multiplicative factor of 1 ± δ, with error probability ≤ ε. Also, we show an information-theoretic lower bound (1 - ε) log log d - 1 on the necessary number of queries any adaptive algorithm makes to estimate the number of defective elements for constant δ.

A significant amount of multidisciplinary research has recently focused on the rate at which i.i.d. distributions can be estimated. In particular, it was shown that for these distributions, optimal estimation implies optimal compression, hence in a sense for i.i.d. distributions, estimation “trumps” compression. Progressing from idealized i.i.d. to more practical distributions, we define and study the rate at which Markov distributions can be estimated. We determine this rate up to a constant factor and show two perhaps surprising implications. First, while the compression redundancy of i.i.d. and Markov distributions have the same growth rate, their estimation losses have different growth rates. Second, while for i.i.d. distributions optimal estimation implies optimal compression, for Markov distributions this implication does not hold, yet we show that any optimal compression algorithm has a smaller cumulative estimation loss than that guaranteed for optimal estimators, hence in a sense, for Markov distributions, compression "trumps" estimation. We also construct an algorithm that is optimal for both estimation and compression. Finally, we consider the important subclass of Markov distributions where all transition probabilities are bounded away from zero. For this subclass we determine the best estimation rate to the right constant factor and show that unlike i.i.d. distributions, for Markov distributions, the estimation rate of the full simplex and its interior differ.

There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size k. We study two of the most important tests under the conditional-sampling model where each query specifies a subset S of the domain, and the response is a sample drawn from S according to the underlying distribution. For identity testing, which asks whether the underlying distribution equals a specific given distribution or ε-differs from it, we reduce the known time and sample complexities from \widetilde\mathcalO(ε^-4) to \widetilde\mathcalO(ε^-2), thereby matching the information theoretic lower bound. For closeness testing, which asks whether two distributions underlying observed data sets are equal or different, we reduce existing complexity from \widetilde\mathcalO(ε^-4 \log^5 k) to an even sub-logarithmic \widetilde\mathcalO(ε^-5 \log \log k) thus providing a better bound to an open problem in Bertinoro Workshop on Sublinear Algorithms (Fisher, 2014).

English words and the outputs of many other natural processes are well-known to follow a Zipf distribution. Yet this thoroughly-established property has never been shown to help compress or predict these important processes. We show that the expected redundancy of Zipf distributions of order α > 1 is roughly the 1/α power of the expected redundancy of unrestricted distributions. Hence for these orders, Zipf distributions can be better compressed and predicted than was previously known. Unlike the expected case, we show that worst-case redundancy is roughly the same for Zipf and for unrestricted distributions. Hence Zipf distributions have significantly different worst-case and expected redundancies, making them the first natural distribution class shown to have such a difference.

Over-the-top estimation of available bandwidth (AB) in a network path has been well studied for wired networks. The AB of a path denotes its slack capacity, i.e., the bandwidth available for use in the path without impacting the existing traffic. This estimation problem has been receiving attention only recently in cellular networks, which are increasingly becoming one of the main modes of access for a large number of applications. In this paper, we discuss the challenges posed by the problem, and why existing techniques developed for wired networks cannot be applied. We show that, interestingly, it may not even be feasible to estimate AB using over-the-top approaches under certain conditions, even when the wireless channel and traffic conditions are non-varying. We then present a novel AB estimation technique for cellular networks, which typically use proportional fair scheduling at base stations. When the wireless channel and traffic conditions are non-varying, our technique can accurately determine AB when it exceeds the “fair share” due to a new flow. We also extend the basic technique for estimation under conditions that are time-varying. The proposed methods can as well be used when one or more bottleneck links in a network path are fair-scheduled using algorithms such as weighted-fair queueing. We evaluate our methods using simulations and over operational networks, and present the results. In simulations, our technique is capable of detecting AB close to 90% of the time under feasible conditions even with bursty traffic.

We conduct an extensive measurement study in an operational cellular network in dense urban settings and identify two key sources of inefficiencies in standard 3GPP handoff technique: wrong timing of handoff and sub-optimal base station association at a point. Based on our study, we propose a novel handoff technique that leverages (1) historical geo-tagged signal strength data from visible base stations at typical mobile user locations and (2) knowledge of the user trajectory. First, we formulate the handoff problem as a bi-criteria optimization problem and present a dynamic programming formulation that provides pareto-optimal solutions that maximize overall signal strength along user trajectory for a range of handoffs. Using an efficient utility based selection technique, we select a solution that balances the tradeoff between reducing number of handoffs and increasing the overall signal strength experienced by the user. Next, we present a much faster greedy heuristic that augments the solution obtained from the dynamic programming formulation when optimizing user performance in the presence of dynamic network load at each base station. A key contribution of our work is to show that striking a tradeoff between the two objectives is much harder in dense macro cellular base station deployments and an effective handoff technique should balance both these objectives well. We show that our technique takes a well balanced approach and achieves more than 25% reduction in the number of handoffs over the standard 3GPP handoff technique in an operational cellular network without incurring reduction in average signal strength, and even improving it by 1dB/sec in some cases. Finally, we propose a novel 3GPP standards compliant trajectory-aware location based handoff protocol and discuss the practical implementation aspects in cellular networks.

Even though wireless standards are promising ever-higher data rates with the advancement from 3G to Wimax, LTE and LTE-A, the practical data rates hit a limit because of inter-cell interference. Many techniques have been proposed for inter-cell interference mitigation, and they offer different tradeoffs in complexity, performance and channel estimation and inter-BS communication overheads. We focus on the class of joint precoding schemes which need Channel State Information (CSI) at the transmitter. For such schemes, we study how the choice of the size and shape of the co-operating cluster affects the performance of the system.