DIFFERENCE-OF-CONVEX LEARNING: DIRECTIONAL STATIONARITY, OPTIMALITY, AND SPARSITY
DIFFERENCE-OF-CONVEX LEARNING: DIRECTIONAL STATIONARITY, OPTIMALITY, AND SPARSITY
复制标题
DOI：
10.1137/16m1084754
复制
发表时间：
2017-01-01
影响因子：
3.1
通讯作者：
Xin, Jack
中科院分区：
文献类型：
--
作者：
Ahn, Miju;Pang, Jong-Shi;Xin, Jack
研究统计学习中变量选择的基本双准则优化问题；这两个标准是损失/残差函数和模型控制（也称为正则化，惩罚）。前一个函数衡量学习模型对数据的适应度，后一个函数用来控制模型的复杂性。我们关注的是损失函数是（强）凸的，而模型控制函数是一个差的-凸（dc）稀疏度测度的情况。本文建立了双准则优化问题的非凸拉格朗日公式的定向平稳解的一些基本最优性和稀疏性性质，基于许多著名的稀疏函数的特殊结构dc表示，可以在分析中有益地利用。我们将拉格朗日优化问题与惩罚约束问题联系起来，根据它们各自的d（方向）-平稳解；这与由于非凸性而不可计算的问题的（全局）最小值的一般分析相反。最重要的是，我们提供了非凸拉格朗日公式的d（方向）-平稳解是全局极小值的充分条件（可能由于不可微性而受到限制），从而填补了以前基于极小值的分析与实际计算考虑之间的空白。所建立的关系使我们可以很容易地将拉格朗日公式的推导结果应用于惩罚约束公式。讨论了精确稀疏函数和代理稀疏函数的条件特殊化，为统计学习问题的现有非凸公式提供了最优性和稀疏性结果。
This paper studies a fundamental bicriteria optimization problem for variable selection in statistical learning; the two criteria are a loss/residual function and a model control (also called regularization, penalty). The former function measures the fitness of the learning model to data and the latter function is employed as a control of the complexity of the model. We focus on the case where the loss function is (strongly) convex and the model control function is a difference of -convex (dc) sparsity measure. Our paper establishes some fundamental optimality and sparsity properties of directional stationary solutions to a nonconvex Lagrangian formulation of the bicriteria optimization problem, based on a specially structured dc representation of many well-known sparsity functions that can be profitably exploited in the analysis. We relate the Lagrangian optimization problem with the penalty constrained problem in terms of their respective d(irectional)-stationary solutions; this is in contrast to common analysis that pertains to the (global) minimizers of the problem which are not computable due to nonconvexity. Most importantly, we provide sufficient conditions under which the d(irectional)-stationary solutions of the nonconvex Lagrangian formulation are global minimizers (possibly restricted due to nondifferentiability), thereby filling the gap between previous minimizer-based analysis and practical computational considerations. The established relation allows us to readily apply the derived results for the Lagrangian formulation to the penalty constrained formulation. Specializations of the conditions to exact and surrogate sparsity functions are discussed, yielding optimality and sparsity results for existing nonconvex formulations of the statistical learning problem.