On the optimality of the Hedge algorithm in the stochastic regime
In this paper, we study the behavior of the Hedge algorithm in the online stochastic setting. We prove that anytime Hedge with decreasing learning rate, which is one of the simplest algorithm for the problem of prediction with expert advice, is surprisingly both worst-case optimal and adaptive to the easier stochastic and adversarial with a gap problems. This shows that, in spite of its small, non-adaptive learning rate, Hedge possesses the same optimal regret guarantee in the stochastic case as recently introduced adaptive algorithms. Moreover, our analysis exhibits qualitative differences with other variants of the Hedge algorithm, such as the fixed-horizon version (with constant learning rate) and the one based on the so-called "doubling trick", both of which fail to adapt to the easier stochastic setting. Finally, we discuss the limitations of anytime Hedge and the improvements provided by second-order regret bounds in the stochastic case.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning Safely Without Knowing the World:COMPASS-Hedge
Online learning algorithms often face a fundamental trilemma: balancing regret guarantees between adversarial and stochastic settings and providing baseline safety against a fixed comparator. While existing methods excel…
Optimality of the Subgradient Algorithm in the Stochastic Setting
We show that the Subgradient algorithm is universal for online learning on the simplex in the sense that it simultaneously achieves $O(\sqrt N)$ regret for adversarial costs and $O(1)$ pseudo-regret for i.i.d costs. To t…
Risk management of guaranteed minimum maturity benefits under stochastic mortality and regime-switching by Fourier space time-stepping framework
In this paper, we adopted a net liability model which assesses both market risk on the liability side and revenue risk on the asset side for a Guaranteed Minimum Maturity Benefit (GMMB) embedded in variable annuity (VA) …
ManagementOn the Universal Near Optimality of Hedge in Combinatorial Settings
In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector $\boldsymbol{x}_t$ from a set $X \subseteq \{0,1\}^d$, observes a full loss vector $\boldsymbol…
On the Adaptivity of Stochastic Gradient-Based Optimization
Stochastic-gradient-based optimization has been a core enabling methodology in applications to large-scale problems in machine learning and related areas. Despite the progress, the gap between theory and practice remains…