536 citations · 4.4k across the 97 of their papers we have counts for
6 papers · 1 filter
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…
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
Itay Safran, Ohad Shamir
We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using…
Distribution-Specific Hardness of Learning Neural Networks
Ohad Shamir
Although neural networks are routinely and successfully trained in practice using simple gradient-based methods, most existing theoretical results are negative, showing that learni…
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…
Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
Ohad Shamir
Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled \emph{with} replacement. In practice, however, samp…