Approximation Schemes for ReLU Regression
Approximation Schemes for ReLU Regression
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;Surbhi Goel;Sushrut Karmalkar;Adam R. Klivans;M. Soltanolkotabi
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Surbhi Goel;Sushrut Karmalkar;Adam R. Klivans;M. Soltanolkotabi
我们考虑了ReLU回归的基本问题，其目标是输出最佳拟合的ReLU，相对于从一些未知分布中提取的平方损失。我们给出了这个问题的第一个有效的常数因子近似算法，假设底层分布满足一些弱浓度和反浓度条件（包括所有对数凹分布）。这解决了Goel等人的主要开放问题，他证明了任何精确的ReLU回归算法的结果都是困难的（直到一个加性$\n $）。使用更复杂的技术，我们可以改善我们的结果，并获得多项式时间的近似方案的任何亚高斯分布。鉴于上述硬度结果，这些保证不能得到实质性的改善。我们的主要见解是一个新的表征代理损失的非凸激活。虽然以前的工作已经建立了单调激活的凸代理的存在，我们表明，基本分布的属性实际上诱导强凸的损失，使我们能够将全局最小激活的周参数。
We consider the fundamental problem of ReLU regression, where the goal is to output the best fitting ReLU with respect to square loss given access to draws from some unknown distribution. We give the first efficient, constant-factor approximation algorithm for this problem assuming the underlying distribution satisfies some weak concentration and anti-concentration conditions (and includes, for example, all log-concave distributions). This solves the main open problem of Goel et al., who proved hardness results for any exact algorithm for ReLU regression (up to an additive $\epsilon$). Using more sophisticated techniques, we can improve our results and obtain a polynomial-time approximation scheme for any subgaussian distribution. Given the aforementioned hardness results, these guarantees can not be substantially improved. Our main insight is a new characterization of surrogate losses for nonconvex activations. While prior work had established the existence of convex surrogates for monotone activations, we show that properties of the underlying distribution actually induce strong convexity for the loss, allowing us to relate the global minimum to the activation's Chow parameters.