Оценка среднего за полиномиальное время

20

Пусть . Мы хотим оценить среднее значение , то есть: .f E [ f ( n ) ] = 2 - nx { 0 , 1 } n f ( x )f:{0,1}n(2n,1]fE[f(n)]=2nx{0,1}nf(x)

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Пусть - (рандомизированный) алгоритм оценки. Предположим, что имеет черный ящик доступа к . Обозначим это через .E F E FEEfEf

Есть два условия:

1) Время выполнения оценщика: существует один многочлен такой, что для всех и всех время выполнения ограничено .n f E f ( 1 n ) p ( n )p()NеЕе(1N)п(N)Е[е(N)]

2) Точность оценки с уверенностью :δ существует один многочлен , такой что для всех и всех мы имеем с вероятностью не менее .Q()Nе1Q(N)<Ее(1N)Е[е(N)]<Q(N)δ

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

Существуют ли такие оценки?

Фон и мотивация

Я не упомянул свою мотивацию в начале, так как она требует большого количества базовых знаний. В любом случае, для энтузиастов, я кратко опишу это: необходимость в таких оценщиках возникает в контексте «Доказательств способностей», как определено в следующей статье:

Михир Белларе, Одед Голдрайх. Доказательство вычислительной способности , 1992. Неопубликованная рукопись.

В частности, в нижней части страницы 5 авторы неявно предположили существование таких оценщиков (здесь нет упоминания о точности, и время выполнения точно не определено; все же контекст четко определяет все).

Моей первой попыткой было прочесть « Образец сэмплеров --- вычислительная перспектива отбора проб ». Это относится к очень похожей проблеме, но определенная вероятность ошибки является аддитивной, а наша - мультипликативной. (Я не полностью прочитал газету, возможно, там упоминается, что мне нужно.)

РЕДАКТИРОВАТЬ (согласно запросу Цуёси): На самом деле, определение «Доказательства вычислительной способности» требует существования «экстрактора знаний», чье (ожидаемое) время выполнения равно . Поскольку мы не знаем , мы хотим оценить его; все же это не должно значительно изменить время выполнения: оно должно изменить его до полиномиального множителя. Условие точности пытается охватить такое требование. E[f(n)]п(N)Е[е(N)]Е[е(N)]

М.С. Дусти
источник
Я не могу понять условие точности. Что мешает алгоритму E всегда выводить 1? Вы имели в виду 1 / q (n) <(истинное значение) / (расчетное значение) <q (n)?
Цуёси Ито
Кажется, что p (n) = q (n) = O (1) и тривиальный алгоритм который выводит «1», должен работать. Время его выполнения - O (1), которое ограничено . И его точность <= 1, что меньше, чем q (n). Ее(1N)п(N)Е[е(N)]
Робин Котари
@Tsuyoshi & Robin: Простите, ребята, я пропустил одно условие в точности. Проверьте это сейчас!
MS Dousti
Кроме того, я предполагаю, что оценщик рандомизирован (просто потому, что иначе это выглядит невозможным). Это тот случай? Кроме того, если это так, что конкретно требуется для условия времени выполнения и условия точности?
Цуёси Ито
1
Я думаю, что я не совсем понимаю вопрос. Почему наивный сэмплер с черновой границей не является хорошим оценщиком?
Сильвен Пейроннет

Ответы:

15

РЕДАКТИРОВАТЬ: Это решает версию проблемы, где f выводит только 0 или 1. Но я думаю, что решение может быть адаптировано, чтобы оно работало для более общего случая.

Может быть, я неправильно понял вопрос, но это не выглядит слишком сложно.

Вместо оценки среднего, давайте подумаем об оценке числа 1 и назовем это число k. Пусть . Таким образом, среднее значение к / ш. Вы хотите оценить это в полиномиальном мультипликативном множителе за время O (N polylog (N) / k).Nзнак равно2N

Я думаю, что это можно сделать с точностью до любого постоянного мультипликативного фактора. Например, предположим, что вы хотите оценить это с точностью до коэффициента 2. Таким образом, выходной сигнал алгоритма будет между k / 2 и 2k.К'

Я нарисую алгоритм, который должен иметь соответствующее время выполнения. Сначала проверьте, находится ли k между N / 2 и N. Это легко, просто выберите несколько случайных значений, и если вы получите больше половины 1 с, то это в этом интервале. Итак, у вас есть 2-приближение. Если нет, то проверьте, находится ли он между N / 4 и N / 2. И так далее. Каждый раз, когда вы делаете интервал меньшим, более затратно оценивать, находится ли k в этом диапазоне. Но стоимость обратно пропорциональна тому, насколько мал интервал.

