125 citations · 237 across the 22 of their papers we have counts for
12 papers · 1 filter
Symmetry & Critical Points for Symmetric Tensor Decomposition Problems
Yossi Arjevani, Gal Vinograd
We consider the nonconvex optimization problem associated with the decomposition of a real symmetric tensor into a sum of rank-one terms. Use is made of the rich symmetry structure…
Symmetry Breaking in Symmetric Tensor Decomposition
Yossi Arjevani, Joan Bruna, Michael Field +3
In this note, we consider the highly nonconvex optimization problem associated with computing the rank decomposition of symmetric tensors. We formulate the invariance properties of…
IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
Yossi Arjevani, Joan Bruna, Bugra Can +3
We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of ap…
Lower Bounds for Non-Convex Stochastic Optimization
Yossi Arjevani, Yair Carmon, John C. Duchi +3
We lower bound the complexity of finding -stationary points (with gradient norm at most ) using stochastic first-order methods. In a well-studied model where algorithms acces…
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
Yossi Arjevani, Ohad Shamir, Nathan Srebro
We provide tight finite-time convergence bounds for gradient descent and stochastic gradient descent on quadratic functions, when the gradients are delayed and reflect iterates fro…
Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
Yossi Arjevani
We study the conditions under which one is able to efficiently apply variance-reduction and acceleration schemes on finite sum optimization problems. First, we show that, perhaps s…
Oracle Complexity of Second-Order Methods for Smooth Convex Optimization
Yossi Arjevani, Ohad Shamir, Ron Shiff
Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we prove tight b…
Oracle Complexity of Second-Order Methods for Finite-Sum Problems
Yossi Arjevani, Ohad Shamir
Finite-sum optimization problems are ubiquitous in machine learning, and are commonly solved using first-order methods which rely on gradient computations. Recently, there has been…
Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
Yossi Arjevani, Ohad Shamir
Many canonical machine learning problems boil down to a convex optimization problem with a finite sum structure. However, whereas much progress has been made in developing faster a…
On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
Yossi Arjevani, Ohad Shamir
We consider a broad class of first-order optimization algorithms which are \emph{oblivious}, in the sense that their step sizes are scheduled regardless of the function under consi…
On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
Yossi Arjevani, Shai Shalev-Shwartz, Ohad Shamir
We develop a novel framework to study smooth and strongly convex optimization algorithms, both deterministic and stochastic. Focusing on quadratic functions we are able to examine…
On Lower and Upper Bounds in Smooth Strongly Convex Optimization - A Unified Approach via Linear Iterative Methods
Yossi Arjevani
In this thesis we develop a novel framework to study smooth and strongly convex optimization algorithms, both deterministic and stochastic. Focusing on quadratic functions we are a…