A well-known issue with Retrieval Augmented Generation (RAG) is that retrieved passages that are irrelevant to the query sometimes distract the answer-generating LLM, causing it to provide an incorrect response.In this paper, we shed light on this core issue and formulate the distracting effect of a passage w.r.t. a query (and an LLM).We provide a quantifiable measure of the distracting effect of a passage and demonstrate its robustness across LLMs.Our research introduces novel methods for identifying and using hard distracting passages to improve RAG systems.By fine-tuning LLMs with these carefully selected distracting passages, we achieve up to a 7.5% increase in answering accuracy compared to counterparts fine-tuned on conventional RAG datasets.Our contribution is two-fold: first, we move beyond the simple binary classification of irrelevant passages as either completely unrelated vs. distracting, and second, we develop and analyze multiple methods for finding hard distracting passages.To our knowledge, no other research has provided such a comprehensive framework for identifying and utilizing hard distracting passages.

Training large language models (LLMs) for external tool usage is a rapidly expanding field, with recent research focusing on generating synthetic data to address the shortage of available data.However, the absence of systematic data quality checks poses complications for properly training and testing models.To that end, we propose two approaches for assessing the reliability of data for training LLMs to use external tools.The first approach uses intuitive, human-defined correctness criteria.The second approach uses a model-driven assessment with in-context evaluation.We conduct a thorough evaluation of data quality on two popular benchmarks, followed by an extrinsic evaluation that showcases the impact of data quality on model performance.Our results demonstrate that models trained on high-quality data outperform those trained on unvalidated data, even when trained with a smaller quantity of data.These findings empirically support the significance of assessing and ensuring the reliability of training data for tool-using LLMs.

Being able to measure the success of online shopping interactions is crucial in order to evaluate and optimize the performance of e-commerce systems. It is especially challenging in the domain of voice shopping, typically supported by voice-based AI assistants. Unlike Web shopping, which offers a rich amount of behavioral signals such as clicks, in voice shopping a non-negligible amount of shopping interactions frequently ends without any immediate explicit or implicit user behavioral signal. Moreover, users may start their journey using a voice-enabled device, but complete it elsewhere, for example on their smartphone mobile app or a Web browser. We explore the challenge of measuring successful interactions in voice product search based on users’ behavior, and propose a medium-term reward metric named Extended ConVersion (ECVR). ECVR extends the notion of conversion beyond the usual purchase action, which serves as an undisputed measure of success in e-commerce. More specifically, it also captures purchase actions that occur at a later stage during a same shopping journey, and possibly on different channel than the one on which the interaction started. In this paper, we formally define the ECVR metric, describe multiple ways of evaluating the quality of a metric, and use these to explore different parameters for ECVR. After selecting the most appropriate parameters, we show that a ranking system optimized for ECVR, set up with these parameters, leads to improvements in long-term engagement and revenue, without compromising immediate conversion gains.

Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n . Given the sketch and a query item y , one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y . Most works to date focused on additive ε n error approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This article investigates multiplicative (1± ε)-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values. The most space-efficient algorithms due to prior work store either O(log (ε 2 n )/ε 2 ) or O (log 3 (ε n )/ε) universe items. We present a randomized sketch storing O (log 1.5 (ε n )/ε) items that can (1± ε)-approximate the rank of each universe item with high constant probability; this space bound is within an \(O(\sqrt {\log (\varepsilon n)})\) factor of optimal. Our algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments.

Transformer-based language models such as BERT (Devlin et al., 2018) have achieved the state-of-the-art performance on various NLP tasks, but are computationally prohibitive.A recent line of works use various heuristics to successively shorten sequence length while transforming tokens through encoders, in tasks such as classification and ranking that require a single token embedding for prediction.We present a novel solution to this problem, called Pyramid-BERT where we replace previously used heuristics with a coreset based token selection method justified by theoretical results.The core-set based token selection technique allows us to avoid expensive pre-training, gives a space-efficient fine tuning, and thus makes it suitable to handle longer sequence lengths.We provide extensive experiments establishing advantages of pyramid BERT over several baselines and existing works on the GLUE benchmarks and Long Range Arena (Tay et al., 2020) datasets.

With the increasing adoption of machine learning (ML) models and systems in high-stakes settings across different industries, guaranteeing a model's performance after deployment has become crucial. Monitoring models in production is a critical aspect of ensuring their continued performance and reliability. We present Amazon SageMaker Model Monitor, a fully managed service that continuously monitors the quality of machine learning models hosted on Amazon SageMaker. Our system automatically detects data, concept, bias, and feature attribution drift in models in real-time and provides alerts so that model owners can take corrective actions and thereby maintain high quality models. We describe the key requirements obtained from customers, system design and architecture, and methodology for detecting different types of drift. Further, we provide quantitative evaluations followed by use cases, insights, and lessons learned from more than two years of production deployment.

The paradigm of pre-training followed by finetuning has become a standard procedure for NLP tasks, with a known problem of domain shift between the pre-training and downstream corpus.Previous works have tried to mitigate this problem with additional pre-training, either on the downstream corpus itself when it is large enough, or on a manually curated unlabeled corpus of a similar domain.In this paper, we address the problem for the case when the downstream corpus is too small for additional pre-training.We propose TADPOLE, a task adapted pre-training framework based on data selection techniques adapted from Domain Adaptation.We formulate the data selection as an anomaly detection problem that unlike existing methods works well when the downstream corpus is limited in size.It results in a scalable and efficient unsupervised technique that eliminates the need for any manual data curation.We evaluate our framework on eight tasks across four different domains: Biomedical, Computer Science, News, and Movie reviews, and compare its performance against competitive baseline techniques from the area of Domain Adaptation.Our framework outperforms all the baseline methods.On small datasets with less than 5K training examples, we get a gain of 1.82% in performance with additional pre-training for only 5% steps.It also compliments some of the other techniques such as data augmentation known for boosting performance when downstream corpus is small; highest performance is achieved when data augmentation is combined with task adapted pre-training.

Attribution methods have been shown as promising approaches for identifying key features that led to learned model predictions. While most existing attribution methods rely on a baseline input for performing feature perturbations, limited research has been conducted to address the baseline selection issues. Poor choices of baselines limit the ability of one-vs-one explanations for multi-class classifiers, which means the attribution methods were not able to explain why an input belongs to its original class but not the other specified target class. Achieving one-vs-one explanation is crucial when certain classes are more similar than others, e.g. two bird types among multiple animals, by focusing on key differentiating features rather than shared features across classes. In this paper, we present GANMEX, a novel approach applying Generative Adversarial Networks (GAN) by incorporating the to-be-explained classifier as part of the adversarial networks. Our approach effectively selects the baseline as the closest realistic sample belong to the target class, which allows attribution methods to provide true one-vs-one explanations. We showed that GANMEX baselines improved the saliency maps and led to stronger performance on multiple evaluation metrics over the existing baselines. Existing attribution results are known for being insensitive to model randomization, and we demonstrated that GANMEX baselines led to better outcome under the cascading randomization of the model.

Approximating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe U equipped with a total order, the task is to compute a sketch (data structure) of size poly (log(n), 1/ε). Given the sketch and a query item y ∈ U, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y. Most works to date focused on additive ε n error approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This paper investigates multiplicative (1±ε)$-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values. The most space-efficient algorithms due to prior work store either O(log(ε2 n)/ε2) or O(log3(ε n)/ε) universe items. This paper presents a randomized algorithm storing O(log1.5 (ε n)/ε) items, which is within an O(√log(ε n)) factor of optimal. The algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments.

