Best-case lower bounds in online learning

Simple item page
dc.catalogadorfcr
dc.contributor.authorGuzman Paredes, Cristobal Andres
dc.contributor.authorNishant Mehta
dc.contributor.authorAli Mortazavi
dc.date.accessioned2024-03-05T15:15:02Z
dc.date.available2024-03-05T15:15:02Z
dc.date.issued2021
dc.description.abstractMuch of the work in online learning focuses on the study of sublinear upper bounds on the regret. In this work, we initiate the study of best-case lower bounds in online convex optimization, wherein we bound the largest improvement an algorithm can obtain relative to the single best action in hindsight. This problem is motivated by the goal of better understanding the adaptivity of a learning algorithm. Another motivation comes from fairness: it is known that best-case lower bounds are instrumental in obtaining algorithms for decision-theoretic online learning (DTOL) that satisfy a notion of group fairness. Our contributions are a general method to provide best-case lower bounds in Follow the Regularized Leader (FTRL) algorithms with time-varying regularizers, which we use to show that best-case lower bounds are of the same order as existing upper regret bounds: this includes situations with a fixed learning rate, decreasing learning rates, timeless methods, and adaptive gradient methods. In stark contrast, we show that the linearized version of FTRL can attain negative linear regret. Finally, in DTOL with two experts and binary losses, we fully characterize the best-case sequences, which provides a finer understanding of the best-case lower bounds.
dc.fuente.origenORCID
dc.identifier.urihttps://research.utwente.nl/en/publications/bestcase-lower-bounds-in-online-learning(dcc267c5-39ff-450e-a170-0a948578fbce).html
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/84091
dc.information.autorucInstituto de Ingenierƭa MatemƔtica y Computacional; Guzman Paredes, Cristobal Andres; 0000-0002-1498-2055; 1041986
dc.language.isoen
dc.nota.accesocontenido completo
dc.rightsacceso abierto
dc.titleBest-case lower bounds in online learning
dc.typecomunicaciĆ³n de congreso
sipa.codpersvinculados1041986
sipa.trazabilidadORCID;2024-01-22
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Best case lower bounds.pdf
Size:
9.6 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
ArtĆ­culos de conferencia