Almost Sure Uniqueness of a Global Minimum Without Convexity

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

43,957 characters · 14 sections · 57 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractThis paper establishes the argmin of a random objective function to be unique almost surely. This paper first formulates a general result that proves almost sure uniqueness without convexity of the objective function. The general result is then applied to a variety of applications in statistics. Four applications are discussed, including uniqueness of M-estimators, both classical likelihood and penalized likelihood estimators, and two applications of the argmin theorem, threshold regression and weak identification. \\ \\ \\ \\ \\ \\ \mbox\\ \mbox\\ \textbf{Keywords:} Global Optimization, Nonconvex Optimization, M-estimation, Mixture Model, Argmax Theorem, Threshold Regression, Weak Identification

Introduction

This paper establishes the argmin of a random objective function to be unique almost surely. This means that the probability the argmin contains two or more points is zero. The task of finding the argmin of a random function is a very general problem, and evaluating whether the argmin is unique is important in many applications. For example, in M-estimation, uniqueness is equivalent to the estimator being well-defined as a point. In addition, uniqueness is a condition for the argmin theorem, which characterizes the asymptotic distribution of many estimators.

The usual argument for uniqueness of the argmin relies on convexity. Without convexity, it is difficult to guarantee uniqueness of the argmin. At the same time, there is a popular intuition that multiple global minimizers occurring with positive probability requires a degenerate random function, in some sense. By considering almost sure uniqueness and relying on a type of nondegeneracy condition, this paper provides a systematic way to relax convexity.

This paper first formulates a general result, Lemma 1, that proves almost sure uniqueness under very weak conditions. This result relies on a type of nondegeneracy condition, called genericity, which states that certain derivatives of the objective function are nonzero. The key to this condition is that it permits derivatives with respect to $z$, a random variable indexing the randomness of the objective function, in addition to derivatives with respect to the domain of optimization. This key aspect makes Lemma 1 useful in a variety of statistical applications.

At this level of generality, there are not many papers that seek to verify uniqueness of the argmin of a function without convexity. The closest is an approach based on a “Mountain Pass Lemma.” This applies if the Hessian of the objective function is positive definite whenever the gradient is zero. The intuition is that between any two minimizers there must exist a local maximum or saddle point. While this condition is sufficient in one dimension, TaroneGruenhage1975 gives a counterexample in multiple dimensions. A variety of papers, including MakelainenSchmidtStyan1981, Demidenko2008, and Mascarenhas2010 supplement the Hessian condition with additional regularity conditions to prove uniqueness of the minimizer.

This approach has two disadvantages. First, it has narrow scope. The conclusion of the Mountain Pass Lemma is that the local minimizer is unique. Thus, this approach does not work for any function with multiple local minimizers but a unique global minimizer. Second, the Hessian condition can be difficult to verify if the derivatives of the objective function are intractable. In contrast, Lemma 1 applies to functions with multiple local minimizers, and the assumptions of Lemma 1 are easy to verify.

Lemma 1 has a variety of applications in statistics and, more broadly, optimization. In this paper, we discuss four applications, two examples of M-estimation and two applications of the argmin theorem. See Section 3 for the literature related to each application.

M-estimators minimize a random objective function. The literature proves uniqueness of an M-estimator for a nonconvex objective function only in isolated cases. Lemma 1 can be used to prove uniqueness more generally, which we demonstrate in two cases not established in the literature. We prove uniqueness for the classical maximum likelihood estimator for a finite mixture model, and we prove uniqueness of the penalized maximum likelihood estimator of a linear regression with a nonconvex penalty.

The argmin theorem characterizes the asymptotic distribution of an estimator using the argmin of a limiting stochastic process, if it is almost surely unique. Lemma 1 can be used to verify the uniqueness condition, which we demonstrate in two cases not established in the literature. MallikBanerjeeSen2013 consider a p-value based estimator of a threshold regression and use the argmin theorem, but are unable to verify the uniqueness condition. We verify it using Lemma 1. Also, characterizing the asymptotic distribution for estimators of parameters that are weakly identified uses the argmin theorem. In this case, we give low-level sufficient conditions for the uniqueness condition to hold, as well as two counterexamples where it does not.

Section 2 states Lemma 1. Section 3 discusses the applications. Section 4 proves Lemma 1. Section 5 concludes. An appendix contains additional proofs.

A General Uniqueness Lemma

This paper studies minimizers of an objective function, $t\mapsto Q(t,z)$, where $z$ is random. The following assumption eliminates mass points in the distribution of $z$.

namedassumption[Absolute Continuity] Let $z$ be an absolutely continuous random $d_z$-vector with distribution $P$. Let $\mathcal{Z}\subset\mathbb{R}^{d_z}$ be a measurable set such that $P(z\in\mathcal{Z})=1$.

Remark:

enumerate• The finite dimensionality of $z$ is not restrictive. Infinite dimensional sources of randomness can be accommodated by focusing on a finite dimensional marginal distribution, and conditioning on the remainder. Section 3.2.1 demonstrates this in an application in which the randomness is a Gaussian stochastic process.

The following assumption specifies the domain over which $Q(t,z)$ is minimized.

