Online learning for min-max discrete problems

Evripidis Bampis, Dimitris Christou, Bruno Escoffier, Nguyen Kim Thang

TL;DR

This paper explores the hidden computational hurdles of moving non-linear discrete optimization problems into an online learning setting. The authors prove that many problems which are easy to solve offline (like min-max vertex cover) become computationally "hard" to learn with low regret, while also providing a matching upper bound using gradient descent and a positive result for a generalized knapsack problem.

What Problem Does This Paper Address?

In the world of online learning, an algorithm makes a sequence of decisions over time. After each decision, an "adversary" reveals a cost, and the goal is to minimize regret—the difference between the algorithm's total cost and the cost of the best single decision made in hindsight.

For linear problems (where the cost is a simple sum), we have efficient tools like "Follow the Perturbed Leader" (FTPL). However, many real-world scenarios involve non-linear objectives, specifically min-max (or "egalitarian") objectives, where we want to minimize the maximum weight of any element in our solution (e.g., preventing any single network link from being overloaded).

The central question this paper tackles is: Does the non-linear nature of min-max problems make them fundamentally harder to learn online, even if they are easy to solve in a static, offline setting?

Methods

The authors approach this through three main lenses:

  1. Hardness Reductions: They develop a general reduction showing that if a standard cardinality problem (like Vertex Cover) is NP-hard, its online min-max version cannot have "vanishing regret" (regret that grows slower than time) unless $NP = RP$.
  2. Algorithm Design (OGD): They adapt Online Gradient Descent (OGD) to the discrete min-max vertex cover problem. Since OGD works on continuous spaces, they use a fractional relaxation of the problem and then apply a rounding procedure to get a discrete solution.
  3. Oracle-Based Learning (GFTPL): They examine the Generalized Follow the Perturbed Leader (GFTPL) framework. This method relies on an "offline oracle"—a subroutine that can solve the problem given all past data. They extend this framework to work with an FPTAS (a very high-quality approximation scheme) instead of requiring an exact solution.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets. Instead, it evaluates algorithmic performance using mathematical proofs on standard combinatorial structures, including:

  • Vertex Cover (selecting nodes to "cover" all edges in a graph).
  • Perfect Matching (pairing all vertices in a graph).
  • Knapsack Problems (selecting items to maximize profit within a weight limit).
  • Job Scheduling ($P3||C_{max}$).

Key Insights and Ideas

  • The "Easy-to-Hard" Paradox: Some problems are trivial to solve offline but become impossible to learn perfectly online. For example, finding a vertex cover that minimizes the maximum vertex weight is easy offline, but the authors prove you cannot achieve better than a 2-approximation for regret online (assuming the Unique Games Conjecture).
  • Non-linearity is the Culprit: In linear problems, optimizing over many instances is as easy as optimizing over one. In min-max problems, the "multi-instance" version (the oracle needed for learning) often becomes strongly NP-hard, creating a massive bottleneck for traditional learning strategies like "Follow the Leader."
  • OGD vs. FTL: The paper highlights a "sharp separation" between strategies. While "Follow the Leader" styles struggle because their required oracles are NP-hard, Online Gradient Descent can sometimes bypass this by working with continuous relaxations, providing a tight 2-regret bound for min-max vertex cover.

Key Results

  • Lower Bounds: For the online min-max vertex cover, the authors show no polynomial-time algorithm can achieve $(2 - \epsilon)$-regret unless Unique Games is in $RP$.
  • Matching Upper Bound: They provide an OGD-based algorithm that achieves a 2-regret bound, perfectly matching the lower bound.
  • Positive Result for Knapsack: They prove that a Generalized Knapsack Problem (where you can exceed capacity for a penalty) does admit a polynomial-time vanishing regret algorithm using their extended GFTPL framework.
  • Complexity of Oracles: They prove that the multi-instance versions of min-max perfect matching, min-max path, and certain scheduling problems are all strongly NP-hard, explaining why simple learning rules fail for them.

Limitations and Future Work

The authors note that their reduction framework is currently focused on min-max objectives. A natural next step is extending these hardness results to other types of non-linear objective functions. Additionally, while they found a matching bound for vertex cover, many other non-linear discrete problems still lack online algorithms with approximation ratios that match their theoretical lower bounds. Bridging this gap remains an open challenge for the community.

Summary updated

Abstract

We study various discrete nonlinear combinatorial optimization problems in an online learning framework. In the first part, we address the question of whether there are negative results showing that getting a vanishing (or even vanishing approximate) regret is computational hard. We provide a general reduction showing that many (min-max) polynomial time solvable problems not only do not have a vanishing regret, but also no vanishing approximation $α$-regret, for some $α$ (unless $NP=BPP$). Then, we focus on a particular min-max problem, the min-max version of the vertex cover problem which is solvable in polynomial time in the offline case. The previous reduction proves that there is no $(2-ε)$-regret online algorithm, unless Unique Game is in $BPP$; we prove a matching upper bound providing an online algorithm based on the online gradient descent method. Then, we turn our attention to online learning algorithms that are based on an offline optimization oracle that, given a set of instances of the problem, is able to compute the optimum static solution. We show that for different nonlinear discrete optimization problems, it is strongly $NP$-hard to solve the offline optimization oracle, even for problems that can be solved in polynomial time in the static case (e.g. min-max vertex cover, min-max perfect matching, etc.). On the positive side, we present an online algorithm with vanishing regret that is based on the follow the perturbed leader algorithm for a generalized knapsack problem.
BibTeX
@article{bampis2022online,
  author = {Evripidis Bampis and Dimitris Christou and Bruno Escoffier and Nguyen Kim Thang},
  title = {{Online learning for min-max discrete problems}},
  journal = {Theoretical Computer Science},
  year = {2022},
  doi = {10.1016/j.tcs.2022.07.024},
}
Figure