87 citations · 373 across the 33 of their papers we have counts for
16 papers · 1 filter
Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity
Dan Garber, Atara Kaplan
We consider convex relaxations for recovering low-rank tensors based on constrained minimization over a ball induced by the tensor nuclear norm, recently introduced in \cite{tensor…
Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle
Dan Garber, Tsur Livney, Shoham Sabach
This paper considers a convex composite optimization problem with affine constraints, which includes problems that take the form of minimizing a smooth convex objective function ov…
Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems
Dan Garber, Atara Kaplan
Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in recent years in d…
Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator
Lior Danon, Dan Garber
Tyler's M-estimator is a well known procedure for robust and heavy-tailed covariance estimation. Tyler himself suggested an iterative fixed-point algorithm for computing his estima…
Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems
Dan Garber, Atara Kaplan
Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in recent years in d…
Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity
Dan Garber, Ron Fisher
We consider optimization problems in which the goal is find a -dimensional subspace of , , which minimizes a convex and smooth loss. Such problems generalize…
Frank-Wolfe with a Nearest Extreme Point Oracle
Dan Garber, Noam Wolf
We consider variants of the classical Frank-Wolfe algorithm for constrained smooth convex minimization, that instead of access to the standard oracle for minimizing a linear functi…
On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
Dan Garber, Atara Kaplan
Convex optimization over the spectrahedron, i.e., the set of all real positive semidefinite matrices with unit trace, has important applications in machine learning, si…
Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
Dan Garber
In recent years it was proved that simple modifications of the classical Frank-Wolfe algorithm (aka conditional gradient algorithm) for smooth convex minimization over convex and c…
Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity
Dan Garber
We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as ph…
On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
Dan Garber
Smooth convex minimization over the unit trace-norm ball is an important optimization problem in machine learning, signal processing, statistics and other fields, that underlies ma…
Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
Dan Garber, Ofer Meshi
Recently, several works have shown that natural modifications of the classical conditional gradient method (aka Frank-Wolfe algorithm) for constrained convex optimization, provably…
Faster Projection-free Convex Optimization over the Spectrahedron
Dan Garber
Minimizing a convex function over the spectrahedron, i.e., the set of all positive semidefinite matrices with unit trace, is an important optimization task with many applications i…
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 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…
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…