namedassumption[Manifold] Let $T=\cup_{j\in J} T_j$ be a disjoint union of finitely or countably many second-countable Hausdorff manifolds, possibly with boundary or corner.

Remark:

enumerate• Using manifolds, possibly with boundaries or corners, is a flexible way to allow for a variety of shapes to be minimized over. $T_j$ is a manifold with boundary or corner if each point, $t\in T_j$, is locally diffeomorphic to a neighborhood in $\mathbb{R}^{d_{T_j}}_+$, where $\mathbb{R}_+$ denotes the nonnegative real numbers, $d_{T_j}$ denotes the dimension of $T_j$, and where a diffeomorphism is a continuously differentiable function with a continuously differentiable inverse. This definition is slightly more general than common definitions in differential topology because it explicitly accounts for corners and higher-dimensional corners (See how the boundary is handled in GuilleminPollack1974 and especially Wall2016, which allows for corners, but not higher-dimensional corners). This generalization is important for many applications in statistics that require irregularly shaped $T$. In the M-estimation application, $T$ is the parameter space. In the weak identification application, $T$ is the identified set, which may have an irregular shape due to bounds.

For each $t\in T_j$, let $A(t)$ denote a subset of the tangent cone of $t$ to $T_j$. (Formally the tangent cone of $t$ to $T_j$ is defined as the set of derivatives of curves in $T_j$ that start at $t$. Informally the tangent cone indexes directions for which derivatives with respect to $t$ can be defined.) This is a flexible way to accommodate derivatives at boundary points of $t\in T_j$, as well as some nondifferentiability of the objective function, which is permitted by the next assumption.

namedassumption[Continuous Differentiability] \begin{enumerate}[label=(\alph*)] • For each $j\in J$, $Q(t,z)$ is a continuous function of $t\in T_j$ and $z\in\mathcal{Z}$. • For every $z\in\mathcal{Z}$ and $t\in T_j$, $Q(t,z)$ is differentiable with respect to $z$, and the derivative is continuous with respect to $t$ and $z$. • For every $z\in\mathcal{Z}$, $t\in T_j$, and $\Delta\in A(t)$, $Q(t,z)$ is differentiable with respect to $t$ in the direction $\Delta$, and the derivative is continuous with respect to $t$ and $z$. \end{enumerate}

Remark:

enumerate• Permitting $A(t)$ to be a strict subset of the tangent cone allows for nondifferentiability of the objective function in directions excluded from $A(t)$.

Let $\Xi=\{(t,s,z): z\in\mathcal{Z}, t, s\in T, \text{ and } t\neq s\}$. Let $\xi(t,s,z)=Q(t,z)-Q(s,z)$ be defined on $\Xi$. The next assumption is a type of nondegeneracy condition that rules out $t\neq s$ both being global minimizers of $Q(t,z)$ simultaneously.

namedassumption[Generic] Assume $\xi(t,s,z)$ is a generic function over $\Xi$. That is, for every $(t,s,z)\in \Xi$, at least one of the following is true: \begin{enumerate}[label=(\alph*)] • $\xi(t,s,z)\neq 0$, • there exists $\Delta\in A(t)$ such that $\frac{d}{d h}\xi(t+h\Delta,s,z)|_{h=0}< 0$, • there exists $\Delta\in A(s)$ such that $\frac{d}{d h}\xi(t,s+h\Delta,z)|_{h=0}> 0$, or • $\frac{d}{dz}\xi(t,s,z)\neq 0$. \end{enumerate}

Remarks:

enumerate• The key to Assumption Generic is condition (d). Often, derivatives with respect to $z$ are more tractable than derivatives with respect to $t$. In the applications, the general strategy for verifying Assumption Generic is to show that $\frac{d}{dz}Q(t,z)=\frac{d}{dz}Q(s,z)$ implies $t=s$. • For interior points, $t$ or $s$, conditions (b) and (c) are related to first order conditions for optimality. If the derivative with respect to $t$ is nonzero, then $t$ not a global minimizer, and condition (b) is satisfied for some $\Delta$. These conditions can be augmented with conditions on second derivatives to allow saddle points and local maximizers. • Assumption Generic makes precise the type of degeneracy needed for a random function to have multiple global minimizers with positive probability. Specifically, for interior $t$ and $s$, Assumption Generic is a system of $n+1$ nonlinear equations in $n$ unknowns. Intuitively, if such a system of equations permits a common solution, then it would seem to be degenerate, in some sense.

lemmaUnder Assumptions Absolute Continuity, Manifold, Continuous Differentiability, and Generic, the argmin of $Q(t,z)$ over $t\in T$ is unique almost surely-$z$.

Remarks:

