Suppose we have a dataset $S = (x_1, \dots x_n)$ drawn i.i.d from distribution $D$, a learning algorithm $A$ and error function $err$. The performance of $A$ is therefore defined by the error/confidence pair $(\alpha, \beta)$, that is $$P(err(A(S)) \geq \alpha) \leq \beta$$ where the randomness is taken on $S$. Usually, by solving this inequality, we can get some constraints between $\alpha$ and $\beta$, in the form that $\alpha \geq f(\beta, n)$. My understanding is that if we treat $\beta$ as a constant, then we have the high probability error bound in terms of $n$. Is that correct?
Another question is that what if the function $f$ we get is not uniform across all $\beta$, for example \begin{equation} \alpha \geq \begin{cases} f_1(n, \beta) \quad \beta \geq 0.5 \\ f_2(n, \beta) \quad \beta< 0.5 \end{cases} \end{equation} In this case, how to derive the high probability error bound?
