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...
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....
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 (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....
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)
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...
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.
Efficient Adaptive Algorithms and Minimax Bounds for Zero-Delay Lossy Source Coding (2004)
Andras Gyorgy, 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...
Moment Inequalities for Functions of Independent Random Variables (2004)
Stephane Boucheron, 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...
Bin Width Selection in Multivariate Histograms (2003)
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...
On the Rate of Convergence of Regularized Boosting Classifiers (2003)
Gilles Blanchard, Gabor Lugosi, 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...
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...
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...
Model Selection and Error Estimation (2000)
Peter L. Bartlett, Stephane Boucheron, Gabor Lugosi
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...
Empirical Quantizer Design in the Presence of Source Noise or Channel Noise (2000)
Tam As Linder, Gabor Lugosi, Kenneth Zeger, Senior Member
The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from...
Worst-case Bounds for the Logarithmic Loss of Predictors (1999)
Nicolo Cesa-bianchi, Gabor 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...
Almost Sure Testability of Classes of Densities (1999)
Luc Devroye, Gabor Lugosi, Ramon Trias Fargas
. Let a class F of densities be given. We draw an i.i.d. sample from a density f whichmayor may not be in F . After every n, one must make a guess whether f 2For not. A class is almost surely...