Operations Research Seminar: Swati Gupta

Convex Optimization over Submodular Polytopes

Swati Gupta, Georgia Institute of Technology

Motivated by bottlenecks in first-order optimization methods, we consider three problems: (i) convex minimization over submodular base polytopes, (ii) movement along a line inside extended submodular polytopes, and (iii) minimization of composite convex and submodular objectives. For (i), we will present a conceptually simple, strongly polynomial algorithm “Inc-Fix” to minimize separable, strictly convex functions. This is useful for computing projections by minimizing the so-called Bregman divergences (for e.g. squared Euclidean distance, KL-divergence) in each step of projection-based first-order methods like mirror descent. Next, (ii) many variants of the conditional gradient method and also Inc-Fix require the computation of the maximum feasible movement along a direction. The use of the discrete Newton’s method for this problem is natural, however no strongly polynomial bound was known for its number of iterations. We solve this open problem by providing a quadratic bound of O(n^2), resulting in a running time improvement by at least n^6 over the former state of the art. Finally, (iii) minimization of composite objectives has recently become popular for structured regression problems where the convex part is the natural regression loss function and the Lov\’{a}sz extension is used as a regularizer to promote sparsity of the model. We will discuss the resolution of Bach’s open problem regarding the running time of the original simplicial method for minimizing these. Our analysis relies on duality between minimization of composite objectives and convex minimization over the submodular base polytopes. 
(i) and (ii) are joint works with Michel Goemans and Patrick Jaillet and (iii) is joint work with Madeleine Udell and Song Zhou.