enumerate• In the special case that $T=\mathbb{R}^m$, the conditions of Lemma 1 can be satisfied without reference to manifolds or tangent cones. Assumption Continuous Differentiability is satisfied if $Q(t,z)$ is continuously differentiable with respect to $(t,z)$. Conditions (b) and (c) in Assumption Generic simplify to \begin{enumerate} • $\frac{d}{dt}\xi(t,s,z)\neq 0$, or • $\frac{d}{ds}\xi(t,s,z)\neq 0$. \end{enumerate} Thus, Assumption Generic is satisfied if, for every $(t,s,z)\in\Xi$, $\xi(t,s,z)$ is nonzero, or any of its derivatives are nonzero. • Intuitively, the proof of Lemma 1 eliminates potential global minimizers occurring at distinct points. Each condition in Assumption Generic eliminates $t\neq s$ as simultaneous global minimizers of $Q(t,z)$. Clearly, using the first-order condition, if the derivative with respect to $t$ is nonzero, then we can eliminate that point as a global minimizer. The novel idea is recognizing that we can do the same thing for derivatives with respect to $z$. If the difference of the derivatives at two distinct points, $t\neq s$, with respect to $z$ is nonzero, then the probability of two global minimizers occurring in neighborhoods of those two points is zero. If, with probability 1, all simultaneous global minimizers $t\neq s$ are eliminated, we can conclude that the argmin contains two or more points with probability zero.

Applications

Nonconvex M-estimation

Lemma 1 can be applied to estimation methods that minimize a random objective function, also known as M-estimation. In this case, $Q$ is the negative of the likelihood or some other objective function, $T$ is the parameter space, and $z$ is the sample. These optimization problems are known to be nonconvex in general.

Uniqueness of the argmin is an important property in M-estimation, for a variety of reasons. (1) Although it is not necessary for asymptotic results, such as consistency, uniqueness is the finite sample property that the estimator is a point, a desirable property in itself. (2) In addition, finding the global minimum is a very hard problem numerically, and there are many algorithms, such as multi-start or branch-and-bound, that are designed to find the global minimum. For all of these, uniqueness of the argmin is important for a well-defined convergence criterion. At the same time, uniqueness is a property that is often difficult to verify numerically because the objective function can be very flat or contain many local minimizers in a neighborhood of the global minimizer. (3) Also, uniqueness is important for replication and communication in research. If a replication study calculates a different value of an M-estimator, the study may come to a different conclusion than the original. (4) In addition, HillierArmstrong1999 provide a formula for the exact density of the maximum likelihood estimator, under the assumption that it is unique, among other regularity conditions. For these reasons, it is useful to have an analytic guarantee that the argmin is unique almost surely.

Classical Likelihood

The canonical example is classical maximum likelihood. A lot of effort has been put into verifying uniqueness of the argmin in isolated cases of nonconvex likelihoods. These examples include the truncated normal likelihood (Orme1989 and OrmeRuud2002), the Cauchy likelihood (Copas1975), the Weibull likelihood (ChengChen1988), the Tobit model (Olsen1978 and WangBice1997), random coefficient regression models (Mallet1986), k-monotone densities (Seregin2010), estimating a covariance matrix with a Kronecker product structure (RosBijmaMunckGunst2016 and SoloveychikTrushin2016), and a variety of nonparametric mixture models (Simar1976, HillSaundersLaud1980, Lindsay1983a, Lindsay1983b, Jewell1982, LindsayCloggGrego1991, LindsayRoeder1993, and Wood1999). All of these examples require specific knowledge about the structure of the objective function.

The mixture model is an important example because of its widespread use and the presence of many local minimizers. The cases where uniqueness has been verified, such as in Lindsay1983a, are for nonparametric mixture models, where the number of mixture components, $J$, is allowed to be as large as necessary to maximize the likelihood. In some cases, this can be as large as $n/2$, or half of the sample size. This contrasts with finite mixture models, where the number of mixture components is fixed and assumed known. To the author's knowledge, uniqueness of the maximum likelihood estimator has not been verified in finite mixture models. Theorem 1, below, uses Lemma 1 to verify uniqueness of the maximum likelihood estimator for a finite mixture of normal distributions.

The normal mixture model assumes the sample, $\{z_i\}_{i=1}^n$, is drawn independently and identically from a continuous distribution with density, $f_0(z)$, that is approximated by a mixture density, $f(z;\tau,\mu)$, where $\tau$ is a $J$-vector of weights and $\mu$ is a $J$-vector of means. The mixture density satisfies \[ f(z; \tau, \mu)=\sum_{j=1}^J \tau_j \phi(z-\mu_j), \] where $\phi(z)$ is the standard normal density. The weights, $\tau_j$, are assumed to be positive and sum to 1. The means, $\mu_j$, are assumed to be strictly increasing: $\mu_1<\mu_2<...<\mu_J$. These assumptions are necessary to ensure that the components can be separately identified. In this case, the parameter to be optimized is $(\tau,\mu)$, while the random vector is the full sample, $z=(z_1,...,z_n)$. We can write the negative of the log-likelihood as: \[ Q(\tau,\mu,z)=-\sum_{i=1}^n \log f(z_i;\tau,\mu). \]

theoremIf $J\le \sqrt{n}$, then the argmin of $Q(\tau,\mu,z)$ over $(\tau,\mu)$ is unique almost surely-$z$.

Remarks:

