论文标题
亚级别正规化多元凸回归的大规模回归
Subgradient Regularized Multivariate Convex Regression at Scale
论文作者
论文摘要
我们提出了新的大规模算法，用于将$ d $ dimensions中$ n $样品的亚级别正规化多元凸回归功能拟合 - 形状约束非参数回归中的关键问题，并在统计，工程和应用科学中应用了应用。无限维学习任务可以通过$ o（nd）$ deciest变量和$ O（n^2）$约束来表达凸二次程序（QP）。尽管可以在合理的运行时间内使用当前算法来解决具有$ n $的实例，但解决较大的问题（例如，$ n \大约10^4 $或$ 10^5 $）是计算上具有挑战性的。为此，我们在双QP上介绍了一个活动集类型算法。对于计算可伸缩性，我们允许近似减少的子问题的优化；并提出了扩展活动集的随机扩展规则。我们为我们的算法提供了新颖的计算保证。我们证明，我们的框架可以大约解决$ n = 10^5 $和$ d = 10 $在几分钟内的下级正规化凸回归问题的实例；与早期方法相比，显示出强大的计算性能。
We present new large-scale algorithms for fitting a subgradient regularized multivariate convex regression function to $n$ samples in $d$ dimensions -- a key problem in shape constrained nonparametric regression with applications in statistics, engineering and the applied sciences. The infinite-dimensional learning task can be expressed via a convex quadratic program (QP) with $O(nd)$ decision variables and $O(n^2)$ constraints. While instances with $n$ in the lower thousands can be addressed with current algorithms within reasonable runtimes, solving larger problems (e.g., $n\approx 10^4$ or $10^5$) is computationally challenging. To this end, we present an active set type algorithm on the dual QP. For computational scalability, we allow for approximate optimization of the reduced sub-problems; and propose randomized augmentation rules for expanding the active set. We derive novel computational guarantees for our algorithms. We demonstrate that our framework can approximately solve instances of the subgradient regularized convex regression problem with $n=10^5$ and $d=10$ within minutes; and shows strong computational performance compared to earlier approaches.
