# What are the best possible time/error tradeoffs for approximate solution of linear programs?

For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity let's make no sparsity assumptions.

Suppose runtime $T$ is available to approximate the value of this game.

One technique for approximating this value is the multiplicative update method (known as no-regret learning in this context). This gives an error of $\tilde O(\sqrt{n/T})$, where $\tilde O$ hides log factors.

I don't know exactly what the error landscape for the best known interior point method looks like, but I'm guessing the error is something like $O(\exp(-T/n^3))$.

The multiplicative update methods give error that's an inverse polynomial in $T$. Interior point methods give error that's exponentially small in $T$. The error of the best of the two therefore slowly decreases for a while until interior point catches up, after which the error suddenly falls off a cliff. My instincts are against the best possible time/error tradeoffs behaving this way.

My question:

Is there an algorithm for approximate linear programming that smoothes out the corner of the time/error tradeoff curve? That is, an algorithm that does at least as well as the best of the two for any value of the available time parameter and has a relatively smooth time/error tradeoff. A more intelligent way to combine interior-point and multiplicative update techniques than taking the better of the two is one likely way to get such an algorithm.

References:

Multiplicative update in general:

http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Multiplicative update for zero-sum games:

http://dx.doi.org/10.1016/0167-6377(95)00032-0

Multiplicative update for covering/packing LPs:

http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf

The original interior point paper:

http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf

Interior-point from an applied math perspective:

Bertsekas's Nonlinear Programming, section 4.1.1.