New answers tagged

1

Algorithm 1, which I refer to in the question, produces a strategy that minimizes cumulative counterfactual regret. The motivation is to get a strategy which minimizes overall regret (as defined earlier in the paper). That's because such a strategy approximates a nash equilibrium strategy. In other words, cumulative counterfactual regret was designed to be: ...


1

Hint:


2

Let $A_n\subseteq \{0,1\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\{0,1\}^{\log n}\rightarrow \{0,1\}^{\log n}$ is a one to one function, $\Pr_{...


1

You need $\Omega(2^n)$ samples in order to accomplish your task. Consider an algorithm that gets $m$ samples from $D$ and then another sample, either from $D$ or from $U$, and has to guess which it is. Its input thus consists of $m+1$ samples $X_1,\ldots,X_m,Y$. We will generate the distribution $D$ at random by choosing a random set $V \subseteq \{0,1\}^n$ ...


0

You can't. Your intuition is wrong. I will give an explicit counter-example. Actually, I'll give you two: two for the price of one. Suppose $n=1$, the distribution $D$ always outputs 1, and $U$ is uniform on $\{0,1\}$. The following algorithm is an optimal distinguisher: Never use the black box. If the input $z$ is 0, guess that it came from $U$, ...


1

Total variation distance, which is exactly half of your notion of distance, is equal to $$ d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|. $$ You can take $A$ to be the indicator of $\Pr[D(x)] \geq \Pr[U(x)]$. The event $A$ might be hard to compute, but it could also be easy to compute....


1

The notation $\|x_n - \mu\|^2$ stands for the squared $L_2$ norm of the vector $x_n - \mu$. The squared $L_2$ norm of the $d$-dimensional vector $v = \begin{pmatrix} v_1 & \cdots & v_d \end{pmatrix}$ is $$\|v\|^2 = v_1^2 + \cdots + v_d^2. $$ In particular, when $d = 1$, we have $\|v\|^2 = v_1^2$. The formula you state works for the Gaussian ...


2

Here is the key. Let $A \otimes B$ be the distribution corresponding to a sample from $A$ and an independent sample from $B$, and denote total variation distance by $d_{TV}$. Then $$d_{TV}(A_1 \otimes A_2, B_1 \otimes B_2) \leq d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2)$$ We can see this using the $L_1$ formula for $d_{TV}$: \begin{align} d_{TV}(A_1\otimes A_2,B_1\...


Top 50 recent answers are included