87 citations · 373 across the 33 of their papers we have counts for
16 papers · 1 filter
Projection-free Online Exp-concave Optimization
Dan Garber, Ben Kretzu
We consider the setting of online convex optimization (OCO) with \textit{exp-concave} losses. The best regret bound known for this setting is , where is the dimens…
New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees
Dan Garber, Ben Kretzu
We present new efficient \textit{projection-free} algorithms for online convex optimization (OCO), where by projection-free we refer to algorithms that avoid computing orthogonal p…
Revisiting Projection-free Online Learning: the Strongly Convex Case
Dan Garber, Ben Kretzu
Projection-free optimization algorithms, which are mostly based on the classical Frank-Wolfe method, have gained significant interest in the machine learning community in recent ye…
On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
Dan Garber
We revisit the use of Stochastic Gradient Descent (SGD) for solving convex optimization problems that serve as highly popular convex relaxations for many important low-rank matrix…
Improved Regret Bounds for Projection-free Bandit Convex Optimization
Dan Garber, Ben Kretzu
We revisit the challenge of designing online algorithms for the bandit convex optimization problem (BCO) which are also scalable to high dimensional problems. Hence, we consider al…
Fast Stochastic Algorithms for Low-rank and Nonsmooth Matrix Problems
Dan Garber, Atara Kaplan
Composite convex optimization problems which include both a nonsmooth term and a low-rank promoting term have important applications in machine learning and signal processing, such…
On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
Dan Garber
In this paper we focus on the problem of Online Principal Component Analysis in the regret minimization framework. For this problem, all existing regret minimization algorithms for…
Learning of Optimal Forecast Aggregation in Partial Evidence Environments
Yakov Babichenko, Dan Garber
We consider the forecast aggregation problem in repeated settings, where the forecasts are done on a binary event. At each period multiple experts provide forecasts about an event.…
Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
Dan Garber, Shoham Sabach, Atara Kaplan
Motivated by robust matrix recovery problems such as Robust Principal Component Analysis, we consider a general optimization problem of minimizing a smooth and strongly convex loss…
Logarithmic Regret for Online Gradient Descent Beyond Strong Convexity
Dan Garber
Hoffman's classical result gives a bound on the distance of a point from a convex and compact polytope in terms of the magnitude of violation of the constraints. Recently, several…
Efficient Online Linear Optimization with Approximation Algorithms
Dan Garber
We revisit the problem of \textit{online linear optimization} in case the set of feasible actions is accessible through an approximated linear optimization oracle with a factor …
Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
Dan Garber, Ohad Shamir, Nathan Srebro
We study the fundamental problem of Principal Component Analysis in a statistical distributed setting in which each machine out of stores a sample of points sampled i.i.d.…
Stochastic Canonical Correlation Analysis
Chao Gao, Dan Garber, Nathan Srebro +2
We study the sample complexity of canonical correlation analysis (CCA), \ie, the number of samples needed to estimate the population canonical correlation and directions up to arbi…
Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis
Weiran Wang, Jialei Wang, Dan Garber +1
We study the stochastic optimization of canonical correlation analysis (CCA), whose objective is nonconvex and does not decouple over training samples. Although several stochastic…
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
Dan Garber, Elad Hazan
Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are…
Universal MMSE Filtering With Logarithmic Adaptive Regret
Dan Garber, Elad Hazan
We consider the problem of online estimation of a real-valued signal corrupted by oblivious zero-mean noise using linear estimators. The estimator is required to iteratively predic…