Elad Hazan

Publications

Most recent

• Efficient learning algorithms for changing environments. (with C. Seshadhri) To appear in 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) In SODA 2009.
  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) In SODA 2009.
  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 {\em regret} of the algorithm. The term {\em 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 $\tilde{O}(\sqrt{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 $\tilde{O}(\sqrt{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.

Conference and Journal papers

• An Efficient Algorithm for Bandit Linear Optimization. (with Jacob Abernethy and Alexander Rakhlin) In COLT 2008.
  We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal $O^*(\sqrt{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.

• Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs. (with Satyen Kale) In COLT 2008.
  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) 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) 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) In 23rd ICML, 2006.
  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.
  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.

Technical Reports

• The "Arrangement Method" for Linear Programming is Equivalent to the Phase-One Method. (with N. Megiddo) IBM Research Report, February 2007.

• Approximate Convex Optimization by Online Game Playing.
  This paper describes a general framework for converting online game playing algorithms into constrained convex optimization algorithms. This framework allows us to convert the well-established bounds on regret of online algorithms to prove convergence in the offline setting. The resulting algorithms are very simple to implement and analyze, and for some scenarios attain better rate of convergence than previously known.
  NOTE: The link above points to a short summary. The full version of the paper is available here..

• Approximating Quadratic Programs with Positive Semidefinite Constraints. (with Satyen Kale) Princeton University Tech Report TR-746-06.
  We describe a simple 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.

• Analysis and Algorithms for Content-based Event Matching. (with Satyen Kale, Fengyun Cao, and J.P Singh.) In 4^th DEBS, 2005

Thesis and Surveys

• The Multiplicative Weights Update Method: A Meta-Algorithm and Applications. (with Sanjeev Arora and Satyen Kale)
  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 analysis are usually very similar and rely on an exponential potential function. We present a simple meta algorithm that unifies these disparate algorithms and drives them as simple instantiations of the meta algorithm.

• Efficient Algorithms for Online Convex Optimization and Their Applications. Phd Thesis, Princeton University, Sept. 2006
  

Contact Info

Projects

• data_490_1000 - This is the data set used in the experimental paper above (ICML 2006). It includes 1000 consecutive trading day prices (roughly 5 years) for 490 stocks. The file is a MATLAB binary.

• NYSE - This is the "classic" data set used in the original Cover experiments, and retested in subsequent paper.