Structured Convex Optimization under Submodular Constraints

Abstract

A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constraints can be solved much more efficiently than general submodular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse optimization methods, in which the proposed methods are effective. Additionally, we evaluate the performance of the proposed method through computational experiments.

Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

References in corpus (2)

• Pathwise coordinate optimization
• Efficient Minimization of Decomposable Submodular Functions

Cited by in corpus (5)

• Attaining Fairness in Communication for Omniscience
• On a reduction for a class of resource allocation problems
• Determining Optimal Rates for Communication for Omniscience
• Fairness in Communication for Omniscience
• Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions