Memorization in language models is a critical yet poorly understood phenomenon. In this work, we investigate memorization in transformer-based language models by analyzing their memorization dynamics during training over multiple epochs. We find that memorization is neither a constant accumulation of sequences nor simply dictated by the recency of exposure to these sequences. Instead, much like generalization, memorization appears to be driven by pattern recognition. Tracking memorization dynamics in mixed datasets, we observe that models memorize different sub-datasets in distinct bursts, suggesting that each subset is associated with unique underlying patterns, and that the model prefers to learn these patterns in a consistent order. We also find that easily learnable patterns tend to support generalization on unseen data, while more complex patterns do not. Furthermore, in datasets with weak or absent patterns, larger models may delay memorization relative to smaller ones, a behavior we term $\textit{overthinking}$. Our results show that the subset of sequences memorized by a model over time is not arbitrary, and give insights into the internal processes a model goes through during training. Our code is available at: https://github.com/mdrpanwar/memorization-patterns.

Abstract Transformers trained on natural language data have been shown to exhibit hierarchical generalization without explicitly encoding any structural bias. In this work, we investigate sources of inductive bias in transformer models and their training that could cause such preference for hierarchical generalization. We extensively experiment with transformers trained on five synthetic, controlled datasets using several training objectives and show that, while objectives such as sequence-to-sequence modeling, classification, etc., often fail to lead to hierarchical generalization, the language modeling objective consistently leads to transformers generalizing hierarchically. We then study how different generalization behaviors emerge during the training by conducting pruning experiments that reveal the joint existence of subnetworks within the model implementing different generalizations. Finally, we take a Bayesian perspective to understand transformers’ preference for hierarchical generalization: We establish a correlation between whether transformers generalize hierarchically on a dataset and if the simplest explanation of that dataset is provided by a hierarchical grammar compared to regular grammars exhibiting linear generalization. Overall, our work presents new insights on the origins of hierarchical generalization in transformers and provides a theoretical framework for studying generalization in language models.

In-context learning (ICL) is one of the surprising and useful features of large language models and subject of intense research. Recently, stylized meta-learning-like ICL setups have been devised that train transformers on sequences of input-output pairs $(x, f(x))$. The function $f$ comes from a function class and generalization is checked by evaluating on sequences generated from unseen functions from the same class. One of the main discoveries in this line of research has been that for several function classes, such as linear regression, transformers successfully generalize to new functions in the class. However, the inductive biases of these models resulting in this behavior are not clearly understood. A model with unlimited training data and compute is a Bayesian predictor: it learns the pretraining distribution. In this paper we empirically examine how far this Bayesian perspective can help us understand ICL. To this end, we generalize the previous meta-ICL setup to hierarchical meta-ICL setup which involve unions of multiple task families. We instantiate this setup on a diverse range of linear and nonlinear function families and find that transformers can do ICL in this setting as well. Where Bayesian inference is tractable, we find evidence that high-capacity transformers mimic the Bayesian predictor. The Bayesian perspective provides insights into the inductive bias of ICL and how transformers perform a particular task when they are trained on multiple tasks. We also find that transformers can learn to generalize to new function classes that were not seen during pretraining. This involves deviation from the Bayesian predictor. We examine these deviations in more depth offering new insights and hypotheses.

The inner workings of neural networks can be better understood if we can fully decipher the information encoded in neural activations. In this paper, we argue that this information is embodied by the subset of inputs that give rise to similar activations. We propose InversionView, which allows us to practically inspect this subset by sampling from a trained decoder model conditioned on activations. This helps uncover the information content of activation vectors, and facilitates understanding of the algorithms implemented by transformer models. We present four case studies where we investigate models ranging from small transformers to GPT-2. In these studies, we show that InversionView can reveal clear information contained in activations, including basic information about tokens appearing in the context, as well as more complex information, such as the count of certain tokens, their relative positions, and abstract knowledge about the subject. We also provide causally verified circuits to confirm the decoded information.

