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:

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.

1 Answer

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

• Indeed that paper is quite relevant. It's the second link given in the references section of my question. Nov 23 '10 at 17:20
• Pardon. I have overlooked that the reference already exists. Thus my comment should be removed or regarded as a review of one of the texts in your list. Some additional results of the same nature but via a more general framework may be found in Juditsky, A., Lan, G., Nemirovski, A., Shapiro, A. Stochastic Approximation approach to Stochastic Programming – SIAM Journal on Optimization 19:4 (2009), 1574-1609. Sergey Nov 28 '10 at 15:55