Spectral Subspaces, Then Langevin: Learning Hidden-Winner Regression Mixtures

Many economic and behavioral datasets record only the winner of a hidden competition. A worker's wage is observed for the occupation they chose, never for the alternatives. A bid is observed only if it was the highest. Statisticians call this the Roy model, or linear regression under self-selection. There are $k$ unknown linear models, each sample reports only $y=\max_j(\langle w_j,x\rangle+\eta_j)$, and in the hard version nobody records which model won. Cherapanamjeri et al. show that the top eigenvectors of one weighted covariance matrix, $\mathbb{E}[\max(0,y)^2\,xx^\top]$, span the subspace containing all $k$ true weight vectors. That computation costs time polynomial in the dimension. Separating the individual vectors inside that subspace is the hard part. Their higher-moment peeling procedure costs $\exp(k)$ and reaches only $1/\mathrm{poly}(k)$ accuracy, and they explicitly leave local refinement by EM as an open problem.

We propose to split the work between the two tools. The cheap spectral step finds the $k$-dimensional subspace. Inside that subspace, a likelihood-based refinement separates the $k$ vectors. The refinement is driven by an unadjusted Langevin sampler, a Markov chain that follows the gradient of the log-density plus Gaussian noise and skips the usual accept/reject test. The sampler is needed because the unobserved losing outcomes are truncated Gaussians whose expectations have no closed form once the noise is correlated across models. The bet is that likelihood-based search in a $k$-dimensional space succeeds reliably at values of $k$ where moment peeling becomes useless and where random initialization in the full $d$-dimensional space fails.

Core Claim

The spectral estimate should be used to restrict where the optimizer searches, not only to choose its starting point. We claim three things. First, an unadjusted-Langevin stochastic approximation of EM (ULA-SAEM), confined to the estimated subspace, recovers all $k$ weight vectors and the noise covariance $\Sigma$ with high probability from in-subspace random starts. Second, a short full-space polish then removes the error inherited from the estimated subspace. Third, the whole pipeline runs in time polynomial in $d$ and $k$, which the moment-peeling route does not.

The proposal also asks a quantitative question that the literature leaves open. How large can the Langevin step size $\gamma$ be before its asymptotic bias pushes the parameters out of the basin around the global optimum? We expect the answer to depend on the subspace error and on the contraction strength of the projected likelihood. Gruffaz et al. show that the parameter bias of biased SAEM scales with the sampler's bias times a Lyapunov-regularity constant. Combined with the standard $O(\gamma)$ bias of the unadjusted Langevin algorithm (Durmus and Moulines), this predicts a fixed-point shift linear in $\gamma$. We will measure that slope and compare it to the basin radius.

Relation to Prior Work

The two halves of the method come from different papers that never meet. Cherapanamjeri et al. motivate the work. They use projected Langevin Monte Carlo with SGD only in the known-winner case, where the likelihood is strongly convex. They use spectral moments only as a standalone estimator in the unknown-winner case. We connect the two, and we replace their peeling stage rather than add a step on top of it.

The refinement engine follows two papers. De Bortoli et al. introduced SOUL, a stochastic optimizer driven by unadjusted Langevin that warm-starts the sampler's chain from one outer iteration to the next. Gruffaz et al. analyze SAEM driven by biased samplers and show that the Metropolis-adjusted variant (MALA) stalls when its acceptance rate collapses. Both papers assume convexity, or iterates that stay in a compact good region, and both use ad hoc starting points. Our contribution is to supply the good region from spectral structure and to measure how sampler bias interacts with it.

Hybrid spectral-then-EM pipelines already exist in other model classes. Gong and Saxena use tensor decomposition followed by Kalman EM for mixtures of linear dynamical systems. Barbault et al. use method-of-moments followed by EM for Bernoulli-Gaussian sparse recovery. Both depend on exact, closed-form E-steps and use the moment estimate only as a point initialization. In our setting the E-step is intractable, and the spectral output is a subspace rather than a point.

