<p>Perhaps this reference will be relevant to your question.</p>

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

<p>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).</p>

<p>Sergey</p>

CC BY-SA 2.5
2010-11-23T17:20:37.643Z
Indeed that paper is quite relevant. It's the second link given in the references section of my question.
Warren Schudy
CC BY-SA 2.5
2010-11-28T15:55:02.880Z
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
Sergey
CC BY-SA 2.5
2010-11-22T18:52:11.790Z
2010-11-22T18:52:11.790Z
Sergey
<p>For concreteness consider the LP for solving a two-player zero-sum game where each player has <span class="math-container">$n$</span> actions. Suppose each entry of the payoff matrix <span class="math-container">$A$</span> is at most 1 in absolute value. For simplicity let's make no sparsity assumptions.</p>
<p>Suppose runtime <span class="math-container">$T$</span> is available to approximate the value of this game.</p>
<p>One technique for approximating this value is the multiplicative update method (known as no-regret learning in this context). This gives an error of <span class="math-container">$\tilde O(\sqrt{n/T})$</span>, where <span class="math-container">$\tilde O$</span> hides log factors.</p>
<p>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 <span class="math-container">$O(\exp(-T/n^3))$</span>.</p>
<p>The multiplicative update methods give error that's an inverse polynomial in <span class="math-container">$T$</span>. Interior point methods give error that's exponentially small in <span class="math-container">$T$</span>. 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.</p>
<p><strong>My question</strong>:</p>
<p>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.</p>
<p><strong>References</strong>:</p>
<p>Multiplicative update in general:</p>
<p><a href="http://www.cs.princeton.edu/%7Earora/pubs/MWsurvey.pdf" rel="nofollow noreferrer">http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf</a></p>
<p>Multiplicative update for zero-sum games:</p>
<p><a href="http://dx.doi.org/10.1016/0167-6377(95)00032-0" rel="nofollow noreferrer">http://dx.doi.org/10.1016/0167-6377(95)00032-0</a></p>
<p>Multiplicative update for covering/packing LPs:</p>
<p><a href="https://arxiv.org/abs/0801.1987" rel="nofollow noreferrer">https://arxiv.org/abs/0801.1987</a></p>
<p>The original interior point paper:</p>
<p><a href="http://math.stanford.edu/%7Elekheng/courses/302/classics/karmarkar.pdf" rel="nofollow noreferrer">http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf</a></p>
<p>Interior-point from an applied math perspective:</p>
<p><a href="http://www.athenasc.com/nonlinbook.html" rel="nofollow noreferrer">Bertsekas's Nonlinear Programming</a>, section 4.1.1.</p>

<ds.algorithms><approximation-algorithms><online-learning><linear-programming>
What are the best possible time/error tradeoffs for approximate solution of linear programs?
Warren Schudy
# What are the best possible time/error tradeoffs for approximate solution of linear programs?

(Asked by: username_0 on 2010-10-19)

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](http://www.cs.princeton.edu/%7Earora/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](http://math.stanford.edu/%7Elekheng/courses/302/classics/karmarkar.pdf)

Interior-point from an applied math perspective:

[Bertsekas's Nonlinear Programming](http://www.athenasc.com/nonlinbook.html), section 4.1.1.

**Tags:** ds.algorithms, approximation-algorithms, online-learning, linear-programming


---

## 1 answers

### Answer by username_1 on 2010-11-22. Score: 2

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).

username_1

> **Comments:**
> **username_0**: Indeed that paper is quite relevant. It's the second link given in the references section of my question.  
> **username_1**: 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. username_1  

---

