Why Search a Grid of Scales?
A model-selection procedure may have many possible sizes to consider. Searching every size can be inconvenient, while a geometric grid keeps only scales that grow by a roughly constant factor. The central question is whether this computational shortcut changes the statistical target substantially. A grid can preserve a near-best trade-off when moving to its next larger scale does not increase complexity too much and the approximation risk does not increase as the scale grows.
We analyze this trade-off deterministically first. The result can then be combined with a bound on the error of an estimated selection criterion. The comparison is not automatic: it depends on explicit assumptions about the risk and complexity terms.
Scales, Objectives, and Grid Coverage
The grid point covering \(m\) is chosen at least as large as \(m\), so monotonicity gives \(A_{g(m)}\leq A_m\). The cost condition controls the price paid for moving upward to that grid point. The definition requires nonnegative costs; this matters when comparing objective values. It is also useful to assume nonnegative approximation risks, as is standard for prediction or estimation risk.
The coverage factor is a property of both the grid and the cost function. It need not be the same for every choice of complexity cost. In particular, a grid with a fixed multiplicative spacing can give a bounded factor for polynomial costs.
Worked Example: Covering Integer Scales With Powers of Two
Take \(M=20\), and use the grid \(G=\{1,2,4,8,16,20\}\). For each scale \(m\), choose the smallest grid point \(g(m)\) that is at least \(m\). The resulting coverage is:
| Scales \(m\) | Chosen grid point \(g(m)\) | Largest ratio \(g(m)/m\) in the range |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3–4 | 4 | 4/3 |
| 5–8 | 8 | 8/5 |
| 9–16 | 16 | 16/9 |
| 17–20 | 20 | 20/17 |
Every listed ratio is at most \(2\), so \(g(m)\leq 2m\) for all \(m\). For the linear cost \(c(m)=m\), this gives \(c(g(m))\leq 2c(m)\), and the grid has coverage factor \(K=2\). For the quadratic cost \(c(m)=m^2\), the same grid instead gives \(c(g(m))\leq 4c(m)\), so \(K=4\). The scale coverage is unchanged; the cost of that coverage depends on how rapidly complexity grows.
A Deterministic Grid Comparison
This inequality says that the best available grid scale is within a multiplicative factor of the best scale in the full collection. It does not say that the selected scales are close to one another, or that a particular grid point recovers the best model. It compares objective values, which combine approximation and complexity.
Proof. Since the scale set is finite, choose \(m^\star\) that minimizes \(J_m\). By the grid coverage condition, there is \(g(m^\star)\in G\) with \(g(m^\star)\geq m^\star\) and \(c(g(m^\star))\leq Kc(m^\star)\). The monotonicity of \(A_m\) gives \(A_{g(m^\star)}\leq A_{m^\star}\). Thus $$ \min_{g\in G}J_g \leq J_{g(m^\star)} \leq A_{m^\star}+\lambda Kc(m^\star). $$ If \(K\geq1\), nonnegativity of \(A_{m^\star}\) implies $$ A_{m^\star}+\lambda Kc(m^\star) \leq K\bigl(A_{m^\star}+\lambda c(m^\star)\bigr) =K\min_{1\leq m\leq M}J_m. $$ If \(0<K<1\), nonnegativity of \(c(m^\star)\) gives $$ A_{m^\star}+\lambda Kc(m^\star) \leq A_{m^\star}+\lambda c(m^\star) =\min_{1\leq m\leq M}J_m. $$ Combining the two cases proves the stated bound. \(\square\)
Worked Example: Comparing the Best Grid and Full Objectives
Let \(M=10\), \(G=\{1,2,4,8,10\}\), \(A_m=16/m\), \(c(m)=m\), and \(\lambda=1\). The objective is \(J_m=16/m+m\). The full minimum is \(J_4=4+4=8\). On the grid, the objective values are $$ J_1=17,\qquad J_2=10,\qquad J_4=8,\qquad J_8=10,\qquad J_{10}=11.6. $$ Hence the grid minimum is also \(8\), at scale \(4\). Since \(c(m)=m\) and this grid covers each scale with \(g(m)\leq2m\), the theorem guarantees only that the grid minimum is at most \(2\cdot8=16\). In this particular example the grid incurs no loss, but the general bound is a worst-case guarantee, not a prediction of the exact loss.
Power Costs and Geometric Spacing
A common complexity cost has the form \(c(m)=m^\alpha\), where \(\alpha>0\). If a grid covers each scale with \(m\leq g(m)\leq q m\) for some \(q\geq1\), then $$ c(g(m))=g(m)^\alpha\leq(qm)^\alpha=q^\alpha c(m). $$ Thus \(K=q^\alpha\) is a coverage factor, and the deterministic comparison gives a factor of at most \(\max(1,q^\alpha)\). For the usual case \(q>1\), this is \(q^\alpha\). Finer geometric spacing means \(q\) closer to one and a smaller worst-case factor; faster-growing costs, with larger \(\alpha\), make coarse spacing more expensive.
For integer scales, one may use a grid formed from powers of \(q\), rounded to integers, and include \(M\) as a final point. Rounding can affect the exact coverage factor, especially at small scales. It is therefore safer to verify the coverage inequality for the actual grid than to assume that rounding leaves the factor exactly \(q\). The powers-of-two example above avoids this issue by checking the integer coverage directly.
Worked Example: A Power Cost on a Coarse Grid
Suppose scales are \(1,\ldots,20\), the grid is \(G=\{1,2,4,8,16,20\}\), and \(c(m)=m^2\). We verify a coverage factor of \(4\). For each \(m\), the smallest grid point above it satisfies \(g(m)\leq2m\), as the table showed. Squaring both nonnegative sides yields \(g(m)^2\leq4m^2\), so \(c(g(m))\leq4c(m)\).
If \(A_m\geq0\) is nonincreasing and \(\lambda>0\), the theorem therefore gives $$ \min_{g\in G}\{A_g+\lambda g^2\} \leq4\min_{1\leq m\leq20}\{A_m+\lambda m^2\}. $$ This factor is valid regardless of the particular nonincreasing risk sequence. It can be conservative; a particular risk sequence may place its best scale directly on the grid.
Selection With an Estimated Criterion
In an application, the objective used for selection may be estimated from data. The following elementary comparison separates the cost of restricting the scales from the error in estimating the objective. It requires an error bound only at the grid points, since those are the candidates the procedure actually compares.
Proof. Let \(g^\star\) minimize \(J_g\) over the finite grid. On \(\mathcal E\), the error bound at \(\widehat g\), the minimizing property of \(\widehat g\), and the error bound at \(g^\star\) give, in order, $$ J_{\widehat g} \leq\widehat J_{\widehat g}+\varepsilon_{\widehat g} \leq\widehat J_{g^\star}+\varepsilon_{\widehat g} \leq J_{g^\star}+\varepsilon_{g^\star}+\varepsilon_{\widehat g} \leq\min_{g\in G}J_g+2\max_{g\in G}\varepsilon_g. $$ Applying the deterministic grid comparison to the last expression proves the second inequality. \(\square\)
Worked Example: Allowing for Criterion Estimation Error
Suppose the grid is \(G=\{1,2,4,8\}\), and the true objective values are \(J_1=11\), \(J_2=9\), \(J_4=8\), and \(J_8=10\). The estimated values are \(\widehat J_1=10.8\), \(\widehat J_2=9.2\), \(\widehat J_4=8.3\), and \(\widehat J_8=9.7\). Each estimated value differs from its true value by at most \(0.3\), and the estimated criterion selects \(\widehat g=4\), since \(8.3\) is the smallest estimated value. Its true objective is \(J_{\widehat g}=8\), while the best grid objective is also \(8\). The theorem's bound is $$ J_{\widehat g}\leq8+2(0.3)=8.6. $$ The bound allows for selection error even when, as here, the selected grid point happens to attain the true grid minimum.
Common Mistake: Ignoring Sign Conditions
A tempting argument is to use the same multiplicative comparison for any complexity cost, including negative costs. That is not valid. In the case \(K<1\), the proof needs \(\lambda Kc(m)\leq\lambda c(m)\), which follows from \(c(m)\geq0\), but can fail if the cost is negative. The nonnegative approximation-risk assumption is likewise used in the \(K\geq1\) case.
For example, take \(M=3\), \(G=\{1,3\}\), \(K=0.5\), \(\lambda=1\), \(A=(10,0,0)\), and \(c=(-2,-3,-2)\). The risk is nonincreasing. Cover scales \(1,2,3\) by grid points \(1,3,3\), respectively; each satisfies \(c(g(m))\leq0.5c(m)\). But the full minimum of \(A_m+c(m)\) is \(-3\), at \(m=2\), whereas the grid minimum is \(-2\). The proposed factor-\(\max(1,0.5)=1\) inequality would require \(-2\leq-3\), which is false. Nonnegative costs are not cosmetic: they are part of the theorem's hypotheses.
A second common overstatement is that geometric spacing always gives a good approximation. The grid comparison requires both an appropriate cost-coverage bound and nonincreasing approximation risk. If either condition fails, the grid point above a scale may have a substantially larger objective. In practice, check the hypotheses for the scales and complexity measure actually being used.
Check Your Understanding
Work through these questions using the definitions and comparisons above.
- For \(c(m)=m^3\), what coverage factor follows from a grid satisfying \(g(m)\leq2m\)?
- Which assumptions are used in the proof when \(K\geq1\), and which are used when \(0<K<1\)?
- Suppose a grid selector's criterion differs from \(J_g\) by at most \(0.2\) at every grid point. How large is the additive term in the selector comparison?
- Why does a geometric grid by itself not guarantee a near-best objective if approximation risk can increase with scale?
- For a proposed finite grid and cost \(c\), describe how you would verify a coverage factor \(K\).