Nearly Tight Bounds for Discrete Search under Outlier Noise
Nearly Tight Bounds for Discrete Search under Outlier Noise
复制标题
离群噪声下离散搜索的近乎严格的界限
DOI：
10.1137/1.9781611977066.11
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Nikpey, Hesam
中科院分区：
文献类型：
--
作者：
De, Anindya;Khanna, Sanjeev;Li, Huan;Nikpey, Hesam
二分搜索是最基本的搜索例程之一，利用搜索空间的隐藏结构。特别是，它以指数方式降低了搜索的复杂性，假设搜索空间是单调的。本文提出了一个基本的问题-如何查询复杂性的搜索问题的变化，如果数据有腐败？特别地，我们研究了强离群噪声模型，并假设这种破坏的分数的界，建立了以下问题的几乎匹配的上界和下界：（i）在大小为[n]的有序集上的二分搜索;（ii）在偏序集{0，1}d上的搜索;（iii）在偏序集[n]d上的搜索。在所有这三种情况下，我们使用随机化来创建鲁棒版本的经典算法，这些问题处理损坏的数据与相对较小的性能损失，指定为corruptionK量的函数。我们补充这些算法的结果与几乎匹配的下界，表明没有随机算法可以解决这些问题，查询复杂度作为一个函数的函数的一个较小的性能打击。
Binary search is one of the most fundamental search routines, exploiting the hidden structure of the search space. In particular, it cuts down exponentially on the complexity of the search assuming that the search space is monotone. This paper is prompted by a basic question - how does the query complexity of the search problem change if the data has corruption? In particular, we study the powerfuloutlier noise modeland assuming a bound on the fraction of such corruptions, establish nearly matching upper and lower bounds for the following problems: (i) binary search on an ordered set of size [n]; (ii) search on the posets {0, 1}d; and (iii) search on the posets [n]d. In all three cases, we use randomization to create robust versions of classical algorithms for these problems that handle corrupted data with relatively small performance penalties, specified as a function of the amount of corruptionK. We complement these algorithmic results with almost matching lower bounds that show that no randomized algorithm can solve these problems with a smaller performance hit on the query complexity as a function ofK.
登录
查看更多内容
单调布尔函数的交互式学习
影响因子：
8.1
作者：
Boris Kovalerchuk;E. Triantaphyllou;A. S. Deshpande;E. Vityaev
通讯作者：
E. Vityaev
DOI：
--
发表时间：
2015
期刊：
Neural Information Processing Systems
影响因子：
--
作者：
Yaron Singer;J. Vondrák
通讯作者：
J. Vondrák
二十个（简单）问题
DOI：
10.1145/3055399.3055422
发表时间：
2016
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Y. Dagan;Yuval Filmus;Ariel Gabizon;S. Moran
通讯作者：
S. Moran
处理二分查找过程中的错误
DOI：
--
发表时间：
1980
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
R. Rivest;A. Meyer;D. Kleitman;Karl Winklmann;J. Spencer
通讯作者：
J. Spencer
具有离群噪声的凸函数的近似优化
DOI：
--
发表时间：
2021
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
De, Anindya;Khanna, Sanjeev;Li, Huan;Nikpey, Hesam
通讯作者：
Nikpey, Hesam