Homotopy Paths That Keep Nonconvex Sparse Estimators on Solid Ground

Many high-dimensional estimation problems have more unknowns than samples and a loss function that is not even convex. Examples include regression where the input features are measured with noise, regression that estimates the noise level jointly with the coefficients, and robust regression that down-weights outliers. Theory now says the statistics of these problems are fine. Nonconvex Theory of $M$-estimators with Decomposable Regularizers shows that every stationary point of a sparsity-penalized nonconvex loss has an error trapped in a small cone and attains the optimal $s\log d/n$ rate. That holds as long as the loss curves upward along sparse directions, a property called restricted strong convexity. The paper gives no algorithm, though. In the noisy-feature case the problem is worse than a missing proof: the corrected loss has negative curvature along the huge null space, so the penalized objective is unbounded below. Plain proximal gradient started from zero can run off to infinity.

This note proposes a specific way to reach the good stationary points. We use homotopy continuation, which means solving a sequence of problems with a regularization weight $\lambda$ that starts large and shrinks geometrically, warm-starting each stage from the last. We add a cheap, computable certificate that checks at every stage that the iterates stayed sparse and that the loss still curves upward along the directions actually travelled. If the certificate fails, the method shrinks $\lambda$ more gently. The claim is that iterates which stay sparse only ever see the part of the landscape where restricted curvature holds. Homotopy therefore turns a nonconvex, globally curvature-deficient problem into a sequence of effectively strongly convex ones. It does so without the side constraint on $\|\theta\|_1$ that current fixes need, and it comes with a provable linear rate down to statistical precision.

Core Claim

We write the estimator as $\min_\theta \mathcal{L}_n(\theta) + \lambda\|\theta\|_1$, where $\mathcal{L}_n$ is a smooth but possibly nonconvex empirical loss on $\theta\in\mathbb{R}^d$ with $d\gg n$. The curvature condition we need is restricted strong convexity with a tolerance term:

$$ \mathcal{L}_n(\theta') - \mathcal{L}_n(\theta) - \langle \nabla\mathcal{L}_n(\theta), \theta'-\theta\rangle \;\ge\; \frac{\mu}{2}\|\theta'-\theta\|_2^2 - \tau\frac{\log d}{n}\|\theta'-\theta\|_1^2 . $$

Here $\mu>0$ is the restricted curvature and $\tau\ge 0$ measures how badly nonconvexity can bite along dense directions. This inequality is useless when $\theta'-\theta$ is dense, because the negative term dominates. When both points have at most $\tilde s$ nonzeros, $\|\theta'-\theta\|_1^2 \le 2\tilde s\|\theta'-\theta\|_2^2$ by Cauchy–Schwarz, so the right-hand side becomes $(\mu/2 - 2\tau\tilde s\log d/n)\|\theta'-\theta\|_2^2$. That is genuine strong convexity once $n \gtrsim \tilde s\log d$.

Homotopy is exactly the mechanism that keeps $\tilde s$ small. The central technical claim is an invariance lemma. Suppose stage $k$ is warm-started from a point whose support is at most $\tilde s$ and whose distance to the stage-$k$ solution is bounded, and suppose $\lambda_{k+1}=\eta\lambda_k$ with $\eta$ above an explicit threshold. Then every proximal-gradient iterate of stage $k+1$ keeps support at most $\tilde s$, even though $\mathcal{L}_n$ is nonconvex. Stacking stages gives a total gradient-evaluation count of order $\kappa_s(\log(\lambda_0/\lambda_{\text{target}}) + \log(1/\epsilon))$, where $\kappa_s$ is the smoothness-to-restricted-curvature ratio. The final point is a stationary point in the sense of Liu, so it inherits the $O(s\log d/n)$ error bound.

The new part is not homotopy itself. It is showing that homotopy replaces convexity as the thing that makes the path safe, and making that safety checkable at run time.

Relation to Prior Work

Two papers supply the method, and both assume a convex quadratic loss. A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem proves that geometric $\lambda$-shrinkage with warm starts keeps Lasso iterates sparse and yields a global linear rate. Decomposable norm minimization with proximal-gradient homotopy algorithm extends this to group and nuclear norms through a sublinear "generalized cardinality." Both proofs use the fact that the smooth part is a convex quadratic, so the objective decreases monotonically along a convex path. Our proof has to replace that fact with the restricted inequality above and control support growth directly.

The accelerated variant, An Adaptive Accelerated Proximal Gradient Method and its Homotopy Continuation for Sparse Optimization, reaches $O(\sqrt{\kappa_s}\log(1/\epsilon))$ but is also restricted to convex $\ell_1$ least squares. We treat acceleration as a secondary extension, not the core.

Two papers motivate the work by establishing the statistical target without an algorithm. Liu's result above guarantees that stationary points are good. High-dimensional nonconvex LASSO-type M-estimators analyzes the global minimizer of nonconvex $\ell_1$-penalized losses, including robust regression and nonlinear least squares, and explicitly leaves computation open. Our algorithm is meant to reach the estimators both papers describe.

Two papers constrain the design. Acceleration in Distributed Sparse Regression shows that momentum applied outside the proximal step pushes iterates into flat null-space directions. On eyedata this made the DPAG method fail to converge to the correct solution. Any acceleration we add must therefore keep the extrapolated point inside the sparse set. Adaptive acceleration without strong convexity priors or restarts estimates curvature from gradient-difference quotients. When iterate differences are dense, that quotient collapses toward zero in the null space. Our certificate reuses the quotient only on differences that are provably sparse, which is what makes it meaningful. Rest-Katyusha supports the broader point that solution structure speeds convergence, but again only for convex Lasso.

The file does not cover the constrained projected-gradient analyses of noisy-feature regression, and it does not cover path-following for nonconvex penalties with convex losses. We expect both to exist and will position against them in the full write-up. The distinction we are claiming is a nonconvex loss handled with no side constraint and with a run-time certificate.

Research Program

The theoretical part has three steps. The first is the support-invariance lemma. We will show that a proximal step with step size $1/L$ applied to an $\tilde s$-sparse point near the stage solution cannot activate more than $\tilde s$ coordinates while $\lambda_k$ exceeds a constant multiple of $\|\nabla\mathcal{L}_n(\theta^*)\|_\infty$. The argument bounds the size of the gradient off the support using only smoothness and the restricted inequality. The second step is a per-stage linear-rate result. It uses the effective strong convexity on sparse differences and yields the stage length needed to reach the tolerance that makes the next warm start valid. The third step is a termination argument showing that the output satisfies Liu's stationarity condition at $\lambda_{\text{target}}$, so his Theorem 3.3 applies. We will then check the generalization to group sparsity using Eghbali and Fazel's cardinality function. The nuclear norm is harder because rank is not preserved along nonconvex steps in the same way, and we leave it as a stretch goal.

The algorithmic part is the certificate. After each stage the method records the iterate's support size. It also records the restricted curvature quotient $\langle\nabla\mathcal{L}_n(\theta_{t+1})-\nabla\mathcal{L}_n(\theta_t),\theta_{t+1}-\theta_t\rangle/\|\theta_{t+1}-\theta_t\|_2^2$, which is only meaningful because the differences are sparse. Both numbers come free from quantities the solver already computes. If support exceeds a budget, or the quotient drops below a fraction of its running estimate, the method rewinds to the previous warm start and sets $\eta\leftarrow\sqrt{\eta}$, which shrinks $\lambda$ more gently. This addresses the tuning sensitivity of continuation schedules noted in the file. It also makes the theory's unknown constants unnecessary in practice, and the proof covers the adaptive version because each accepted stage satisfies the lemma's hypotheses by construction. As an extension, we will add momentum in the form that keeps the extrapolated point inside the sparse set, following Maros and Scutari. We test whether that recovers a $\sqrt{\kappa_s}$ dependence without breaking the support budget.

Baselines

The naive reference point is proximal gradient run directly at $\lambda_{\text{target}}$ from zero, with the same step size and the same gradient-evaluation budget. For noisy-feature regression we expect it to diverge on a measurable fraction of seeds, because the objective is unbounded below. For robust losses we expect it to stall. Reporting the divergence rate is itself a result.

The strongest existing competitor for the nonconvex setting is side-constrained proximal gradient. This adds the constraint $\|\theta\|_1\le R$, which makes the objective bounded and is the standard practical fix. We run it at an oracle $R=\|\theta^*\|_1$ and at $R$ misspecified by factors of 0.5 and 2. We also give it a cross-validation tuning budget equal in gradient evaluations to our homotopy's total cost. It is strongest because, with the right $R$, it already converges linearly under the same curvature condition. Our method beats it if it matches oracle-$R$ accuracy and speed while clearly outperforming tuned $R$ at equal total compute. No reported result was found on Lacuna for this baseline on these benchmarks.

For noisy-feature regression, the convexified competitor projects the corrected covariance onto the positive semidefinite cone and then runs the convex homotopy method of Eghbali and Fazel. Their paper reports that homotopy reached an objective gap of $10^{-10}$ significantly faster than standard proximal gradient and accelerated proximal gradient on convex matrix and group recovery. That is the strongest reported number on nearby problems. No reported result was found on Lacuna for it on nonconvex corrected regression.

The key ablation removes the certificate and runs a fixed-$\eta$ homotopy across a grid of $\eta$ values. We report both the best $\eta$ picked afterwards and the median $\eta$. This isolates whether the adaptive safety check matters or whether plain continuation is enough.

A ridge-regularized variant, with $\epsilon$ chosen by cross-validation, completes the comparison.

All methods share data splits, a gradient-evaluation budget, and wall-clock measurement on the same hardware.

Why not just…?

Why not just add a ridge penalty to restore global convexity? For noisy-feature regression, a ridge term large enough to cancel the negative curvature of the corrected covariance must be about as large as the noise variance. That biases the estimate at order $\epsilon\|\theta^*\|_2$ and keeps correlated groups instead of true supports. The file's evidence from Uncorrelated Lasso is that Elastic Net reached about 91% on Leukemia while ULasso reached 100% with 22 genes. A small ridge term, by contrast, gives a huge condition number. The ridge baseline will show this bias-versus-speed tradeoff directly.

Why not just add the $\ell_1$-ball side constraint? This is the real threat. The certificate's value depends on the claim that tuning $R$ costs more than homotopy saves, and that misspecified $R$ hurts either accuracy (too small) or speed (too large). If oracle-free cross-validated $R$ matches our method at equal compute, we will report that the contribution is mainly theoretical: a constraint-free guarantee rather than a practical speedup.

Why not just convexify the corrected covariance? This is only possible for quadratic losses, and it changes the estimator. For Tukey-loss robust regression and for joint estimation of coefficients and noise variance, no such projection exists. That is why those two problems are the primary testbeds, with convexification compared only on corrected regression.

Proposed Experiments

The synthetic suite follows Liu's two worked examples plus a robust case. The first is corrected regression with additive feature noise and with missing entries. The second is Lasso with unknown noise variance, estimated jointly. The third is Tukey-biweight regression with heavy-tailed noise. All three use the $1000\times5000$ correlated design from the adaptive accelerated homotopy paper, with column correlation swept to raise $\kappa_s$, and with $s$ and feature-noise level also swept.

For real data we take eyedata ($n\approx200$, $d\approx20{,}000$). We inject controlled feature noise at known variance and generate responses from a planted sparse vector, so estimation error remains measurable. We also run robust sparse regression on the Colon Cancer and Leukemia expression sets with label corruption, reporting held-out accuracy and selected-gene counts. The group extension uses Eghbali and Fazel's $50\times1000$ group-sparsity benchmark with noisy features.

Metrics are $\ell_2$ estimation error against $\theta^*$, support F1 score, gradient evaluations and time to reach within 10% of the final statistical error, divergence frequency across 50 seeds, the maximum support size seen along the path, and the number of certificate-triggered rewinds.

Three checks decide the outcome. First, the maximum support along our path should stay near $s$ while the naive method's support grows and its objective falls without bound. That confirms the mechanism, not just the result. Second, as the tolerance ratio $\tau\tilde s\log d/n$ is pushed toward 1 by shrinking $n$, the certificate should fire more often and fixed-$\eta$ homotopy should begin to fail. That shows the check tracks the theory's condition. Third, gradient evaluations to statistical precision should scale roughly linearly in $\kappa_s$ for the unaccelerated method, and should flatten toward $\sqrt{\kappa_s}$ for the in-set momentum variant without support blow-up. If the side-constrained baseline with cross-validated $R$ matches us everywhere, or if the certificate never fires in practice, we will report that plainly.