Language models of code (LMs) work well when the surrounding code provides sufficient context. This is not true when it becomes necessary to use types, functionality or APIs defined elsewhere in the repository or a linked library, especially those not seen during training. LMs suffer from limited awareness of such global context and end up hallucinating. Integrated development environments (IDEs) assist developers in understanding repository context using static analysis. We extend this assistance, enjoyed by developers, to LMs. We propose monitor-guided decoding (MGD) where a monitor uses static analysis to guide the decoding. We construct a repository-level dataset PragmaticCode for method-completion in Java and evaluate MGD on it. On models of varying parameter scale, by monitoring for type-consistent object dereferences, MGD consistently improves compilation rates and agreement with ground truth. Further, LMs with fewer parameters, when augmented with MGD, can outperform larger LMs. With MGD, SantaCoder-1.1B achieves better compilation rate and next-identifier match than the much larger text-davinci-003 model. We also conduct a generalizability study to evaluate the ability of MGD to generalize to multiple programming languages (Java, C# and Rust), coding scenarios (e.g., correct number of arguments to method calls), and to enforce richer semantic constraints (e.g., stateful API protocols). Our data and implementation are available at https://github.com/microsoft/monitors4codegen.

In supervised learning, it is known that overparameterized neural networks with one hidden layer provably and efficiently learn and generalize, when trained using stochastic gradient descent with a sufficiently small learning rate and suitable initialization. In contrast, the benefit of overparameterization in unsupervised learning is not well understood. Normalizing flows (NFs) constitute an important class of models in unsupervised learning for sampling and density estimation. In this paper, we theoretically and empirically analyze these models when the underlying neural network is a one-hidden-layer overparametrized network. Our main contributions are two-fold: (1) On the one hand, we provide theoretical and empirical evidence that for constrained NFs (this class of NFs underlies most NF constructions) with the one-hidden-layer network, overparametrization hurts training. (2) On the other hand, we prove that unconstrained NFs, a recently introduced model, can efficiently learn any reasonable data distribution under minimal assumptions when the underlying network is overparametrized and has one hidden-layer.

Humans can reason compositionally whilst grounding language utterances to the real world.Recent benchmarks like ReaSCAN (Wu et al., 2021) use navigation tasks grounded in a grid world to assess whether neural models exhibit similar capabilities.In this work, we present a simple transformer-based model that outperforms specialized architectures on ReaSCAN and a modified version (Qiu et al., 2021) of gSCAN (Ruis et al., 2020).On analyzing the task, we find that identifying the target location in the grid world is the main challenge for the models.Furthermore, we show that a particular split in ReaSCAN, which tests depth generalization, is unfair.On an amended version of this split, we show that transformers can generalize to deeper input structures.Finally, we design a simpler grounded compositional generalization task, RefEx, to investigate how transformers reason compositionally.We show that a single self-attention layer with a single head generalizes to novel combinations of object attributes.Moreover, we derive a precise mathematical construction of the transformer's computations from the learned network.Overall, we provide valuable insights about the grounded compositional generalization task and the behaviour of transformers on it, which would be useful for researchers working in this area.

We consider the problem of robust parameter estimation from observational data in the context of linear structural equation models (LSEMs). Under various conditions on LSEMs and the model parameters the prior work provides efficient algorithms to recover the parameters. However, these results are often about generic identifiability. In practice, generic identifiability is not sufficient and we need robust identifiability: small changes in the observational data should not affect the parameters by a huge amount. Robust identifiability has received far less attention and remains poorly understood. Sankararaman et al. (2019) recently provided a set of sufficient conditions on parameters under which robust identifiability is feasible. However, a limitation of their work is that their results only apply to a small sub-class of LSEMs, called “bow-free paths.” In this work, we show that for any “bow-free model”, in all but $\frac{1}{\poly(n)}$-measure of instances robust identifiability holds. Moreover, whenever an instance is robustly identifiable, the algorithm proposed in Foygel et al., (2012) can be used to recover the parameters in a robust fashion. In contrast, for generic identifiability Foygel et al., (2012) proved that with measure $1$, instances are generically identifiable. Thus, we show that robust identifiability is a strictly harder problem than generic identifiability. Finally, we validate our results on both simulated and real-world datasets.

The problem of designing NLP solvers for math word problems (MWP) has seen sustained research activity and steady gains in the test accuracy.Since existing solvers achieve high performance on the benchmark datasets for elementary level MWPs containing one-unknown arithmetic word problems, such problems are often considered "solved" with the bulk of research attention moving to more complex MWPs.In this paper, we restrict our attention to English MWPs taught in grades four and lower.We provide strong evidence that the existing MWP solvers rely on shallow heuristics to achieve high performance on the benchmark datasets.To this end, we show that MWP solvers that do not have access to the question asked in the MWP can still solve a large fraction of MWPs.Similarly, models that treat MWPs as bag-ofwords can also achieve surprisingly high accuracy.Further, we introduce a challenge dataset, SVAMP, created by applying carefully chosen variations over examples sampled from existing datasets.The best accuracy achieved by state-of-the-art models is substantially lower on SVAMP, thus showing that much remains to be done even for the simplest of the MWPs.PROBLEM: Text: Jack had 8 pens and Mary had 5 pens.Jack gave 3 pens to Mary.How many pens does Jack have now?Equation: 8 -3 = 5 QUESTION SENSITIVITY VARIATION: Text: Jack had 8 pens and Mary had 5 pens.Jack gave 3 pens to Mary.How many pens does Mary have now?Equation: 5 + 3 = 8 REASONING ABILITY VARIATION: Text: Jack had 8 pens and Mary had 5 pens.Mary gave 3 pens to Jack.How many pens

Simple recurrent neural networks (RNNs) and their more advanced cousins LSTMs etc. have been very successful in sequence modeling. Their theoretical understanding, however, is lacking and has not kept pace with the progress for feedforward networks, where a reasonably complete understanding in the special case of highly overparametrized one-hidden-layer networks has emerged. In this paper, we make progress towards remedying this situation by proving that RNNs can learn functions of sequences. In contrast to the previous work that could only deal with functions of sequences that are sums of functions of individual tokens in the sequence, we allow general functions. Conceptually and technically, we introduce new ideas which enable us to extract information from the hidden state of the RNN in our proofs---addressing a crucial weakness in previous work. We illustrate our results on some regular language recognition problems.

While recurrent models have been effective in NLP tasks, their performance on context-free languages (CFLs) has been found to be quite weak.Given that CFLs are believed to capture important phenomena such as hierarchical structure in natural languages, this discrepancy in performance calls for an explanation.We study the performance of recurrent models on Dyck-n languages, a particularly important and well-studied class of CFLs.We find that while recurrent models generalize nearly perfectly if the lengths of the training and test strings are from the same range, they perform poorly if the test strings are longer.At the same time, we observe that recurrent models are expressive enough to recognize Dyck words of arbitrary lengths in finite precision if their depths are bounded.Hence, we evaluate our models on samples generated from Dyck languages with bounded depth and find that they are indeed able to generalize to much higher lengths.Since natural language datasets have nested dependencies of bounded depth, this may help explain why they perform well in modeling hierarchical dependencies in natural language data despite prior works indicating poor generalization performance on Dyck languages.We perform probing studies to support our results and provide comparisons with Transformers.

Transformers are being used extensively across several sequence modeling tasks.Significant research effort has been devoted to experimentally probe the inner workings of Transformers.However, our conceptual and theoretical understanding of their power and inherent limitations is still nascent.In particular, the roles of various components in Transformers such as positional encodings, attention heads, residual connections, and feedforward networks, are not clear.In this paper, we take a step towards answering these questions.We analyze the computational power as captured by Turing-completeness.We first provide an alternate and simpler proof to show that vanilla Transformers are Turing-complete and then we prove that Transformers with only positional masking and without any positional encoding are also Turing-complete.We further analyze the necessity of each component for the Turing-completeness of the network; interestingly, we find that a particular type of residual connection is necessary.We demonstrate the practical implications of our results via experiments on machine translation and synthetic tasks.

Transformers have supplanted recurrent models in a large number of NLP tasks.However, the differences in their abilities to model different syntactic properties remain largely unknown.Past works suggest that LSTMs generalize very well on regular languages and have close connections with counter languages.In this work, we systematically study the ability of Transformers to model such languages as well as the role of its individual components in doing so.We first provide a construction of Transformers for a subclass of counter languages, including well-studied languages such as n-ary Boolean Expressions, Dyck-1, and its generalizations.In experiments, we find that Transformers do well on this subclass, and their learned mechanism strongly correlates with our construction.Perhaps surprisingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance as we make languages more complex according to a well-known measure of complexity.Our analysis also provides insights on the role of self-attention mechanism in modeling certain behaviors and the influence of positional encoding schemes on the learning and generalization abilities of the model.

The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called geodesic convexity. Extensively studied computational problems such as convex optimization and sampling in convex sets also have meaningful counterparts in the manifold setting. Geodesically convex optimization is a well-studied problem with ongoing research and considerable recent interest in machine learning and theoretical computer science. In this paper, we study sampling and convex optimization problems over manifolds of non-negative curvature proving polynomial running time in the dimension and other relevant parameters. Our algorithms assume a warm start. We first present a random walk based sampling algorithm and then combine it with simulated annealing for solving convex optimization problems. To our knowledge, these are the first algorithms in the general setting of positively curved manifolds with provable polynomial guarantees under reasonable assumptions, and the first study of the connection between sampling and optimization in this setting.

Non-Gaussian component analysis (NGCA) is a problem in multidimensional data analysis which, since its formulation in 2006, has attracted considerable attention in statistics and machine learning. In this problem, we have a random variable X in n-dimensional Euclidean space. There is an unknown subspace Γ of the n-dimensional Euclidean space such that the orthogonal projection of X onto Γ is standard multidimensional Gaussian and the orthogonal projection of X onto Γ⊥, the orthogonal complement of Γ, is non-Gaussian, in the sense that all its one-dimensional marginals are different from the Gaussian in a certain metric defined in terms of moments. The NGCA problem is to approximate the non-Gaussian subspace Γ⊥ given samples of X.

Thompson Sampling (TS) is one of the oldest heuristics for multiarmed bandit problems. It is a randomized algorithm based on Bayesian ideas and has recently generated significant interest after several studies demonstrated that it has favorable empirical performance compared to the state-of-the-art methods. In this article, a novel and almost tight martingale-based regret analysis for Thompson Sampling is presented. Our technique simultaneously yields both problem-dependent and problem-independent bounds: (1) the first near-optimal problem-independent bound of O (√ NT ln T ) on the expected regret and (2) the optimal problem-dependent bound of (1 + ϵ)Σ i ln T / d (μ i ,μ 1 ) + O ( N /ϵ 2 ) on the expected regret (this bound was first proven by Kaufmann et al. (2012b)). Our technique is conceptually simple and easily extends to distributions other than the Beta distribution used in the original TS algorithm. For the version of TS that uses Gaussian priors, we prove a problem-independent bound of O (√ NT ln N ) on the expected regret and show the optimality of this bound by providing a matching lower bound. This is the first lower bound on the performance of a natural version of Thompson Sampling that is away from the general lower bound of Ω (√ NT ) for the multiarmed bandit problem.

The Noisy Non-negative Matrix factorization (NMF) is: given a data matrix A (d x n), find non-negative matrices B;C (d x k, k x n respy.) so that A = BC +N, where N is a noise matrix. Existing polynomial time algorithms with proven error guarantees require EACH column N_⋅j to have l1 norm much smaller than ||(BC)_⋅j ||_1, which could be very restrictive. In important applications of NMF such as Topic Modeling as well as theoretical noise models (e.g. Gaussian with high sigma), almost EVERY column of N_.j violates this condition. We introduce the heavy noise model which only requires the average noise over large subsets of columns to be small. We initiate a study of Noisy NMF under the heavy noise model. We show that our noise model subsumes noise models of theoretical and practical interest (for e.g. Gaussian noise of maximum possible sigma). We then devise an algorithm TSVDNMF which under certain assumptions on B,C, solves the problem under heavy noise. Our error guarantees match those of previous algorithms. Our running time of O(k.(d+n)^2) is substantially better than the O(d.n^3) for the previous best. Our assumption on B is weaker than the “Separability” assumption made by all previous results. We provide empirical justification for our assumptions on C. We also provide the first proof of identifiability (uniqueness of B) for noisy NMF which is not based on separability and does not use hard to check geometric conditions. Our algorithm outperforms earlier polynomial time algorithms both in time and error, particularly in the presence of high noise.

Independent component analysis (ICA) is the problem of efficiently recovering a matrix A ∈ ℝn×nfrom i.i.d. Observations of X=AS where S ∈ ℝnis a random vector with mutually independent coordinates. This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates Si have finite fourth moments. We consider the heavy-tailed ICA problem where we do not make this assumption, about the second moment. This problem also has received considerable attention in the applied literature. In the present work, we first give a provably efficient algorithm that works under the assumption that for constant γ > 0, each Sihas finite (1+γ)-moment, thus substantially weakening the moment requirement condition for the ICA problem to be solvable. We then give an algorithm that works under the assumption that matrix A has orthogonal columns but requires no moment assumptions. Our techniques draw ideas from convex geometry and exploit standard properties of the multivariate spherical Gaussian distribution in a novel way.

In this paper we show that very large mixtures of Gaussians are efficiently learnable in high dimension. More precisely, we prove that a mixture with known identical covariance matrices whose number of components is a polynomial of any fixed degree in the dimension n is polynomially learnable as long as a certain non-degeneracy condition on the means is satisfied. It turns out that this condition is generic in the sense of smoothed complexity, as soon as the dimensionality of the space is high enough. Moreover, we prove that no such condition can possibly exist in low dimension and the problem of learning the parameters is generically hard. In contrast, much of the existing work on Gaussian Mixtures relies on low-dimensional projections and thus hits an artificial barrier. Our main result on mixture recovery relies on a new “Poissonization"-based technique, which transforms a mixture of Gaussians to a linear map of a product distribution. The problem of learning this map can be efficiently solved using some recent results on tensor decompositions and Independent Component Analysis (ICA), thus giving an algorithm for recovering the mixture. In addition, we combine our low-dimensional hardness results for Gaussian mixtures with Poissonization to show how to embed difficult instances of low-dimensional Gaussian mixtures into the ICA setting, thus establishing exponential information-theoretic lower bounds for underdetermined ICA in low dimension. To the best of our knowledge, this is the first such result in the literature. In addition to contributing to the problem of Gaussian mixture learning, we believe that this work is among the first steps toward better understanding the rare phenomenon of the “blessing of dimensionality" in the computational aspects of statistical inference.

Motivated by the surging popularity of commercial cloud computing services, a number of recent works have studied annotated data streams and variants thereof. In this setting, a computationally weak verifier (cloud user), lacking the resources to store and manipulate his massive input locally, accesses a powerful but untrusted prover (cloud service). The verifier must work within the restrictive data streaming paradigm. The prover, who can annotate the data stream as it is read, must not just supply the final answer but also convince the verifier of its correctness. Ideally, both the amount of annotation from the prover and the space used by the verifier should be sublinear in the relevant input size parameters. A rich theory of such algorithms—which we call schemes—has started to emerge. Prior work has shown how to leverage the prover's power to efficiently solve problems that have no non-trivial standard data stream algorithms. However, even though optimal schemes are now known for several basic problems, such optimality holds only for streams whose length is commensurate with the size of the data universe. In contrast, many real-world data sets are relatively sparse, including graphs that contain only o(n2) edges, and IP traffic streams that contain much fewer than the total number of possible IP addresses, 2128 in IPv6. Here we design the first annotation schemes that allow both the annotation and the space usage to be sublinear in the total number of stream updates rather than the size of the data universe. We solve significant problems, including variations of INDEX, SET-DISJOINTNESS, and FREQUENCY-MOMENTS, plus several natural problems on graphs. On the other hand, we give a new lower bound that, for the first time, rules out smooth tradeoffs between annotation and space usage for a specific problem. Our technique brings out new nuances in Merlin-Arthur communication complexity models, and provides a separation between online versions of the MA and AMA models.

Whether or not the problem of finding maximal independent sets (MIS)in hypergraphs is in R NC is one of the fundamental problems in the theory of parallel computing. Unlike the well-understood case of MIS in graphs, for the hypergraph problem, our knowledge is quite limited despite considerable work. It is known that the problem is in RNC when the edges of the hypergraph have constant size. For general hypergraphs with n vertices and m edges, the fastest previously known algorithm works in time O(√‾n) with poly(m,n) processors. In this paper we give an EREW PRAM algorithm that works in time no(1) with poly(m,n) processors on general hypergraphs satisfying m

Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution. To make this algorithmic, we develop a robust tensor decomposition method; this is also of independent interest. Our main application is the first provably polynomial-time algorithm for underdetermined ICA, i.e., learning an n × m matrix A from observations y = Ax where x is drawn from an unknown product distribution with arbitrary non-Gaussian components. The number of component distributions m can be arbitrarily higher than the dimension n and the columns of A only need to satisfy a natural and efficiently verifiable nondegeneracy condition. As a second application, we give an alternative algorithm for learning mixtures of spherical Gaussians with linearly independent means. These results also hold in the presence of Gaussian noise.

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of a small number of spanning trees of a graph. We prove that for any bounded-degree $n$-vertex graph, the union of two uniformly random spanning trees approximates the expansion of the graph to within a factor of $O(\log n)$. For the complete graph, we prove that the union of two uniformly random spanning trees is an expander with high probability. For the random graph $G_{n,p}$, for $p = \Omega(\log{n}/n)$, we give a randomized algorithm for constructing two spanning trees whose union is an expander. A closely related construction, which we call a selector, has similar properties. A random selector of a graph is obtained by starting with any spanning tree of the graph and adding a small number of random edges at each vertex.

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have comparable or better empirical performance compared to the state of the art methods. In this paper, we provide a novel regret analysis for Thompson Sampling that proves the first near-optimal problem-independent bound of O(\sqrtNT\ln T) on the expected regret of this algorithm. Our novel martingale-based analysis techniques are conceptually simple, and easily extend to distributions other than the Beta distribution. For the version of Thompson Sampling that uses Gaussian priors, we prove a problem-independent bound of O(\sqrtNT\ln N) on the expected regret, and demonstrate the optimality of this bound by providing a matching lower bound. This lower bound of Ω(\sqrtNT\ln N) is the first lower bound on the performance of a natural version of Thompson Sampling that is away from the general lower bound of O(\sqrtNT) for the multi-armed bandit problem. Our near-optimal problem-independent bounds for Thompson Sampling solve a COLT 2012 open problem of Chapelle and Li. Additionally, our techniques simultaneously provide the optimal problem-dependent bound of (1+ε)\sum_i \frac\ln Td(\mu_i, \mu_1)+O(\fracNε^2) on the expected regret. The optimal problem-dependent regret bound for this problem was first proven recently by Kaufmann et al. [2012].

We show an efficient algorithm for the following problem: Given uniformly random points from an arbitrary n-dimensional simplex, estimate the simplex. The size of the sample and the number of arithmetic operations of our algorithm are polynomial in n. This answers a question of Frieze, Jerrum and Kannan Frieze et al. (1996). Our result can also be interpreted as efficiently learning the intersection of n + 1 half-spaces in R^n in the model where the intersection is bounded and we are given polynomially many uniform samples from it. Our proof uses the local search technique from Independent Component Analysis (ICA), also used by Frieze et al. (1996). Unlike these previous algorithms, which were based on analyzing the fourth moment, ours is based on the third moment. We also show a direct connection between the problem of learning a simplex and ICA: a simple randomized reduction to ICA from the problem of learning a simplex. The connection is based on a known representation of the uniform measure on a simplex. Similar representations lead to a reduction from the problem of learning an affine transformation of an n-dimensional l_p ball to ICA.

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state of the art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied version of the contextual bandits problem. We prove a high probability regret bound of \tildeO(\fracd\sqrtε\sqrtT^1+ε) in time T for any ε∈(0,1), where d is the dimension of each context vector and εis a parameter used by the algorithm. Our results provide the first theoretical guarantees for the contextual version of Thompson Sampling, and are close to the lower bound of Ω(\sqrtdT) for this problem. This essentially solves the COLT open problem of Chapelle and Li [COLT 2012] regarding regret bounds for Thompson Sampling for contextual bandits problem with linear payoff functions. Our version of Thompson sampling uses Gaussian prior and Gaussian likelihood function. Our novel martingale-based analysis techniques also allow easy extensions to the use of other distributions, satisfying certain general conditions.

A typical problem for a search engine (hosting sponsored search service) is to provide the advertisers with a forecast of the number of impressions his/her ad is likely to obtain for a given bid. Accurate forecasts have high business value, since they enable advertisers to select bids that lead to better returns on their investment. They also play an important role in services such as automatic campaign optimization. Despite its importance the problem has remained relatively unexplored in literature. Existing methods typically overfit to the training data, leading to inconsistent performance. Furthermore, some of the existing methods cannot provide predictions for new ads, i.e., for ads that are not present in the logs. In this paper, we develop a generative model based approach that addresses these drawbacks. We design a Bayes net to capture inter-dependencies between the query traffic features and the competitors in an auction. Furthermore, we account for variability in the volume of query traffic by using a dynamic linear model. Finally, we implement our approach on a production grade MapReduce framework and conduct extensive large scale experiments on substantial volumes of sponsored search data from Bing. Our experimental results demonstrate significant advantages over existing methods as measured using several accuracy/error criteria, improved ability to provide estimates for new ads and more consistent performance with smaller variance in accuracies. Our method can also be adapted to several other related forecasting problems such as predicting average position of ads or the number of clicks under budget constraints.

We consider the following network design problem. We are given an undirected graph G = ( V , E ) with edge costs c ( e ) and a set of terminal nodes W ⊆ V . A hose demand matrix is any symmetric matrix D , indexed by the terminals, such that for each i ∈ W , ∑ j≠i D ij ≤ 1. We must compute the minimum-cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An oblivious routing template, in this context, is a simple path P ij for each pair i,j ∈ W . Given such a template, if we are to route a demand matrix D , then for each i,j , we send D ij units of flow along each P ij . Fingerhut et al. [1997] and Gupta et al. [2001] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked and subsequently conjectured [Italiano et al. 2006] that this solution actually results in the optimal capacity for the single-path VPN design problem; this has become known as the VPN Conjecture . The conjecture has previously been proven for some restricted classes of graphs [Fingerhut et al. 1997; Fiorini et al. 2007; Grandoni et al. 2008; Hurkens et al. 2007]. Our main theorem establishes that this conjecture is true in general graphs. This also has the implication that the single-path VPN problem is solvable in polynomial time. A natural fractional version of the conjecture had also been proposed [Hurkens et al. 2007]. In this version, the routing may split flow between many paths, in specified proportions. We demonstrate that this multipath version of the conjecture is in fact false. The multipath and single path versions of the VPN problem are essentially direct analogues of the randomized and nonrandomized versions of oblivious routing schemes for minimizing congestion for permutation routing [Borodin and Hopcroft 1982; Valiant 1982].

The Lovász local lemma (LLL) [P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets, Vol. II, A. Hajnal, R. Rado, and V. T. Sós, eds., North--Holland, Amsterdam, 1975, pp. 609--627] is a powerful result in probability theory that informally states the following: the probability that none of a set of bad events happens is positive if the probability of each event is small compared to the number of events that depend on it. The LLL is often used for nonconstructive existence proofs of combinatorial structures. A prominent application is to $k$-CNF formulas, where the LLL implies that if every clause in a formula shares variables with at most $d \leq 2^k/e-1$ other clauses, then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment in this setting was given by Moser [A constructive proof of the Lovász local lemma, in STOC '09: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 343--350]. Subsequently Moser and Tardos [J. ACM, 57 (2010), pp. 11:1--11:15] gave a general algorithmic framework for the LLL and a randomized algorithm within this framework to construct the structures guaranteed by the LLL. The main problem left open by Moser and Tardos was to design an efficient deterministic algorithm for constructing structures guaranteed by the LLL. In this paper we provide such an algorithm. Our algorithm works in the general framework of Moser and Tardos with a minimal loss in parameters. For the special case of constructing satisfying assignments for $k$-CNF formulas with $m$ clauses, where each clause shares variables with at most $d \leq 2^{k/(1+\epsilon)}/e - 1$ other clauses, for any $\epsilon\in (0,1)$, we give a deterministic algorithm that finds a satisfying assignment in time $\tilde{O}(m^{2(1+1/\epsilon)})$. This improves upon the deterministic algorithms of Moser and of Moser and Tardos with running times $m^{\Omega(k^2)}$ and $m^{\Omega(d \log d)}$, respectively, which are superpolynomial for $k=\omega(1)$ and $d=\omega(1)$, and upon the previous best deterministic algorithm of Beck, which runs in polynomial time only for $d\leq 2^{k/16}/4$. Our algorithm is the first deterministic algorithm that works in the general framework of Moser and Tardos. We also give a parallel NC algorithm for the same setting, improving upon an algorithm of Alon [Random Structures Algorithms, 2 (1991), pp. 367--378].

Smoothed analysis of multiobjective 0-1 linear optimization has drawn considerable attention recently. In this literature, the number of Pareto-optimal solutions (i.e., solutions with the property that no other solution is at least as good in all the coordinates and better in at least one) for multiobjective optimization problems is the central object of study. In this paper, we prove several lower bounds for the expected number of Pareto optima. Our basic result is a lower bound of Omega_d(n^{d-1}) for optimization problems with d objectives and $n$ variables under fairly general conditions on the distributions of the linear objectives. Our proof relates the problem of lower bounding the number of Pareto optima to results in discrete geometry and geometric probability connected to arrangements of hyperplanes. We use our basic result to derive (1) To our knowledge, the first lower bound for natural multiobjective optimization problems. We illustrate this for the maximum spanning tree problem with randomly chosen edge weights. Our technique is sufficiently flexible to yield such lower bounds for other standard objective functions studied in this setting (such as multiobjective shortest path, TSP tour, matching). (2) Smoothed lower bound of min(Omega_d( n^{d-1.5} phi^{(d-\log d) (1-Theta(1/phi))}), 2^{Theta(n)}) for the 0-1 knapsack problem with d profits for phi-semirandom distributions for a version of the knapsack problem. This improves the recent lower bound of Brunsch and Röglin.

The Lovász Local Lemma [5] (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d ≤ 2k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser [13]. Subsequently Moser and Tardos [14] gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We address the main problem left open by Moser and Tardos of derandomizing these algorithms efficiently. Specifically, for a k-CNF formula with m clauses and d ≤ 2k/(1+ε)/e for some ε ∊ (0, 1), we give an algorithm that finds a satisfying assignment in time . This improves upon the deterministic algorithms of Moser and of Moser-Tardos with running times mΩ(k2) and mΩ(k · 1.ε) which are superpolynomial for k = ω(1) and upon other previous algorithms which work only for d ≤ 2k/16/e. Our algorithm works efficiently for the asymmetric version of LLL under the algorithmic framework of Moser and Tardos [14] and is also parallelizable, i.e., has polylogarithmic running time using polynomially many processors.

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph Gn,p, for p = Ω(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary; each spanning tree can be produced independently using an algorithm by Aldous and Broder: A random walk in the graph with edges leading to previously unvisited vertices included in the tree. Splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. For random graphs, splicers provide simple algorithms for sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).

We consider the following network design problem. We are given an undirected graph G=(V,E) with edges costs c(e) and a set of terminal nodes W. A hose demand matrix for W is any symmetric matrix [Dij] such that for each i, ∑ j ≠ i Dij ≤ 1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network.

We say that an algorithm for nearest neighbor search is combinatorial if only direct comparisons between two pairwise similarity values are allowed. Combinatorial algorithms for nearest neighbor search have two important advantages: (1) they do not map similarity values to artificial distance values and do not use the triangle inequality for the latter, and (2) they work for arbitrarily complicated data representations and similarity functions.

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model, defined by El Gamal in [Open problems presented at the $1984$ workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research, in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath, eds., Springer-Verlag, New York, 1987, pp. 60–62]. In this model there are $n+1$ processors $P_0,P_1,\ldots,P_n$, each of which is initially given a private input bit $x_i$. The goal is for $P_0$ to learn the value of $f(x_1,\ldots,x_n)$, for some specified function f, using a series of noisy broadcasts. At each step a designated processor broadcasts one bit to all of the other processors, and the bit received by each processor is flipped with fixed probability (independently for each recipient). In 1988, Gallager [IEEE Trans. Inform. Theory, 34 (1988), pp. 176–180] gave a noise-resistant protocol that allows $P_0$ to learn the entire input with constant probability in $O(n\log\log n)$ broadcasts. We prove that Gallager's protocol is optimal, up to a constant factor. Our lower bound follows by reduction from a lower bound for generalized noisy decision trees, a new model which may be of independent interest. For this new model we show a lower bound of $\Omega(n \log n)$ on the depth of a tree that learns the entire input. While the above lower bound is for an n-bit function, we also show an $\Omega(n\log\log n)$ lower bound for the number of broadcasts required to compute certain explicit boolean-valued functions, when the correct output must be attained with probability at least $1-n^{-\alpha}$ for a constant parameter $\alpha>0$ (this bound applies to all threshold functions as well as any other boolean-valued function with linear sensitivity). This bound also follows by reduction from a lower bound of $\Omega(n\log n)$ on the depth of generalized noisy decision trees that compute the same functions with the same error. We also show a (nontrivial) $\Omega(n)$ lower bound on the depth of generalized noisy decision trees that compute such functions with small constant error. Finally, we show the first protocol in the noisy broadcast model that computes the Hamming weight of the input using a linear number of broadcasts.

Let CCo(n)[m] be the class of circuits that have size o(n) and in which all gates are MOD[m] gates. We show that CC [m] circuits cannot compute MODqin sub-linear size when m, q > 1 are co-prime integers. No non-trivial lower bounds were known before on the size of CC [m] circuits of constant depth for computing MODq. On the other hand, our results show circuits of type MAJ o CCo(n)[m] need exponential size to compute MODq. Using Bourgain's recent breakthrough result on estimates of exponential sums, we extend our bound to the case where small fan-in AND gates are allowed at the bottom of such circuits i.e. circuits of type MAJ o CC[m] o ANDepsiv log n, where epsiv > 0 is a sufficiently small constant. CC [m] circuits of constant depth need superlinear number of wires to compute both the AND and MODqfunctions. To prove this, we show that any circuit computing such functions has a certain connectivity property that is similar to that of superconcentration. We show a superlinear lower bound on the number of edges of such graphs extending results on superconcentrators

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n + 1 processors P/sub 0/, P/sub 1/, ..., P/sub n/. Each P/sub i/, for i /spl ges/ 1, initially has a private bit x/sub i/ and the goal is for P/sub 0/ to learn f (x/sub l/, ..., x/sub n/) for some specified function f. At each time step, a designated processor broadcasts some function of its private bit and the bits it has heard so far. Each broadcast is received by the other processors but each reception may be corrupted by noise. In this model, Gallager (1988) gave a noise-resistant protocol that allows P/sub 0/ to learn the entire input in O(n log log n) broadcasts. We prove that Gallager's protocol is optimal up to a constant factor. Our lower bound follows from a lower bound in a new model, the generalized noisy decision tree model, which may be of independent interest.

We consider the problem of evaluating a Boolean function on PRAMs. We exhibit a Boolean function f:{0,1}/sup n//spl rarr/{0,1} that can be evaluated in time O(log log n) in a deterministic CROW (concurrent read owner write) PRAM model, but requires time /spl Omega/(log n) in EROW (exclusive read owner write) PRAM. Our lower bound also holds in the randomized Monte Carlo EROW model. This Boolean function is derived from the well-known pointer chasing problem, and was first considered by Nisan and Bar-Yossef (1997). Our lower bound improves a special case of the previous result of Nisan and Bar-Yossef, who proved a lower bound of /spl Omega/(/spl radic/(log n)) for this function in the deterministic EREW model (and hence in the EROW model). Our result is the first to achieve the best possible separation between the CROW and EROW PRAM models for functions on complete domains (Boolean or nonBoolean), improving the previous results (E. Gafni et al., 1989; F. Fich et al., 1990; N. Nisan et al., 1997).

Efficient bandwidth allocation strategy with simultaneous fulfillment of QoS requirement of a user in a mobile cellular network is still a critical and an important practical issue. We explore the problem of finding the reservation schedule that would minimize the amount of time for which bandwidth has to be allocated in a cell while meeting the QoS constraint. With the knowledge about the arrival and residence time distribution of a user in a cell, the above problem can be optimally solved using a dynamic programming based approach in polynomial time. To be able to use the solution, we provide a mechanism for constructing the arrival/residence time distribution based on the measurement of hand-off events in a cell. The above solution allows us to propose an optimal time based bandwidth reservation and call admission scheme. By being scalable and distributed, the proposed scheme justifies for practical implementation. Simulations results are also presented to show the effectiveness of the scheme to achieve the target QoS level and optimal bandwidth utilization.