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:
https://arxiv.org/abs/0801.1987
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.
