• Home
 • Publications
 • Google Scholar page

Online Sparse Linear Regression. 2016
With Dean Foster and Howard Karloff. In 29thCOLT, 2016. [ps]

We consider the online sparse linear regression problem, which is the problem of sequentially making predictions observing only a limited number of features in each round, to minimize regret with respect to the best sparse linear regressor, where prediction accuracy is measured by square loss. We give an inefficient algorithm that obtains regret bounded by \( \tilde{O}(\sqrt{T}) \) after \(T\) prediction rounds. We complement this result by showing that no algorithm running in polynomial time per iteration can achieve regret bounded by \(O(T^{1-\delta})\) for any constant \(\delta > 0\) unless \( NP \subseteq BPP \). This computational hardness result resolves an open problem presented in COLT 2014 (Kale, 2014) and also posed by Zolghadr et al. (2013). This hardness result holds even if the algorithm is allowed to access more features than the best sparse linear regressor up to a logarithmic factor in the dimension.

Online Gradient Boosting. 2015
With Alina Beygelzimer, Elad Hazan, and Haipeng Luo. In 29thNIPS, 2015. [ps]

We extend the theory of boosting for regression problems to the online learning setting. Generalizing from the batch setting for boosting, the notion of a weak learning algorithm is modeled as an online learning algorithm with linear loss functions that competes with a base class of regression functions, while a strong learning algorithm is an online learning algorithm with smooth convex loss functions that competes with a larger class of regression functions. Our main result is an online gradient boosting algorithm that converts a weak online learning algorithm into a strong one where the larger class of functions is the linear span of the base class. We also give a simpler boosting algorithm that converts a weak online learning algorithm into a strong one where the larger class of functions is the convex hull of the base class, and prove its optimality.

Optimal and Adaptive Algorithms for Online Boosting. 2015
With Alina Beygelzimer and Haipeng Luo. In 32ndICML, 2015. [ps]

We study online boosting, the task of converting any weak online learner into a strong online learner. Based on a novel and natural definition of weak online learnability, we develop two online boosting algorithms. The first algorithm is an online version of boost-by-majority. By proving a matching lower bound, we show that this algorithm is essentially optimal in terms of the number of weak learners and the sample complexity needed to achieve a specified accuracy. The second algorithm is adaptive and parameter-free, albeit not optimal.

Budgeted Prediction With Expert Advice. 2015
With Kareem Amin, Gerald Tesauro, and Deepak Turaga. In 29thAAAI, 2015. [ps]

We consider a budgeted variant of the problem of learning from expert advice with \(N\) experts. Each queried expert incurs a cost and there is a given budget \(B\) on the total cost of experts that can be queried in any prediction round. We provide an online learning algorithm for this setting with regret after \(T\) prediction rounds bounded by \(O\!\!\left(\sqrt{\frac{C}{B}\log(N)T}\right)\), where \(C\) is the total cost of all experts. We complement this upper bound with a nearly matching lower bound \(\Omega\!\left(\sqrt{\frac{C}{B}T}\right)\) on the regret of any algorithm for this problem. We also provide experimental validation of our algorithm.

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. 2014
With Alekh Agarwal, Daniel Hsu, John Langford, Lihong Li, and Robert E. Schapire. In 31st ICML, 2014. [ps]

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of \(K\) actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only \(\tilde{O}(\sqrt{KT})\) oracle calls across all \(T\) rounds. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We further conduct a proof-of-concept experiment which demonstrates the excellent computational and prediction performance of (an online variant of) our algorithm relative to several baselines.

Multiarmed Bandits With Limited Expert Advice. 2014
In 27th COLT, 2014. [ps]

We consider the problem of minimizing regret in the setting of advice-efficient multiarmed bandits with expert advice. We give an algorithm for the setting of \(K\) arms and \(N\) experts out of which we are allowed to query and use only \(M\) experts' advice in each round, which has a regret bound of \(\tilde{O}\left(\sqrt{\frac{\min\{K, M\} N}{M} T}\right)\) after \(T\) rounds. We also prove that any algorithm for this problem must have expected regret at least \(\tilde{\Omega}\left(\sqrt{\frac{\min\{K, M\} N}{M}T}\right)\), thus showing that our upper bound is nearly tight. This solves the COLT 2013 open problem of Seldin et al.

