A Generalized Online Algorithm for Translation and Scale Invariant Prediction with Expert Advice
In this work, we aim to create a completely online algorithmic framework for prediction with expert advice that is translation-free and scale-free of the expert losses. Our goal is to create a generalized algorithm that is suitable for use in a wide variety of applications. For this purpose, we study the expected regret of our algorithm against a generic competition class in the sequential prediction by expert advice problem, where the expected regret measures the difference between the losses of our prediction algorithm and the losses of the 'best' expert selection strategy in the competition. We design our algorithm using the universal prediction perspective to compete against a specified class of expert selection strategies, which is not necessarily a fixed expert selection. The class of expert selection strategies that we want to compete against is purely determined by the specific application at hand and is left generic, which makes our generalized algorithm suitable for use in many different problems. We show that no preliminary knowledge about the loss sequence is required by our algorithm and its performance bounds, which are second order, expressed in terms of sums of squared losses. Our regret bounds are stable under arbitrary scalings and translations of the losses.
Code (0)
등록된 구현이 없습니다.
Tasks
PredictionTranslationSimilar Papers 제목 키워드 기반
Generalized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits
We study the adversarial multi-armed bandit problem and create a completely online algorithmic framework that is invariant under arbitrary translations and scales of the arm losses. We study the expected performance of o…
Multi-Armed BanditsTranslationScattering Statistics of Generalized Spatial Poisson Point Processes
We present a machine learning model for the analysis of randomly generated discrete signals, modeled as the points of an inhomogeneous, compound Poisson point process. Like the wavelet scattering transform introduced by …
Point ProcessesRecursive Preferences and Ambiguity Attitudes
We study the implications of recursivity and state monotonicity in intertemporal consumption problems under ambiguity. We show that monotone recursive preferences admit a recursive and ex-ante representation, both with t…
TranslationScale Invariant Power Iteration
Power iteration has been generalized to solve many interesting problems in machine learning and statistics. Despite its striking success, theoretical understanding of when and how such an algorithm enjoys good convergenc…
Scaled Relative Graph Analysis of Lur'e Systems and the Generalized Circle Criterion
Scaled Relative Graphs (SRGs) provide a novel graphical frequency-domain method for the analysis of nonlinear systems. However, we show that the current SRG analysis suffers from a pitfall that limit its applicability in…