Transformers (Vaswani et al., 2017) have gradually become a key component for many state-of-the-art natural language representation models.A recent Transformer based model- BERT (Devlin et al., 2018) achieved state-of-the-art results on various natural language processing tasks, including GLUE, SQuAD v1.1, and SQuAD v2.0.This model however is computationally prohibitive and has a huge number of parameters.In this work we revisit the architecture choices of BERT in efforts to obtain a lighter model.We focus on reducing the number of parameters yet our methods can be applied towards other objectives such FLOPs or latency.We show that much efficient light BERT models can be obtained by reducing algorithmically chosen correct architecture design dimensions rather than reducing the number of Transformer encoder layers.In particular, our schuBERT gives 6.6% higher average accuracy on GLUE and SQuAD datasets as compared to BERT with three encoder layers while having the same number of parameters.

This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. Leveraging ideas from the theory of suprema of empirical processes, we provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. Unlike previous approaches which sample based on minimizing a worst-case variance (e.g. G-optimal design), we define an experimental design objective based on the Gaussian-width of the underlying arm set. We provide a novel lower bound in terms of this objective that highlights its fundamental role in the sample complexity. The sample complexity of our fixed confidence algorithm matches this lower bound, and in addition is computationally efficient for combinatorial classes, e.g. shortest-path, matchings and matroids, where the arm sets can be exponentially large in the dimension. Finally, we propose the first algorithm for linear bandits in the the fixed budget setting. Its guarantee matches our lower bound up to logarithmic factors.

There is a large body of research on scalable machine learning (ML). Nevertheless, training ML models on large, continuously evolving datasets is still a difficult and costly undertaking for many companies and institutions. We discuss such challenges and derive requirements for an industrial-scale ML platform. Next, we describe the computational model behind Amazon SageMaker, which is designed to meet such challenges. SageMaker is an ML platform provided as part of Amazon Web Services (AWS), and supports incremental training, resumable and elastic learning as well as automatic hyperparameter optimization. We detail how to adapt several popular ML algorithms to its computational model. Finally, we present an experimental evaluation on large datasets, comparing SageMaker to several scalable, JVM-based implementations of ML algorithms, which we significantly outperform with regard to computation time and cost.

This paper defines the notion of class discrepancy for families of functions. It shows that low discrepancy classes admit small offline and streaming coresets. We provide general techniques for bounding the class discrepancy of machine learning problems. As corollaries of the general technique we bound the discrepancy of logistic regression, sigmoid activation loss, matrix covariance, kernel density and any analytic function of the dot product or the squared distance. Our result resolves a long-standing open problem regarding the coreset complexity of Gaussian kernel density estimation. We provide two more related but independent results. First, an exponential improvement of the widely used merge-and-reduce trick which gives improved streaming sketches for any low discrepancy problem. Second, an extremely simple deterministic algorithm for finding low discrepancy sequences (and therefore coresets) for any positive semi-definite kernel. This paper establishes some explicit connections between class discrepancy, coreset complexity, learnability, and streaming algorithms.

We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.

Online sparse linear regression is an online problem where an algorithm repeatedly chooses a subset of coordinates to observe in an adversarially chosen feature vector, makes a real-valued prediction, receives the true label, and incurs the squared loss. The goal is to design an online learning algorithm with sublinear regret to the best sparse linear predictor in hindsight. Without any assumptions, this problem is known to be computationally intractable. In this paper, we make the assumption that data matrix satisfies restricted isometry property, and show that this assumption leads to computationally efficient algorithms with sublinear regret for two variants of the problem. In the first variant, the true label is generated according to a sparse linear model with additive Gaussian noise. In the second, the true label is chosen adversarially.

We study the multi-armed dueling bandit problem in which feedback is provided in the form of relative comparisons between pairs of actions, with the goal of eventually learning to select actions that are close to the best. Following Dudik et al. (2015), we aim for algorithms whose performance approaches that of the optimal randomized choice of actions, the von Neumann winner, expressly avoiding more restrictive assumptions, for instance, regarding the existence of a single best action (a Condorcet winner). In this general setting, the best known algorithms achieve regret O(\sqrtKT) in T rounds with K actions. In this paper, we present the first instance-dependent regret bounds for the general problem, focusing particularly on when the von Neumann winner is sparse. Specifically, we propose a new algorithm whose regret, relative to a unique von Neumann winner with sparsity s, is at most O(\sqrtsT), plus an instance-dependent constant. Thus, when the sparsity is much smaller than the total number of actions, our result indicates that learning can be substantially faster.

