Apr, 2020

大规模稀疏回归：基于一阶优化的分支定界

PDF
TL;DR本文提出了一种新的混合整数规划框架，结合非线性分支定界和坐标下降方法，用于计算最小二乘回归中的 $l_{0} l_{2}$ 惩罚，证明了该框架不仅比现有方法快很多，而且可以处理一些统计性较强的示例，并提供了 $L0BnB$ 工具箱的开源实现。
least squares regression$\ell_0\ell_2$ regularizationmixed integer programmingbranch-and-bound frameworkcoordinate descent
发现论文，激发创造
  • 一个新的分支界限修剪框架用于 $l_0$ 正则化问题

    通过分支定界（Branch-and-Bound）算法解决涉及 $\ell_0$ 正则化的学习问题，并提出一种用于一类通用的 $\ell_0$ 正则化问题的修剪测试的替代方法，该方法可以同时评估多个区域，在标准分支定界实现中具有可忽略的计算开销，并通过数值模拟表明该修剪策略可以将分支定界过程的求解时间从机器学习应用中常见的典型问题的数量级上提升。

    Jun, 2024

  • 使用离散优化的稀疏高斯图模型：计算和统计视角

    我们提出了一种稀疏图的学习方法，应用于一个无向高斯图模型的问题，并通过凸混合整数规划框架得到了新的估计器，该估计器在稀疏性精度矩阵的估计与变量选择方面有着优越的性能。

    Jul, 2023

  • 关于带有 L1 正则化的最小二乘回归的一些尖锐性能界

    通过参数估计准确性和特征选择质量两个角度，我们得出了最小二乘回归与 $L_1$ 正则化的性能边界。对于 $L_1$ 正则化得出的主要结果扩展了 Dantzig 选择器中 [Ann.Statist.35 (2007) 2313-2351] 类似的结果，并肯定回答了 [Ann.Statist.35 (2007) 2358-2364] 中的一个未解问题。此外，该结果还产生了一种更广泛的特征选择观点，该观点比一些最近的工作具有更少的约束条件。基于理论洞察力，我们分析了具有选择性处罚的新型两阶段 $L_1$ 正则化过程，并表明如果目标参数向量可以分解为具有大系数的稀疏参数向量和具有相对较小系数的其他较少稀疏向量的总和，则两阶段过程可以提高性能。

    Aug, 2009

  • 多元凸回归及其变形的计算框架

    本文针对多元凸回归函数的非参数最小二乘估计器提出一种基于增广 Lagrange 方法的可扩展算法框架，并且给出了平滑凸的 LSE 拟合（分段仿射）的凸逼近方法及近似质量的形式保证，此外，提出了一种 Lipschitz 凸回归的正则化方案，并研究了所得 LSE 的收敛速度．数值研究表明了本文所提算法的可扩展性。

    Sep, 2015

  • 正则化无界贝叶斯优化

    本研究基于贝叶斯优化方法，提出了两种自动调整搜索空间大小的算法，并将它们应用于深度学习中的优化问题，包括超参数调优、神经网络模型训练等，取得了不错的结果。

    Aug, 2015

  • 非凸双层优化与一阶随机逼近的惩罚方法

    本文主要研究双层优化的一阶算法，目标函数在两个层次上都是光滑但可能非凸的，变量限制在闭凸集合中。首先通过罚函数方法，研究了双层优化的景观，并建立了罚函数与超目标之间的强连接。接着，提出了一阶算法来优化罚函数，以找到一个 ε- 稳定解。在满足小误差近似条件的情况下，算法以 O (ε^{-3}) 和 O (ε^{-7}) 程度的复杂度达到 ε- 稳定点。在随机预言机的额外假设下，算法的实现可以完全使用单循环方式，并分别达到 O (ε^{-3}) 和 O (ε^{-5}) 的优化复杂度。

    Sep, 2023

  • 高维数据的深度修剪残差罚最小二乘回归模型

    大数据时代中的数据挑战包括：维度常常大于样本大小，异常值或污染点通常隐藏且更难检测。这篇论文系统地检查了文献中的主要惩罚回归方法，并提出了一种基于剪枝残差最小平方和的鲁棒惩罚回归方法，实验证明在估计和预测准确性方面胜过其他竞争对手。

    Sep, 2023

  • 稀疏高维回归：精确可扩展算法和相变

    本文提出了一种新的二元凸重构稀疏回归问题的方法，并提供了一种新的切平面方法来解决高维数据时出现的问题。实验证明，与当前最先进的算法相比，本方法能够在秒内解决样本数和回归器数均在 10 万个数量级的稀疏回归问题，并且可以观察到新的相变现象。

    Sep, 2017

  • 具有非凸性的正则化 M 估计：局部最优解的统计和算法理论

    本文提供了关于正则化 M - 估计器局部最优解的新理论结果，覆盖了许多感兴趣的非凸目标函数，包括误差 - 变量线性模型的校正套索方法，具有非凸罚项的广义线性模型回归，以及高维图模型估计，我们提供了误差的上限，证明了我们的理论结果，同时提出了一种简单的修改方法，使得可以在 log (1/∊) 步内以任意精度获得近似全局最优解，这是任何一阶方法可能达到的最快速度。

    May, 2013

  • 稀疏非凸学习问题的最优计算和统计收敛速率

    提出了一种近似正则化路径追踪方法，用于求解许多具有非凸问题求解的学习问题，该算法迭代复杂度与全正则化路径相同，可以同时提供统计和计算收敛率的显式表达式，并可以实现全局几何收敛，以及对于所有近似局部解的样本复杂度分析和精确支持恢复结果。

    Jun, 2013