enumerate• The proof of Theorem 1 verifies condition (d) in Assumption Generic by taking derivatives with respect to $z$ and arguing that $\frac{d}{dz_i}Q(\tau,\mu,z)=\frac{d}{dz_i}Q(\varsigma,\nu,z)$ for all $i=1,...,n$ implies $\tau=\varsigma$ and $\mu=\nu$. • The assumption that $J\le \sqrt{n}$ is an artifact of the proof. The proof needs $n$ to be large so that there are enough derivatives with respect to $z_i$ for the argument in the first remark to be successful. In practice, the assumption that $J\le\sqrt{n}$ is weak. Practical uses of finite mixture models require very few components relative to the sample size. • Theorem 1 does not require the model to be correctly specified. The proof only requires that $z_i$ is continuously distributed. • Theorem 1 demonstrates how Lemma 1 can be used to verify uniqueness of M-estimators. It is stated for a normal mixture, but the proof also covers any mixture of a 1-parameter exponential family. In addition, the proof of Theorem 1 can be extended to any mixture of a $p$-parameter exponential family. • The mixture of a $p$-parameter exponential family includes, as a special case, a normal mixture with unknown variance, but with an important caveat. As a variance parameter goes to zero, the likelihood diverges. Thus, the assumption that $Q(t,z)$ is a real-valued function rules out values of the variance equal to zero. If no lower bound is placed on the variance, no global minimum exists. With a lower bound on the variance, an extension to the proof of Theorem 1 gives almost sure uniqueness.

Theorem 1 requires $\mu_1<\mu_2<...<\mu_J$. In practice, $Q(\tau,\mu,z)$ is usually minimized without this restriction, resulting in nonuniqueness of the argmin. In this case, Lemma 1 can still be used to characterize the argmin given any one global minimizer. When the global minimizer has all distinct means, the argmin is composed of all permutations of the components. An additional complication arises when the global minimizer happens to have multiple components with exactly the same mean. In that case, one can reweight the identical components to find other global minimizers. Corollary 1, below, states this characterization in a way that covers both cases.

Let $\nu^*$ denote another $J$-vector of means, and let $\varsigma^*$ denote another $J$-vector of positive weights that sum to $1$.

corollaryIf $J\le \sqrt{n}$ and if $(\tau^*,\mu^*)$ is a global minimizer of $Q(\tau,\mu,z)$ over the unrestricted parameter space, then the argmin of $Q(\tau,\mu,z)$ over the unrestricted parameter space is equal to \[ \{(\varsigma^*,\nu^*): \sum_{j=1}^J\varsigma_j^*\mathds{1}\{\nu^*_j=\mu^*_k\} =\sum_{j=1}^J\tau_j^*\mathds{1}\{\mu^*_j=\mu^*_k\} \text{ for all } k=1,...,J\} \] almost surely-z.

Remarks:

enumerate• Corollary 1 states that the set of all global minimizers can be computed by permuting and reweighting any one global minimizer. • The proof of Corollary 1 demonstrates a general argument for characterizing the argmin of a random objective function, even when the argmin is not unique. The proof transforms the parameter space to a nonredundant version, and then applies Lemma 1.

Penalized Likelihood

Nonconvexity may also arise from a penalty term. Nonconvex penalties are popular because they have desirable properties for recovering sparsity. The $L_0$ penalty is the most direct way to impose sparsity. The $L_q$ penalty for $q\in (0,1)$, or bridge penalty, is a continuous penalty that still leads to sparse estimates. FanLi2001, FanPeng2004, and FanXueZou2014 consider a class of folded concave penalties, including the smoothly clipped absolute deviation (SCAD) penalty. Zhang2010 proposes the minimax concave penalty (MCP), which minimizes the nonconvexity of the penalty subject to constraints. LohWainwright2017 consider a class of nonconvex penalties and give conditions for variable selection consistency.

In particular, the global minimizer using these penalties has desirable properties. ZhangZhang2012 show that the global minimizer has desirable recovery performance. They also show that the global minimizer is the unique sparse local solution. Also, HuangHorowitzMa2008 show an oracle property for the global minimizer with the bridge penalty, and KimChoiOh2008 show an oracle property for the global minimizer with the SCAD penalty.

We show that the global minimizer of the penalized likelihood is unique almost surely in the case of the linear regression model with a wide variety of penalties, including all the penalties mentioned above. Let \[ Y=X\beta+\epsilon, \] where $Y$ is an $n\times 1$ vector and $X$ is a $n\times d$ matrix. We estimate $\beta$ by minimizing \[ Q(\beta,Y,X)=\frac{1}{2}\|Y-X\beta\|^2+p(\beta), \] where $p(\beta)$ is a penalty term, over $\beta\in B\subset \mathbb{R}^d$.

theoremAssume $B=\cup_{j=1}^J B_j$, where each $B_j$ is a manifold, possibly with boundary or corner, such that $p(\beta)$ is continuous over each $B_j$. If $X$ is full rank $d$ and the distribution of $Y$ conditional on $X$ is absolutely continuous, then the argmin of $Q(\beta,Y,X)$ over $B$ is unique almost surely.

Remarks:

enumerate• The assumption that $X$ is full rank is the same condition for uniqueness in unpenalized least squares. It is surprising that the only additional condition needed for uniqueness in penalized least squares is absolute continuity of $Y$ conditional on $X$. • Theorem 2 accommodates a wide variety of nonconvex penalties. Even some discontinuous penalties can be accommodated, including the $L_0$ penalty by partitioning the parameter space into all possible combinations of $\beta_j=0$ and $\beta_j\neq 0$. • Theorem 2 is stated for the linear regression model, but the argument can be used for more general penalized likelihood models. In fact, if we verify uniqueness of the unpenalized likelihood using Lemma 1, where we verify Assumption Generic using condition (d), as in the finite mixture model, then uniqueness of the global minimizer of the penalized likelihood follows by the same argument for any continuous, deterministic penalty.

The Argmin Theorem

In many cases, limit theory for M-estimators follows from the argmin theorem (see KimPollard1990 or VaartWellner1996). An important condition in the argmin theorem is that the limiting stochastic process has a unique minimum almost surely.

The uniqueness condition has been analyzed in the case that the limiting stochastic process is, itself, a Gaussian process. Papers considering this case include Lifshits1982, KimPollard1990, Arcones1992, MullerSong1996, and Ferger1999. The arguments used in these papers are all specific to proving uniqueness of the minimizer of a Gaussian process, rather than a more general function of a Gaussian process. In addition, Pimentel2014 and LopezPimentel2016 characterize uniqueness using differentiability of a perturbation-expectation operator, which is useful in some examples.

Lemma 1 provides a new technique for verifying the uniqueness condition. In addition to covering the case where the limit is, itself, a Gaussian stochastic process, Lemma 1 is applicable to the more general setting, where the limit is a function of a Gaussian process. We demonstrate the usefulness of Lemma 1 using two novel applications in this setting: p-value based threshold regression and weak identification.

Threshold Regression

Consider the threshold regression model of MallikBanerjeeSen2013: \[ Y=\mu(X)+\epsilon, \] where $\mu(\cdot)$ is a continuous function that is equal to a fixed value $\tau$ for $X\le d_0$ and is strictly larger than $\tau$ for $X>d_0$. The parameter of interest is the threshold $d_0$ estimated by a p-value based M-estimator.

MallikBanerjeeSen2013 characterize the limit of the objective function as a functional of a Gaussian process. Specifically, let $W(t)$ with $t\in\mathbb{R}$ be a Gaussian process with almost surely continuous sample paths, continuous drift $m(t)$ and continuous covariance kernel $\Sigma_{t_1,t_2}$. The limiting objective function is

equation[equation omitted — 60 chars of source]

where $\Phi(\cdot)$ is the standard normal cdf and $\gamma$ is a constant. This defines a functional of a Gaussian process. MallikBanerjeeSen2013 are unable to prove that (3.1) has a unique minimum almost surely, but assume uniqueness in order to invoke the argmin theorem. We show that under the assumption $\Sigma_{t,s}>0$ for all $t, s\in\mathbb{R}$ (which follows from Assumption 3(a) and Lemma 2 in MallikBanerjeeSen2013), the minimum is indeed almost surely unique.

theoremIf $\Sigma_{t,s}>0$ for all $s,t\in\mathbb{R}$, then the argmin of $Q(t,W(\cdot))$, defined in equation (3.1), over $t\in\mathbb{R}$ is unique almost surely.

Remark:

enumerate• The proof of Theorem 3 demonstrates how Lemma 1 can accommodate an infinite dimensional source of randomness: by taking derivatives with respect to $Z=W(M)$, for fixed values of $M$.

Limit Theory for Weakly Identified Parameters

Limit theory for estimators of weakly identified parameters relies on the argmin theorem. This requires a unique minimum assumption on the limit of the profiled objective function. Papers that use this assumption include StockWright2000, AndrewsCheng2012, Cheng2015, Cox2019, and HanMcCloskey2018. AndrewsCheng2012 provide sufficient conditions for uniqueness in the special case that the key parameter, which determines the strength of identification, is scalar. However, examples that require a vector of key parameters, including Cheng2015 and Cox2019, can benefit from the low-level sufficient conditions stated in this paper.

Following Cox2019, one first reparameterizes the model into the identified parameters, $\beta$, and the unidentified parameters, $\pi$. Next, one defines a function, $h: (\beta,\pi)\mapsto h(\beta,\pi)\in\mathbb{R}^{d_h}$, that maps structural parameters to identified reduced-form parameters. $h$ has the property that for some values of $\beta$, $h$ is injective as a function of $\pi$, and then $\pi$ is identified, but for other values of $\beta$, $h$ is not injective as a function of $\pi$, and then $\pi$ is not identified. In this way, the identifiability of $\pi$ depends on the true value of $\beta$. The simplest example of a function satisfying this property is $h(\beta,\pi)=\beta\pi$, which is injective as a function of $\pi$ if and only if $\beta\neq 0$.

Consider an estimator $(\hat\beta,\hat\pi)$ that minimizes a random objective, $Q_n(\beta,\pi)$. To derive the asymptotic distribution of $\hat\pi$ we consider the profiled objective, $Q_n^p(\pi)=\min_\beta Q_n(\beta,\pi)$. Appropriately standardized, this converges to a limiting stochastic process over $\pi$ whose argmin characterizes the asymptotic distribution, if it is unique. In what follows we give the formula for the limit, as well as sufficient conditions for the argmin to be unique.

Let parameters $\beta$ and $\pi$ have dimensions $d_\beta$ and $d_\pi$, respectively. We characterize the limit along a sequence of true values of the parameters, $\beta_n$ converging to $\beta_0$, a point for which $h$ is not an injective function of $\pi$. These sequences lead to an intermediate identification strength, called weak identification, indexed by a local parameter $b\in\mathbb{R}^{d_\beta}$. The asymptotic distributions are continuous in this local parameter, and thus are the appropriate sequences for contiguity. The case $b=0$ is an important special case corresponding to a complete loss of identification. It derives from $\beta_n=\beta_0$ for all $n$. A typical sequence satisfies the following assumption, which says that $\beta_n$ influences the value of $h(\beta,\pi)$ at the $\sqrt{n}$ rate.

namedassumption[Weak Identification] \begin{enumerate}[label=(\alph*)] • $h(\beta,\pi)$ is twice continuously differentiable, and • for some $b\in\mathbb{R}^{d_\beta}$, $\sqrt{n}\left[h(\beta_n,\pi)-h(\beta_0,\pi)\right]\rightarrow h_\beta(\beta_0,\pi)b$, uniformly on compact sets over $\pi$, where $h_\beta(\beta,\pi)$ denotes the derivative of $h(\beta,\pi)$ with respect to $\beta$. \end{enumerate}

In this application, the parameter $\pi$ serves the same purpose as $t$, indexing the domain of the random function. The domain is the identified set for $\pi$ under identification loss. Allowing the domain to be a union of manifolds is useful because the identified set often has an unusual shape that may be difficult to characterize exactly. Following calculations in Cox2019, there exists a continuous random vector, $z$, with dimension $d_z=d_\beta+d_h$, and there exists a symmetric and positive definite $d_z\times d_z$ matrix, $H$, such that the limit of the profiled objective function is

equation[equation omitted — 99 chars of source]

where

align*[align* omitted — 275 chars of source]

and $\kappa(\pi)$ is some continuous deterministic function of $\pi$. Notice that this limit is indexed by a finite dimensional random vector, $z$, rather than an infinite dimensional stochastic process, and hence is more susceptible to nonuniqueness.

The following theorem places low-level conditions on $h$ in order to show that the argmin of $Q(\pi,z)$ over $\pi$ is almost surely unique.

theoremAssume the identified set can be written as a finite or countable disjoint union of second-countable Hausdorff manifolds. Let $h(\beta,\pi)$ and the sequence $\beta_n$ satisfy Assumption Weak Identification. Let $Q(\pi,z)$ be defined in equation (3.2). If \begin{enumerate}[label=(\alph*)] \setcounter{enumi}{2} • for all $\pi_1\neq \pi_2$, the rank of $h_\beta(\beta_0,\pi_1)-h_\beta(\beta_0,\pi_2)$ is $d_h$, and • there exists an open set $B$ containing $\beta_0$, such that for almost every $\beta\in B$, $h(\beta,\pi)-h(\beta_0,\pi)$ is an injective function of $\pi$. \end{enumerate} Then, $\xi(\pi_1,\pi_2,z)=Q(\pi_1,z)-Q(\pi_2,z)$ satisfies Assumption Generic. Therefore, by Lemma 1, the argmin of $Q(\pi,z)$ over $\pi$ is unique almost surely.

Remarks:

enumerate• Conditions (c) and (d) eliminate degeneracy in $Q(\pi,z)$ as a function of $\pi$ so that Assumption Generic can be verified by taking derivatives with respect to $z$. Condition (c) is a rank condition guaranteeing that $h_\beta(\beta_0,\pi)$ varies enough as a function of $\pi$. A necessary condition is that $d_\pi\le d_h$. Condition (d) says that $\pi$ is generically identified locally around $\beta_0$. Below, two examples are given that demonstrate the importance of these two conditions. • The proof of Theorem 4 using Lemma 1 is nontrivial and requires an appeal to Sard's theorem to characterize the critical values of $h_\beta(\beta_0,\pi)(z_1-b)$ as a function of $\pi$.

figure[figure omitted — 474 chars of source]

exampleThis example demonstrates the importance of condition (d), that $\pi$ is generically identified in a neighborhood of $\beta_0$. Consider the model, \[ Y_i=\alpha+\beta_1 X_{1i}+\beta_2 X_{2i}+(\beta_1\pi+\beta_2\pi^2)X_{3i}+u_i, \] where $\mathbb{E}(u_i|X_{1i},X_{2i},X_{3i})=0$. In this case, identification of $\pi$ is determined by injectivity of $h(\beta_1,\beta_2,\pi)=\beta_1\pi+\beta_2\pi^2$ in a neighborhood of $(\beta_1,\beta_2)=(0,0)$. Condition (d) is not satisfied because, for any $\beta_1$ and $\beta_2\neq 0$, there exists an $h\in\mathbb{R}$ such that the quadratic equation, $\beta_1\pi+\beta_2\pi^2=h$, has multiple solutions in $\pi$. We can calculate $\frac{d}{d\beta}h(\beta_1,\beta_2,\pi)|_{\beta_1=0, \beta_2=0}=[\pi, \pi^2]$, which satisfies condition (c). If $\pi$ is estimated by nonlinear least squares, the limit of the profiled objective function, $Q(\pi,z)$, has multiple minimizers with positive probability. Figure 1 gives some simulations of this function.

