124 citations · 1.6k across the 112 of their papers we have counts for
14 papers · 1 filter
A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets
Elad Hazan
We consider minimizing a smooth, strongly convex function over a convex set. Projected gradient descent is known to converge linearly in this setting, but each iteration requires a…
A Regret Minimization Approach to Multi-Agent Control
Udaya Ghai, Udari Madhushani, Naomi Leonard +1
We study the problem of multi-agent control of a dynamical system with known dynamics and adversarial disturbances. Our study focuses on optimal control without centralized precomp…
Robust Online Control with Model Misspecification
Xinyi Chen, Udaya Ghai, Elad Hazan +1
We study online control of an unknown nonlinear dynamical system that is approximated by a time-invariant linear system with model misspecification. Our study focuses on robustness…
Revisiting the Polyak step size
Elad Hazan, Sham Kakade
This paper revisits the Polyak step size schedule for convex optimization problems, proving that a simple variant of it simultaneously attains near optimal convergence rates for th…
Lower Bounds for Higher-Order Convex Optimization
Naman Agarwal, Elad Hazan
State-of-the-art methods in convex and non-convex optimization employ higher-order derivative information, either implicitly or explicitly. We explore the limitations of higher-ord…
Finding Approximate Local Minima Faster than Gradient Descent
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins +2
We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and t…
Variance Reduction for Faster Non-Convex Optimization
Zeyuan Allen-Zhu, Elad Hazan
We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem…
Optimal Black-Box Reductions Between Optimization Objectives
Zeyuan Allen-Zhu, Elad Hazan
The diverse world of machine learning applications has given rise to a plethora of algorithms and optimization methods, finely tuned to the specific regression or classification ta…
Fast and Simple PCA via Convex Optimization
Dan Garber, Elad Hazan
The problem of principle component analysis (PCA) is traditionally solved by spectral or algebraic methods. We show how computing the leading principal component could be reduced t…
Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier
Jacob Abernethy, Elad Hazan
This paper explores a surprising equivalence between two seemingly-distinct convex optimization methods. We show that simulated annealing, a well-studied random walk algorithms, is…
Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
Dan Garber, Elad Hazan
The Frank-Wolfe method (a.k.a. conditional gradient algorithm) for smooth optimization has regained much interest in recent years in the context of large scale optimization and mac…
Oracle-Based Robust Optimization via Online Learning
Aharon Ben-Tal, Elad Hazan, Tomer Koren +1
Robust optimization is a common framework in optimization under uncertainty when the problem parameters are not known, but it is rather known that the parameters belong to some giv…
Almost Optimal Sublinear Time Algorithm for Semidefinite Programming
Dan Garber, Elad Hazan
We present an algorithm for approximating semidefinite programs with running time that is sublinear in the number of entries in the semidefinite instance. We also present lower bou…
An optimal algorithm for stochastic strongly-convex optimization
Elad Hazan, Satyen Kale
We consider stochastic convex optimization with a strongly convex (but not necessarily smooth) objective. We give an algorithm which performs only gradient updates with optimal rat…