This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An ε approximate quantile sketch receives a stream of items x1,⋯,xn and allows one to approximate the rank of any query item up to additive error ε n with probability at least 1-δ.The rank of a query x is the number of stream items such that xi≤ x. The minimal sketch size required for this task is trivially at least 1/ε.Felber and Ostrovsky obtain a O((1/ε)log(1/ε)) space sketch for a fixed δ.Without restrictions on the nature of the stream or the ratio between ε and n, no better upper or lower bounds were known to date. This paper obtains an O((1/ε)log log (1/δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching for which an Ω((1/ε)log(1/ε)) lower bound is known. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This modification allows for an analysis which is both tight and extremely simple. The same technique was reported, in private communications, to be useful for improving other sketching objectives and geometric coreset constructions.

We consider the problem of finding the best arm in a stochastic Mutli-armed Bandit (MAB) game and propose a general framework based on verification that applies to multiple well-motivated generalizations of the classic MAB problem. In these generalizations, additional structure is known in advance, causing the task of verifying the optimality of a candidate to be easier than discovering the best arm. Our results are focused on the scenario where the failure probability $\delta$ must be very low; we essentially show that in this high confidence regime, identifying the best arm is as easy as the task of verification. We demonstrate the effectiveness of our framework by applying it, and improving the state-of-the art results in the problems of: Linear bandits, Dueling bandits with the Condorcet assumption, Copeland dueling bandits, Unimodal bandits and Graphical bandits.

We consider sequential decision making problem in the adversarial setting, where regret is measured with respect to the optimal sequence of actions and the feedback adheres the bandit setting. It is well-known that obtaining sublinear regret in this setting is impossible in general, which arises the question of when can we do better than linear regret? Previous works show that when the environment is guaranteed to vary slowly and furthermore we are given prior knowledge regarding its variation (i.e., a limit on the amount of changes suffered by the environment), then this task is feasible. The caveat however is that such prior knowledge is not likely to be available in practice, which causes the obtained regret bounds to be somewhat irrelevant. Our main result is a regret guarantee that scales with the variation parameter of the environment, without requiring any prior knowledge about it whatsoever. By that, we also resolve an open problem posted by [Gur, Zeevi and Besbes, NIPS' 14]. An important key component in our result is a statistical test for identifying non-stationarity in a sequence of independent random variables. This test either identifies non-stationarity or upper-bounds the absolute deviation of the corresponding sequence of mean values in terms of its total variation. This test is interesting on its own right and has the potential to be found useful in additional settings.

Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributed computing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the number of nodes or in their degrees. The result trivially applies for the dynamic distributed model, in which edges or nodes may be inserted or deleted. In this paper, we take a different approach which exploits locality to the extreme, and show how to update an MIS in a dynamic distributed setting, either synchronous or asynchronous, with only a single adjustment and in a single round, in expectation. These strong guarantees hold for the complete fully dynamic setting: Insertions and deletions, of edges as well as nodes, gracefully and abruptly. This strongly separates the static and dynamic distributed models, as super-constant lower bounds exist for computing an MIS in the former.

With email traffic increasing, leading Web mail services have started to offer features that assist users in reading and processing their inboxes. One approach is to identify "important" messages, while a complementary one is to bundle messages, especially machine-generated ones, in pre-defined categories. We rather propose here to go back to the task at hand and consider what actions the users might conduct on received messages. We thoroughly studied, in a privacy-preserving manner, the actions of a large number of users in Yahoo mail, and found out that the most frequent actions are typically read, reply, delete and a sub-type of delete, delete-without-read. We devised a learning framework for predicting these four actions, for users with various levels of activity per action. Our framework leverages both vertical learning for personalization and horizontal learning for regularization purposes. In order to verify the quality of our predictions, we conducted a large-scale experiment involving users who had previously agreed to participate in such research studies. Our results show that, for recall values of 90%, we can predict important actions such as read or reply at precision levels up to 40% for active users, which we consider pretty encouraging for an assistance task. For less active users, we show that our regularization achieves an increase in AUC of close to 50%. To the best of our knowledge, our work is the first to provide a unified framework of this scale for predicting multiple actions on Web email, which hopefully provides a new ground for inventing new user experiences to help users process their inboxes.

Numerous learning problems that contain exploration, such as experiment design, multi-arm bandits, online routing, search result aggregation and many more, have been studied extensively in isolation. In this paper we consider a generic and efficiently computable method for action space exploration based on convex geometry. We define a novel geometric notion of an exploration mechanism with low variance called volumetric spanners, and give efficient algorithms to construct such spanners. We describe applications of this mechanism to the problem of optimal experiment design and the general framework for decision making under uncertainty of bandit linear optimization. For the latter we give efficient and near-optimal regret algorithm over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self- concordant barrier for the underlying set.

A version of the dueling bandit problem is addressed in which a Condorcet winner may not exist. Two algorithms are proposed that instead seek to minimize regret with respect to the Copeland winner, which, unlike the Condorcet winner, is guaranteed to exist. The first, Copeland Confidence Bound (CCB), is designed for small numbers of arms, while the second, Scalable Copeland Bandits (SCB), works better for large-scale problems. We provide theoretical results bounding the regret accumulated by CCB and SCB, both substantially improving existing results. Such existing results either offer bounds of the form O(K log T) but require restrictive assumptions, or offer bounds of the form O(K^2 log T) without requiring such assumptions. Our results offer the best of both worlds: O(K log T) bounds without restrictive assumptions.

We consider the online version of the well known Principal Component Analysis (PCA) problem. In standard PCA, the input to the problem is a set of d-dimensional vectors X = [x1, …, xn] and a target dimension k < d; the output is a set of k-dimensional vectors Y = [y1, …, yn] that minimize the reconstruction error: . Here, Φ ∊ ℝd × k is restricted to being isometric. The global minimum of this quantity, OPTk, is obtainable by offline PCA. In online PCA (OPCA) the setting is identical except for two differences: i) the vectors xt are presented to the algorithm one by one and for every presented xt the algorithm must output a vector yt before receiving xt+1; ii) the output vectors yt are ℓ dimensional with ℓ ≥ k to compensate for the handicap of operating online. To the best of our knowledge, this paper is the first to consider this setting of OPCA. Our algorithm produces yt ∊ ℝℓ with ℓ = O(k · poly(1/ε)) such that .

It is well known that collaborative filtering (CF) based recommender systems provide better modeling of users and items associated with considerable rating history. The lack of historical ratings results in the user and the item cold-start problems. The latter is the main focus of this work. Most of the current literature addresses this problem by integrating content-based recommendation techniques to model the new item. However, in many cases such content is not available, and the question arises is whether this problem can be mitigated using CF techniques only. We formalize this problem as an optimization problem: given a new item, a pool of available users, and a budget constraint, select which users to assign with the task of rating the new item in order to minimize the prediction error of our model. We show that the objective function is monotone-supermodular, and propose efficient optimal design based algorithms that attain an approximation to its optimum. Our findings are verified by an empirical study using the Netflix dataset, where the proposed algorithms outperform several baselines for the problem at hand.

Email classification is still a mostly manual task. Consequently, most Web mail users never define a single folder. Recently however, automatic classification offering the same categories to all users has started to appear in some Web mail clients, such as AOL or Gmail. We adopt this approach, rather than previous (unsuccessful) personalized approaches because of the change in the nature of consumer email traffic, which is now dominated by (non-spam) machine-generated email. We propose here a novel approach for (1) automatically distinguishing between personal and machine-generated email and (2) classifying messages into latent categories, without requiring users to have defined any folder. We report how we have discovered that a set of 6 "latent" categories (one for human- and the others for machine-generated messages) can explain a significant portion of email traffic. We describe in details the steps involved in building a Web-scale email categorization system, from the collection of ground-truth labels, the selection of features to the training of models. Experimental evaluation was performed on more than 500 billion messages received during a period of six months by users of Yahoo mail service, who elected to be part of such research studies. Our system achieved precision and recall rates close to 90% and the latent categories we discovered were shown to cover 70% of both email traffic and email search queries. We believe that these results pave the way for a change of approach in the Web mail industry, and could support the invention of new large-scale email discovery paradigms that had not been possible before.

Numerous machine learning problems require an \it exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance called volumetric spanners, and give efficient algorithms to construct such bases. We show how efficient volumetric spanners give rise to an efficient and near-optimal regret algorithm for bandit linear optimization over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.

We present algorithms for reducing the Dueling Bandits problem to the conventional (stochastic) Multi-Armed Bandits problem. The Dueling Bandits problem is an online model of learning with ordinal feedback of the form “A is preferred to B” (as opposed to cardinal feedback like “A has value 2.5”), giving it wide applicability in learning from implicit user feedback and revealed and stated preferences. In contrast to existing algorithms for the Dueling Bandits problem, our reductions – named \Doubler, \MultiSbm and \DoubleSbm – provide a generic schema for translating the extensive body of known results about conventional Multi-Armed Bandit algorithms to the Dueling Bandits setting. For \Doubler and \MultiSbm we prove regret upper bounds in both finite and infinite settings, and conjecture about the performance of \DoubleSbm which empirically outperforms the other two as well as previous algorithms in our experiments. In addition, we provide the first almost optimal regret bound in terms of second order terms, such as the differences between the values of the arms.

We study the problem of exploration in stochastic Multi-Armed Bandits. Even in the simplest setting of identifying the best arm, there remains a logarithmic multiplicative gap between the known lower and upper bounds for the number of arm pulls required for the task. This extra logarithmic factor is quite meaningful in nowadays large-scale applications. We present two novel, parameter-free algorithms for identifying the best arm, in two different settings: given a target confidence and given a target budget of arm pulls, for which we prove upper bounds whose gap from the lower bound is only doubly-logarithmic in the problem parameters. We corroborate our theoretical results with experiments demonstrating that our algorithm outperforms the state-of-the-art and scales better as the size of the problem increases.

We consider the problem of independently sampling $s$ non-zero entries of a matrix $A$ in order to produce a sparse sketch of it, $B$, that minimizes $\|A-B\|_2$. For large $m \times n$ matrices, such that $n \gg m$ (for example, representing $n$ observations over $m$ attributes) we give distributions exhibiting four important properties. First, they have closed forms for the probability of sampling each item which are computable from minimal information regarding $A$. Second, they allow sketching of matrices whose non-zeros are presented to the algorithm in arbitrary order as a stream, with $O(1)$ computation per non-zero. Third, the resulting sketch matrices are not only sparse, but their non-zero entries are highly compressible. Lastly, and most importantly, under mild assumptions, our distributions are provably competitive with the optimal offline distribution. Note that the probabilities in the optimal offline distribution may be complex functions of all the entries in the matrix. Therefore, regardless of computational complexity, the optimal distribution might be impossible to compute in the streaming model.

We study exploration in Multi-Armed Bandits (MAB) in a setting where~$k$ players collaborate in order to identify an $\epsilon$-optimal arm. Our motivation comes from recent employment of MAB algorithms in computationally intensive, large-scale applications. Our results demonstrate a non-trivial tradeoff between the number of arm pulls required by each of the players, and the amount of communication between them. In particular, our main result shows that by allowing the $k$ players to communicate \emph{only once}, they are able to learn $\sqrt{k}$ times faster than a single player. That is, distributing learning to $k$ players gives rise to a factor~$\sqrt{k}$ parallel speed-up. We complement this result with a lower bound showing this is in general the best possible. On the other extreme, we present an algorithm that achieves the ideal factor $k$ speed-up in learning performance, with communication only logarithmic in~$1/\epsilon$.

Viewing email messages as parts of a sequence or a thread is a convenient way to quickly understand their context. Current threading techniques rely on purely syntactic methods, matching sender information, subject line, and reply/forward prefixes. As such, they are mostly limited to personal conversations. In contrast, machine-generated email, which amount, as per our experiments, to more than 60% of the overall email traffic, requires a different kind of threading that should reflect how a sequence of emails is caused by a few related user actions. For example, purchasing goods from an online store will result in a receipt or a confirmation message, which may be followed, possibly after a few days, by a shipment notification message from an express shipping service. In today's mail systems, they will not be a part of the same thread, while we believe they should. In this paper, we focus on this type of threading that we coin "causal threading". We demonstrate that, by analyzing recurring patterns over hundreds of millions of mail users, we can infer a causality relation between these two individual messages. In addition, by observing multiple causal relations over common messages, we can generate "causal threads" over a sequence of messages. The four key stages of our approach consist of: (1) identifying messages that are instances of the same email type or "template" (generated by the same machine process on the sender side) (2) building a causal graph, in which nodes correspond to email templates and edges indicate potential causal relations (3) learning a causal relation prediction function, and (4) automatically "threading" the incoming email stream. We present detailed experimental results obtained by analyzing the inboxes of 12.5 million Yahoo! Mail users, who voluntarily opted-in for such research. Supervised editorial judgments show that we can identify more than 70% (recall rate) of all "causal threads" at a precision level of 90%. In addition, for a search scenario we show that we achieve a precision close to 80% at 90% recall. We believe that supporting causal threads in email clients opens new grounds for improving both email search and browsing experiences.

We give the first subexponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 multilinear circuits with a plus gate at the top (also known as $\Sigma\Pi\Sigma\Pi$ circuits) and has a running time of $\exp(\mathrm{poly}(\log(n),\log(s),k))$ where $n$ is the number of variables, $s$ is the size of the circuit, and $k$ is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. Prior to this work, sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-$4$ circuits. The main ingredient in our proof is a new structural theorem for multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits. Roughly, this theorem shows that any nonzero multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit contains an “embedded” nonzero multilinear $\Sigma\Pi\Sigma(k)$ circuit. Using ideas from previous works on identity testing of sums of read-once formulas and of depth-3 multilinear circuits, we are able to exploit this structure and obtain an identity testing algorithm for multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits.

We present a simplex algorithm for linear programming in a linear classification formulation. The paramount complexity parameter in linear classification problems is called the margin. We prove that for margin values of practical interest our simplex variant performs a polylogarithmic number of pivot steps in the worst case, and its overall running time is near linear. This is in contrast to general linear programming, for which no sub-polynomial pivot rule is known.

We construct a small set of explicit linear transformations mapping $\mathbb{R}^n$ to $\mathbb{R}^t$, where $t=O(\log (\gamma^{-1}) \epsilon^{-2})$, such that the $L_2$ norm of any vector in $\mathbb{R}^n$ is distorted by at most $1\pm \epsilon$ in at least a fraction of $1 - \gamma$ of the transformations in the set. Albeit the tradeoff between the size of the set and the success probability is suboptimal compared with probabilistic arguments, we nevertheless are able to apply our construction to a number of problems. In particular, we use it to construct an $\epsilon$-sample (or pseudorandom generator) for linear threshold functions on $\mathbb{S}^{n-1}$ for $\epsilon = o(1)$. We also use it to construct an $\epsilon$-sample for spherical digons in $\mathbb{S}^{n-1}$ for $\epsilon = o(1)$. This construction leads to an efficient oblivious derandomization of the Goemans–Williamson Max-Cut algorithm and similar approximation algorithms (i.e., we construct a small set of hyperplanes such that for any instance we can choose one of them to generate a good solution). Our technique for constructing an $\epsilon$-sample for linear threshold functions on the sphere is considerably different than previous techniques that rely on k-wise independent sample spaces.

For any 0 0, we give an efficient deterministic construction of a linear subspace V ⊆ Rn, of dimension (1-ε)n in which the lp and lr norms are the same up to a multiplicative factor of poly(ε-1) (after proper normalization). As a corollary we get a deterministic compressed sensing algorithm (Basis Pursuit) for a new range of parameters. In particular, for any constant ε>0 and p<2, we obtain a linear operator A:Rn -> Rε n with the l1/lp guarantee for (n ⋅ poly(ε))-sparse vectors. Namely, let x be a vector in Rn whose l1 distance from a k-sparse vector (for some k=n ⋅ poly(ε)) is δ. The algorithm, given Ax as input, outputs an n dimensional vector y such that ||x-y||p ≤ δ k1/p-1. In particular this gives a weak form of the l2/l1 guarantee.

We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as ΣΠΣΠ circuits) and has a running time of exp(poly(log(n),log(s),k)) where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. In [AV08], it was shown that derandomizing polynomial identity testing for general ΣΠΣΠ circuits implies a derandomization of polynomial identity testing in general arithmetic circuits. Prior to this work sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-4 circuits.

