Strategies for prediction under imperfect monitoring. (2008)
Lugosi, Gábor, Mannor, Shie, Stoltz, Gilles
We propose simple randomized strategies for sequential decision (or prediction) under imperfect monitoring, that is, when the decision maker (forecaster) does not have access to the past outcomes but...
Tracking the best quantizer (2008)
Gyorgy, Andras, Linder, Tamas, Lugosi, Gábor
An algorithm is presented for online prediction that allows to track the best expert efficiently even when the number of experts is exponentially large, provided that the set of experts has a certain...
Local tail bounds for functions of independent random variables (2008)
It is shown that functions defined on {0, 1, . . . , r − 1} n satisfying certain condi- tions of bounded differences that guarantee subgaussian tail behavior also satisfy a much stronger...
On the performance of clustering in Hilbert spaces (2008)
Biau, Gerard, Devroye, Luc, Lugosi, Gábor
Based on $n$ randomly drawn vectors in a separable Hilbert space, one may construct a $k$-means clustering scheme by minimizing an empirical squared error. We investigate the risk of such a...
Ranking and empirical minimization of U-statistics (2008)
Clemencon, Stephan, Lugosi, Gábor, Vayatis, Nicolas
The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the \textit{ranking problem} in a...
Local tail bounds for functions of independent random variables (2007)
It is shown that functions defined on $\{0,1,...,r-1\}^n$ satisfying certain conditions of bounded differences that guarantee sub-Gaussian tail behavior also satisfy a much stronger ``local''...
Clémençon, Stéphan, Lugosi, Gábor, Vayatis, Nicolas
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Strategies for prediction under imperfect monitoring (2007)
Lugosi, Gábor, Stoltz, Gilles, Mannor, Shie
We propose simple randomized strategies for sequential prediction under imperfect monitoring, that is, when the forecaster does not have access to the past outcomes but rather to a feedback signal....
Strategies for prediction under imperfect monitoring (2007)
Lugosi, Gábor, Stoltz, Gilles, Mannor, Shie
We propose simple randomized strategies for sequential prediction under imperfect monitoring, that is, when the forecaster does not have access to the past outcomes but rather to a feedback signal....
The online shortest path problem under partial monitoring (2007)
Gyorgy, Andras, Linder, Tamas, Lugosi, Gábor, Ottucsak, Gyorgy
The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a...
Ranking and empirical minimization of U-statistics (2006)
Clémençon, Stéphan, Lugosi, Gábor, Vayatis, Nicolas
The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous...
Ranking and empirical minimization of U-statistics (2006)
Clémençon, Stéphan, Lugosi, Gábor, Vayatis, Nicolas
The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous...
Ranking and empirical minimization of U-statistics (2006)
Clémençon, Stéphan, Lugosi, Gábor, Vayatis, Nicolas
The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous...
Ranking and empirical minimization of U-statistics (2006)
Clémençon, Stéphan, Lugosi, Gábor, Vayatis, Nicolas
The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous...
Ranking and empirical minimization of U-statistics (2006)
Clémençon, Stéphan, Lugosi, Gábor, Vayatis, Nicolas
The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous...
Prediction, Learning, and Games (2006)
Cesa-Bianchi, Nicolò, Lugosi, Gábor
This book offers the first comprehensive treatment of the problem of predicting "individual sequences". Unlike standard statistical approaches to forecasting, prediction of individual sequences does...
Regret minimization under partial monitoring (2006)
Cesa-Bianchi, Nicolò, Lugosi, Gábor, Stoltz, Gilles
We consider repeated games in which the player, instead of observing the action chosen by the opponent in each game round, receives a feedback generated by the combined choice of the two players. We...
Local tail bounds for functions of independent random variables (2006)
It is shown that functions defined on $\{0,1,\ldots,r-1\}^n$ satisfying certain conditions of bounded differences that guarantee subgaussian tail behavior also satisfy a much stronger ``local''...
Existence of sparsely supported correlated equilibria (2006)
Germano, Fabrizio, Lugosi, Gábor
We show that every $N$-player $K_1 \times \cdots \times K_N$ game possesses a correlated equilibrium with at least $\prod_{i=1}^{N} K_i -1 - \sum_{i=1}^{N} K_i (K_i -1)$ zero entries. In particular,...
Nonparametric kernel-based sequential investment strategies (2006)
Gyorfi, Laszlo, Lugosi, Gábor, Udina, Frederic
The purpose of this paper is to introduce sequential investment strategies that guarantee an optimal rate of growth of the capital under minimal assumptions on the behavior of the market. The new...
Prédiction randomisée de suites individuelles (2006)
Cet article fait suite ‡ la confÈrence que j'ai eu l'honneur de donner en hommage ‡ Lucien Le Cam, lors des {\sl XXXVI\`emes Journ\'ees de Statistique} ‡ Montpellier, en 2004. Il passe en...
Theory of classification: some recent advances (2005)
Boucheron, Stephane, Bousquet, Olivier, Lugosi, Gábor
The last few years have witnessed important new developments in the theory and practice of pattern classification. We intend to survey some of the main new ideas that have lead to these important...
Existence of sparsely supported correlated equilibria (2005)
Germano, Fabrizio, Lugosi, Gábor
We show that every finite N-player game possesses a correlated equilibrium with a precise lower bound on the number of outcomes to which it assigns zero probability. In particular, the largest games...
Moment inequalities for functions of independent random variables (2005)
Boucheron, Stéphane, Bousquet, Olivier, Lugosi, Gábor, Massart, Pascal
A general method for obtaining moment inequalities for functions of independent random variables is presented. It is a generalization of the entropy method which has been used to derive concentration...
Moment inequalities for functions of independent random variables. (2005)
Boucheron, Stephane, Bousquet, Olivier, Lugosi, Gábor, Massart, Pascal
A general method for obtaining moment inequalities for functions of independent random variables is presented. It is a generalization of the entropy method which has been used to derive concentration...
Internal regret in on-line portfolio selection (2005)
This paper extends the game-theoretic notion of internal regret to the case of on-line potfolio selection problems. New sequential investment strategies are designed to minimize the cumulative...
Minimizing Regret with Label Efficient Prediction (2005)
Cesa-Bianchi, Nicolò, Lugosi, Gábor, Stoltz, Gilles
We investigate label efficient prediction, a variant, proposed by Helmbold and Panizza, of the problem of prediction with expert advice. In this variant the forecaster, after guessing the next...
Ranking and scoring using empirical risk minimization (2005)
Clemencon, Stephan, Lugosi, Gábor, Vayatis, Nicolas
A general model is proposed for studying ranking problems. We investigate learning methods based on empirical minimization of the natural estimates of the ranking risk. The empirical estimates are of...
Tracking the best of many experts (2005)
Gyorgy, Andras, Linder, Tamas, Lugosi, Gábor
An algorithm is presented for online prediction that allows to track the best expert efficiently even if the number of experts is exponentially large, provided that the set of experts has a certain...
Global Nash convergence of Foster and Young's regret testing (2004)
Germano, Fabrizio, Lugosi, Gábor
We construct an uncoupled randomized strategy of repeated play such that, if every player follows such a strategy, then the joint mixed strategy profiles converge, almost surely, to a Nash...
Global Nash Convergence of Foster and Young's Regret Testing (2004)
Germano, Fabrizio, Lugosi, Gábor
We construct an uncoupled randomized strategy of repeated play such that, if every player follows such a strategy, then the joint mixed strategy profiles converge, almost surely, to a Nash...
Regret minimization under partial monitoring (2004)
Cesa-Bianchi, Nicolò, Lugosi, Gábor, Stoltz, Gilles
We consider repeated games in which the player, instead of observing the action chosen by the opponent in each game round, receives a feedback generated by the combined choice of the two players. We...
Complexity regularization via localized random penalties (2004)
Lugosi, Gábor, Wegkamp, Marten
In this article, model selection via penalized empirical loss minimization in nonparametric classification problems is studied. Data-dependent penalties are constructed, which are based on estimates...
Learning correlated equilibria in games with compact sets of strategies (2004)
Hart and Schmeidler's extension of correlated equilibrium to games with infinite sets of strategies is studied. General properties of the set of correlated equilibria are described. It is shown that,...
On the Bayes-risk consistency of regularized boosting methods (2004)
Lugosi, Gábor, Vayatis, Nicolas
The probability of error of classification methods based on convex combinations of simple base classifiers by "boosting" algorithms is investigated. The main result of the paper is that certain...
Discussions of boosting papers, and rejoinders (2004)
Bartlett, Peter L., Bickel, Peter J., Bühlmann, Peter, Freund, Yoav, Friedman, Jerome, Hastie, Trevor, ...
Discussions of: "Process consistency for AdaBoost" [Ann. Statist. 32 (2004), no. 1, 13-29] by W. Jiang; "On the Bayes-risk consistency of regularized boosting methods" [ibid., 30-55] by G. Lugosi and...
Bin Width Selection in Multivariate Histograms by the Combinatorial Method (2004)
We present several multivariate histogram density estimates that are universally $L_1$-optimal to within a constant factor and an additive term $O(\sqrt{\log n / n })$. The bin widths are chosen by...
Bin Width Selection in Multivariate Histograms by the Combinatorial Method (2004)
We present several multivariate histogram density estimates that are universally $L_1$-optimal to within a constant factor and an additive term $O(\sqrt{\log n / n })$. The bin widths are chosen by...
Minimizing Regret with Label Efficient Prediction (2004)
Cesa-Bianchi, Nicolò, Lugosi, Gábor, Stoltz, Gilles
We investigate label efficient prediction, a variant of the problem of prediction with expert advice, proposed by Helmbold and Panizza, in which the forecaster does not have access to the outcomes of...
Concentration inequalities (2004)
Boucheron, Stephane, Bousquet, Olivier, Lugosi, Gábor
Concentration inequalities deal with deviations of functions of independent random variables from their expectation. In the last decade new tools have been introduced making it possible to establish...
Statistical Learning Theory (2004)
Bousquet, Olivier, Boucheron, Stephane, Lugosi, Gábor
The goal of statistical learning theory is to study, in a statistical framework, the properties of learning algorithms. In particular, most results take the form of so-called error bounds. This...
Theory of classification: some recent advances (2004)
Bousquet, Olivier, Boucheron, Stephane, Lugosi, Gábor
The last few years have witnessed important new developments in the theory and practice of pattern classification. We intend to survey some of the main new ideas that have lead to these important...
Concentration inequalities using the entropy method (2003)
Boucheron, Stéphane, Lugosi, Gábor, Massart, Pascal
We investigate a new methodology, worked out by Ledoux and Massart, to prove concentration-of-measure inequalities. The method is based on certain modified logarithmic Sobolev inequalities. We...
Model Selection and Error Estimation (2000)
Bartlett, Peter, Boucheron, Stéphane, Lugosi, Gábor
We study model selection strategies based on penalized empirical loss minimization. We point out a tight relationship between error estimation and data-based complexity penalization: any good error...
Strategies for Sequential Prediction of Stationary Time Series (2000)
We present simple procedures for the prediction of a real valued sequence. The algorithms are based on a combination of several simple predictors. We show that if the sequence is a realization of a...
A Note on Robust Detection (2000)
Devroye, Luc, Györfi, László, Lugosi, Gábor
We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of $k$ nominal densities is the true density is closest to,...
A Zero-delay Sequential Scheme for Lossy Coding of Individual Sequences (2000)
We consider adaptive sequential lossy coding of bounded individual sequences when the performance is measured by the sequentially accumulated mean squared distortion. The encoder and the decoder are...
Adaptive model selection using empirical complexities (1999)
Lugosi, Gábor, Nobel, Andrew B.
Given $n$ independent replicates of a jointly distributed pair $(X, Y) \in \mathscr{R}^d \times \mathscr{R}$, we wish to select from a fixed sequence of model classes $\mathscr{F}_1,...
On prediction of individual sequences (1999)
Cesa-Bianchi, Nicolò, Lugosi, Gábor
Sequential randomized prediction of an arbitrary binary sequence is investigated. No assumption is made on the mechanism of generating the bit sequence. The goal of the predictor is to minimize its...
Worst-case Bounds for the Logarithmic Loss of Predictors (1999)
Cesa-Bianchi, Nicolò, Lugosi, Gábor
We investigate on-line prediction of individual sequences. Given a class of predictors, the goal is to predict as well as the best predictor in the class, where the loss is measured by the self...
Almost Sure Testability of Classes of Densities (1999)
Let a class $\F$ of densities be given. We draw an i.i.d.\ sample from a density $f$ which may or may not be in $\F$. After every $n$, one must make a guess whether $f \in \F$ or not. A class is...
A Sharp Concentration Inequality with Applications (1999)
Boucheron, Stéphane, Lugosi, Gábor, Massart, Pascal
We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.
Variable Kernel Estimates: On the Impossibility of Tuning the Parameters (1998)
For the standard kernel density estimate, it is known that one can tune the bandwidth such that the expected L1 error is within a constant factor of the optimal L1 error (obtained when one is allowed...
On Prediction of Individual Sequences (1998)
Cesa-Bianchi, Nicolò, Lugosi, Gábor
Sequential randomized prediction of an arbitrary binary sequence is investigated. No assumption is made on the mechanism of generating the bit sequence. The goal of the predictor is to minimize its...
Adaptive Model Selection Using Empirical Complexities (1998)
Lugosi, Gábor, Nobel, Andrew B.
Given $n$ independent replicates of a jointly distributed pair $(X,Y) \in {\cal R}^d \times {\cal R}$, we wish to select from a fixed sequence of model classes ${\cal F}_1, {\cal F}_2, \ldots$ a...
A Simple Randomized Algorithm for Consistent Sequential Prediction of Ergodic Time Series (1998)
Györfi, László, Lugosi, Gábor, Morvai, Gusztáv
We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from recent developments of the theory of the prediction of individual sequences. We show...
An Inequality for Uniform Deviations of Sample Averages from their Means (1998)
Bartlett, Peter, Lugosi, Gábor
We derive a new inequality for uniform deviations of averages from their means. The inequality is a common generalization of previous results of Vapnik and Chervonenkis (1974) and Pollard (1986)....
Inequalities for a New Data-Based Method for Selecting Nonparametric Density Estimates (1998)
Devroye, Luc, Lugosi, Gábor, Udina I Abelló, Frederic
We continue the development of a method for the selection of a bandwidth or a number of design parameters in density estimation. We provide explicit non-asymptotic density-free inequalities that...
Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes (1997)
We introduce a method to select a smoothing factor for kernel density estimation such that, for all densities in all dimensions, the $L_1$ error of the corresponding kernel estimate is not larger...
Minimax Lower Bounds for the Two-Armed Bandit Problem (1997)
Kulkarni, Sanjeev R., Lugosi, Gábor
We obtain minimax lower bounds on the regret for the classical two--armed bandit problem. We provide a finite--sample minimax version of the well--known log $n$ asymptotic lower bound of Lai and...
Strong Minimax Lower Bounds for Learning (1997)
Minimax lower bounds for concept learning state, for example, that for each sample size $n$ and learning rule $g_n$, there exists a distribution of the observation $X$ and a concept $C$ to be learnt...
The Minimax Distortion Redundancy in Empirical Quantizer Design (1997)
Bartlett, Peter, Linder, Tamás, Lugosi, Gábor
We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean squared distortion of a vector quantizer designed from...
A Data-Dependent Skeleton Estimate and a Scale-Sensitive Dimension for Classification (1996)
The classical binary classification problem is investigated when it is known in advance that the posterior probability function (or regression function) belongs to some class of functions. We...
A universally acceptable smoothing factor for kernel density estimates (1996)
We define a minimum distance estimate of the smoothing factor for kernel density estimates, based on a methodology first developed by Yatracos. It is shown that if $f_{nh}$ denotes the kernel density...
Consistency of data-driven histogram methods for density estimation and classification (1996)
We present general sufficient conditions for the almost sure $L_1$-consistency of histogram density estimates based on data-dependent partitions. Analogous conditions guarantee the almost-sure risk...
Existence of sparsely supported correlated equilibria
Fabrizio Germano, Gábor Lugosi
We show that every finite N-player normal form game possesses a correlated equilibrium with a precise lower bound on the number of outcomes to which it assigns zero probability. In particular, the...
Universal smoothing factor selection in density estimation: theory and practice
Duc Devroye, J. Beirlant, R. Cao, R. Fraiman, P. Hall, M. Jones, ...
Density estimation, kernel estimate, convergence, smoothing factor, minimum distance estimate, asymptotic optimality, simulation study, 62G05,
Bin width selection in multivariate histograms by the combinatorial method
Multivariate density estimation, nonparametric estimation, variable histogram estimate, bandwith selection, 62G05,
Existence of Sparsely Supported Correlated Equilibria
Fabrizio Germano, Gábor Lugosi
Correlated equilibrium, Finite games, C72,
Strong Minimax Lower Bounds for Learning
Minimax lower bounds for concept learning state, for example, that for each sample size $n$ and learning rule $g_n$, there exists a distribution of the observation $X$ and a concept $C$ to be learnt...
The Minimax Distortion Redundancy in Empirical Quantizer Design
Peter Bartlett, Tamas Linder, Gábor Lugosi
We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean squared distortion of a vector quantizer designed from...
A Data-Dependent Skeleton Estimate and a Scale-Sensitive Dimension for Classification
The classical binary classification problem is investigated when it is known in advance that the posterior probability function (or regression function) belongs to some class of functions. We...
Minimax Lower Bounds for the Two-Armed Bandit Problem
Sanjeev R. Kulkarni, Gábor Lugosi
We obtain minimax lower bounds on the regret for the classical two--armed bandit problem. We provide a finite--sample minimax version of the well--known log $n$ asymptotic lower bound of Lai and...
An Inequality for Uniform Deviations of Sample Averages from their Means
We derive a new inequality for uniform deviations of averages from their means. The inequality is a common generalization of previous results of Vapnik and Chervonenkis (1974) and Pollard (1986)....
Inequalities for a New Data-Based Method for Selecting Nonparametric Density Estimates
Luc Devroye, Gábor Lugosi, Frederic Udina
We continue the development of a method for the selection of a bandwidth or a number of design parameters in density estimation. We provide explicit non-asymptotic density-free inequalities that...
A Simple Randomized Algorithm for Consistent Sequential Prediction of Ergodic Time Series
László Györfi, Gábor Lugosi, Gusztáv Morvai
We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from recent developments of the theory of the prediction of individual sequences. We show...
Adaptive Model Selection Using Empirical Complexities
Given $n$ independent replicates of a jointly distributed pair $(X,Y) \in {\cal R}^d \times {\cal R}$, we wish to select from a fixed sequence of model classes ${\cal F}_1, {\cal F}_2, \ldots$ a...
On Prediction of Individual Sequences
Nicolo Cesa Bianchi, Gábor Lugosi
Sequential randomized prediction of an arbitrary binary sequence is investigated. No assumption is made on the mechanism of generating the bit sequence. The goal of the predictor is to minimize its...
Variable Kernel Estimates: On the Impossibility of Tuning the Parameters
For the standard kernel density estimate, it is known that one can tune the bandwidth such that the expected L1 error is within a constant factor of the optimal L1 error (obtained when one is allowed...
Almost Sure Testability of Classes of Densities
Let a class $\F$ of densities be given. We draw an i.i.d.\ sample from a density $f$ which may or may not be in $\F$. After every $n$, one must make a guess whether $f \in \F$ or not. A class is...
A Sharp Concentration Inequality with Applications
Stéphane Boucheron, Gábor Lugosi, Pascal Massart
We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.
Worst-case Bounds for the Logarithmic Loss of Predictors
Nicolò Cesa Bianchi, Gábor Lugosi
We investigate on-line prediction of individual sequences. Given a class of predictors, the goal is to predict as well as the best predictor in the class, where the loss is measured by the self...
Luc Devroye, László Györfi, Gábor Lugosi
We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of $k$ nominal densities is the true density is closest to,...
A Zero-delay Sequential Scheme for Lossy Coding of Individual Sequences
We consider adaptive sequential lossy coding of bounded individual sequences when the performance is measured by the sequentially accumulated mean s