Regret Bounds for Optimistic Follow The Leader: Applications in Portfolio Selection and Linear Regression

Follow-The-Leader (FTL) is a simple online learning algorithm that is often overlooked. This paper investigates the FTL algorithm and two of its variant. The Optimistic FTL (OFTL) algorithm in the context of online learning with hints and the Follow The Approximate Leader (FTAL) with adaptive curvature. We provide a general regret inequality for OFTL that explicitly captures the effect of the hints and the curvature of the cost functions. This directly leads to a regret bound for FTAL. We generalize prior regret bounds of FTAL by incorporating adaptive curvature and movement of the iterates. We demonstrate the applicability of our results by deriving regret bounds for the online portfolio selection problem using FTAL with adaptive curvature. We further show the applicability of OFTL by obtaining a uniform regret bound for online linear regression. Our analysis contributes to a better understanding of FTL and its variants in various online learning scenarios.