Smooth convex optimization problems over polytopes are an important class of problems that appear in many settings, such as low-rank matrix completion [1],structured supervised learning [2,3],electrical flowsovergraphs [4],video co-localization in computer vision [5], traffic assignment problems [6], and submodular function minimization [7].