Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.
Mirror descent meets fixed share (and feels no regret) / N. Cesa-Bianchi, P. Gaillard, G. Lugosi, G. Stoltz - In: Advances in neural information processing systems 25 : 26th annual conference on neural information processing systems 2012 : proceedings / [a cura di] P.L. Bartlett, F.C.N. Pereira, C.J.C. Burges, L. Bottou, K.Q. Weinberger. - [s.l] : Neural information processing systems foundation, 2012. - pp. 989-997 (( Intervento presentato al 26. convegno Conference on Neural Information Processing Systems tenutosi a South Lake Tahoe, USA nel 2012.
Mirror descent meets fixed share (and feels no regret)
N. Cesa-Bianchi;
2012
Abstract
Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
