Home . Bio . Publications . Code & Data

Publications

Conference and Journal papers

• On Stochastic and Worst-case Models for Investing. (with S. Kale) To appear NIPS 2009.
  In practice, most investing is done assuming a probabilistic model of stock price returns known as the Geometric Brownian Motion (GBM). While a very good 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.

• Online Submodular Minimization. (with S. Kale) To appear NIPS 2009.
  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.

• An Efficient Interior-Point Method for Minimum-Regret Learning in Online Convex Optimization. (with N. Megiddo) To appear NIPS 2009.
  A new algorithm for regret minimization in online convex optimization is described. The regret of the algorithm after T time periods is almost the minimum possible. However, in n-dimensional space, during each iteration the new algorithm essentially solves a system of linear equations of order n, whereas previous algorithms have to solve some constrained convex optimization problem in n dimensions and possibly many constraints. Thus, the new algorithm improves running time by a factor of at least √ n, and much more for nontrivial domains.

• Efficient learning algorithms for changing environments. (with C. Seshadhri) The 26th International Conference on Machine Learning (ICML 2009).
  We describe a series of reductions, based upon data streaming techniques, which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead. Using this method, we obtain efficient low adaptive-regret algorithms for the problem of general online convex optimization.

• How hard is it to approximate the best Nash equilibrium? (with Robert Krauthgamer) ACM-SIAM Symposium on Discrete Algorithms (SODA09).
  The quest for a PTAS for Nash equilibrium in a two-player game is a major open question in Algorithmic Game Theory. We show that the optimization version of problem, namely, finding in a two-player game an approximate equilibrium achieving large social welfare is unlikely to have a polynomial time algorithm. Technically, our result is a reduction from a seemingly unrelated yet notoriously difficult problem in modern Combinatorics, of finding a planted (but hidden) clique in a random graph.

• Better Algorithms for Benign Bandits. (with Satyen Kale) ACM-SIAM Symposium on Discrete Algorithms (SODA09).
  We describe a novel algorithm for the classical Multi-Armed-Bandit problem and its generalizations, which attains scenario-dependent regret bounds thereby improving the state of the art. The new method attains regret 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.

• An Efficient Algorithm for Bandit Linear Optimization. (with Jacob Abernethy and Alexander Rakhlin) The 21st Annual Conference on Learning Theory (COLT 2008).
  We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal √T regret. The setting is a natural generalization of the non-stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of recent papers. We show how the difficulties encountered by previous approaches are overcome by the use of a self-concordant potential function.
  IBM 2008 Pat Goldberg Memorial Best Paper Award
  COLT 2008 Machine Learning Journal Best Student Paper Award
  

• Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs. (with Satyen Kale) The 21st Annual Conference on Learning Theory (COLT 2008). Invited to special issue of Machine Learning Journal.
  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 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.

• Sparse Approximate Solutions to Semidefinite Programs. LATIN 2008.
  We analyze a generalization of the Frank-Wolfe algorithm for approximately maximizing a concave function over the bounded semi-definite cone which produces sparse solutions (sparsity for SDP corresponds to low rank matrices).
  

• Adaptive Online Gradient Descent. (with Peter Bartlett and Alexander Rakhlin) Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, (NIPS) 2007.
  We study the rates of growth of the regret in online convex optimization, and propose an algorithm which interpolates between previous regret bounds for linear and strongly convex loss functions, achieving intermediate rates between root(T) and logarithmic in T.
  

• Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria. (with Satyen Kale) Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, (NIPS) 2007.
  We study some general notions of game-theoretic equilibria, and show that it is possible to efficiently approximate fixed points corresponding to certain equilibria if and only if there exist efficient no regret algorithms. (the interested reader should also check out the recent Stoltz and Lugosi paper)
  

• Online Learning with Prior Information.(with Nimrod Megiddo) Proceedings of 20th Annual Conference on Learning Theory, (COLT) 2007.
  We extend the standard so-called ``experts`` framework by allowing an experts algorithm to rely on state information, namely, partial information about the future which is revealed to the decision maker before the latter chooses an action. This extension is very natural in prediction problems. For illustration, an experts algorithm, which is supposed to predict whether the next day will be rainy, can be extended to predicting the same given the current temperature. We introduce new algorithms, which attain almost optimal performance in the new framework, and apply to more general settings than variants of regression that have been considered in the statistics literature.
  

• Logarithmic Regret Algorithms for Online Convex Optimization. (with Amit Agarwal and Satyen Kale) In Machine Learning Volume 69 , Issue 2-3 Pages: 169 - 192 (December 2007)
  We present new algorithms for the problem of online convex optimization, that use second derivatives, analogous to Newton's method. These new algorithms attain logarithmic regret (versus polynomial regret of other methods) and are computationally efficient. We also show a surprising connection to the intuitive "follow the leader" approach, and prove on the affirmative the conjecture about universal portfolios made by Ordentlich and independently by Kalai and Vempala, that the FTL method attains low regret for certain convex loss functions. This paper is a journal version, combining results from a conference paper that appeared in COLT 2006 (with Adam Kalai, Satyen Kale and Amit Agarwal) and a ECCC report (with Amit Agarwal).

• Algorithms for Portfolio Management based on the Newton Method. (with Amit Agarwal, Satyen Kale and Robert E. Schapire) ICML 2006: 23rd International Conference on Machine Learning.
  We experimentally study the application of the on-line algorithms proposed in the above paper to portfolio management.

• A Fast Random Sampling Algorithm for Sparsifying Matrices. (with Sanjeev Arora and Satyen Kale) In APPROX 2006
  We present a simple procedure for sparsifying matrices. Unlike previous results, our performance guarantees can be proved with nothing more than simple Chernoff bounds.

• Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update Method. In Proceedings of the 46th Annual Symposium on the Foundations of Computer Science, (FOCS) 2005 (with Sanjeev Arora and Satyen Kale)
  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.

• On Non-Approximability for Quadratic Programs (with Sanjeev Arora, Eli Berger, Guy Kindler, and Muli Safra.) In Proceedings of the 46th Annual Symposium on the Foundations of Computer Science, (FOCS) 2005
  This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x in {-1,1}^n that maximizes x^T M x. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within a certain constant factor. We show that it is quasi-NP-hard to approximate to a poly-logarithmic factor. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be Theta(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is tight up to a log(log(n)) factor, essentially answering one of the open problems of Alon et al.

• HAPLOFREQ - Estimating Haplotype Frequencies Efficiently(with Eran Halperin) Special issue of Journal of Computational Biology,March 2006, Vol. 13, No. 2: 481-500. Extended abstract appeared in RECOMB 2005.
  This paper gives efficient algorithms for a computational problem in bio-informatics. We give theoretical analysis as well as experiments which show the algorithm's advantage over previous methods.

• (√(log n)) approximation to SPARSEST CUT can be found in Õ(n²) time. (with Sanjeev Arora and Satyen Kale.) In Proc. 45th FOCS, 238-247, 2004. Submitted to SIAM Journal on Computing.
  We show how to compute O(√log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in Õ(n²) time, improving upon the algorithm of Arora, Rao and Vazirani (2004) which uses semidefinite programming and required Õ(n^4.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs.

• On the Complexity of Approximating k-Set Packing. (with Muli Safra and Oded Schwartz.) In Computational Complexity 15(1): 20-39 (2006). Extended abstract appeared in APPROX 2003
  We study the fundamental computational problem of set packing in bounded-degree graphs, and prove near-optimal lower bounds.