Nicolò Cesa-Bianchi - Selected papers

nicolò cesa-bianchi - selected papers

"Nothing is more practical than a good theory." - V. Vapnik

Prediction with Expert Advice and Game-Theoretic Learning

E. Gofer, N. Cesa-Bianchi, C. Gentile, and Y. Mansour
Regret Minimization for Branching Experts
Proceedings of the 26th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 30():?-?, 2013.
N. Cesa-Bianchi, P. Gaillard, G. Lugosi, and G. Stoltz
Mirror Descent meets Fixed Share (and feels no regret)
Proceedings of the 26th Conference on Neural Information Processing Systems (NIPS 2012).
N. Cesa-Bianchi, Y. Mansour, and G. Stoltz
Improved second-order bounds for prediction with expert advice
Machine Learning, 66(2/3):321-352, 2007.
N. Cesa-Bianchi, G. Lugosi, and G. Stoltz
Regret minimization under partial monitoring
Mathematics of Operations Research, 31(3):562-580, 2006.
Slides presented at the IEEE 2006 Information Theory Workshop.
N. Cesa-Bianchi, G. Lugosi, and G. Stoltz
Minimizing regret with label efficient prediction
IEEE Transactions on Information Theory, 51(6):2152-2162, 2005.
N. Cesa-Bianchi and G. Lugosi
Potential-based algorithms in on-line prediction and game theory
Machine Learning, 51(3):239-261, 2003.
N. Cesa-Bianchi
Universal prediction
In: L. Györfi (editor), Principles of Nonparametric Learning
Springer (CISM courses and lectures no. 434), 2002.
N. Cesa-Bianchi and G. Lugosi
Worst-case bounds for the logarithmic loss of predictors
Machine Learning, 43(3):247-264, 2001.
N. Cesa-Bianchi and G. Lugosi
On prediction of individual sequences
Annals of Statistics, 27(6):1865-1895, 1999.
N. Cesa-Bianchi, D.P. Helmbold, and S. Panizza
On Bayes methods for on-line boolean prediction
Algorithmica, 22(1/2):112-137, 1998.
N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, D. Haussler, R. Schapire, and M.K. Warmuth
How to use expert advice
Journal of the ACM, 44(3):427-485, 1997.
N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, and M.K. Warmuth
On-line prediction and conversion strategies
Machine Learning, 25:71-110, 1996.

Bandit Problems

N. Cesa-Bianchi, C. Gentile, and Y. Mansour
Regret minimization for reserve prices in second-price auctions
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA13), 2013.
S. Bubeck, N. Cesa-Bianchi, and G. Lugosi
Bandits with heavy tail
Submitted, September 2012.
S. Bubeck and N. Cesa-Bianchi
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Foundations and Trends in Machine Learning, 5(1)1-122, 2012.
S. Bubeck, N. Cesa-Bianchi, and S. Kakade
Towards minimax policies for online linear optimization with bandit feedback
Proceedings of the 25th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 23:41.1-41.14, 2012.
Y. Seldin, N. Cesa-Bianchi, P. Auer, F. Laviolette, and J. Shawe-Taylor
PAC-Bayes-Bernstein inequality for martingales and its application to multiarmed bandits
Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2. JMLR Workshop and Conference Proceedings, 26:98-111, 2012.
N. Cesa-Bianchi and G. Lugosi
Combinatorial bandits
Journal of Computer and Systems Sciences, 78:1404-1422, 2012.
P. Auer, N. Cesa-Bianchi, and P. Fischer
Finite-time analysis of the multiarmed bandit problem
Machine Learning, 47(2/3):235-256, 2002.
P. Auer, N. Cesa-Bianchi, Y. Freund, and R.E. Schapire
The nonstochastic multiarmed bandit problem
SIAM Journal on Computing, 32(1):48-77, 2002.

Learning on Graphs

N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella
A linear time active learning algorithm for link classification
Proceedings of the 26th Conference on Neural Information Processing Systems (NIPS 2012). Curran Associates, 2013.
N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella
A correlation clustering approach to link classification in signed networks
Proceedings of the 25th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 23:34.1-34.20, 2012.
F. Vitale, N. Cesa-Bianchi, C. Gentile, and G. Zappella
See the tree through the lines: the Shazoo algorithm
Proceedings of the 25th Conference on Neural Information Processing Systems (NIPS 2011). Curran Associates, 2012.
(Slightly revised version, July 2012)
N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella
Active learning on trees and graphs
Proceedings of the 23rd Conference on Learning Theory. Omnipress, 2010.
N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella
Random spanning trees and the prediction of weighted graphs
Journal of Machine Learning Research, 14:1251-1284, 2013.
N. Cesa-Bianchi, C. Gentile, and F. Vitale
Predicting the labels of an unknown graph via adaptive exploration
Theoretical Computer Science, 412(19):1791-1804, 2011.
N. Cesa-Bianchi, C. Gentile, and F. Vitale
Fast and optimal prediction on a labeled tree
Proceedings of the 22nd Conference on Learning Theory. Omnipress, 2009.

Pattern Classification and Regression

F. Orabona, K. Crammer, and N. Cesa-Bianchi
A generalized online mirror descent with applications to classification and regression
Submitted for journal publication, 2012.
F. Orabona, N. Cesa-Bianchi, and C. Gentile
Beyond logarithmic bounds in online learning
Proceedings of the 15th International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 22:823-831, 2012.
N. Cesa-Bianchi and O. Shamir
Efficient online learning via randomized rounding
Proceedings of the 25th Conference on Neural Information Processing Systems (NIPS 2011). Curran Associates, 2012.
F. Orabona and N. Cesa-Bianchi
Better algorithms for selective sampling
Proceedings of the 28th International Conference on Machine Learning. Omnipress, 2011.
N. Cesa-Bianchi, S. Shalev-Shwartz, and O. Shamir
Quantity Makes Quality: Learning with Partial Views
Proceedings of the 25th AAAI Conference on Artificial Intelligence (Nectar Program). AAAI Press, 2011.
N. Cesa-Bianchi, S. Shalev-Shwartz, and O. Shamir
Online learning of noisy data with kernels
IEEE Transaction on Information Theory, 57(12):7907-7931, 2011.
L. Jie, F. Orabona, M. Fornoni, B. Caputo, and N. Cesa-Bianchi
OM-2: An online multi-class multi-kernel learning algorithm
4th IEEE Online Learning for Computer Vision Workshop, 2010.
N. Cesa-Bianchi, S. Shalev-Shwartz, and O. Shamir
Efficient learning with partially observed attributes
Journal of Machine Learning Research, 12:2857-2878, 2011.
G. Cavallanti, N. Cesa-Bianchi, and C. Gentile
Linear algorithms for online multitask classification
Journal of Machine Learning Research, 11:2597-2630, 2010.
N. Cesa-Bianchi, C. Gentile, and F. Orabona
Robust bounds for classification via selective sampling
Proceedings of the 26th International Conference on Machine Learning. Omnipress, 2009.
G. Cavallanti, N. Cesa-Bianchi, and C. Gentile
Tracking the best hyperplane with a simple budget Perceptron
Machine Learning, 69(2/3):143-167. Springer, 2007.
N. Cesa-Bianchi
Applications of regularized least squares to classification problems
Theoretical Computer Science, 382(3):221-231. Elsevier, 2007.
N. Cesa-Bianchi, C. Gentile, and L. Zaniboni
Worst-case analysis of selective sampling for linear classification
Journal of Machine Learning Research, 7:1205-1230, 2006.
N. Cesa-Bianchi, C. Gentile, and L. Zaniboni
Hierarchical classification: combining Bayes with SVM
Proceedings of the 23rd International Conference on Machine Learning, 2006.
N. Cesa-Bianchi, C. Gentile, and L. Zaniboni
Incremental algorithms for hierarchical classification
Journal of Machine Learning Research, 7:31--54, 2006.
N. Cesa-Bianchi, A. Conconi, and C. Gentile
A second-order Perceptron algorithm
SIAM Journal on Computing, 34(3):640-668. SIAM, 2005.
P. Auer, N. Cesa-Bianchi, and C. Gentile
Adaptive and self-confident on-line learning algorithms
Journal of Computer and System Sciences, 64(1):48-75, 2002.
N. Cesa-Bianchi
Analysis of two gradient-based algorithms for on-line regression
Journal of Computer and System Sciences, 59(3):392-411, 1999.
N. Cesa-Bianchi, P.M. Long, and M.K. Warmuth
Worst-case quadratic loss bounds for prediction using linear functions and gradient descent
IEEE Transactions on Neural Networks, 7(3):604-619, 1996.