Adaptive Market Making via Online Learning. 2013
With Jacob Abernethy. In 27th NIPS, 2013. [ps]

We consider the design of strategies for market making in an exchange. A market maker generally seeks to profit from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. Profit guarantees for market making strategies have typically required certain stochastic assumptions on the price fluctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. We propose a class of "spread-based" market making strategies whose performance can be controlled even under worst-case (adversarial) settings. We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. We run a set of experiments showing favorable performance on recent real-world stock price data.

Bargaining for Revenue Shares on Tree Trading Networks. 2013
With Arpita Ghosh, Kevin Lang, and Benjamin Moseley. In 23rd IJCAI, 2013. [ps]

We study trade networks with a tree structure, where a seller with a single indivisible good is connected to buyers, each with some value for the good, via a unique path of intermediaries. Agents in the tree make multiplicative revenue share offers to their parent nodes, who choose the best offer and offer part of it to their parent, and so on; the winning path is determined by who finally makes the highest offer to the seller. In this paper, we investigate how these revenue shares might be set via a natural bargaining process between agents on the tree, specifically, egalitarian bargaining between endpoints of each edge in the tree. We investigate the fixed point of this system of bargaining equations and prove various desirable for this solution concept, including (i) existence, (ii) uniqueness, (iii) efficiency, (iv) membership in the core, (v) strict monotonicity, (vi) polynomial-time computability to any given accuracy. Finally, we present numerical evidence that asynchronous dynamics with randomly ordered updates always converges to the fixed point, indicating that the fixed point shares might arise from decentralized bargaining amongst agents on the trade network.

The Approximability of the Binary Paintshop Problem 2013
With Anupam Gupta, Viswanath Nagarajan, Rishi Saket, and Baruch Schieber. In 16th APPROX, 2013. [ps]

In the Binary Paintshop problem, there are $ m$ cars appearing in a sequence of length $2m$, with each car occurring twice. Each car needs to be colored with two colors. The goal is to choose for each car, which of its occurrences receives either color, so as to minimize the total number of color changes in the sequence. We show that the Binary Paintshop problem is equivalent (up to constant factors) to the Minimum Uncut problem, under randomized reductions. By derandomizing this reduction for hard instances of the Minimun Uncut problem arising from the Unique Games Conjecture, we show that the Binary Paintshop problem is $\omega(1)$-hard to approximate (assuming the UGC). This answers an open question from Eppinger et al (2006), Meunier and Sebo (2009) and Andres and Hochstattler (2011).

Near-Optimal Algorithms for Online Matrix Prediction 2012
With Elad Hazan and Shai Shalev-Shwartz. In 25th COLT, 2012. [ps]

In several online prediction problems of recent interest the comparison class is composed of matrices with bounded entries. For example, in the online max-cut problem, the comparison class is matrices which represent cuts of a given graph and in online gambling the comparison class is matrices which represent permutations over n teams. Another important example is online collaborative filtering in which a widely used comparison class is the set of matrices with a small trace norm. In this paper we isolate a property of matrices, which we call $(\beta,\tau)$-decomposability, and derive an efficient online learning algorithm, that enjoys a regret bound of $\tilde{O}(\sqrt{\beta \tau T})$ for all problems in which the comparison class is composed of $(\beta,\tau)$-decomposable matrices. By analyzing the decomposability of cut matrices, triangular matrices, and low trace-norm matrices, we derive near optimal regret bounds for online max-cut, online gambling, and online collaborative filtering. In particular, this resolves (in the affirmative) an open problem posed by Abernethy (2010) and Kleinberg et al (2010). Finally, we derive lower bounds for the three problems and show that our upper bounds are optimal up to logarithmic factors. In particular, our lower bound for the online collaborative filtering problem resolves another open problem posed by Shamir and Srebro (2011).

Projection-free Online Learning 2012
With Elad Hazan. In 29th ICML, 2012. [ps]

The computational bottleneck in applying online learning to massive data sets is usually the projection step. We present efficient online learning algorithms that eschew projections in favor of much more efficient linear optimization steps using the Frank-Wolfe technique. We obtain a range of regret bounds for online convex optimization, with better bounds for specific cases such as stochastic online smooth convex optimization.

