Structured Convex Optimization under Submodular Constraints
This work addresses efficiency improvements in optimization for machine learning, particularly in sparse optimization, but appears incremental as it builds on existing submodular methods.
The paper tackles convex optimization problems under submodular constraints by leveraging a directed graph structure, showing that these problems can be solved more efficiently via reduction to maximum flow, with computational experiments demonstrating effectiveness.
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.