In this paper we give reconstruction algorithms for depth-3 arithmetic circuits with k multiplication gates (also known as SigmaPiSigma(k) circuits), where k=O(1). Namely, we give an algorithm that when given a black box holding a SigmaPiSigma(k) circuit C over a field F as input, makes queries to the black box (possibly over a polynomial sized extension field of F) and outputs a circuit C' computing the same polynomial as C. In particular we obtain the following results. (1) When C is a multilinear SigmaPiSigma(k) circuit (i.e. each of its multiplication gates computes a multilinear polynomial) then our algorithm runs in polynomial time (when k is a constant) and outputs a multilinear SigmaPiSigma(k) circuits computing the same polynomial. (2) In the general case, our algorithm runs in quasi-polynomial time and outputs a generalized depth-3 circuit with k multiplication gates. For example, the polynomials computed by generalized depth-3 circuits can be computed by quasi-polynomial sized depth-3 circuits. In fact, our algorithm works in the slightly more general case where the black box holds a generalized depth-3 circuits. Prior to this work there were reconstruction algorithms for several different models of bounded depth circuits: the well studied class of depth-2 arithmetic circuits (that compute sparse polynomials) and its close by model of depth-3 set-multilinear circuits. For the class of depth-3 circuits only the case of k = 2 (i.e. SigmaPiSigma(2) circuits) was known. Our proof technique combines ideas from previous works with some new ideas. Our most notable new ideas are: We prove the existence of a unique canonical representation of depth-3 circuits. This enables us to work with a specific representation in mind. Another technical contribution is an isolation lemma for depth-3 circuits that enables us to reconstruct a single multiplication gate of the circuit.

In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f(xmacr) = Sigmai=1khi(xmacr) ldr gi(xmacr), where each hi is a polynomial that depends on at most p linear functions, and each giis a product of linear functions (when hi= 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as SigmaPiSigma(k) circuits, but the general case is much richer). When maxi(deg(hildrgi)) = d we say that f is computable by a SigmaPiSigma(k, d, p) circuit. We obtain the following results. 1. A deterministic black-box identity testing algorithm for SigmaPiSigma(k, d, p) circuits that runs in quasi-polynomial time (for p = polylog(n + d)). 2. A deterministic black-box identity testing algorithm for read-k SigmaPiSigma circuits (depth-3 circuits where each variable appears at most k times) that runs in time n2o(k2)This gives a polynomial time algorithm for k = 0(1). These are the first sub-exponential black-box PIT algorithms for circuits of depth higher than 2. Our results can also be stated in terms of test sets for the underlying circuit model. A test set is a set of points s.t. if two circuits get the same values on every point of the set then they compute the same polynomial. Thus, our first result gives an explicit test set, of quasi-polynomial size, for SigmaPiSigma(k, d, p) circuits (for p = polylog(n + d)). Our second result gives an explicit polynomial size test set for read-k depth-3 circuits. The proof technique involves a construction of a family of affine subspaces that have a rank-preserving property that is inspired by the construction of linear seeded extractors for affine sources of Gabizon andRaz [9], and a generalization of a theorem of [8] regarding the structure of identically zero depth-3 circuits with bounded top fan-in.