The truncated-sampling machinery follows Bhattacharyya et al. and the Daskalakis line, for example Daskalakis et al.. Their membership-oracle Langevin samplers avoid the $e^{\Omega(d)}$ cost of rejection sampling. Bhattacharyya et al. also note that jointly estimating mean and covariance under truncation is open. Our joint estimation of $\Sigma$ is a modest step in that direction.

Finally, Koehler et al. warm-start samplers from data to escape multimodality. We warm-start the optimizer's search space. This is a different object, although we borrow their idea of initializing the inner chains from the data.

Research Program

The model. The Roy model has correlated noise $\eta\sim\mathcal N(0,\Sigma)$ with $\Sigma$ an unknown $k\times k$ matrix. This is the economically realistic case. With independent noise the likelihood $\sum_j\phi(y-\langle w_j,x\rangle)\prod_{i\ne j}\Phi(y-\langle w_i,x\rangle)$ is closed-form, where $\phi$ and $\Phi$ are the standard normal density and cumulative distribution function. With correlated noise it requires orthant probabilities and truncated multivariate-normal moments. For a sample $(x,y)$, the latent variables are the winning index $j$ and the $k-1$ losing outcomes $u_{-j}$. Given $j$, the losing outcomes follow a Gaussian conditioned on $u_j=y$ and truncated to $u_{-j}\le y$.

The inner sampler. For each candidate winner $j$ we keep one projected-ULA chain over $u_{-j}$, warm-started across iterations as in SOUL. Each chain takes a Langevin step and then projects back into the box $u_{-j}\le y$. The posterior weight of each winner combines the Gaussian density at $y$ with an orthant probability, which we estimate by quasi-Monte Carlo integration.

Stage 1: spectral subspace. We compute the top-$k$ eigenvectors $U\in\mathbb R^{d\times k}$ of the empirical weighted covariance from Cherapanamjeri et al.

Stage 2: in-subspace search. We write $w_j=Uv_j$ and run ULA-SAEM over the $v_j\in\mathbb R^k$ and over $\Sigma$, starting from $R$ random in-subspace initializations. We keep the run with the best estimated likelihood.

Stage 3: full-space polish. We release the subspace constraint and run a short full-space ULA-SAEM with a decreasing step size $\gamma_t$.

Analysis. On the theory side, we will try to show that the projected population likelihood has no spurious local maxima for small $k$, or for well-separated $w_j$. We will also derive the admissible step size in terms of the subspace angle error and the local curvature. We regard the landscape result as uncertain. The empirical program does not depend on it.

Baselines

The do-nothing reference is full-space ULA-SAEM from a random initialization. We run it with $R'$ restarts, with $R'$ chosen so that total gradient evaluations match our three stages combined, so the comparison is at equal compute. Its expected failure mode comes from Gong and Saxena. They report that tensor-initialized EM beat randomly initialized EM and pure tensor methods in 91% of their synthetic configurations. That is evidence from a different model class, not from ours. Beating this baseline means a higher probability of recovering all $k$ vectors, up to relabeling, within a fixed error $\epsilon$.

The strongest existing method is the moment-peeling estimator of Cherapanamjeri et al., implemented from their description with the same samples. We found no reported empirical result on Lacuna for this estimator. The file gives only its theoretical guarantee, which is accuracy $1/\mathrm{poly}(k)$ at cost $\exp(k)$ for $k>2$. Beating it means lower parameter error and lower wall-clock time at every $k\ge3$, by a margin that widens as $k$ grows.

A full-warm-start variant uses peeling as a point initialization, followed by full-space ULA-SAEM. This is the "obvious combination," and it tests whether the subspace restriction matters once a good point exists. At small $k$, where peeling is affordable, it should match our method. At larger $k$, where peeling is expensive and inaccurate, we expect it to fall behind.

The key ablation keeps the spectral subspace only to place the starting point inside it, then runs full-space ULA-SAEM from step one. Comparing this ablation with our Stage 2 isolates whether constraining the search, rather than merely starting inside the subspace, is what drives reliability.

