Concentration inequality for a function whose parameter depends on input samples

Question

Concentration inequalities can be used to establish results such as sample mean cannot be too far from the actual population mean, and so on. For example, let $X_1 \ldots X_n$ be i.i.d instances of a random variable $X \in R^d$, and $f : R^d \rightarrow R$ then one can bound quantities such as $ P\big(|\frac{1}{n}\sum_i f(X_i) - E[f(X)]|> \epsilon \big)$.

The assumption here is that $f$ is completely determined before drawing the samples, and has no dependency as such on the samples.

However, consider the situation where the function is parameterized - i.e., $f_\theta$ - and the parameter $\theta$ can potentially depend on the sample set; thus $\theta(X)$ itself is a random variable with non-zero mutual information with $X$. Is it possible to construct concentration inequalities that takes into account such a dependence? It seems plausible that if $\theta$ doesn't retain too much information about the samples, then such an inquality may be possible. Or perhaps ineualities exist that involve the mutual information in the bounds? Could such question make sense? If so, is there any literature at all on this?

Answer 1

If $f_\theta(x)$ is a Lipschitz function of $X$ then standard concentration inequalities for Lipschitz functions (e.g. Mcdiarmid's inequality, see for instance https://people.eecs.berkeley.edu/~bartlett/courses/281b-sp08/13.pdf) will yield the concentration you seek. In practice you might check that $\theta(X)$ is a Lipschitz function of $X$ and $f_\theta(x)$ has bounded gradient when considered as a function of both variables $x,\theta$.