On concentration of self-bounding functions (2009)
Boucheron, Stephane; Université Paris-Diderot; Stephane.boucheron@math.jussieu.fr, Lugosi, Gabor; Pompeu Fabra University; Gabor.lugosi@gmail.com, Massart, Pascal; Université Paris-Sud; Pascal.massart@gmail.com
We prove some new concentration inequalities for self-bounding functions using the entropy method. As an application, we recover Talagrand's convex distance inequality. The new Bernstein-like...
On combinatorial testing problems (2009)
Addario-Berry, Louigi, Broutin, Nicolas, Devroye, Luc, Lugosi, Gabor
We study a class of hypothesis testing problems in which, upon observing the realization of an n-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal...
Sharp threshold for percolation on expanders (2009)
Benjamini, Itai, Boucheron, Stephane, Lugosi, Gabor, Rossignol, Raphael
We study the appearance of the giant component in random subgraphs of a given finite graph G=(V,E) in which each edge is present independently with probability p. We show that if G is an expander...
Online Multi-task Learning with Hard Constraints (2009)
Lugosi, Gabor, Papaspiliopoulos, Omiros, Stoltz, Gilles
We discuss multi-task online learning when a decision maker has to deal simultaneously with M tasks. The tasks are related, which is modeled by imposing that the M-tuple of actions taken by the...
Online Multi-task Learning with Hard Constraints (2009)
Lugosi, Gabor, Papaspiliopoulos, Omiros, Stoltz, Gilles
We discuss multi-task online learning when a decision maker has to deal simultaneously with M tasks. The tasks are related, which is modeled by imposing that the M-tuple of actions taken by the...
Online Multi-task Learning with Hard Constraints (2009)
Lugosi, Gabor, Papaspiliopoulos, Omiros, Stoltz, Gilles
We discuss multi-task online learning when a decision maker has to deal simultaneously with M tasks. The tasks are related, which is modeled by imposing that the M-tuple of actions taken by the...
Online Multi-task Learning with Hard Constraints (2009)
Lugosi, Gabor, Papaspiliopoulos, Omiros, Stoltz, Gilles
We discuss multi-task online learning when a decision maker has to deal simultaneously with M tasks. The tasks are related, which is modeled by imposing that the M-tuple of actions taken by the...
Online Multi-task Learning with Hard Constraints (2009)
Lugosi, Gabor, Papaspiliopoulos, Omiros, Stoltz, Gilles
We discuss multi-task online learning when a decision maker has to deal simultaneously with M tasks. The tasks are related, which is modeled by imposing that the M-tuple of actions taken by the...
Pattern classification and learning theory (2008)
1.1 A binary classification problem Pattern recognition (or classification or discrimination) is about guessing or predicting the unknown class of an observation. An observation is a collection of...
The longest minimum-weight path in a complete graph (2008)
Addario-Berry, Louigi, Broutin, Nicolas, Lugosi, Gabor
We consider the minimum-weight path between any pair of nodes of the n-vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the...
Abstract Multiple Choice Tries and Distributed Hash Tables ∗ (2008)
Luc Devroye, Gabor Lugosi, Gahyun Park, Wojciech Szpankowski
Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Recent years have seen a resurgence of interest in tries. In some of these applications, most...
Nonparametric Estimation via (2008)
Empirical Risk Miriimization, Gabor Lugosi, Kenneth Zeger, Senior Member
Abstract- A general notion of universal consistency of non-parametric estimators is introduced that applies to regression estimation, conditional median estimation, curve fitting, pattern...
Infinite-σ Limits For Tikhonov Regularization (2008)
We consider the problem of Tikhonov regularization with a general convex loss function: this formalism includes support vector machines and regularized least squares. For a family of kernels that...
Effective resistance of random trees (2008)
Addario-Berry, Louigi, Broutin, Nicolas, Lugosi, Gabor
We investigate the effective resistance R_n and conductance C_n between the root and leaves a binary tree of height n. In this electrical network, the resistance of each edge e at distance d from the...
Strategies for prediction under imperfect monitoring (2008)
Lugosi, Gabor, Mannor, Shie, Stoltz, Gilles
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 (2008)
Lugosi, Gabor, Mannor, Shie, Stoltz, Gilles
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....
ALMOST SURE TESTABILITY OF CLASSES OF DENSITIES (2007)
Abstract. Let a class F of densities be given. We draw an i.i.d. sample from a density f which mayor may not be in F. After every n, one must make a guess whether f 2F or not. A class is almost...
Moment Inequalities for Functions of Independent Random Variables (2007)
Stéphane Boucheron, Olivier Bousquet, Gabor Lugosi, Bousquet Gábor Lugosi, Pascal Massart, ...
this paper is to provide such general-purpose inequalities. Our approach is based on a generalization of Ledoux's entropy method (see [26, 28]). Ledoux's method relies on abstract...
. After every n, one must make a guess whether f (2007)
Let a class of densities be given. We draw an i.i.d. sample from a density f which may or may not be in . After every n, one must make a guess whether f or not. A class is almost surely discernible...
Bin Width Selection in Multivariate Histograms (2007)
The Combinatorial Method, Luc Devroye, Gabor Lugosi
We present several multivariate histogram density estimates that are universally L 1 -optimal to within a constant factor and an additive term O( log n/n). The bin widths are chosen by the...
Strategies for prediction under imperfect monitoring (2007)
Lugosi, Gabor, Mannor, Shie, Stoltz, Gilles
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, Gabor, Mannor, Shie, Stoltz, Gilles
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 on-line shortest path problem under partial monitoring (2007)
Gyorgy, Andras, Linder, Tamas, Lugosi, Gabor, 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...
Strategies for prediction under imperfect monitoring (2007)
Lugosi, Gabor, Mannor, Shie, Stoltz, Gilles
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, Gabor, Mannor, Shie, Stoltz, Gilles
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....
Charles A. Micchelli, Yuesheng Xu, Haizhang Zhang, Gabor Lugosi
In this paper we investigate conditions on the features of a continuous kernel so that it may approximate an arbitrary continuous target function uniformly on any compact subset of the input space. A...
Moment inequalities for functions of independent random variables (2005)
Boucheron, Stephane, Bousquet, Olivier, Lugosi, Gabor, 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...
Regret minimization under partial monitoring (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Minimizing regret with label-efficient prediction (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Learning correlated equilibria in games with compact sets of strategies (2005)
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,...
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...
Regret minimization under partial monitoring (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Minimizing regret with label-efficient prediction (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Learning correlated equilibria in games with compact sets of strategies (2005)
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,...
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...
Regret minimization under partial monitoring (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Minimizing regret with label-efficient prediction (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Learning correlated equilibria in games with compact sets of strategies (2005)
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,...
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...
Regret minimization under partial monitoring (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Minimizing regret with label-efficient prediction (2005)
Cesa-Bianchi, Nicolo, Lugosi, Gabor, 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...
Learning correlated equilibria in games with compact sets of strategies (2005)
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,...
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...
Moment Inequalities for Functions of Independent Random Variables (2005)
Stephane Boucheron Olivier, Olivier Bousquet, Gabor Lugosi, Pascal Massart
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...
Complexity regularization via localized random penalties (2004)
Lugosi, Gabor, 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...
Andras Gyorgy, Tamas Linder, Gabor Lugosi
Zero-delay lossy source coding schemes are considered for individual sequences. Performance is measured by the distortion redundancy, defined as the di#erence between the normalized cumulative mean...
Concentration inequalities using the entropy method (2003)
Boucheron, Stephane, Massart, Pascal, LUGOSI, Gabor
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 provide...
On the Rate of Convergence of Regularized Boosting Classifiers (2003)
Gilles Blanchard, Gabor Lugosi, Ramon Trias Fargas, Nicolas Vayatis
A regularized boosting method is introduced, for which regularization is obtained through a penalization function. It is shown through oracle inequalities that this method is model adaptive. The rate...
Efficient Adaptive Algorithms and Minimax Bounds for Zero-Delay Lossy Source Coding (2003)
Andras György, Tamas Linder, Gabor Lugosi
Zero-delay lossy source coding schemes are considered for both individual sequences and random sources. Performance is measured by the distortion redundancy, defined as the difference between the...
On the Bayes-risk consistency of regularized boosting methods (2003)
Gabor Lugosi, Ramon Trias Fargas, Nicolas Vayatis
The probability of error of classi cation methods based on convex combinations of simple base classi ers by \boosting" algorithms is investigated. The main result of the paper is that certain...
Worst-case Bounds for the Logarithmic Loss of Predictors (2001)
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...
Stephane Boucheron, Gabor Lugosi, Ramon Trias Fargas, Pascal Massart
We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results nd direct applications in some problems of learning theory.
Adaptive model selection using empirical complexities (1999)
Key words and phrases. Complexity regularization, classi cation, pattern recognition, regression estimation, curve tting, minimum description length. 1 Given n independent replicates of a jointly...
Strong minimax lower bounds for learning (1998)
Minimax lower bounds for concept learning state, for example, that for each sample size n and learning rule gn, there exists a distribution of the observation X and a concept C to be learnt such that...
The minimax distortion redundancy in empirical quantizer design (1998)
Peter Bartlett, Tamas Linder, Gabor 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...
Marta Horvath, Gabor Lugosi, Ramon Trias Fargas
data-dependent skeleton estimate and a
On the strong universal consistency of nearest neighbor regression function estimates (1994)
Luc Devroye, Laszlo Gyorfi, Adam Krzyzak, Gabor Lugosi
Two results are presented concerning the consistency of the k-nearest neighbor regression estimate. We show that all modes of convergence in L 1 (in probability, almost sure, complete) are equivalent...