The sampler ablation replaces ULA with MALA inside Stage 2 and Stage 3, tuned over the same step-size grid. Gruffaz et al. report that on german MALA's acceptance rate collapsed at large step sizes and the algorithm stalled while ULA kept progressing. We test whether that pattern carries over to truncated latents.

Finally, for the independent-noise model and for correlated noise at small $k$, we include an exact-likelihood baseline. This is spectral subspace plus direct gradient ascent on the numerically integrated likelihood. It serves as the near-unbiased reference, and it also measures ULA's bias.

Why not just…?

Why not just use random restarts of ULA-SAEM? Restarts are the cheapest fix, and at small $d$ they may be enough. That is exactly why the first baseline runs them at matched compute. Our expectation rests on a counting argument. The space of starting points scales with $dk$ coordinates, while the space our method searches scales with $k^2$. Restarts in $d$ dimensions should therefore stop finding the basin at a rate that worsens with $d$, while in-subspace restarts should not. Plotting success probability against $d$ at fixed $k$ settles the question directly.

Why not just refine the peeling estimate, as in Tensor-EM? This is the natural transfer of Gong and Saxena. The weakness is that it inherits peeling's $\exp(k)$ cost and its coarse accuracy at large $k$. It is a real threat at $k\le3$, and the full-warm-start baseline will show where our method stops being needed. If that baseline matches ours at all tested $k$, the subspace-restriction claim fails.

Why not just integrate the likelihood numerically and skip Langevin? For independent noise, and for correlated noise with small $k$, numerical integration works and is probably more accurate. We therefore include it as a baseline rather than argue against it. Langevin earns its place only if, at moderate $k$ (8 to 16), its per-iteration cost is lower than that of exact integration with gradients of truncated moments at matched accuracy. If it does not, we will report that the contribution reduces to "spectral subspace plus exact-likelihood search." That would still be a useful answer to the problem Cherapanamjeri et al. left open.

Why not just use MALA to avoid bias? The sampler ablation tests this directly. We also quantify ULA's bias against the exact-likelihood reference, so any accuracy MALA would buy appears as a measured gap rather than an assumption.

Proposed Experiments

Implementation checks. We first reproduce two published behaviors on benchmarks from the file. On WDBC, the ULA-SAEM code should land near the result of De Bortoli et al., who report that SOUL came within about 3% of the true marginal-likelihood estimate. On german, the ULA/MALA step-size pattern should qualitatively match Gruffaz et al., who give no scalar test log-predictive density in the file.

Main study. The main experiments use synthetic Roy models, because no dataset in the file covers self-selection. We use Gaussian $x$ with $d\in\{50,200,500\}$, $k\in\{2,3,5,8,12,16\}$, sample sizes spanning roughly a decade around the point where the spectral subspace becomes accurate, and $\Sigma$ ranging from independent to strongly correlated. The metrics are:

  • the success rate of recovering all $w_j$ within $\epsilon$, after matching labels;
  • the median parameter error relative to the exact-likelihood reference, where that reference is computable;
  • the error in $\Sigma$;
  • gradient evaluations and wall-clock time to reach $\epsilon$.

Decisive check 1: subspace restriction. At equal compute, the in-subspace method's success rate stays flat as $d$ grows, while both the random-restart baseline and the start-in-subspace-only ablation decline.

Decisive check 2: scaling in $k$. Our method's error and time stay polynomial in $k$ while peeling's blow up.

Decisive check 3: step size versus basin. We sweep $\gamma$ and plot the final parameter shift against $\gamma$ and against the subspace angle error, to locate the step size at which runs begin leaving the correct basin. We expect a linear bias regime at small $\gamma$, following from the Lyapunov-times-sampler-bias bound of Gruffaz et al. Beyond it, we expect an abrupt drop in success once the shift exceeds the basin radius. Observing that transition, and whether it moves with subspace accuracy, is the empirical answer to the open trade-off between sampler bias and the spectral basin.