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.



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.