Adaptation To An Unknown Best Model Scale

Why Adaptation Is Needed

A model scale balances two competing effects. A small scale may be easy to estimate but unable to approximate the target well; a large scale may approximate it more closely but require more data to estimate reliably. If the best balance depends on an unknown feature of the data-generating distribution, choosing the scale in advance is not generally possible. The goal here is to use one data-dependent selector whose risk is close to the best risk available among the candidate scales.

The guarantee is an oracle inequality: it compares the selected predictor with the best candidate at each scale, then takes the best of those comparisons. It does not say the selector identifies a uniquely correct model. It says that the selected predictor can achieve a risk comparable to the best approximation-estimation tradeoff, with a penalty for searching across scales.

Setup and the Penalized Selector

Suppose the observations $Z_1,\ldots,Z_n$ are independent and identically distributed. A predictor $f$ has loss $\ell_f(Z)$ satisfying $0\leq \ell_f(Z)\leq 1$. Its risk and empirical risk are

R(f)=E[\ell_f(Z)], \qquad \widehat R_n(f)=\frac{1}{n}\sum_{i=1}^n \ell_f(Z_i).

At each scale $j$ in an index set $J$, let $\mathcal F_j$ be a nonempty finite candidate class, with $M_j=|\mathcal F_j|$. The set $J$ may be finite or countable. Write $R_j^*=\min_{f\in\mathcal F_j}R(f)$ for the best risk at scale $j$. Assign each scale a positive weight $w_j$, with $\sum_{j\in J}w_j\leq 1$, and fix a confidence level $0<\alpha<1$.

Definition: The scale-dependent deviation penalty is $$ \delta_j=\sqrt{\frac{\log\{2M_j/(\alpha w_j)\}}{2n}}. $$ For each scale, let $\widehat f_j$ minimize $\widehat R_n(f)$ over $f\in\mathcal F_j$. A penalized scale selector chooses an index $\widehat j$ whose score $\widehat R_n(\widehat f_j)+\delta_j$ is within $\eta\geq 0$ of the infimum of these scores, and returns $\widehat f=\widehat f_{\widehat j}$. If the infimum is attained, $\eta=0$ is permitted.

The term $M_j$ accounts for searching among predictors within a scale, while $w_j$ allocates the confidence budget across scales. A smaller weight assigns less of that budget to the scale and increases its penalty through $\log(1/w_j)$. The weights need not be known to the data-generating process; they are part of the selector's design.

Worked Example: Computing Scale Penalties and Selecting a Scale

Take $n=100$, $\alpha=0.1$, and three scales with $(M_1,M_2,M_3)=(1,2,4)$ and $(w_1,w_2,w_3)=(0.5,0.3,0.2)$. The weights sum to one. Suppose the empirical best risks are $0.32,0.28,0.27$, respectively. Using natural logarithms, the penalties are

$\delta_1=\sqrt{\log(2/(0.1\cdot0.5))/200}=\sqrt{\log(40)/200}\approx 0.1358$.

$\delta_2=\sqrt{\log(4/(0.1\cdot0.3))/200}=\sqrt{\log(133.333\ldots)/200}\approx 0.1564$.

$\delta_3=\sqrt{\log(8/(0.1\cdot0.2))/200}=\sqrt{\log(400)/200}\approx 0.1731$.

The three penalized scores are therefore approximately $0.4558$, $0.4364$, and $0.4431$. The selector chooses scale 2: its empirical risk is not the smallest, but its penalized score is. This calculation illustrates the decision rule; a risk guarantee requires the simultaneous-deviation event proved below.

Simultaneous Control Across Scales

For a fixed predictor with loss in $[0,1]$, Hoeffding's inequality gives $P(|\widehat R_n(f)-R(f)|>t)\leq 2\exp(-2nt^2)$. Applying this bound to every predictor and scale yields a single event on which all empirical risks are controlled at once.

Result: With probability at least $1-\alpha$, for every $j\in J$ and every $f\in\mathcal F_j$, $$ |\widehat R_n(f)-R(f)|\leq \delta_j. $$

To verify the probability statement, for any fixed $j$ and $f\in\mathcal F_j$, the probability of a deviation larger than $\delta_j$ is at most

2\exp(-2n\delta_j^2) =2\exp\left[-\log\left\{\frac{2M_j}{\alpha w_j}\right\}\right] =\frac{\alpha w_j}{M_j}.

Summing this upper bound over the $M_j$ predictors at scale $j$ gives at most $\alpha w_j$. Summing over all scales gives at most $\alpha\sum_jw_j\leq\alpha$, by the union bound. The argument applies to a countable collection because the sum of the failure probabilities is bounded by the same convergent series. Thus the stated event has probability at least $1-\alpha$.

The Adaptation Oracle Inequality

Theorem: Under the setup above, with probability at least $1-\alpha$, the selected predictor satisfies $$ R(\widehat f)\leq \inf_{j\in J}\{R_j^*+2\delta_j\}+\eta. $$

This statement is meaningful even when no scale is known in advance to be best. The selector uses the observed penalized scores, while the bound compares its risk with every scale, including the one that gives the smallest approximation-estimation tradeoff.

