125 citations · 237 across the 22 of their papers we have counts for
25 papers
Eigenvalues of the Hessian in Deep Learning: The Origin of Symmetry and Its Breaking
Yossi Arjevani
Hessian spectra at trained models in deep learning exhibit a persistent pattern: eigenvalues organize into distinct clusters, including a large bulk near zero and a few isolated ou…
Geometry and Optimization of Shallow Polynomial Networks
Yossi Arjevani, Joan Bruna, Joe Kileel +2
We study shallow neural networks with monomial activations and output dimension one. The function space for these models can be identified with a set of symmetric tensors with boun…
Symmetry & Critical Points
Yossi Arjevani
Critical points of an invariant function may or may not be symmetric. We prove, however, that if a symmetric critical point exists, those adjacent to it are generically symmetry br…
Hidden Minima in Two-Layer ReLU Networks
Yossi Arjevani
We consider the optimization problem associated with training two-layer ReLU networks with \(d\) inputs under the squared loss, where the labels are generated by a target network.…
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…
Annihilation of Spurious Minima in Two-Layer ReLU Networks
Yossi Arjevani, Michael Field
We study the optimization problem associated with fitting two-layer ReLU neural networks with respect to the squared loss, where labels are generated by a target network. Use is ma…
Equivariant bifurcation, quadratic equivariants, and symmetry breaking for the standard representation of
Yossi Arjevani, Michael Field
Motivated by questions originating from the study of a class of shallow student-teacher neural networks, methods are developed for the analysis of spurious minima in classes of gra…
Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
Yossi Arjevani, Michael Field
We study the optimization problem associated with fitting two-layer ReLU neural networks with respect to the squared loss, where labels are generated by a target network. We make u…
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…
Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry
Yossi Arjevani, Michael Field
We consider the optimization problem associated with fitting two-layers ReLU networks with respect to the squared loss, where labels are generated by a target network. We leverage…
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
Yossi Arjevani, Yair Carmon, John C. Duchi +3
We design an algorithm which finds an -approximate stationary point (with ) using stochastic gradient and Hessian-vector products, matching gua…
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…
Symmetry & critical points for a model shallow neural network
Yossi Arjevani, Michael Field
We consider the optimization problem associated with fitting two-layer ReLU networks with hidden neurons, where labels are assumed to be generated by a (teacher) neural network…
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
Yossi Arjevani, Amit Daniely, Stefanie Jegelka +1
Recent advances in randomized incremental methods for minimizing -smooth -strongly convex finite sums have culminated in tight complexity of $\tilde{O}((n+\sqrt{n L/μ})\log(1…
On the Principle of Least Symmetry Breaking in Shallow ReLU Models
Yossi Arjevani, Michael Field
We consider the optimization problem associated with fitting two-layer ReLU networks with respect to the squared loss, where labels are assumed to be generated by a target network.…
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…
Communication Complexity of Distributed Convex Learning and Optimization
Yossi Arjevani, Ohad Shamir
We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to ind…
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…