0
$\begingroup$

I have a known function $f:[0,1]^K \rightarrow [0,1]^K$ which is L-Lipschitz (w.r.t to $L_1$ but can also be w.r.t to $L_2$ if the results differ). Denote the input vector by $\theta$.

Each entry in $\theta_i \sim Bernoulli(p_i)$ but $p_i$'s are unknown. The goal is to find the minimal number of observations required from each distribution s.t. $\forall i \in [K] \; |\max_{\theta' \in C_N} f(\theta')_i - \min_{\theta' \in C_N} f(\theta')_i | \leq \alpha$. Where $C_N$ is a $K$ dimensional ball centered around the observed $\theta$ after observing $N$ samples from each distribution with radius $\sqrt{\frac{2 \log T}{N}}$. Where $T$ is a known constant ($\alpha$ is a. function of $T$).

A naive solution uses Hoeffding's inequality and ignores the functions' properties. I want to also use the functions' properties.

What I tried so far - I defined $N_{\alpha}$ to be the minimal number of observations from each distribution such that a $K$ dimensional ball around the true $\theta$ with radius $\sqrt{\frac{2\log T}{N_{\alpha}}}$ satisfies the required condition ($\forall i \in [K] \; |\max_{\theta' \in C_N} f(\theta')_i - \min_{\theta' \in C_N} f(\theta')_i | \leq \alpha$). Denote this ball by $\mathcal{B}_{N_{ \alpha}}$.

W.h.p, if we obtain $4N_{\alpha}$ observations from each entry the observed mean is not too far from the read mean and the radius is small enough so the obtained ball is contained in $\mathcal{B}_{N_{\alpha}}$.

I wonder if there are other approaches for this problem and \ or better ways to formalize it.

Thanks

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.