9 papers
Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
Dan Garber
We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave alg…
Linear Convergence of a Frank-Wolfe-type Method over the Spectrahedron without Strict Complementarity
Dan Garber
We consider smooth convex minimization over the spectrahedron using Frank-Wolfe-type methods based only on extreme-eigenvector computations. In our recent work \cite{garber2026rand…
Revisiting Decomposition-Invariant Conditional Gradient Methods for Polytopes
Dan Garber
We revisit Decomposition-Invariant Conditional Gradient methods, originally introduced by Garber and Meshi in 2016, for minimizing a convex and -smooth function over a polytope…
Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
Dan Garber
We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent cons…
A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron
Dan Garber
We consider the problem of minimizing a smooth and convex function over the -dimensional spectrahedron -- the set of real symmetric positive semidefinite matrices wi…
Weak Proximal Newton Oracles for Composite Convex Optimization
Dan Garber
Second-order methods are of great importance for composite convex optimization problems due to their local super-linear convergence rates (under appropriate assumptions). However,…
Projection-Free Online Convex Optimization with Time-Varying Constraints
Dan Garber, Ben Kretzu
We consider the setting of online convex optimization with adversarial time-varying constraints in which actions must be feasible w.r.t. a fixed constraint set, and are also requir…
Low-Rank Extragradient Methods for Scalable Semidefinite Optimization
Dan Garber, Atara Kaplan
We consider several classes of highly important semidefinite optimization problems that involve both a convex objective function (smooth or nonsmooth) and additional linear or nonl…
From Oja's Algorithm to the Multiplicative Weights Update Method with Applications
Dan Garber
Oja's algorithm is a well known online algorithm studied mainly in the context of stochastic principal component analysis. We make a simple observation, yet to the best of our know…