536 citations · 4.4k across the 97 of their papers we have counts for
8 papers · 1 filter
On the Complexity of Learning with Kernels
Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir
A well-recognized limitation of kernel learning is the requirement to handle a kernel matrix, whose size is quadratic in the number of training examples. Many methods have been pro…
On the Computational Efficiency of Training Neural Networks
Roi Livni, Shai Shalev-Shwartz, Ohad Shamir
It is well-known that neural networks are computationally hard to train. On the other hand, in practice, modern day neural networks are trained efficiently using SGD and a variety…
Attribute Efficient Linear Regression with Data-Dependent Sampling
Doron Kukliansky, Ohad Shamir
In this paper we analyze a budgeted learning setting, in which the learner can only choose and observe a small subset of the attributes of each training example. We develop efficie…
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile +3
We present and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associa…
A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
Ohad Shamir
We describe and analyze a simple algorithm for principal component analysis and singular value decomposition, VR-PCA, which uses computationally cheap stochastic iterations, yet co…
On the Complexity of Bandit Linear Optimization
Ohad Shamir
We study the attainable regret for online linear optimization problems with bandit feedback, where unlike the full-information setting, the player can only observe its own loss rat…