Statistical Learning Theory

G. Cavallanti, N. Cesa-Bianchi, and C. Gentile
Learning noisy linear classifiers via adaptive and selective sampling
Machine Learning, 83:71-102, 2011.
N. Cesa-Bianchi and C. Gentile
Improved risk tail bounds for on-line algorithms
IEEE Transactions on Information Theory, 54(1):386-390, 2008.
N. Cesa-Bianchi, A. Conconi, and C. Gentile
On the generalization ability of on-line learning algorithms
IEEE Transactions on Information Theory, 50(9):2050-2057, 2004.
N. Cesa-Bianchi, E. Dichterman, P. Fischer, E. Shamir, and H.U. Simon
Sample-efficient strategies for learning in the presence of noise
Journal of the ACM, 46(5):684-719, 1999.
N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler
Scale-sensitive dimensions, uniform convergence, and learnability
Journal of the ACM, 44(4):615-631, 1997.
S. Ben-David, N. Cesa-Bianchi, D. Haussler, and P.M. Long
Characterizations of learnability for classes of {0,..,n}-valued functions
Journal of Computer and System Sciences, 50(1):74-86, 1995.

Boolean Learning and Learning with Queries

P. Auer and N. Cesa-Bianchi
On-line learning with malicious noise and the closure algorithm
Annals of AI and Mathematics, 23(1/2):83-99, 1998.
A. Bertoni, N. Cesa-Bianchi e G. Fiorino
Efficient learning with equivalence queries of conjunctions of modulo functions
Information Processing Letters, 56:15--17, 1995.

Bioinformatics

N. Cesa-Bianchi, M. Re, and G. Valentini
Synergy of multilabel hierarchical ensembles, data fusion, and cost-sensitive methods for gene functional inference
Machine Learning, 88:209-241, 2012.
N. Cesa-Bianchi and G. Valentini
Hierarchical cost-sensitive algorithms for genome-wide gene function prediction
Proceedings of the 3rd International Workshop on Machine Learning in Systems Biology, JMLR Workshop and Conference Proceedings, 8:14-29, 2010.
G. Valentini and N. Cesa-Bianchi
HCGene: a software tool to support the hierarchical classification of genes
Bioinformatics, 24(5):729-731, 2008.

Other Areas

Y. Seldin, F. Laviolette, N. Cesa-Bianchi, J. Shawe-Taylor, and Peter Auer
PAC-Bayesian Inequalities for Martingales
IEEE Transactions on Information Theory, 58(12):7086-7093, 2012.
P. Auer and N. Cesa-Bianchi
A distributed voting scheme to maximize preferences
RAIRO - Theoretical Informatics and Applications, 40:389-403, 2006.
N. Cesa-Bianchi and G. Lugosi
Minimax values and metric entropy bounds for portfolio selection problems
Communicated at the First World Congress of the Game Theory Society (Games 2000).
N. Cesa-Bianchi and D. Haussler,
A graph-theoretic generalization of the Sauer-Shelah lemma
Discrete Applied Mathematics, 86(1):27-35, 1998.
N. Cesa-Bianchi, A. Krogh and M.K. Warmuth
Bounds on approximate steepest descent for likelihood maximization in exponential families
IEEE Transactions on Information Theory, 40(4):1215-1218, 1994.
B. Apolloni, N. Cesa-Bianchi, and D. De Falco
A numerical implementation of quantum annealing
Stochastic Processes, Physics and Geometry: Proceedings of the Ascona-Locarno Conference, pages 97-111, 1988.