标题： 一种用于最小化$\ell_1$正则化凸函数的降维算法 显示英文标题

标题： A Reduced-Space Algorithm for Minimizing $\ell_1$-Regularized Convex Functions

摘要： 我们提出了一种新的方法，用于最小化可微凸函数和$\ell_1$-范数正则化项的和。 新方法的主要特点包括：$(i)$一个随时间变化的索引集合，对应于在解中被预测为非零的变量（即，支持集）；$(ii)$在预测支持集的基础上定义的简化空间子问题；$(iii)$确定每个子问题必须被求解准确程度的条件，这允许采用牛顿法、牛顿共轭梯度法和坐标下降技术；$(iv)$一个计算上实用的条件，用于确定何时应更新预测的支持集；以及$(v)$一个简化的近端梯度步骤，在决定将变量添加到预测支持集时确保目标函数的充分下降。 我们证明了该方法的收敛性保证，并在大量模型预测问题上展示了其效率。 显示英文摘要

摘要： We present a new method for minimizing the sum of a differentiable convex function and an $\ell_1$-norm regularizer. The main features of the new method include: $(i)$ an evolving set of indices corresponding to variables that are predicted to be nonzero at a solution (i.e., the support); $(ii)$ a reduced-space subproblem defined in terms of the predicted support; $(iii)$ conditions that determine how accurately each subproblem must be solved, which allow for Newton, Newton-CG, and coordinate-descent techniques to be employed; $(iv)$ a computationally practical condition that determines when the predicted support should be updated; and $(v)$ a reduced proximal gradient step that ensures sufficient decrease in the objective function when it is decided that variables should be added to the predicted support. We prove a convergence guarantee for our method and demonstrate its efficiency on a large set of model prediction problems.