Prediction with Advice of Unknown Number of Experts

Alexey V. Chernov, Vladimir VovkUAI 2010

TL;DR

This paper introduces a new prediction algorithm that achieves regret bounds depending only on the effective number of experts, not the total number. This is a significant improvement as it allows for better performance when many experts offer similar advice, and it's the first bound of its kind that doesn't depend on the nominal number of experts.

What Problem Does This Paper Address?

In the realm of "prediction with expert advice" (PEA) and its related "decision-theoretic online learning" (DTOL), a key goal is to minimize "regret." Regret measures how much worse a learner performs compared to the best possible strategy (e.g., the best expert). Traditionally, regret bounds have depended on the total number of experts available. However, this can be misleading if many experts provide redundant or similar advice. The authors argue that a more informative bound should depend on the effective number of experts, which captures the true diversity of advice. They aim to develop an algorithm that achieves such bounds, particularly when the total number of experts is unknown or very large.

Methods

The core of the paper's approach is the Defensive Forecasting (DF) method. DF works by bounding the growth of a "supermartingale," which acts like a potential function. The authors introduce a novel concept called multivalued supermartingales and prove a key lemma (Levin's Lemma for Multivalued Supermartingales) that is crucial for their DF application. They then construct a specific type of supermartingale, the Hoeffding Supermartingale, tailored for their needs. This allows them to derive their main theoretical results.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and algorithms, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Effective vs. Nominal Experts: The most significant insight is the distinction between the nominal number of experts and the effective number. The latter is a more accurate measure of the difficulty of a prediction task, especially when advice is redundant.
  • Bounds Independent of Nominal Experts: The paper achieves a breakthrough by deriving regret bounds that do not depend on the nominal number of experts. This is a major theoretical advance.
  • Multivalued Supermartingales: The introduction of this new type of supermartingale is a key technical contribution, enabling the derivation of the desired bounds.
  • Defensive Forecasting Power: The paper demonstrates the versatility and power of the Defensive Forecasting framework for achieving novel theoretical guarantees.

Key Results

The paper presents two main theoretical results:

  • Theorem 8: For DTOL with $N$ actions, the DFA achieves an $\epsilon$-quantile regret bound of $L_T < L_\epsilon + \sqrt{\frac{2}{\epsilon} \ln \frac{1}{\epsilon}} + O(\sqrt{T \ln T})$. This bound is uniform in $T$ and $\epsilon$, and crucially, it depends on $\epsilon$ (related to the effective number of experts) but not on $N$.
  • Theorem 9: For DTOL with $N$ actions, there exists a strategy that achieves a bound of $L_T < L_\epsilon + 2\sqrt{T \ln \frac{1}{\epsilon}} + 7\sqrt{T}$. This bound is also independent of the nominal number of experts and is asymptotically optimal in $T$.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on deriving new bounds. It doesn't include empirical evaluations to demonstrate the practical performance of the proposed algorithms.
  • Asymptotic Behavior: While the bounds are theoretically significant, the paper notes that for fixed $\epsilon$ and large $T$, their bounds might be asymptotically worse than some existing bounds that do depend on $N$. However, their bounds are superior when $T$ is relatively small or when the effective number of experts is much smaller than the nominal number.
  • Open Questions: The authors mention that similar bounds for internal regret and time selection functions are derived with modest changes, but they leave open the question of whether similar bounds can be obtained when the (effective) number of actions is not known. They also suggest that their algorithms can be adapted for settings where experts arrive at different times.

Summary updated

BibTeX
@inproceedings{chernov2010prediction,
  author = {Alexey V. Chernov and Vladimir Vovk},
  title = {{Prediction with Advice of Unknown Number of Experts}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure