Evaluating a new ranking policy using data logged by a previously deployed policy requires a counterfactual (off-policy) estimator that corrects for presentation and selection biases. Some estimators (e.g., the position-based model) perform this correction by making strong assumptions about user behavior, which can lead to high bias if the assumptions are not met. Other estimators (e.g., the item-position model) rely on randomization to avoid these assumptions, but they often suffer from high variance. In this paper, we develop a new counterfactual estimator, called Interpol, that provides a tunable trade-off in the assumptions it makes, thus providing a novel ability to optimize the bias-variance trade-off. We analyze the bias of our estimator, both theoretically and empirically, and show that it achieves lower error than both the position-based model and the item-position model, on both synthetic and real datasets. This improvement in accuracy not only benefits offline evaluation of ranking policies, we also find that Interpol improves learning of new ranking policies when used as the training objective for learning-to-rank.

Personalization is a crucial aspect of many online experiences. In particular, content ranking is often a key component in delivering sophisticated personalization results. Commonly, supervised learning-to-rank methods are applied, which suffer from bias introduced during data collection by production systems in charge of producing the ranking. To compensate for this problem, we leverage contextual multi-armed bandits. We propose novel extensions of two well-known algorithms viz. LinUCB and Linear Thompson Sampling to the ranking use-case. To account for the biases in a production environment, we employ the position-based click model. Finally, we show the validity of the proposed algorithms by conducting extensive offline experiments on synthetic datasets as well as customer facing online A/B experiments.

We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing table of the current node. For any fixed eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons.

Let C1,…, Cd+i be d + 1 point sets in ℝd, each containing the origin in its convex hull. A subset C of is called a colorful choice (or rainbow) for C1,…, Cd+1, if it contains exactly one point from each set Ci. The colorful Carathéodory theorem states that there always exists a colorful choice for C1,…, Cd+1 that has the origin in its convex hull. This theorem is very general and can be used to prove several other existence theorems in high-dimensional discrete geometry, such as the centerpoint theorem or Tverberg's theorem. The colorful Carathéodory problem (ColorfulCarathéodory) is the computational problem of finding such a colorful choice. Despite several efforts in the past, the computational complexity of ColorfulCarathéodory in arbitrary dimension is still open. We show that ColorfulCarathéodory lies in the intersection of the complexity classes PPAD and PLS. This makes it one of the few geometric problems in PPAD and PLS that are not known to be solvable in polynomial time. Moreover, it implies that the problem of computing centerpoints, computing Tverberg partitions, and computing points with large simplicial depth is contained in PPAD Π PLS. This is the first nontrivial upper bound on the complexity of these problems. Finally, we show that our PPAD formulation leads to a polynomial-time algorithm for a special case of ColorfulCarathéodory in which we have only two color classes C1 and C2 in d dimensions, each with the origin in its convex hull, and we would like to find a set with half the points from each color class that contains the origin in its convex hull.

Let P_1,...,P_{d+1} be d-dimensional point sets such that the convex hull of each P_i contains the origin. We call the sets P_i color classes, and we think of the points in P_i as having color i. A colorful choice is a set with at most one point of each color. The colorful Caratheodory theorem guarantees the existence of a colorful choice whose convex hull contains the origin. So far, the computational complexity of finding such a colorful choice is unknown. We approach this problem from two directions. First, we consider approximation algorithms: an m-colorful choice is a set that contains at most m points from each color class. We show that for any fixed epsilon > 0, an (epsilon d)-colorful choice containing the origin in its convex hull can be found in polynomial time. This notion of approximation has not been studied before, and it is motivated through the applications of the colorful Caratheodory theorem in the literature. In the second part, we present a natural generalization of the colorful Caratheodory problem: in the Nearest Colorful Polytope problem (NCP), we are given d-dimensional point sets P_1,...,P_n that do not necessarily contain the origin in their convex hulls. The goal is to find a colorful choice whose convex hull minimizes the distance to the origin. We show that computing local optima for the NCP problem is PLS-complete, while computing a global optimum is NP-hard.

Let k ≥ 0 be an integer. In the approximate k-flat nearest neighbor (k-ANN) problem, we are given a set P ⊂ Rd of n points in d-dimensional space and a fixed approximation factor c > 1. Our goal is to preprocess P so that we can efficiently answer approximate k-flat nearest neighbor queries: given a k-flat F, find a point in P whose distance to F is within a factor c of the distance between F and the closest point in P. The case k = 0 corresponds to the well-studied approximate nearest neighbor problem, for which a plethora of results are known, both in low and high dimensions. The case k = 1 is called approximate line nearest neighbor. In this case, we are aware of only one provably efficient data structure, due to Andoni, Indyk, Krauthgamer, and Nguyen (AIKN) [2]. For k ≥ 2, we know of no previous results.