In model selection problems for machine learning, the desire for a well-performing model with meaningful structure is typically expressed through a regularized optimization problem. In many scenarios, however, the meaningful structure is specified in some discrete space, leading to difficult nonconvex optimization problems. In this paper, we connect the model selection problem with structure-promoting regularizers to submodular function minimization with continuous and discrete arguments. In particular, we leverage the theory of submodular functions to identify a class of these problems that can be solved exactly and efficiently with an agnostic combination of discrete and continuous optimization routines. We show how simple continuous or discrete constraints can also be handled for certain problem classes and extend these ideas to a robust optimization framework. We also show how some problems outside of this class can be embedded within the class, further extending the class of problems our framework can accommodate. Finally, we numerically validate our theoretical results with several proof-of-concept examples with synthetic and real-world data, comparing against state-of-the-art algorithms.
翻译:在机器学习的模型选择问题中,对有有意义结构的完善模型的愿望通常通过正规化优化问题来表达。但是,在许多情景中,有意义的结构在某些离散的空间里被具体指定,导致困难的非convex优化问题。在本文中,我们将模型选择问题与促进结构的规范化者联系起来,用连续和离散的参数来将亚模块功能最小化。特别是,我们利用子模块功能理论来找出这些问题的一类,这些问题可以通过分流和连续优化常规的不可知性组合来准确和有效地加以解决。我们展示了对某些问题类别可以如何处理简单的连续或离散的限制,并将这些概念扩大到一个强有力的优化框架。我们还展示了该类别以外的一些问题如何嵌入该类别,进一步扩大了我们框架可以容纳的问题类别。最后,我们用数数化的理论结果验证了我们理论的结果,用合成和现实世界数据的一些验证实例来比较最新算算法。