Elad Hazan

Princeton University

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Naman Agarwal

Indian Institute of Technology Bombay

Satyen Kale

Google (United States)

Tomer Koren

Tel Aviv University

Cyril Zhang

Microsoft Research (United Kingdom)

Brian Bullins

Toyota Technological Institute at Chicago

Dan Garber

Technion – Israel Institute of Technology

Karan Singh

Chandigarh University

Sham M. Kakade

Harvard University Press

Sanjeev Arora

University of New Mexico

Udaya Ghai

Princeton University

Cooperative Institutions

Princeton University

Google (United States)

Massachusetts Institute of Technology

University of California, Berkeley

Stanford University

Technion – Israel Institute of Technology

Tel Aviv University

Microsoft Research (United Kingdom)

Microsoft (United States)

Institute for Advanced Study

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Projection-free Adaptive Regret with Membership Oracles

arXiv (Cornell University) (2022)

Lu Zhou Nataly Brukhim Paula Gradu Elad Hazan

In the framework of online convex optimization, most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. To tackle this problem HK12 proposed the study of projection-free methods that replace projections with less expensive computations. The most common approach is based on the Frank-Wolfe method, that uses linear optimization computation in lieu of projections. Recent work by GK22 gave sublinear adaptive regret guarantees with projection free algorithms based on the Frank Wolfe approach. In this work we give projection-free algorithms that are based on a different technique, inspired by Mhammedi22, that replaces projections by set-membership computations. We propose a simple lazy gradient-based algorithm with a Minkowski regularization that attains near-optimal adaptive regret bounds. For general convex loss functions we improve previous adaptive regret bounds from $O(T^{3/4})$ to $O(\sqrt{T})$, and further to tight interval dependent bound $\tilde{O}(\sqrt{I})$ where $I$ denotes the interval length. For strongly convex functions we obtain the first poly-logarithmic adaptive regret bounds using a projection-free algorithm.

Sublinear function

10.48550/arxiv.2211.12638

Cite

Citations (2)

Logistic Regression: Tight Bounds for Stochastic and Online Optimization

arXiv (Cornell University) (2014)

Elad Hazan Tomer Koren Kfir Y. Levy

The logistic loss function is often advocated in machine learning and statistics as a smooth and strictly convex surrogate for the 0-1 loss. In this paper we investigate the question of whether these smoothness and convexity properties make the logistic loss preferable to other widely considered options such as the hinge loss. We show that in contrast to known asymptotic bounds, as long as the number of prediction/optimization iterations is sub exponential, the logistic loss provides no improvement over a generic non-smooth loss function such as the hinge loss. In particular we show that the convergence rate of stochastic logistic optimization is bounded from below by a polynomial in the diameter of the decision set and the number of prediction iterations, and provide a matching tight upper bound. This resolves the COLT open problem of McMahan and Streeter (2012).

Smoothness

Hinge loss

Convexity

Logistic function

10.48550/arxiv.1405.3843

Cite

Citations (38)

Online Learning with Low Rank Experts

Conference on Learning Theory (2016)

Elad Hazan Tomer Koren Roi Livni Yishay Mansour

We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of p ? dTq, and extend it to a setting of an approximated subspace. For the adversarial model we show an upper bound ofOpd ? Tq and a lower bound of p ? dTq.

Rank (graph theory)

Learning to Rank

Source

Cite

Citations (3)

A Regret Minimization Approach to Iterative Learning Control

arXiv (Cornell University) (2021)

Naman Agarwal Elad Hazan Anirudha Majumdar Karan Singh

We consider the setting of iterative learning control, or model-based policy learning in the presence of uncertain, time-varying dynamics. In this setting, we propose a new performance metric, planning regret, which replaces the standard stochastic uncertainty assumptions with worst case regret. Based on recent advances in non-stochastic control, we design a new iterative algorithm for minimizing planning regret that is more robust to model mismatch and uncertainty. We provide theoretical and empirical evidence that the proposed algorithm outperforms existing methods on several benchmarks.

Iterative Learning Control

Minification

Performance metric

Source

Cite

Citations (3)

The Convex Optimization Approach to Regret Minimization

The MIT Press eBooks (2011)

Elad Hazan

Minification

10.7551/mitpress/8996.003.0012

Cite

Citations (33)

weak) Calibration is Computationally Hard

Conference on Learning Theory (2012)

