7 papers
Subtractive random forests with two choices
Francisco Calvillo, Luc Devroye, Gábor Lugosi
Recommendation systems are pivotal in aiding users amid vast online content. Broutin, Devroye, Lugosi, and Oliveira proposed Subtractive Random Forests (\textsc{surf}), a model tha…
Learning latent tree models with small query complexity
Luc Devroye, Gabor Lugosi, Piotr Zwiernik
We consider the problem of structure recovery in a graphical model of a tree where some variables are latent. Specifically, we focus on the Gaussian case, which can be reformulated…
On the size of temporal cliques in subcritical random temporal graphs
Caelan Atamanchuk, Luc Devroye, Gabor Lugosi
A \emph{random temporal graph} is an ErdÅs-Rényi random graph , together with a random ordering of its edges. A path in the graph is called \emph{increasing} if the edges…
Broadcasting in random recursive dags
Simon Briend, Luc Devroye, Gabor Lugosi
A uniform -{\sc dag} generalizes the uniform random recursive tree by picking parents uniformly at random from the existing nodes. It starts with ''roots''. Each of the…
Uniform temporal trees
Caelan Atamanchuk, Luc Devroye, Gabor Lugosi
Motivated by the study of random temporal networks, we introduce a class of random trees that we coin \emph{uniform temporal trees}. A uniform temporal tree is obtained by assignin…
Online-to-PAC Conversions: Generalization Bounds via Regret Analysis
Gábor Lugosi, Gergely Neu
We present a new framework for deriving bounds on the generalization bound of statistical learning algorithms from the perspective of online learning. Specifically, we construct an…