Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm

Ryotaro Mitsuboshi, Kohei Hatano, Eiji TakimotoarXiv 2023 · arXiv

TL;DR

This paper introduces a highly efficient "metarounding" algorithm that converts offline relaxation-based approximation algorithms into online linear optimization algorithms. By leveraging a Frank-Wolfe-based framework and a clever dual-bounding technique, the authors eliminate a costly factor of $n^2$ from the required number of oracle calls per round, achieving massive practical speedups while maintaining optimal regret bounds.

What Problem Does This Paper Address?

In many real-world applications—such as routing, ad placement, and resource allocation—decisions must be made sequentially using complex combinatorial structures (e.g., matchings, spanning trees, or paths). This setup is known as Online Combinatorial Linear Optimization (OCLO). The goal is to minimize $\alpha$-regret, which measures how much worse the online player's cumulative loss is compared to the best static combinatorial choice in hindsight, scaled by an approximation factor $\alpha \ge 1$.

One powerful, generic way to solve OCLO is metarounding. As shown in Figure 1, metarounding acts as a bridge: it takes a fractional, continuous decision from an Online Linear Optimization (OLO) algorithm over a relaxed space and randomly "rounds" it into a valid discrete combinatorial object. It does this by repeatedly querying an offline approximation algorithm (an "oracle").

Figure 1: A conceptual diagram for online combinatorial linear optimization via metarounding. In each round t, metarounding converts a vector xt into a combinatorial vector ct ∈C.

However, existing metarounding methods (like the state-of-the-art by Fujita et al.) are computationally expensive. They require $O(n^2)$ oracle calls per trial, where $n$ is the dimension of the vector space. For large-scale problems, this dependency on the dimension makes metarounding prohibitively slow.

Methods

The authors propose a new boosting-based metarounding algorithm (Algorithm 1) inspired by ERLPBoost (Entropy Regularized Linear Programming Boosting) and the Frank-Wolfe framework. Their approach hinges on two main technical steps:

  1. Bounding the Dual Variable: The authors prove that the variables in the Lagrange dual problem can be bounded by a constant $M$ dependent on the input vector. This allows them to reformulate the unbounded dual problem into an equivalent, bounded optimization problem over a probability simplex.
  2. Entropy Regularization & Frank-Wolfe Optimization: They add a strongly convex entropy regularizer to the objective function. By applying Fenchel duality, the problem transforms into minimizing a smooth function over a simplex. They then solve this using a Frank-Wolfe-style conditional gradient method, which naturally uses the offline approximation algorithm as its linear optimization oracle.

Datasets

The algorithm was evaluated using a synthetic set cover instance, generated following the standard experimental procedure established in prior literature (Fujita et al., 2013).

  • Setup: The item size was fixed at $m = 10$.
  • Scaling: To test scalability, the number of sets $n$ was varied across $\{10, 50, 100, 200, 500, 1000\}$.
  • Inputs: The input for the metarounding algorithm was a fractional solution to the relaxed set cover problem under a random cost vector.

Key Insights and Ideas

  • Eliminating the Dimension Dependency: The core "aha!" moment comes from the dual reformulation. Prior work suffered from an $n^2$ factor because the dual space was unbounded, forcing loose approximations. Bounding the dual variables directly removes the dimension $n$ from the iteration complexity's leading terms.
  • The Smoothness Shortcut: By regularizing the primal problem with relative entropy, its Fenchel conjugate becomes mathematically smooth ($\eta$-smooth). This smoothness is exactly what allows Frank-Wolfe algorithms to converge rapidly—specifically in $O(1/\epsilon^2)$ iterations—yielding a much tighter convergence bound.
  • A Unified View of Boosting: The resulting algorithm generalizes ERLPBoost. When the input vector $\mathbf{x} = \mathbf{1}$, the method gracefully reduces back to standard soft-margin margin optimization boosting.

Key Results

The paper delivers major improvements both theoretically and empirically:

  • Theoretical Complexity: As summarized in Table 1, the number of oracle calls per trial drops from $O(D_\infty^2 n^2 \ln(n)/\epsilon^2)$ to $O(D_\infty^2 \ln(n)/\epsilon^2)$. The $n^2$ factor is completely gone, while the algorithm retains the optimal $O(T^{1/2})$ regret bound.
Table 1: Comparison of the previous works. Our assumption is the same as the one in Fujita et al. [9]. Note that the work by Fujita et al. and ours aim to optimize (α + ϵ)-regret RT (α + ϵ) for arbitrarily small ϵ > 0.
  • Empirical Speedups: In experiments (Figure 2, left), the proposed algorithm runs orders of magnitude faster than Fujita et al.'s method. For $n=1000$, the previous method takes over $10^4$ seconds, whereas the new Frank-Wolfe-based approach finishes in a fraction of a second.
  • Lower Cumulative Loss: When plugged into an online game, the algorithm achieves significantly lower cumulative loss over 1,000 rounds compared to alternative baseline conversion methods like Kakade et al., 2009 (Figure 2, right).
Figure 2: Comparison of previous works and our work. Both figure uses combinatorial vector of dimension n = 20. Left: comparison of running time. Right: comparison of cumulative losses. KKL ’09 is the algorithm proposed by Kakade et al., 2009 [15]. In this experiment, we set |C| = 100.

Limitations and Future Work

While the theoretical bounds are robust, the empirical evaluation is limited to a synthetic set cover problem. Testing the algorithm on diverse, large-scale real-world combinatorial problems (such as online shortest path routing or dynamic spanning tree maintenance) would further validate its practical utility. Additionally, the algorithm assumes the existence of a relaxation-based offline approximation algorithm; extending this framework to non-relax-based or purely black-box approximation oracles remains an open challenge.

Summary updated

Abstract

Metarounding is an approach to convert an approximation algorithm for linear optimization over some combinatorial classes to an online linear optimization algorithm for the same class. We propose a new metarounding algorithm under a natural assumption that a relax-based approximation algorithm exists for the combinatorial class. Our algorithm is much more efficient in both theoretical and practical aspects.
BibTeX
@misc{mitsuboshi2023online,
  author = {Ryotaro Mitsuboshi and Kohei Hatano and Eiji Takimoto},
  title = {{Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm}},
  year = {2023},
  eprint = {2310.12629},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.12629},
}

Loading related content...

Figure