Approximate Extremum Estimators and Optimization Error

Why Approximate Optimization Needs Its Own Condition

An extremum estimator is defined by optimizing a sample criterion, but many practical algorithms stop before finding an exact minimizer. This is not automatically a problem for consistency. The relevant question is whether the value of the criterion at the computed estimate is sufficiently close to its sample infimum compared with the population criterion’s penalty for being away from the true parameter.

This comparison matters because sample criteria fluctuate around their population targets, and numerical routines operate at a chosen tolerance. A tolerance that is harmless for one objective scaling may be too large for another. We make the comparison precise for minimization; maximization can be handled by changing the sign of the criterion.

Definition: Let $Q_n(\theta)$ be a sample criterion on a parameter space $\Theta$. An estimator $\tilde{\theta}_n$ is an approximate minimizer with optimization gap $a_n\geq 0$ if $$ Q_n(\tilde{\theta}_n)\leq \inf_{\theta\in\Theta}Q_n(\theta)+a_n. $$ The gap $a_n$ measures how far the computed criterion value may be above the sample infimum. It may be random, and the bound need only hold with probability tending to one if stated that way.

An exact minimizer has $a_n=0$. An approximate minimizer need not be close to an exact sample minimizer in parameter distance: the criterion may be shallow, or there may be multiple minimizers. The consistency argument instead asks whether a parameter far from the population minimizer would incur a criterion penalty too large to be explained by either sample fluctuation or optimization error.

Separation and the Consistency Result

Let $Q(\theta)$ denote the population criterion and let $\theta_0$ be its unique minimizer. The needed separation condition says that every fixed distance away from $\theta_0$ comes with a positive population criterion penalty.

Definition: The population criterion is separated at $\theta_0$ if, for every $\varepsilon>0$ for which the set is nonempty, $$ \inf_{\theta\in\Theta:\,\|\theta-\theta_0\|\geq\varepsilon} \bigl[Q(\theta)-Q(\theta_0)\bigr]\geq\delta_\varepsilon>0. $$ The positive number $\delta_\varepsilon$ may depend on $\varepsilon$. It is a lower bound on the population criterion penalty for all parameter values at least $\varepsilon$ from $\theta_0$.

A standard sufficient condition for this separation is that $\Theta$ is compact, $Q$ is continuous, and $\theta_0$ is its unique minimizer. More generally, separation can be assumed directly. The sample criterion is required to converge uniformly in probability to the population criterion: $$ \sup_{\theta\in\Theta}|Q_n(\theta)-Q(\theta)|\xrightarrow{p}0. $$ Uniform convergence controls criterion error across the whole parameter space, including at a data-dependent approximate minimizer.

Theorem: Suppose $Q$ has a unique minimizer $\theta_0$, the population criterion is separated at $\theta_0$, and $Q_n$ converges uniformly in probability to $Q$. If $\tilde{\theta}_n$ is an approximate minimizer with $a_n=o_p(1)$, then $$ \tilde{\theta}_n\xrightarrow{p}\theta_0. $$ Thus an optimization gap that vanishes on the scale of the criterion preserves consistency under these conditions.

The result does not require the approximate estimator to be an exact minimizer of $Q_n$. It does require the solver’s criterion gap to vanish in probability for the criterion as written. The gap is compared with population separation, not directly with the parameter error.

Why the Criterion-Gap Bound Works

Write $u_n=\sup_{\theta\in\Theta}|Q_n(\theta)-Q(\theta)|$. Fix any $\varepsilon>0$, and let $\delta_\varepsilon$ be a positive separation bound. Consider the event that $u_n<\delta_\varepsilon/4$ and $a_n<\delta_\varepsilon/4$. If $\tilde{\theta}_n$ were at least $\varepsilon$ from $\theta_0$, separation and uniform convergence would imply $$ Q_n(\tilde{\theta}_n)-Q_n(\theta_0) \geq Q(\tilde{\theta}_n)-Q(\theta_0)-2u_n \geq\delta_\varepsilon-2u_n >\frac{\delta_\varepsilon}{2}. $$ But the approximate-minimization inequality and the fact that $\inf_{\theta\in\Theta}Q_n(\theta)\leq Q_n(\theta_0)$ give $$ Q_n(\tilde{\theta}_n)-Q_n(\theta_0)\leq a_n<\frac{\delta_\varepsilon}{4}. $$ These inequalities contradict one another. Therefore, on this event, $\|\tilde{\theta}_n-\theta_0\|<\varepsilon$. Uniform convergence implies $P(u_n\geq\delta_\varepsilon/4)\to0$, and $a_n=o_p(1)$ implies $P(a_n\geq\delta_\varepsilon/4)\to0$. Hence $P(\|\tilde{\theta}_n-\theta_0\|\geq\varepsilon)\to0$ for every such $\varepsilon$, which is consistency.

Worked Example: Approximate Least-Squares Minimization

Suppose $Y_1,\ldots,Y_n$ are independent and identically distributed, with finite second moment and mean $2$. On $\Theta=[0,4]$, consider the average squared-error criterion $$ Q_n(\theta)=\frac{1}{n}\sum_{i=1}^n(Y_i-\theta)^2. $$ The population criterion is $Q(\theta)=E[(Y_i-\theta)^2]=\operatorname{Var}(Y_i)+(2-\theta)^2$, so its unique minimizer is $\theta_0=2$. For every $\varepsilon>0$, parameters at least $\varepsilon$ from 2 have population penalty at least $\varepsilon^2$, when that set is nonempty. Thus separation holds. Expanding the sample criterion shows it is a quadratic in $\theta$ whose coefficients are the first and second sample raw moments; by the law of large numbers, those moments converge to their expectations. On the compact interval, this gives uniform convergence of $Q_n$ to $Q$.

For a concrete hypothetical sample $Y=(1,2,3,4)$, the sample mean is $2.5$, and $$ Q_n(\theta)=\frac{(1-\theta)^2+(2-\theta)^2+(3-\theta)^2+(4-\theta)^2}{4} =1.25+(\theta-2.5)^2. $$ The exact sample minimizer is $2.5$. If a numerical routine returns $2.6$, its criterion gap is $$ Q_n(2.6)-Q_n(2.5)=(2.6-2.5)^2=0.01. $$ This calculation illustrates how to measure the optimization gap; by itself, a single sample cannot establish asymptotic consistency.

For an asymptotic illustration, suppose the routine returns $\tilde{\theta}_n=\bar{Y}+n^{-1/4}$, whenever this lies in $[0,4]$, with any boundary adjustment otherwise. With probability tending to one, $\bar{Y}$ is near 2 and the adjustment is unnecessary. Completing the square gives the gap $n^{-1/2}$, which tends to zero. The theorem therefore establishes consistency, provided the stated moment and uniform-convergence conditions hold.

Worked Example: Translating a Tolerance for a Summed Criterion

Suppose the algorithm minimizes a summed criterion $S_n(\theta)=\sum_{i=1}^n q_i(\theta)$, but the statistical argument is written for its average $Q_n(\theta)=S_n(\theta)/n$. If the solver guarantees $$ S_n(\tilde{\theta}_n)\leq\inf_{\theta\in\Theta}S_n(\theta)+b_n, $$ then division by $n$ gives the average-criterion gap $a_n=b_n/n$. The condition relevant to the theorem is therefore $b_n/n=o_p(1)$, or equivalently $b_n=o_p(n)$. The raw tolerance $b_n$ need not itself tend to zero.

For a numerical check, take $n=100$ and a summed-objective tolerance $b_n=0.2$. The corresponding average-objective gap is $a_n=0.2/100=0.002$. Suppose the population criterion is $Q(\theta)=(\theta-1)^2$, with $\theta\in[0,2]$, and the sample criterion satisfies $\sup_{\theta\in\Theta}|Q_n(\theta)-Q(\theta)|<0.01$. At any $\theta$ at least $0.2$ from 1, the population penalty is at least $0.2^2=0.04$. Consequently, $$ Q_n(\theta)-Q_n(1)\geq 0.04-2(0.01)=0.02. $$ If $\tilde{\theta}_n$ were at least $0.2$ from 1, this difference would be at least $0.02$. Yet approximate minimization implies $Q_n(\tilde{\theta}_n)-Q_n(1)\leq0.002$, a contradiction. This check shows how a solver tolerance and a uniform-error bound can be compared with a concrete separation margin.

The numerical inequalities establish the conclusion on the stated event; consistency requires the probability of the relevant uniform-error event to tend to one and the normalized gap $b_n/n$ to vanish in probability. A fixed total-objective tolerance, such as $b_n=0.2$ for every $n$, does satisfy $b_n/n\to0$. A tolerance that grows proportionally to $n$ generally does not.

Worked Example: A Fixed Gap Can Prevent Consistency

Let $\Theta=[-1,1]$ and $Q_n(\theta)=Q(\theta)=\theta^2$ for every $n$. The unique population minimizer is $\theta_0=0$, and separation holds: for $\varepsilon>0$, the penalty at distance at least $\varepsilon$ is at least $\varepsilon^2$, when such parameters exist.

Now let a solver return $\tilde{\theta}_n=0.3$ for every $n$. Its criterion gap is $$ Q_n(0.3)-\inf_{\theta\in[-1,1]}Q_n(\theta)=0.3^2=0.09. $$ The estimator is not consistent, because $P(|\tilde{\theta}_n-\theta_0|\geq0.2)=1$ for every $n$. A solver permitted a fixed tolerance of $0.1$ could return this value, but the permitted gap does not vanish. The theorem’s vanishing-gap condition is not satisfied.

This example does not say that every nonvanishing gap must cause inconsistency. It shows that a fixed criterion tolerance alone does not guarantee consistency: for a given separation margin, the allowed gap may be large enough to leave a parameter value far from $\theta_0$.

Practical Checks and Common Pitfalls

To apply the result, keep the objective used by the optimizer consistent with the objective used in the asymptotic argument. If one is a constant multiple of the other, translate the solver tolerance by the same factor. If the criterion is a sum over observations but the population comparison uses an average, divide the solver’s bound by $n$. A criterion-gap statement without its scale is incomplete.

A small criterion gap also does not by itself guarantee a small parameter error. The conclusion comes from combining that gap with uniform convergence and separation. If the population criterion has multiple minimizers or becomes arbitrarily close to its minimum far from $\theta_0$, the separation condition can fail. In that case, even exact optimization need not identify a particular parameter value consistently.

Mistake: Concluding that a solver is adequate because its absolute tolerance looks numerically small. Correction: Express the tolerance on the same scale as the sample criterion and compare it with the separation margin.
Mistake: Treating a small criterion gap as proof that the returned parameter is near the target. Correction: Check that the population criterion separates parameters a fixed distance from its minimizer.
Mistake: Assuming a fixed tolerance for an average criterion automatically becomes negligible as the sample grows. Correction: A fixed positive gap is not $o_p(1)$; for a summed criterion, check the normalized gap $b_n/n$.

Key takeaway: Approximate optimization preserves consistency when the sample criterion converges uniformly to a separated population criterion and the approximate minimizer’s gap, measured on the criterion’s relevant scale, vanishes in probability.

Check Your Understanding

Use the definitions and criterion-gap comparison to answer the following questions.

What does the optimization gap $a_n$ measure, and how does it differ from the distance between an approximate estimator and an exact sample minimizer?
Why is uniform convergence useful when the parameter being evaluated, $\tilde{\theta}_n$, is data-dependent?
If a solver’s error bound for a summed criterion is $b_n=n^{1/3}$, what is the corresponding average-criterion gap, and does it vanish?
In the consistency proof, which inequality rules out an approximate minimizer that is at least $\varepsilon$ from $\theta_0$?
Can an exact minimizer be inconsistent if the population criterion is not separated at a unique minimizer? Explain why or why not.

Approximate Extremum Estimators and Optimization Error

What You'll Learn