13 papers
Trading off rewards and errors in multi-armed bandits
Akram Erraqabi, Alessandro Lazaric, Michal Valko +2
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm…
Large-scale semi-supervised learning with online spectral graph sparsification
Daniele Calandriello, Alessandro Lazaric, Michal Valko
We introduce Sparse-HFS, a scalable algorithm that can compute solutions to SSL problems using only O(n polylog(n)) space and O(m polylog(n)) time.
Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
Daniele Calandriello, Alessandro Lazaric, Michal Valko
One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasibl…
A single algorithm for both restless and rested rotting bandits
Julien Seznec, Pierre Ménard, Alessandro Lazaric +1
In many application domains (e.g., recommender systems, intelligent tutoring systems), the rewards associated to the actions tend to decrease over time. This decay is either caused…
Improved large-scale graph learning through ridge spectral sparsification
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric +1
Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Lapl…
Analysis of Nystrom method with sequential ridge leverage scores
Daniele Calandriello, Alessandro Lazaric, Michal Valko
Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of c…