Proof. Work on the simultaneous-deviation event. Let $\widehat j$ be the selected scale. The event gives $R(\widehat f)\leq \widehat R_n(\widehat f)+\delta_{\widehat j}$. For any $j\in J$, the definition of the selector gives

\widehat R_n(\widehat f)+\delta_{\widehat j} \leq \widehat R_n(\widehat f_j)+\delta_j+\eta.

The same event implies $\widehat R_n(\widehat f_j)\leq R(\widehat f_j)+\delta_j$. Combining these inequalities,

R(\widehat f) \leq \widehat R_n(\widehat f)+\delta_{\widehat j} \leq \widehat R_n(\widehat f_j)+\delta_j+\eta \leq R(\widehat f_j)+2\delta_j+\eta.

Since $\widehat f_j$ minimizes empirical risk within its class, it need not be the risk minimizer there. For the oracle comparison, instead take any $g\in\mathcal F_j$. The selector property and the fact that $\widehat f_j$ has no larger empirical risk than $g$ give

R(\widehat f) \leq \widehat R_n(\widehat f)+\delta_{\widehat j} \leq \widehat R_n(g)+\delta_j+\eta \leq R(g)+2\delta_j+\eta.

The class is finite, so a risk minimizer $g_j^*$ exists in $\mathcal F_j$, with $R(g_j^*)=R_j^*$. Substituting it gives $R(\widehat f)\leq R_j^*+2\delta_j+\eta$ for every $j$. Taking the infimum over $j$ proves the theorem. $\square$

Worked Example: Reading the Oracle Bound

Continue with the penalties in the numerical example, and suppose the best risks within the three scales are $R_1^*=0.30$, $R_2^*=0.20$, and $R_3^*=0.12$. The scale-specific oracle bounds, for an exact minimizer of the penalized scores, are

Scale 1: $0.30+2(0.1358)=0.5716$.

Scale 2: $0.20+2(0.1564)=0.5128$.

Scale 3: $0.12+2(0.1731)=0.4662$.

The theorem therefore gives $R(\widehat f)\leq 0.4662$ on the simultaneous event, even though the selector did not know that scale 3 had the best risk. This is a bound, not a claim that the selected scale must be 3: the realized empirical risks determine the selected scale, and the theorem controls its risk relative to all the candidates.

What the Bound Says About Rates

Worked Example: A Rate From Approximation and Complexity

Suppose scales are indexed by positive integers and, for constants $A,c>0$ and $s>0$, the best risks satisfy $R_j^*\leq A j^{-2s}$. Suppose also that $\log M_j\leq cj$, and use weights $w_j=2^{-j}$, which sum to one. For fixed $\alpha$, the penalty obeys

$\delta_j^2=\log\{2M_j/(\alpha w_j)\}/(2n)\leq \{(c+\log 2)j+\log(2/\alpha)\}/(2n)$.

Choose $j_n=\lceil n^{1/(2s+1)}\rceil$, assuming this scale is among the candidates. For $n\geq1$, $j_n\leq 2n^{1/(2s+1)}$, so $R_{j_n}^*=O(n^{-2s/(2s+1)})$, while $\delta_{j_n}=O(n^{-s/(2s+1)})$. The oracle inequality consequently gives

R(\widehat f) \leq R_{j_n}^*+2\delta_{j_n}+\eta =O\left(n^{-s/(2s+1)}\right)+\eta

with probability at least $1-\alpha$. Thus the stated rate follows when $\eta=O(n^{-s/(2s+1)})$, in particular for an exact minimizer with $\eta=0$. In this calculation the deviation penalty, not the approximation term, determines the stated rate. A faster rate would require a sharper deviation or penalty bound; it does not follow from these assumptions alone.

Why Adaptation Matters—and a Common Pitfall

A fixed-scale guarantee answers the question, “How well does this procedure work if scale $j$ is chosen?” An adaptive guarantee answers a different question: “How well does one procedure work when the best scale is unknown?” The oracle inequality answers the second question. It allows the relevant comparison scale to depend on the risk function, while the estimator itself is defined without knowing that scale.

Pitfall: reversing the effect of a weight. A smaller $w_j$ does not give scale $j$ more confidence budget. Its allocated budget is $\alpha w_j$, which is smaller; accordingly, $\log(1/w_j)$ and the penalty increase.
Pitfall: treating the oracle scale as recovered. The theorem controls risk, not the probability of selecting the scale with minimum true risk. Several scales can have similar risks, and empirical fluctuations can change which score is smallest.
Pitfall: dropping the search penalty. Comparing empirical risks across many candidates without accounting for their number does not yield the simultaneous event used in the proof. Both $M_j$ and $w_j$ enter the bound for that reason.

Key takeaway: A single scale-penalized empirical-risk selector can compete, with high probability, against the best candidate at every scale. Its adaptation cost is quantified by the scale-specific deviation penalty, not by knowing the best scale beforehand.

Check Your Understanding

Answer these questions using the definitions and result above.

Why does the penalty include $M_j$, and what changes when a scale is assigned a smaller weight $w_j$?
Which event must hold simultaneously for the oracle inequality proof to work?
Where does the factor $2\delta_j$ arise in the comparison with a candidate at scale $j$?
Does the oracle inequality imply that $\widehat j$ equals the scale with smallest true risk? Explain.
Under the approximation and complexity assumptions in the rate example, which term determines the stated rate, and why?