9.11 Frank-Wolfe: Solving a Quintillion-Vertex Problem in 100 Steps

The projection from the article "Arbitrage Is Just Projection" is the whole game: find the closest fair price to the current unfair one, and you have the trade, the profit, and the target. The problem is that the arbitrage-free shape has up to 9.2 quintillion corners for an NCAA-scale market, and every standard projection method wants to see all of them. Frank-Wolfe does the projection by looking at about a hundred corners out of the quintillion, adding one per step, and printing a number at each step that tells you how much profit you might still be leaving behind. If you have ever leaned on lazy evaluation to avoid computing something you did not need, this is the same instinct applied to arbitrage.

Why the direct approaches are dead on arrival

Projected gradient descent and interior-point methods, the usual tools, both need something you cannot afford. They either enumerate the corners of the shape or repeatedly check feasibility against the full constraint set at once. For a shape with quintillions of corners, neither finishes this century. The article "The Marginal Polytope" is where that wall first appears, and it is a hard wall, not a slow one.

Frank-Wolfe sidesteps it by never asking for the whole shape. It replaces the projection with a sequence of much simpler questions, each answered by one call to the oracle from the article "Trillions of Outcomes, 200 Constraints": hand it a direction, get back the single cheapest valid outcome. Each answer is one corner. The method builds its solution out of the few corners it actually needed, and the count of corners it needs to reach an accurate answer is small, on the order of a hundred, regardless of whether the shape has a thousand corners or a quintillion.

The loop, in the order a trader would run it

The algorithm is short. Strip the notation and it is five steps repeated.

start with a few known outcomes (the initial working set)
repeat:
    subproblem: best trade using only the outcomes found so far
    oracle:     ask for the worst outcome you have NOT yet considered
    update:     add that outcome to the working set
    gap:        compute how much profit you might still be missing
    stop:       if the gap is small enough, trade; else loop

Read each step for what it means, not what it computes. The subproblem is "given the handful of outcomes I have discovered, what is my best trade." That is a small convex problem over a few hundred corners, quick. The oracle call asks the integer-program solver the sharp question: among all valid outcomes, which one does my current trade handle worst. That worst offender is the corner worth adding, because it is the one most likely to break the trade if the world lands there. Add it, and the working set grows by one.

The gap is the part that makes this usable rather than merely convergent.

$$ g(p_t) = \nabla F(p_t) \cdot (p_t - z_t), \qquad D(p_t \,\|\, \theta) - D(p^* \,\|\, \theta) \le g(p_t) $$

The gap g at step t is the current iterate scored against the worst outcome the oracle just returned. The inequality is the reason it matters: the true distance to the real optimum is at most the gap. So the gap is a certified upper bound on how far you are from the best possible trade, computed for free at every step. It is a profit thermometer. When it is small relative to the profit you have already secured, you are done.

The stopping condition is one line of code.

if gap <= (1 - alpha) * divergence:
    break

With alpha set to 0.9, you break the moment your guaranteed profit reaches 90 percent of the theoretical maximum. The last 10 percent is not worth the iterations, because the market moves while you compute, and a trade captured now beats a marginally better trade captured too late. This connects straight to the profit guarantee from the article "Arbitrage Is Just Projection": the guaranteed profit is the divergence minus the gap, and convex duality keeps that non-negative, so stopping early is safe by construction.

The lazy-evaluation analogy, made concrete

Brute force enumerates all 9.2 quintillion brackets, computes the optimal trade over every one, then executes. It never finishes. Frank-Wolfe says: I will only look at the brackets that threaten my current trade. Each iteration, it asks the solver for the single bracket that most endangers where it stands. If no threatening bracket exists, the current trade is optimal or close enough, and it stops. After a hundred iterations you have examined a hundred brackets out of 9.2 quintillion and you hold a near-optimal trade with a mathematical profit guarantee attached.

A programmer sees this immediately. You do not evaluate the whole list. You pull elements one at a time, driven by need, and you stop when the next element cannot change your answer. The oracle is the generator; the gap is the "have I seen enough" check. The quintillion outcomes that never threatened your trade never get touched, and touching them would have added nothing.

How fast, and how many corners

The convergence rate is honest about being slow, and it does not matter as much as it sounds.

$$ F(p_t) - F(p^*) \;\le\; \frac{2L \cdot \text{diam}(M)^2}{t + 2} $$

The error shrinks like 1 over t, where t is the iteration count. After 100 iterations you are roughly 100 times more accurate than after one. That is slow next to gradient descent, but each iteration costs a single solver call, and you need on the order of tens to a hundred of them. The active set after t iterations holds at most its starting size plus t corners, so even 150 iterations on an NCAA-scale market leaves you working with around 150 corners, not a quintillion. Slow-per-step convergence over a tiny working set beats fast convergence you can never start because you cannot load the shape.

One term in that bound is a landmine, and it is labeled L, the Lipschitz constant, a measure of how fast the gradient can change. The whole rate is multiplied by it, and the guarantee only holds if L is finite. Note that word: finite.

The starting point, and the caveat that breaks everything

Frank-Wolfe needs a feasible place to begin. The initialization routine builds one by asking, for each unsettled security, two feasibility questions: is there a valid outcome where this security pays, and is there one where it does not. Three cases follow. Both feasible means the security is genuinely undecided, so both possibilities go into the starting set. Only one feasible means the security is already logically settled, so its price gets locked. The routine produces the initial working set, an interior point sitting strictly inside the shape (the average of the starting corners), and a record of anything it settled along the way. It runs in under a second even for a full bracket, and the interior point it produces is not a throwaway. The next article needs it.

The caveat. The convergence guarantee assumed L is finite, and on a log-scoring market maker, the kind Polymarket runs, L is infinite. The gradient of the market maker's cost function blows up as any price approaches zero, and the shape has corners where prices are exactly zero, because those are outcomes where a security does not pay. Approach one of those corners and the gradient runs to negative infinity, the rate bound becomes meaningless, and the algorithm either crashes or oscillates instead of converging. This is not an edge case you can ignore. It happens every time a security resolves, which is constantly. The clean loop in this article, run naively on a real prediction market, fails. The fix is the entire subject of the article "Why Your Arbitrage Solver Crashes at 99 Cents," and it is a necessity, not a refinement.

KEY POINTS

• Frank-Wolfe does the projection by adding one corner of the arbitrage-free shape per step, needing about a hundred corners out of up to 9.2 quintillion, because it never asks to see the whole shape at once.
• The loop is five steps: best trade over the corners found so far, ask the oracle for the worst unconsidered outcome, add it, compute the gap, stop if the gap is small. Each oracle call is one integer-program solve.
• The gap is a certified upper bound on how far you are from the optimal trade, printed free at every step. It is a profit thermometer, and the stop condition "gap at most (1 minus alpha) times divergence" with alpha 0.9 breaks at 90 percent of max profit.
• The analogy is lazy evaluation: pull outcomes one at a time driven by which one most threatens the current trade, and stop when the next one cannot change the answer. The untouched quintillion never mattered.
• Convergence is 1 over t, slow per step but cheap per step, and the working set stays around 150 corners even for a full bracket. Slow convergence over a tiny set beats fast convergence you cannot start.
• The rate multiplies by the Lipschitz constant L and only holds when L is finite. On a log-scoring market maker L is infinite because the gradient explodes near zero prices, so naive Frank-Wolfe crashes on real markets and needs the barrier fix.

References

• Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization - Jaggi (2013)
• Arbitrage-Free Combinatorial Market Making via Integer Programming - Kroer et al. (2016)