Besides the computational advantage, other desirable features of our algorithms are that they are parameter-free in the stochastic case and produce sparse decisions. We apply our algorithms to computationally intensive applications of collaborative filtering, and show the theoretical improvements to be clearly visible on standard datasets.

Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization 2012
With Haim Avron, Shiva Prasad Kasiviswanathan, and Vikas Sindhwani. In 29th ICML, 2012. [ps]

We describe novel subgradient methods for a broad class of matrix optimization problems involving nuclear norm regularization. Unlike existing approaches, our method executes very cheap iterations by combining low-rank stochastic subgradients with efficient incremental SVD updates, made possible by highly optimized and parallelizable dense linear algebra operations on small matrices. Our practical algorithms always maintain a low-rank factorization of iterates that can be conveniently held in memory and efficiently multiplied to generate predictions in matrix completion settings. Empirical comparisons confirm that our approach is highly competitive with several recently proposed state-of-the-art solvers for such problems.

Contextual Bandit Learning with Predictable Rewards 2012
With Alekh Agarwal, Miroslav Dudik, John Langford and Robert E. Schapire. In 15th AISTATS, 2012. [ps]

Contextual bandit learning is a reinforcement learning problem where the learner repeatedly receives a set of features (context), takes an action and receives a reward based on the action and context. We consider this problem under a realizability assumption: there exists a function in a (known) function class, always capable of predicting the expected reward, given the action and context. Under this assumption, we show three things. We present a new algorithm - Regressor Elimination - with a regret similar to the agnostic setting (i.e. in the absence of realizability assumption). We prove a new lower bound showing no algorithm can achieve superior performance in the worst case even with the realizability assumption. However, we do show that for any set of policies (mapping contexts to actions), there is a distribution over rewards (given context) such that our new algorithm has constant regret unlike the previous approaches.

Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction. 2011
With Elad Hazan. In 27th NIPS, 2011. [ps]

We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in (Abernethy and Rakhlin, 2009), which is parameterized by a scalar $\alpha$. We prove that the regret of Newtron is O(log T) when $\alpha$ is a constant that does not vary with horizon T, and at most O(T2/3) if $\alpha$ is allowed to increase to infinity with T. For α = O(log T), the regret is bounded by O(√T), thus solving the open problem of Kakade et al (2008) and Abernethy and Rakhlin (2009). Our algorithm is based on a novel application of the online Newton method (Hazan et al, 2007). We test our algorithm and show it to perform well in experiments, even when $\alpha$ is a small constant.

Efficient optimal learning for contextual bandits. 2011
With Miroslav Dudik, Daniel Hsu, Nikos Karampatziakis, John Langford, Lev Reyzin and Tong Zhang. In 27th UAI, 2011. [ps]

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time polylog(N), where N is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.

Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. 2011
With Elad Hazan. In 24th COLT, 2011. [ps]

We give a novel algorithm for stochastic strongly-convex optimization in the gradient oracle model which returns an O(1/T)-approximate solution after T gradient updates. This rate of convergence is optimal in the gradient oracle model. This improves upon the previously known best rate of O(log(T)/T)), which was obtained by applying an online strongly-convex optimization algorithm with regret O(log(T)) to the batch setting.

We complement this result by proving that any algorithm has expected regret of Ω(log(T)) in the online stochastic strongly-convex optimization setting. This lower bound holds even in the full-information setting which reveals more information to the algorithm than just gradients. This shows that any online-to-batch conversion is inherently suboptimal for stochastic strongly-convex optimization. This is the first formal evidence that online convex optimization is strictly more dicult than batch stochastic convex optimization.

Who Moderates the Moderators? Crowdsourcing Abuse Detection in User-generated Content 2011
With Arpita Ghosh and R. Preston McAfee. In 12th EC, 2011. [ps]

A large fraction of user-generated content on the Web, such as posts or comments on popular online forums, consists of abuse or spam. Due to the volume of contributions on popular sites, a few trusted moderators cannot identify all such abusive content, so viewer ratings of contributions must be used for moderation. But not all viewers who rate content are trustworthy and accurate. What is a principled approach to assigning trust and aggregating user ratings, in order to accurately identify abusive content?

