Majorizing measures for the optimizer

ConferencePreprintprobability
Sander Borst, Daniel Dadush, Neil Olver and Makrand Sinha,
Accepted to ICTS 2021

The theory of majorizing measures, extensively developed by Fernique, Talagrand and many others, provides one of the most general frameworks for controlling the behavior of stochastic processes. In particular, it can be applied to derive quantitative bounds on the expected suprema and the degree of continuity of sample paths for many processes.

One of the crowning achievements of the theory is Talagrand’s tight alternative characterization of the suprema of Gaussian processes in terms of majorizing measures. The proof of this theorem was difficult, and thus considerable effort was put into the task of developing both shorter and easier to understand proofs. A major reason for this difficulty was considered to be theory of majorizing measures itself, which had the reputation of being opaque and
mysterious. As a consequence, most recent treatments of the theory (including by Talagrand himself) have eschewed the use of majorizing measures in favor of a purely combinatorial approach (the generic chaining) where objects based on sequences of partitions provide roughly matching upper and lower bounds on the desired expected supremum.

In this paper, we return to majorizing measures as a primary object of study, and give a viewpoint that we think is natural and clarifying from an optimization perspective. As our main contribution, we give an algorithmic proof
of the majorizing measures theorem based on two parts:

  • We make the simple (but apparently new) observation that finding the best majorizing measure can be cast as a convex program.
    This also allows for efficiently computing the measure using off-the-shelf methods from convex optimization.
  • We obtain tree-based upper and lower bound certificates by rounding, in a series of steps, the primal and dual solutions to this convex program.

While duality has conceptually been part of the theory since its beginnings, as far as we are aware no explicit link to convex optimization has been previously made.

Emergent hypercongestion in Vickrey bottleneck networks

agtPreprint
Dario Frascaria, Neil Olver and Erik Verhoef
Tinbergen Institute Discussion Paper TI 2020-002/VIII

Hypercongestion—the phenomenon that higher traffic densities can reduce throughput—is well understood at the link level, but has also been observed in a macroscopic form at the level of traffic networks; for instance, in morning rush-hour traffic into a downtown core. In this paper, we show that macroscopic hypercongestion can occur as a purely emergent effect of dynamic equilibrium behaviour on a network, even if the underlying link dynamics (we consider Vickrey bottlenecks with spaceless vertical queues) do not exhibit hypercongestion.

Improved approximation algorithms for inventory problems

approximationnetworkPreprint
Thomas Bosman and Neil Olver
Preprint (arXiv:1912.00101). Accepted to IPCO 2020.

We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of N items and a discrete time horizon of T days in which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time t can be satisfied by an order on any day prior to t, but a holding
cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost. Our approximation factor for both problems is O(log log min(N,T)); this
improves exponentially on the previous best results.

A Duality-based 2-approximation algorithm for maximum agreement forest

approximationPreprint
N. Olver, F. Schalekamp, S. van der Ster, L. Stougie and A. van Zuylen
Preprint (arXiv:1811.05916)