Abstract
First-order methods provide a simple general framework to quickly recover approximate solutions to smooth and non-smooth convex problems.In the context of linear programming, the running time of these algorithm has a quadratic dependence on the largest entry in the constraint matrix, I.e., the width of the LP. While this dependence is inevitable for algorithms solving general non-smooth convex problems, it can surprisingly be eliminated in the context of packing and covering LPs, when the constraint matrices are non-negative, yielding truly-polynomial time algorithms.
In this talk, I will review some of the rich history of width-independent algorithms, discuss some recent progress through an optimization perspective and highlight a number of open problems. Conceptually, I will attempt to provide a simple intuition of why non-negativity enables width-independence.