In this paper, we introduce a framework to address the problem of moderating online content using crowdsourced ratings. Our framework encompasses users who are untrustworthy or inaccurate to an unknown extent - that is, both the content and the raters are of unknown quality. With no knowledge whatsoever about the raters, it is impossible to do better than a random estimate. We present efficient algorithms to accurately detect abuse that only require knowledge about the identity of a single `good' agent, who rates contributions accurately more than half the time. We prove that our algorithm can infer the quality of contributions with error that rapidly converges to zero as the number of observations increases; we also numerically demonstrate that the algorithm has very high accuracy for much fewer observations. Finally, we analyze the robustness of our algorithms to manipulation by adversarial or strategic raters, an important issue in moderating online content, and quantify how the performance of the algorithm degrades with the number of manipulating agents.

Cross-Validation and Mean-Square Stability 2011
With Ravi Kumar and Sergei Vassilvitskii. In 2nd ICS 2011. [ps]

k-fold cross validation is a popular practical method to get a good estimate of the error rate of a learning algorithm. Here, the set of examples is first partitioned into k equal-sized folds. Each fold acts as a test set for evaluating the hypothesis learned on the other k-1 folds. The average error across the k hypotheses is used as an estimate of the error rate. Although widely used, especially with small values of k (such as 10), the technique has heretofore resisted theoretical analysis. With only sanity-check bounds known, there is not a compelling reason to use the k-fold cross-validation estimate over a simpler holdout estimate. The complications stem from the fact that the k distinct estimates have intricate correlations between them.

Combinatorial Approximation Algorithms for MaxCut using Random Walks 2011
With C. Seshadhri. In 2nd ICS 2011. arXiv version. [ps]
We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant b > 1.5, there is an O(nb) algorithm that outputs a (0.5+δ) approximation for Maxcut, where δ = δ(b) is some positive constant.

One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex i and a conductance parameter φ, unless a random walk of length l = O(log n) starting from i mixes rapidly (in terms of φ and l), we can find a cut of conductance at most φ close to the vertex. The work done per vertex found in the cut is sublinear in n.

Non-Stochastic Bandit Slate Problems 2010
With Lev Reyzin and Robert E. Schapire. In 24th NIPS 2010. [ps]

We consider bandit problems, motivated by applications in online advertising and news story selection, in which the learner must repeatedly select a slate, that is, a subset of size s from K possible actions, and then receives rewards for just the selected actions. The goal is to minimize the regret with respect to total reward of the best slate computed in hindsight. We consider unordered and ordered versions of the problem, and give efficient algorithms which have regret O(√T), where the constant depends on the specific nature of the problem. We also consider versions of the problem where we have access to a number of policies which make recommendations for slates in every round, and give algorithms with O(√T) regret for competing with the best such policy as well. We make use of the technique of relative entropy projections combined with the usual multiplicative weight update algorithm to obtain our algorithms.

Learning rotations with little regret 2010
With Elad Hazan and Manfred K. Warmuth. In 23rd COLT 2010. Corrigendum. [ps]

We describe online algorithms for learning a rotation from pairs of unit vectors in Rn. We show that the expected regret of our online algorithm compared to the best fixed rotation chosen offline is O(√(nL)), where L is the loss of the best rotation. We also give a lower bound that proves that this expected regret bound is optimal within a constant factor. This resolves an open problem posed in COLT 2008. Our online algorithm for choosing a rotation matrix in each trial is based on the Follow-The-Perturbed-Leader paradigm. It adds a random spectral perturbation to the matrix characterizing the loss incurred so far and then chooses the best rotation matrix for that loss. We also show that any deterministic algorithm for learning rotations has Ω(T) regret in the worst case.

Corrigendum: There is an unfortunate error in our paper "Learning rotations with little regret" which appeared in COLT 2010. A fix is posted here as a corrigendum to our paper.

Online Submodular Minimization 2009
With Elad Hazan. In 23rd NIPS 2009. [ps]

We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and bandit settings.

On Stochastic and Worst-case Models for Investing 2009
With Elad Hazan. In 23rd NIPS 2009. [ps]

In practice, most investing is done assuming a probabilistic model of stock price returns known as the Geometric Brownian Motion (GBM). While it is often an acceptable approximation, the GBM model is not always valid empirically. This motivates a worst-case approach to investing, called universal portfolio management, where the objective is to maximize wealth relative to the wealth earned by the best fixed portfolio in hindsight.

In this paper we tie the two approaches, and design an investment strategy which is universal in the worst-case, and yet capable of exploiting the mostly valid GBM model. Our method is based on new and improved regret bounds for online convex optimization with exp-concave loss functions.

Better Algorithms for Benign Bandits 2009
With Elad Hazan. In 20th SODA 2009. Accepted to Journal of Machine Learning Research. [ps]

The online multi-armed bandit problem and its generalizations are repeated decision making problems, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. The difference in these costs is known as the regret of the algorithm. The term bandit refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information.

Perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining Õ(√T) regret was discovered in this setting.

In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of Õ(√Q), where Q is the total variation in the cost functions. This regret bound, previously conjectured to hold in the full information case, shows that it is possible to incur much less regret in a slowly changing environment even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling.

Noise Tolerance of Expanders and Sublinear Expander Reconstruction 2008
With Yuval Peres and C. Seshadhri. In 49th FOCS, 2008. [ps]

We consider the problem of online sublinear expander reconstruction and its relation to random walks in "noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph G, we want to convert this graph into a bounded-degree expander G' changing G as little as possible. The graph G' will be output by a distributed filter: this is a sublinear time procedure that given a query vertex, outputs all its neighbors in G', and can do so even in a distributed manner, ensuring consistency in all the answers.

One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We also design sublinear time procedures to distinguish vertices of the expander part from those in the noise part, and use this procedure in the reconstruction algorithm.

Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs 2008
With Elad Hazan. In 21st COLT 2008. Invited to Machine Learning Journal special issue for COLT 2008 (80(2-3), 165-188, 2010). [ps]

Prediction from expert advice is a fundamental problem in machine learning. A major pillar of the field is the existence of learning algorithms whose average loss approaches that of the best expert in hindsight (in other words, whose average regret approaches zero). Traditionally the regret of online algorithms was bounded in terms of the number of prediction rounds.

Cesa-Bianchi, Mansour and Stoltz posed the question whether it is be possible to bound the regret of an online algorithm by the variation of the observed costs. In this paper we resolve this question, and prove such bounds in the fully adversarial setting, in two important online learning scenarios: prediction from expert advice, and online linear optimization.

An Expansion Tester for Bounded Degree Graphs 2008
With C. Seshadhri. In 35th ICALP 2008. Earlier version: ECCC Report TR07-076. Accepted to SIAM Journal on Computing. [ps]

We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [GR]. We give a property tester that given a graph with degree bound \(d\), an expansion bound $\alpha$, and a parameter $ \varepsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and rejects it with high probability if it is $\varepsilon$-far from any graph with expansion $\alpha'$ with degree bound $ d$, where $\alpha' < \alpha$ is a function of $\alpha$. For edge expansion, we obtain $\alpha' = \Omega(\alpha^2/d)$. In either case, the algorithm runs in time $ O(n^{(1+\mu)/2}d^2/ \varepsilon\alpha^2)$ for any given constant $\mu > 0$.

The Uniform Hardcore Lemma via Approximate Bregman Projections 2007
With Moritz Hardt and Boaz Barak. In 20th SODA 2009. Earlier version: ECCC Report TR07-131. [ps]

We give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. Our result follows from the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. Informally stated, our result is the following: suppose we fix a family of boolean functions. Assume there is an efficient algorithm which for every input length and every smooth distribution (i.e. one that doesn't assign too much weight to any single input) over the inputs produces a circuit such that the circuit computes the boolean function noticeably better than random. Then, there is an efficient algorithm which for every input length produces a circuit that computes the function correctly on almost all inputs.

Our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. The algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate Bregman projection. Bregman projections are widely used in convex optimization and machine learning. We present an algorithm which efficiently approximates the Bregman projection onto the set of high density measures when the Kullback-Leibler divergence is used as a distance function. Our algorithm has a logarithmic runtime over any domain provided that we can efficiently sample from this domain. High density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. Hence, our technique may be of independent interest.

Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria 2007
With Elad Hazan. In 21st NIPS, 2007. [ps]

We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational players are modeled by players using no regret algorithms, which guarantee that their payoff in the long run is close to the maximum they could hope to achieve by consistently deviating from the algorithm's suggested action.

We show that for a given set of deviations over the strategy set of a player, it is possible to efficiently approximate fixed points of a given deviation if and only if there exist efficient no regret algorithms resistant to the deviations. Further, we show that if all players use a no regret algorithm, then the empirical distribution of their plays converges to an equilibrium.

Efficient Algorithms using the Multiplicative Weights Update Method 2007
Ph.D. thesis. Princeton Tech Report TR-804-07. [ps]

Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is very high. Designing simpler and more efficient algorithms is important for practical impact.

In this thesis, we explore applications of the Multiplicative Weights method in the design of efficient algorithms for various optimization problems. This method, which was repeatedly discovered in quite diverse fields, is an algorithmic technique which maintains a distribution on a certain set of interest, and updates it iteratively by multiplying the probability mass of elements by suitably chosen factors based on feedback obtained by running another algorithm on the distribution.

We present a single meta-algorithm which unifies all known applications of this method in a common framework. Next, we generalize the method to the setting of symmetric matrices rather than real numbers. We derive the following applications of the resulting Matrix Multiplicative Weights algorithm:

  1. The first truly general, combinatorial, primal-dual method for algorithms for semidefinite programming. Using these techniques, we obtain significantly faster algorithms for obtaining O(√log(n)) approximations to various graph partitioning problems, such as Sparsest Cut, Balanced Separator in both directed and undirected weighted graphs, and constraint satisfaction problems such as Min UnCut and Min 2CNF Deletion.
  2. An Õ(n3) time derandomization of the Alon-Roichman construction of expanders using Cayley graphs. The algorithm yields a set of O(log n) elements which generates an expanding Cayley graph in any group of n elements.
  3. An Õ(n3) time deterministic O(log n) approximation algorithm for the quantum hypergraph covering problem.
  4. An alternative proof of a result of Aaronson that the gamma-fat-shattering dimension of quantum states on n qubits is O(n/gamma2).

Using our framework for the classical Multiplicative Weights Update method, we derive the following algorithmic applications:

  1. Fast algorithms for approximately solving several families of semidefinite programs which beat interior point methods. Our algorithms rely on eigenvector computations, which are very efficient in practice compared to the Cholesky decompositions needed by interior point methods. We also give a matrix sparsification algorithm to speed up the eigenvector computation using the Lanczos iteration.
  2. O(√log(n)) approximation to the Sparsest Cut and the Balanced Separator problems in undirected weighted graphs in Õ(n2) time by embedding expander flows in the graph. This improves upon the previous Õ(n4.5) time algorithm of Arora, Rao, and Vazirani, which was based on semidefinite programming.

A Combinatorial, Primal-Dual approach to Semidefinite Programs 2007
With Sanjeev Arora. In 39th STOC, 2007. [ps]

Semidefinite programs (SDP) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as Sparsest Cut and Balanced Separator in undirected and directed weighted graphs, and the Min UnCut problem, this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones.

Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release 2007
With Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Frank McSherry and Kunal Talwar. In 26th PODS, 2007. [ps]
The contingency table is a work horse of official statistics, the format of reported data for the US Census, Bureau of Labor Statistics, and the Internal Revenue Service. In many settings such as these privacy is not only ethically mandated, but frequently legally as well. Consequently there is an extensive and diverse literature dedicated to the problems of statistical disclosure control in contingency table release. However, all current techniques for reporting contingency tables fall short on at least one of privacy, accuracy, and consistency (among multiple released tables). We propose a solution that provides strong guarantees for all three desiderata simultaneously.

Our approach can be viewed as a special case of a more general approach for producing synthetic data: Any privacy-preserving mechanism for contingency table release begins with raw data and produces a (possibly inconsistent) privacy-preserving set of marginals. From these tables alone -- and hence without weakening privacy -- we will find and output the "nearest" consistent set of marginals. Interestingly, this set is no farther than the tables of the raw data, and consequently the additional error introduced by the imposition of consistency is no more than the error introduced by the privacy mechanism itself.

The privacy mechanism of Dwork, McSherry, Nissim, Smith '06 gives the strongest known privacy guarantees, with very little error. Combined with the techniques of the current paper, we therefore obtain excellent privacy, accuracy, and consistency among the tables. Moreover, our techniques are surprisingly efficient.

Our techniques apply equally well to the logical cousin of the contingency table, the OLAP cube.

A Fast Random Sampling Algorithm for Sparsifying Matrices 2006
With Sanjeev Arora and Elad Hazan. In 10th RANDOM 2006. [ps]

We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the Chernoff-Hoeffding bounds. Despite the simplicity, the approximation is comparable and sometimes better than previous work.

Our algorithm computes the sparse matrix approximation in a single pass over the data. Further, most of the entries in the output matrix are quantized, and can be succinctly represented by a bit vector, thus leading to much savings in space.

Efficient Aggregation Algorithms for Probabilistic Data 2006
With T. S. Jayram and Erik Vee. In 18th SODA 2007. [ps]

We study the problem of computing aggregation operators on probabilistic data in an I/O efficient manner. Algorithms for aggregation operators such as SUM, COUNT, AVG, and MIN/MAX are crucial to applications on probabilistic databases. We give a generalization of the classical data stream model to handle probabilistic data, called probabilistic streams, in order to analyze the I/O-requirements of our algorithms. Whereas the algorithms for SUM and COUNT turn out to be simple, the problem is harder for both AVG and MIN/MAX. Although data stream algorithms typically use randomness, all of the algorithms we present are deterministic.

For MIN and MAX, we obtain efficient one-pass data stream algorithms for estimating each of these quantities with relative accuracy (1 + ε), using constant update time per element and O((log R)/ε) space, where each element has a value between 1 and R. For AVG, we present a new data stream algorithm for estimating its value to a relative accuracy (1 + &epsilon) in O(log n) passes over the data with O((log2 n)/ε) space and update time O((log n)/ε) per element. On the other hand, we prove a space lower bound of Ω(n) for any exact one-pass deterministic data stream algorithm. Complementing this result, we also present an O(n(log2n))-time exact deterministic algorithm which uses O(n) space (thus removing the data-streaming restriction), improving dramatically on the previous O(n3)-time algorithm. Our algorithms for AVG involve a novel technique based on generating functions and numerical integration, which may be of independent interest.

Finally, we provide an experimental analysis and show that our algorithms, coupled with additional heuristics, have excellent performance over large data sets.

Logarithmic Regret Algorithms for Online Convex Optimization 2006
With Elad Hazan and Amit Agarwal. In 19th COLT 2006 (this version in collaboration with Adam Kalai also). Invited to Machine Learning Journal special issue for COLT 2006 (69(2-3), 169-192, 2007). [ps]

In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., chooses a sequence of points in Euclidean space, from a fixed feasible set. After each point is chosen, it encounters a sequence of (possibly unrelated) convex cost functions. Zinkevich (2003) introduced this framework, which models many natural repeated decision-making problems and generalizes many existing problems such as Prediction from Expert Advice and Cover's Universal Portfolios. Zinkevich showed that a simple online gradient descent algorithm achieves additive regret O(√T), for an arbitrary sequence of T convex cost functions (of bounded gradients), with respect to the best single decision in hindsight.

In this paper, we give algorithms that achieve regret O(log(T)) for an arbitrary sequence of strictly convex functions (with bounded first and second derivatives). This mirrors what has been done for the special cases of prediction from expert advice by Kivinen and Warmuth (1999), and Universal Portfolios by Cover (1991). We propose several algorithms achieving logarithmic regret, which besides being more general are also much more efficient to implement.

The main new ideas give rise to an efficient algorithm based on the Newton method for optimization, a new tool in the field. Our analysis shows a surprising connection to follow-the-leader method, and builds on the recent work of Agarwal and Hazan (2005). We also analyze other algorithms, which tie together several different previous approaches including follow-the-leader, exponential weighting, Cover's algorithm and gradient descent.

Algorithms for Portfolio Management based on the Newton Method 2006
With Amit Agarwal, Elad Hazan, and Robert Schapire. In 23rd ICML, 2006. [ps]

We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio determined in hindsight. These algorithms are the first to combine optimal logarithmic regret bounds with efficient deterministic computability. They are based on the Newton method for offline optimization which, unlike previous approaches, exploits second order information. After analyzing the algorithm using the potential function introduced by Agarwal and Hazan, we present extensive experiments on actual financial data. These experiments confirm the theoretical advantage of our algorithms, which yield higher returns and run considerably faster than previous algorithms with optimal regret. Additionally, we perform financial analysis using mean-variance calculations and the Sharpe ratio.

A Variation on SVD Based Image Compression 2006
With Abhiram Ranade and Srikanth S. M. In WCVGIP, 2006. Journal paper in Image and Vision Computing 25(6): 771-777 (2007). [ps]

We present a variation to the well studied SVD based image compression technique. Our variation can be viewed as a preprocessing step in which the input image is permuted as per a fixed, data independent permutation, after which it is fed to the standard SVD algorithm. Likewise, our decompression algorithm can be viewed as the standard SVD algorithm followed by a postprocessing step which applies the inverse permutation.

On experimenting with standard images we show that our method performs substantially better than the standard method. Typically, for any given compression quality, our method needs about 30% fewer singular values and vectors to be retained. We also present a bit allocation scheme and show that our method also performs better than the more familiar Discrete Cosine Transform (DCT).

We show that the original SVD algorithm as well as our variation, can be viewed as instances of the Karhunen- Loeve transform (KLT). In fact, we observe that there is a whole family of variations possible by choosing different parameter values while applying the KLT. We present heuristic arguments to show that our variation is likely to yield the best compression of all these. We also present experimental evidence which appears to justify our analysis.

Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update method 2005
With Sanjeev Arora and Elad Hazan. In 46th FOCS, 339-348, 2005. [ps]

Semidefinite programming (SDP) relaxations appear in many recent approximation algorithms but the only general technique for solving such SDP relaxations is via interior point methods. We use a Lagrangian-relaxation based technique (modified from the papers of Plotkin, Shmoys, and Tardos (PST), and Klein and Lu) to derive faster algorithms for approximately solving several families of SDP relaxations. The algorithms are based upon some improvements to the PST ideas --which lead to new results even for their framework-- as well as improvements in approximate eigenvalue computations by using random sampling.

The Multiplicative Weights Update Method: A Meta-Algorithm and Applications 2012
With Sanjeev Arora and Elad Hazan. In Theory of Computing Volume 8, pages 121-164. [ps]

Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analyses are usually very similar and rely on an exponential potential function.

In this survey we present a simple meta-algorithm that unifies many of these disparate algorithms and derives them as simple instantiations of the meta-algorithm. We feel that since this meta-algorithm and its analysis are so simple, and its applications so broad, it should be a standard part of algorithms courses, like "divide and conquer".

Analysis and Algorithms for Content-based Event Matching 2005
With Elad Hazan, Fengyun Cao and Jaswinder Pal Singh. In 4th DEBS, 2005. [ps]

Content-based event matching is an important problem in large-scale event-based publish/subscribe systems. However, open questions remain in analysis of its difficulty and evaluation of its solutions. This paper makes a few contributions toward analysis, evaluation and development of matching algorithms. First, based on a simplified yet generic model, we give a formal proof of hardness of matching problem by showing its equivalence to the notoriously hard Partial Match problem. Second, we compare two major existing matching approaches and show that countingbased algorithms are likely to be more computationally expensive than tree-based algorithms in this model. Third, we observe an important, prevalent characteristic of real-world publish/subscribe events, and develop a new matching algorithm called RAPIDMatch to exploit it. Finally, we propose a new metric for evaluation of matching algorithms. We analyze and evaluate RAPIDMatch using both the traditional and new metrics proposed. Results show that RAPIDMatch achieves large performance improvement over the tree-based algorithm under certain publish/subscribe scenarios.

O(√log n) approximation to SPARSEST CUT in Õ(n²) time 2004
With Sanjeev Arora and Elad Hazan. In 45th FOCS, 238-247, 2004. [ps]

We show how to compute O(√log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their algorithm uses semidefinite programming and required Õ(n4.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani.

Approximating Quadratic Programs with Positive Semidefinite Constraints 2004
With Elad Hazan. Princeton Tech Report TR-746-06. [ps]

We describe a polynomial time approximation algorithm to the problem of maximizing a quadratic form subject to quadratic constraints specified by PSD matrices. A special case, that has applications for clustering, is optimizing quadratic forms over the unit cube.

Approximation algorithms with similar guarantees are known, and there is evidence that this factor is optimal. The following analysis is particularly simple.


Copy = Wrong. Design by Arnab Nandi.