Например, если вы проверяете, находится ли k между и 2 N / 2 q , то вам нужно выполнить около O ( 2 q ) запросов. В любом случае, после повторения этой процедуры достаточно времени, вы должны получить интервал, в котором лежит k. Скажем, k лежит между N / 2 q и 2 N / 2 q . Тогда k примерно N / 2 q . Итак, 2 квN/2Q2N/2QО(2Q)N/2Q2N/2QN/2Q2Qо к / ш. Таким образом, на этом этапе мы бы потратили O (k / N) запросов. Но для перехода к этому шагу потребовалось q других шагов, но это всего лишь дополнительный множитель (N). Таким образом, общее время работы O (N polylog (N) / k) для 2-приближения.

(Фактически нужно было бы усиливать ошибки, чтобы получить приличную точность на каждом шаге. Но это только дополнительный фактор полилога.)


Причина, по которой мне нравится думать об этом в этом многоступенчатом процессе, заключается в том, что он выделяет этот процесс как предположение и проверяет предварительное условие. Если кто-то сказал вам, что находится между N / 2 q и 2 n / 2 q , то вы можете оценить его с еще большей точностью, зная этот факт, в течение обещанного периода времени. Таким образом, нам нужно исключить шаг, чтобы дать предположение для k . Это делается с помощью бинарного поиска по всем возможным интервалам этого типа.КN/2Q2N/2QК

Чтобы это работало для случая небулевых выходных данных, вместо подсчета числа 1, просто сложите полученные значения. Я постараюсь найти ссылку, чтобы показать, что это работает строго.

Робин Котари
источник
(1) Поскольку функция f может принимать нецелые значения, вы, вероятно, захотите использовать сумму значений вместо числа 1. (2) Нужно ли оценивать поэтапно? Я предполагаю, что мы можем сделать это за один этап, просто повторяя, пока сумма не превысит фиксированный многочлен. Смотрите также мой комментарий к вопросу.
Цуёси Ито
О, я не заметил, что диапазон составляет [0,1]. Я думал, что это было {0,1}. Но я думаю, что та же самая процедура работает. Может быть, мы можем свести одну проблему к другой, так как мы можем «посчитать» количество единиц в определенной позиции двоичного представления вывода с достаточной точностью. О (2), я думаю, что ваша процедура эквивалентна. Я думаю об этом так, потому что это похоже на процесс «угадай и проверь», т. Е. С паршивой оценкой k получи лучшую. Я добавлю это в мой ответ.
Робин Котари
Я согласен, что два алгоритма по сути одинаковы. Кроме того, что касается [0,1] и {0,1}, ваш алгоритм, вероятно, работает, как указано, после замены каждой оценки нецелого значения f (x) на бросок монеты (1 wp f (x) и 0 wp 1-е (х)).
Цуёси Ито
@ Робин: Спасибо за ответ. Что-то для меня также неясно: вы сказали: «Просто выберите несколько случайных значений, и если вы получите больше половины 1 с, то это в этом интервале». Я считаю, что это должно быть определено количественно: сколько образцов дает с какой точностью? (Я изменил OP, чтобы учесть такую ​​уверенность. В противном случае было бы невозможно спроектировать требуемый пробоотборник!)
MS Dousti 2.10.10
@ Садек: это связано с Черновым. если вы ожидаете, что k будет n / 2 (например, неплохая монета), вы можете быстро записать границу хвоста, чтобы увидеть больше чем n (1 + eps) / 2, и аналогично для нижней границы.
Суреш Венкат
3

Пусть обозначают значения f, примененные к бесконечной последовательности случайных выборок (с заменой) из { 0 , 1 } n . Пусть K будет наименьшее положительное целое число , такое , что Σ K я = 1 е яМ при некотором значении М , может быть , М = р о л у л о г ( п ) . Я бы догадался, что оценщик M kf1,f2,f{0,1}nki=1kfiMMM=polylog(n)M/k должен выполнить то, что вы хотите.

Для анализа вы не можете применить границы Черноффа непосредственно к случайной переменной но есть прием, позволяющий вам использовать Черноффа в любом случае. Обозначим через μ неизвестное ожидание E ( f ) . Найти константы k l o w и k h i g h (функции от µ ) так, чтобы с вероятностью не менее 1 - δ мы имели k l o w i = 1 f i < M и k hkμE(f)klowkhighμ1δi=1klowfi<M. Эти суммыеяс может быть ограниченапомощью Чернова. Отсюда следует, чтоklow<k<khighс вероятностью не менее1-δи, следовательно, оценкаM/kхорошо сконцентрирована.i=1khighfi>Mfiklow<k<khigh1δM/k

Уоррен Шуди
источник