figure[figure omitted — 471 chars of source]

exampleThis example demonstrates the importance of condition (c), which states that $h_\beta(\beta_0,\pi_1)-h_\beta(\beta_0,\pi_2)$ has full rank, $d_h$, for all $\pi_1\neq \pi_2$. Consider the model, \[ Y_i=\alpha+\beta X_{1i}+\beta(\pi+\pi^2) X_{2i}+\beta^2\pi X_{3i}+u_i, \] where $\mathbb{E}(u_i|X_{1i},X_{2i},X_{3i})=0$. In this case, identification of $\pi$ is determined by injectivity of \[ h(\beta,\pi)=\left[\begin{array}{c}\beta(\pi+\pi^2)\\ \beta^2\pi\end{array}\right], \] in a neighborhood of $\beta=0$. Condition (d) is satisfied because for any $\beta\neq 0$, $\beta^2\pi$ is injective as a function of $\pi$. We can calculate \[ \frac{d}{d\beta}h(\beta,\pi)|_{\beta=0}=\left[\begin{array}{c}\pi+\pi^2\\ 0 \end{array}\right], \] which does not satisfy condition (c) because the rank is zero whenever $\pi_1$ and $\pi_2$ are both roots of $\pi+\pi^2=c$. If $\pi$ is estimated by nonlinear least squares, the limit of the profiled objective function, $Q(\pi,z)$, has multiple minimizers with positive probability. Figure 2 gives some simulations of this function. The key components of this example are the two functions in $h(\beta,\pi)$ that depend nonlinearly on $\beta$, and contain different amounts of information about $\pi$. As $\beta_n\rightarrow 0$, the more informative function is weaker, and therefore cannot satisfy condition (c). This example is concerning because it seems likely that these key components are present in more complicated weakly identified models.

The Proof of Lemma 1

This section gives the proof of Lemma 1. The proof is simple and intuitive. The first subsection reduces the global problem to a local problem, the second subsection states lemmas for the local problem, and the third subsection finishes the proof. The proofs of the additional lemmas are in the appendix.

Global to Local

We first reduce from minimization over all of $T$ to minimization over a countable collection of compact neighborhoods, $K\in \mathcal{K}_j$, that separate points of $T_j$. Since each $T_j$ is second-countable and Hausdorff, this countable collection always exists. For any $K\subset T$, define the value function, \[ V(K,z)=\inf_{t\in K} Q(t,z). \]

We consider $j_1,j_2\in J$. Let $K\in\mathcal{K}_{j_1}$ and $C\in\mathcal{K}_{j_2}$ be disjoint. Lemma 2 shows that the value of the minimum over disjoint compact sets, $K$ and $C$, being different from each other or from the value of the minimum over all of $T$ is sufficient for the argmin to be unique almost surely.

lemmaSuppose that $\{\mathcal{Z}_k\}_{k=1}^{\infty}$ is a sequence of compact subsets of $\mathcal{Z}$ such that $P(\mathcal{Z}_k)\rightarrow 1$ as $k\rightarrow\infty$, and suppose that for every $k\in\mathbb{N}$, for every $j_1,j_2\in J$, for every $K\in \mathcal{K}_{j_1}$ and $C\in\mathcal{K}_{j_2}$ such that $K\cap C=\emptyset$, \[ P\left(\{z\in \mathcal{Z}_k| V(T,z)=V(K,z)=V(C,z)\}\right)=0. \] Then, the argmin of $Q(t,z)$ over $t\in T$ is unique almost surely.

The condition in Lemma 2 is still not local. Lemma 3 reduces this condition to a local condition by finding neighborhoods of $t$, $s$, and $z$ that can be used to cover these compact sets such that an appropriate probability is zero.

lemmaFix $\mathcal{Z}_k\subset \mathcal{Z}$, compact, fix $j_1,j_2\in J$, and fix $K\in\mathcal{K}_{j_1}$ and $C\in\mathcal{K}_{j_2}$ such that $K\cap C=\emptyset$. Suppose, for every $\bar z\in\mathcal{Z}_k$ and for every $(t,s)\in K\times C$, there exist neighborhoods, $N_{t, s,\bar z}, M_{t,s,\bar z}$, and $W_{t,s,\bar z}$ of $t, s$, and $\bar z$, respectively, such that \begin{align} P\left(\{z\in W_{t,s,\bar z}| \right.V(T,z)=V(K,z)&=V(N_{t,s,\bar z},z)\nonumber\\ &\left.=V(C,z)=V(M_{t,s,\bar z},z)\}\right)=0. \end{align} Then, \[ P\left(\{z\in\mathcal{Z}_k| V(T,z)=V(K,z)=V(C,z)\}\right)=0. \]

The Local Problem

For the rest of this section, fix $j_1,j_2\in J$, $K\in \mathcal{K}_{j_1}$, $C\in\mathcal{K}_{j_2}$ such that $K\cap C=\emptyset$, $t\in K$, $s\in C$, and $\bar{z}\in \mathcal{Z}_k$. We state lemmas that are useful for showing the existence of neighborhoods, $N, M$, and $W$, that satisfy (4.1), using properties of $Q(t,\bar z)$ that follow from Assumption Generic. Assumption Generic implies one of three conditions:

