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.
Perhaps this reference will be relevant to your question.

Grigoriadis M., Khachiyan L. A sublinear randomized approximation algorithm to matrix games// Oper. Res. Lett. 1995. V. 18. No 2. P. 53-58.

The algorithm therein is 1) randomized 2) the error is ADDITIVE, but 3) is sublinear (you need to check only tiny fraction of the input to find solutiom with high probability).

Sergey