Regret minimization is a powerful framework for repeated matrix-game playing, with certain provable guarantees on the accrued utility in comparison to that of the best fixed strategy. The framework has found numerous applications, including the rediscovery of efficient *sequential* algorithms for approximately solving linear programs (LPs). Indeed, the connection between regret minimization and LP solving is well understood and has inspired the discovery of many new algorithms.
How can we apply this understanding to devise a *parallel* algorithm for approximately solving LPs using the regret minimization framework? In this talk, I will present a brief introduction to regret minimization algorithms and show how to use them to obtain a parallel NC algorithm for approximately solving positive linear programs (PLPs), up to arbitrary accuracy. This algorithm can be viewed as a unification of earlier work on approximately solving PLPs, as seen through the regret minimization lens. Standard complexity theoretic assumptions rule out the possibility of such algorithms for linear programs in general.
This is joint work with Guy Blelloch and Anupam Gupta.