Adaptive and Efficient Algorithms for Tracking the Best Expert
In this paper, we consider the problem of prediction with expert advice in dynamic environments. We choose tracking regret as the performance metric and develop two adaptive and efficient algorithms with data-dependent tracking regret bounds. The first algorithm achieves a second-order tracking regret bound, which improves existing first-order bounds. The second algorithm enjoys a path-length bound, which is generally not comparable to the second-order bound but offers advantages in slowly moving environments. Both algorithms are developed under the online mirror descent framework and draw inspiration from existing algorithms that attain data-dependent bounds of static regret. The key idea is to use a clipped simplex in the updating step of online mirror descent. Finally, we extend our algorithms and analysis to online matrix prediction and provide the first data-dependent tracking regret bound for this problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Tracking the Best Expert Privately
We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three natural types of adversaries, stochastic…
AAA: Adaptive Aggregation of Arbitrary Online Trackers with Theoretical Performance Guarantee
For visual object tracking, it is difficult to realize an almighty online tracker due to the huge variations of target appearance depending on an image sequence. This paper proposes an online tracking method that adaptiv…
DeblurringObject TrackingVisual Object TrackingTracking Dynamic Sources of Malicious Activity at Internet Scale
We formulate and address the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision tree, but with additional challenges: (1) severe space re…
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust
In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times), given a set of $n$ experts who make predictions on each day (or time). The algorithm is gi…
Adaptive calibration for binary classification
This note proposes a way of making probability forecasting rules less sensitive to changes in data distribution, concentrating on the simple case of binary classification. This is important in applications of machine lea…
Binary ClassificationClassification