This paper by Mehryar Mohri and Scott Yang provides a significant computational and theoretical upgrade to the field of online learning. By introducing the concept of transductive regret, the authors unify several disparate branches of learning theory and provide a suite of algorithms that are orders of magnitude faster than previous state-of-the-art methods.
The Problem: Beyond External Regret
In the standard "prediction with expert advice" setting, a learner typically tries to minimize external regret—the difference between their cumulative loss and the loss of the single best expert in hindsight. However, external regret is a weak benchmark if no single expert performs well throughout the entire game, such as in non-stationary environments.
To address this, researchers previously developed stronger benchmarks like internal regret and swap regret. These compare the learner against a competitor who can systematically modify the learner's actions (e.g., "every time you played Expert A, you should have played Expert B").
Historically, these stronger benchmarks faced two major challenges:
- Fragmentation: Different types of regret (internal, swap, conditional swap) were treated as entirely separate problems.
- Computational Complexity: Minimizing swap regret traditionally required solving for the stationary distribution of an $N \times N$ matrix every round. This operation costs $O(N^3)$ time, making it prohibitively slow for large sets of experts.
Methods: A Unified and Efficient Approach
The paper’s core contribution is utilizing a Weighted Finite-State Transducer (WFST) approach to unify regret minimization and drastically reduce its computational overhead.
1. Transductive Regret
The authors define a new, general notion of regret where the competitor class is represented by a family of WFSTs. Because WFSTs can model complex sequence-to-sequence mappings, this single framework naturally encompasses and generalizes previous regret types:
- External Regret: Represented by a constant mapping.
- Swap Regret: Represented by all possible per-symbol swaps.
- Conditional Swap Regret: Represented by swaps that depend on a fixed history (k-grams).
2. The "FAST" Algorithms
To solve the computational bottleneck, the authors introduce the FASTSWAP and FASTTRANSDUCE algorithms. The key innovation is moving away from exact fixed-point computations.
Instead of using Gaussian elimination to find a stationary distribution ($O(N^3)$), they employ a Reduced Power Method (RPM). By performing a limited number of "modified power iterations" each round, they approximate the necessary distribution well enough to maintain theoretical regret guarantees while reducing the per-round complexity to $O(N^2 \log T)$.
Key Insights and Results
- Approximation is Enough: The authors prove that you do not need the exact stationary distribution of the transition matrix to minimize regret. A "good enough" approximation, updated iteratively, preserves the optimal $O(\sqrt{T})$ regret bound.
- Computational Efficiency: FASTSWAP achieves the same regret bound as the classic Blum-Mansour algorithm but improves per-iteration complexity from $O(N^3)$ to $O(N^2 \log T)$.
- Empirical Performance: In synthetic toy experiments with up to 200 base learners, the authors found that the algorithm required only about 4 iterations of the power method to reach sufficient accuracy, regardless of the number of experts. This suggests that in practice, the cost is effectively $O(N^2)$.
- Exponential Speedup for Time-Selection: In the "time-selection" setting (where regret is only calculated on specific rounds), previous algorithms were exponentially slow ($O(N^N)$). This paper provides the first polynomial-time algorithm for this setting.
- Sparsity Matters: The complexity of the transductive algorithm depends on the "in-degree" of the transducer. If the modification rules are sparse, the algorithm becomes even more efficient.
Limitations and Future Work
- The $\alpha$ Assumption: The efficiency of the FAST algorithms relies on a mild assumption that the sum of minimal probabilities assigned to experts is bounded below by a constant $\alpha > 0$. While often true in practice, it remains a theoretical constraint.
- Full Information Only: The current work focuses on the "full information" setting where the losses of all experts are revealed. Extending these efficient transductive methods to the Bandit setting (where only the loss of the chosen action is seen) remains an open challenge.
- Transducer Selection: The paper assumes the family of transducers is given a priori. A promising future direction is "learning the transducer"—automatically discovering the best modification rules directly from the data.
Summary updated