536 citations · 4.4k across the 97 of their papers we have counts for
8 papers · 1 filter
Multi-Player Bandits -- a Musical Chairs Approach
Jonathan Rosenski, Ohad Shamir, Liran Szlak
We consider a variant of the stochastic multi-armed bandit problem, where multiple players simultaneously choose from the same set of arms and may collide, receiving no reward. Thi…
The Power of Depth for Feedforward Neural Networks
Ronen Eldan, Ohad Shamir
We show that there is a simple (approximately radial) function on , expressible by a small 3-layer feedforward neural networks, which cannot be approximated by any 2-laye…
On the Quality of the Initial Basin in Overspecified Neural Networks
Itay Safran, Ohad Shamir
Deep learning, in the form of artificial neural networks, has achieved remarkable practical success in recent years, for a variety of difficult machine learning applications. Howev…
Convergence of Stochastic Gradient Descent for PCA
Ohad Shamir
We consider the problem of principal component analysis (PCA) in a streaming stochastic setting, where our goal is to find a direction of approximate maximal variance, based on a s…
Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
Ohad Shamir
We study the convergence properties of the VR-PCA algorithm introduced by \cite{shamir2015stochastic} for fast computation of leading singular vectors. We prove several new results…
An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
Ohad Shamir
We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per roun…