论文标题
查询定价信息的策略，重新审视
Query strategies for priced information, revisited
论文作者
论文摘要
我们考虑了Charikar等人提出的定价信息的查询策略的问题。在此问题中，给出了算法设计器一个函数$ f：\ {0,1 \}^n \ to \ { - 1,1 \} $，并且与$ n $坐标相关的价格。目标是设计一种查询策略，以确定$ f $的价值，以最低成本确定未知输入的价值。 有关此问题的先前工作集中在特定的功能上。我们分析了一种适用于所有功能$ f $的简单自然策略，并表明它相对于最佳策略的性能可以根据$ f $的基本复杂度度量（其影响）来表达。对于$ \ varepsilon \ in（0，\ frac1 {2}）$，编写$ \ mathsf {opt} $表示最佳策略的预期成本，该策略最多会出现$ \ varepsilon $ -Fractions的输入，我们的策略预期的是$ \ \ \ \ \ \ \ \ \ \ \ cdot { \ Mathrm {Inf}（f）/\ Varepsilon^2 $，并且最多也要在$ o（\ varepsilon）$ - 输入的分数上犯错。这种连接产生了新的保证，可以补充现有的函数类别，这些函数类已在此上下文中进行了研究，并为新课程提供了新的保证。 最后，我们表明，改进我们实现的参数将需要在正确学习决策树的长期开放问题上取得进展。
We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function $f : \{0,1\}^n \to \{-1,1\}$ and a price associated with each of the $n$ coordinates. The goal is to design a query strategy for determining $f$'s value on unknown inputs for minimum cost. Prior works on this problem have focused on specific classes of functions. We analyze a simple and natural strategy that applies to all functions $f$, and show that its performance relative to the optimal strategy can be expressed in terms of a basic complexity measure of $f$, its influence. For $\varepsilon \in (0,\frac1{2})$, writing $\mathsf{opt}$ to denote the expected cost of the optimal strategy that errs on at most an $\varepsilon$-fraction of inputs, our strategy has expected cost $\mathsf{opt} \cdot \mathrm{Inf}(f)/\varepsilon^2$ and also errs on at most an $O(\varepsilon)$-fraction of inputs. This connection yields new guarantees that complement existing ones for a number of function classes that have been studied in this context, as well as new guarantees for new classes. Finally, we show that improving on the parameters that we achieve will require making progress on the longstanding open problem of properly learning decision trees.
