Unconditional Coresets for Regularized Loss Minimization
Unconditional Coresets for Regularized Loss Minimization
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Alireza Samadian;K. Pruhs;Benjamin Moseley;Sungjin Im;Ryan R. Curtin
中科院分区：
文献类型：
--
作者：
Alireza Samadian;K. Pruhs;Benjamin Moseley;Sungjin Im;Ryan R. Curtin
我们设计和数学分析基于采样的算法，用于在流行的大数据中实现的正规损失最小化问题，其中对数据的访问在某种程度上受到限制。可以忽略的假设量表的规范，而随着数据量表的范围，均匀尺寸的均匀样本具有较高的概率。回归或软边缘支撑向量机，正常化程序是常见的建议选择之一，该结果意味着尺寸O（d√n）的均匀样本具有很高的概率（CID：CID： 6.我们与两个下限的上限对比。从某种意义上说，均匀的采样接近最佳，因为通常不存在较小的核心集。
We design and mathematically analyze sampling-based algorithms for regularized loss minimization problems that are implementable in popular computational models for large data, in which the access to the data is restricted in some way. Our main result is that if the regularizer’s effect does not become negligible as the norm of the hypothesis scales, and as the data scales, then a uniform sample of modest size is with high probability a coreset. In the case that the loss function is either logistic regression or soft-margin support vector machines, and the regularizer is one of the common recommended choices, this result implies that a uniform sample of size O ( d √ n ) is with high probability a core-set of n points in (cid:60) d . We contrast this upper bound with two lower bounds. The first lower bound shows that our analysis of uniform sampling is tight; that is, a smaller uniform sample will likely not be a core set. The second lower bound shows that in some sense uniform sampling is close to optimal, as sig-nificantly smaller core sets do not generally exist.