enumerate• $Q(t,\bar z)\neq Q(s,\bar z)$, • there exists a $\Delta\in A(t)$ such that $\frac{d}{dh}Q(t+h\Delta,\bar z)|_{h=0}<0$, and symmetrically for $s$, and • $\frac{d}{dz}Q(t,\bar z)\neq\frac{d}{dz}Q(s,\bar z)$.

Lemmas 4, 5, and 6, below, show the existence of neighborhoods that satisfy (4.1) for each of these cases, respectively.

Lemma 4 follows from the intuitive notion that if the value of $Q(t,\bar z)$ is far from the value of $Q(s,\bar z)$, then the value of $V(N,z)$ is far from the value of $V(M,z)$, for small enough neighborhoods of $t$, $s$, and $\bar z$.

lemmaIf $Q(t,\bar z)\neq Q(s,\bar z)$, then there exist neighborhoods, $N$, $M$, and $W$, so that \[ \{z\in W | V(N,z)=V(M,z)\}=\emptyset. \]

Lemma 5 uses the first order conditions for optimality of $t$ or $s$. It uses the intuitive notion that if $t$ is not a relative minimum of $Q(t,\bar z)$, then it is not a global minimum of $Q(t,\bar z)$ over $T$, and it can be bounded away from the minimum in a neighborhood of $\bar z$.

lemmaIf there exists a $\Delta\in A(t)$ such that \[ \frac{d}{d h}\left.Q(t+h \Delta,\bar z)\right|_{h=0}<0, \] then there exist neighborhoods of $t$ and $\bar z$, $N$ and $W$, such that \[ \{z\in W| V(N,z)=V(T,z)\}=\emptyset. \]

Lemma 6 is a novel contribution allowing a simple proof of Lemma 1. It relies on a type of mean value bound for secants of the value function. The intuition is if, in some $z$-direction, the derivative of $Q(t,\bar z)$ is always less than the derivative of $Q(s,\bar z)$, then any secants of $V(N,\bar z)$ and $V(M,\bar z)$ share that property, for sufficiently small neighborhoods, $N$ and $M$. Thus, $V(N,\bar z)$ is always increasing or decreasing at a rate which is less than the rate at which $V(M,\bar z)$ is increasing or decreasing. This implies that they cannot cross more than once, and the set of crossing points must have probability zero.

lemmaIf \[ \frac{d}{dz}Q(t,\bar z)\neq \frac{d}{dz}Q(s,\bar z), \] then there exist neighborhoods, $N$, $M$, and $W$, so that \[ P(\{z\in W| V(N,z)=V(M,z)\})=0. \]

Lemmas 4-6 are sufficient to find neighborhoods that satisfy (4.1). We now use them to prove Lemma 1.

Proof of Lemma 1

For any $P$ over $\mathbb{R}^{d_z}$, there exists a sequence of compact sets, $\mathcal{Z}_k\subset \mathcal{Z}$, such that $P(\mathcal{Z}_k)\rightarrow 1$ as $k\rightarrow\infty$. Fix $j_1, j_2\in J$, $K\in\mathcal{K}_{j_1}$, and $C\in\mathcal{K}_{j_2}$ such that $K\cap C=\emptyset$. We seek to verify the conditions of Lemma 3. Fix $t\in K$, $s\in C$, and let $\bar z\in\mathcal{Z}_k$. We divide into cases:

enumerate• $Q(t,\bar z)\neq Q(s,\bar z)$. In this case, the existence of neighborhoods, $N$, $M$, and $W$, satisfying (4.1) follows from Lemma 4. • There exists a $\Delta\in A(t)$ such that $\frac{d}{dh} Q(t+h\Delta,\bar z)|_{h=0}<0$ or $\frac{d}{dh} Q(s+h\Delta,\bar z)|_{h=0}<0$. In both cases, the existence of neighborhoods satisfying equation (4.1) follows from Lemma 5. • $\frac{d}{d z}Q(t,\bar z)\neq \frac{d}{d z}Q(s,\bar z)$. In this case, the existence of neighborhoods, $N$, $M$, and $W$, satisfying (4.1) follows from Lemma 6.

The above cases exhaust the possibilities. Thus, for every $(t,s)\in K\times C$, the condition of Lemma 3 is satisfied for $K$ and $C$. Since $K$ and $C$ are arbitrary, this verifies the condition of Lemma 2. Therefore, by Lemma 2, the argmin of $Q(t,z)$ over $t\in T$ is unique almost surely-$z$. \qed

Conclusion

This paper establishes the argmin of a random objective function to be unique almost surely. This paper first formulates a general result, Lemma 1, that proves uniqueness without convexity of the objective function. This paper applies the result to prove uniqueness in a variety of statistical applications. In M-estimation, uniqueness of the argmin is established for the first time in finite mixture models and penalized linear regression with nonconvex penalty. In the argmin theorem, uniqueness of the argmin of the limiting stochastic process is established for the first time in two cases: p-value based threshold estimation and the profiled objective function for weakly identified parameters.