On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions

Purushottam Kar, Bharath Sriperumbudur, Prateek Jain, Harish Karnick
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):441-449, 2013.

Abstract

In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al. (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly con-vex pairwise loss functions. We are also able to analyze a class of memory efficient on-line learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-kar13, title = {On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions}, author = {Kar, Purushottam and Sriperumbudur, Bharath and Jain, Prateek and Karnick, Harish}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {441--449}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/kar13.pdf}, url = {https://proceedings.mlr.press/v28/kar13.html}, abstract = {In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al. (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly con-vex pairwise loss functions. We are also able to analyze a class of memory efficient on-line learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees.} }
Endnote
%0 Conference Paper %T On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions %A Purushottam Kar %A Bharath Sriperumbudur %A Prateek Jain %A Harish Karnick %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-kar13 %I PMLR %P 441--449 %U https://proceedings.mlr.press/v28/kar13.html %V 28 %N 3 %X In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al. (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly con-vex pairwise loss functions. We are also able to analyze a class of memory efficient on-line learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees.
RIS
TY - CPAPER TI - On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions AU - Purushottam Kar AU - Bharath Sriperumbudur AU - Prateek Jain AU - Harish Karnick BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-kar13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 441 EP - 449 L1 - http://proceedings.mlr.press/v28/kar13.pdf UR - https://proceedings.mlr.press/v28/kar13.html AB - In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al. (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly con-vex pairwise loss functions. We are also able to analyze a class of memory efficient on-line learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees. ER -
APA
Kar, P., Sriperumbudur, B., Jain, P. & Karnick, H.. (2013). On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):441-449 Available from https://proceedings.mlr.press/v28/kar13.html.

Related Material