Fixed-weight-matrix conjecture for spurious local minima

Let $\epsilon\in[0,1]$, let $C$ be a fixed weight matrix satisfying $C_{ij}\in\{0\}\cup[\epsilon,1]$, and let $u^*$ be a solution. Define

$$\mathbb{D}_C(u^*):= \left(\min_{(C,\tilde{u}^*)\in\overline{\mathcal{D}}}\|u^* - \tilde{u}^*\|_1\right)^{-1}.$$

Here $\overline{\mathcal{D}}$ is the closure of the set of desired instances, and a spurious local minimum is a local minimum that is not a desired solution.

Fixed-weight-matrix conjecture. There exists a large constant $\Gamma(\epsilon)>0$ such that every instance $\mathcal{MC}(C,u^*)$ satisfying

$$C_{ij}\in\{0\}\cup[\epsilon,1],\qquad \mathbb{D}_C(u^*)\geq\Gamma(\epsilon)$$

has spurious local minima.

The conjecture gives a necessary-condition-type prediction for spurious local minima using the modified complexity metric for a fixed weight matrix. The preceding theorem establishes an analogous result for $\mathbb{D}_{\alpha,\epsilon}$, but the supplied text does not establish this fixed-weight formulation.