Elad Hazan Sham M. Kakade

We show that the existence of a computationally efficient calibration algorithm, with a low weak calibration rate, would imply the existence of an efficient algorithm for computing approximate Nash equilibria — thus implying the unlikely conclusion that every problem inPPAD is solvable in polynomial time.

Source

Cite

Citations (3)

Approximate Convex Optimization by Online Game Playing

arXiv (Cornell University) (2006)

Elad Hazan

Lagrangian relaxation and approximate optimization algorithms have received much attention in the last two decades. Typically, the running time of these methods to obtain a $ε$ approximate solution is proportional to $\frac{1}{ε^2}$. Recently, Bienstock and Iyengar, following Nesterov, gave an algorithm for fractional packing linear programs which runs in $\frac{1}ε$ iterations. The latter algorithm requires to solve a convex quadratic program every iteration - an optimization subroutine which dominates the theoretical running time. We give an algorithm for convex programs with strictly convex constraints which runs in time proportional to $\frac{1}ε$. The algorithm does NOT require to solve any quadratic program, but uses gradient steps and elementary operations only. Problems which have strictly convex constraints include maximum entropy frequency estimation, portfolio optimization with loss risk constraints, and various computational problems in signal processing. As a side product, we also obtain a simpler version of Bienstock and Iyengar's result for general linear programming, with similar running time. We derive these algorithms using a new framework for deriving convex optimization algorithms from online game playing algorithms, which may be of independent interest.

10.48550/arxiv.cs/0610119

Cite

Citations (11)

Hyperparameter Optimization: A Spectral Approach

arXiv (Cornell University) (2017)

Elad Hazan Adam R. Klivans Yuan Yang

We give a simple, fast algorithm for hyperparameter optimization inspired by techniques from the analysis of Boolean functions. We focus on the high-dimensional regime where the canonical example is training a neural network with a large number of hyperparameters. The algorithm --- an iterative application of compressed sensing techniques for orthogonal polynomials --- requires only uniform sampling of the hyperparameters and is thus easily parallelizable. Experiments for training deep neural networks on Cifar-10 show that compared to state-of-the-art tools (e.g., Hyperband and Spearmint), our algorithm finds significantly improved solutions, in some cases better than what is attainable by hand-tuning. In terms of overall running time (i.e., time required to sample various settings of hyperparameters plus additional computation time), we are at least an order of magnitude faster than Hyperband and Bayesian Optimization. We also outperform Random Search 8x. Additionally, our method comes with provable guarantees and yields the first improvements on the sample complexity of learning decision trees in over two decades. In particular, we obtain the first quasi-polynomial time algorithm for learning noisy decision trees with polynomial sample complexity.

Hyperparameter

Parallelizable manifold

Bayesian Optimization

Hyperparameter Optimization

Source

Cite

Citations (28)

Online Control with Adversarial Disturbances

arXiv (Cornell University) (2019)

Naman Agarwal Brian Bullins Elad Hazan Sham M. Kakade Karan P. Singh

We study the control of a linear dynamical system with adversarial disturbances (as opposed to statistical noise). The objective we consider is one of regret: we desire an online control procedure that can do nearly as well as that of a procedure that has full knowledge of the disturbances in hindsight. Our main result is an efficient algorithm that provides nearly tight regret bounds for this problem. From a technical standpoint, this work generalizes upon previous work in two main aspects: our model allows for adversarial noise in the dynamics, and allows for general convex costs.

Hindsight bias

10.48550/arxiv.1902.08721

Cite

Citations (24)

AI safety by debate via regret minimization

arXiv (Cornell University) (2023)

Xinyi Chen Angelica Chen Dean P. Foster Elad Hazan

We consider regret minimization in repeated games with a very large number of actions. Such games are inherent in the setting of AI safety via debate, and more generally games whose actions are language-based. Existing algorithms for online game playing require per-iteration computation polynomial in the number of actions, which can be prohibitive for large games. We thus consider oracle-based algorithms, as oracles naturally model access to AI agents. With oracle access, we characterize when internal and external regret can be minimized efficiently. We give a novel efficient algorithm for internal regret minimization whose regret and per-iteration computation depend logarithmically on the number of actions. We conclude with experiments in the setting of AI Safety via Debate that shows the benefit of insights from our algorithmic analysis.

Minification

10.48550/arxiv.2312.04792

Cite

Citations (1)