Feedback-Tuned Regularization for Nonconvex Generalized Newton Methods

Newton's method converges very fast near a solution because it models the objective with its curvature (the Hessian). Many machine-learning objectives, however, have kinks: sparse regression with an $\ell_0$ penalty, robust regression, image restoration with nonsmooth regularizers. For these problems a recent line of "generalized Newton" methods replaces the Hessian with a curvature operator from variational analysis. That operator, the coderivative of the subgradient map, captures how the slope changes across kinks. These methods converge from any starting point and can be orders of magnitude faster than first-order solvers. Their weak point is practical rather than theoretical. When the generalized curvature is singular or indefinite, the Newton system needs a regularizing shift, and the authors of the nonconvex method state plainly that its proximal parameters must be retuned for each application. A method that is fast only after hand-tuning is hard to use as a default solver.

We propose to make that shift self-correcting and to measure the result with a pre-registered sensitivity study. The shift is the product of two quantities. The first is a residual factor, which shrinks to zero near a solution and so preserves fast local convergence. The second is a multiplier that rises when the Newton model mispredicts the actual decrease and falls when the model is accurate. In plain terms, the residual factor tells the method how close it is to the answer, and the agreement feedback tells it how much to trust its own curvature right now. The claim is concrete. With this rule, coderivative Newton methods on nonconvex, prox-regular problems keep their guarantees of global convergence to stationary points and local superlinear convergence. In addition, their runtime varies far less across the rule's own meta-parameters than the fixed-schedule rules they replace.

What exists and where the gap is

The mechanism we build on comes from convex proximal Newton methods. A globally convergent proximal Newton-type method in nonsmooth convex optimization regularizes the Hessian as $B_k + \alpha_k I$ with $\alpha_k = c\|R(x_k)\|^p$. Here $R$ is the prox-gradient residual, the distance the iterate would move under one proximal gradient step. The authors prove global convergence without strong convexity, and superlinear or quadratic local rates under metric subregularity. That paper motivates our design, and it also constrains it in two ways. Its analysis is convex only. More importantly, it reports that performance depends on $p$, with $p=0.1$ or $p=0.5$ working best on $\ell_1$-logistic regression, and it gives no rule for choosing $p$. In the nonconvex setting the problem gets worse. The pure residual rule cannot know how negative the local curvature is, so no single constant $c$ is both large enough far from the solution and small enough near it.

The nonsmooth Newton machinery comes from the coderivative line. Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization introduces a damped variant (GDNM) and a regularized variant (GRNM) for $C^{1,1}$ and convex composite problems. GRNM uses a shift $c_k I$ on a fixed schedule. Coderivative-Based Newton Methods in Structured Nonconvex and Nonsmooth Optimization extends the approach to prox-regular $g$ such as the $\ell_0$ norm (GCNM). It globalizes by running a line search on the forward-backward envelope, a smooth surrogate of the composite objective. It explicitly notes that its proximal parameters need application-specific tuning. We reuse this machinery unchanged and replace only the parameter logic.

The feedback signal comes from trust-region methods. A Trust-Region Method for Nonsmooth Nonconvex Optimization updates its radius from the ratio of actual to predicted decrease. It proves global convergence, and local quadratic convergence under strict complementarity. However, it covers only convex $g$, and it leaves its own update constants ($\eta, r_1, r_2, \Delta_{\max}$) fixed while naming adaptive selection as future work. We borrow the agreement ratio but use it to scale a regularizer rather than a radius. This keeps the Newton system in the simple linear form that coderivative methods exploit.

Finally, Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems warns that adaptive rules introduce "hyper-hyperparameters" whose sensitivity is rarely characterized. We treat that warning as the evaluation criterion rather than as a footnote.

Core Claim

Let $\Phi = f + g$, with $f$ smooth and possibly nonconvex and $g$ prox-regular. Let $\varphi_\gamma$ be its forward-backward envelope with step $\gamma$, and let $R_\gamma(x_k)$ be the prox-gradient residual. At iterate $x_k$ we solve the regularized coderivative Newton system with shift

$$\alpha_k = \mu_k \,\|R_\gamma(x_k)\|^{p}, \qquad \mu_k \in [\mu_{\min}, \mu_{\max}].$$

After a trial step $d_k$ we compute the agreement ratio

$$\rho_k = \frac{\varphi_\gamma(x_k) - \varphi_\gamma(x_k + d_k)}{m_k(0) - m_k(d_k)},$$

where $m_k$ is the regularized Newton model of $\varphi_\gamma$ at $x_k$. We then multiply $\mu_k$ by a factor above one if $\rho_k$ is small and by a factor below one if $\rho_k$ is close to one. The envelope step $\gamma$ is halved whenever the envelope's sufficient-decrease inequality fails. That backtracking is standard practice in envelope methods and is not claimed as new.

The new element is the coupling. Far from a solution, $\mu_k$ inflates just enough to counter indefinite curvature, a role a fixed $c$ cannot play. Near a tilt-stable minimizer the model becomes accurate, so $\rho_k \to 1$ and $\mu_k$ settles at $\mu_{\min}$. From then on $\alpha_k$ behaves like the residual rule, which is what makes superlinear rates provable.

We will prove two results. First, every accumulation point is stationary for $\Phi$ under prox-regularity and bounded level sets. Second, the method converges Q-superlinearly under the semismooth* and tilt-stability conditions used for GCNM. Along the way we will show that $\mu_k$ changes only finitely often near such a point. The expected sensitivity result is empirical: across a wide grid of $(\mu_{\min}, p)$ and update factors, runtime should vary much less than GCNM's runtime varies across its proximal parameters.

Research Program

The analytic work adapts the global-convergence argument for envelope line searches in GCNM. The main new lemma bounds how many consecutive $\mu$-inflations can occur before the step is accepted. This follows from $\alpha_k$ eventually dominating the most negative eigenvalue of the coderivative operator, which is bounded under prox-regularity. The local analysis combines the finite-switching argument with the superlinear proof of the convex residual rule. The difference from that proof is that it runs on the nonconvex envelope under tilt stability, not under metric subregularity of a convex subdifferential.

We will implement the method in the same code base as GRNM and GCNM so that only the parameter logic differs. We will release the sensitivity grid, the random seeds, and the tuning budgets alongside the code.

Baselines

The naive reference point is the proximal gradient method with a backtracking step. It needs almost no tuning and serves as the floor that any second-order method must clear in wall-clock time.

The strongest existing competitor on nonconvex problems is GCNM from Coderivative-Based Newton Methods in Structured Nonconvex and Nonsmooth Optimization. It is the only method in the file that handles $\ell_0$-type prox-regular penalties with global and superlinear guarantees. That paper reports solve times of 0.01 to 1.3 seconds on $\ell_0$-$\ell_2$ signal recovery, described as orders of magnitude faster than GSSN and ZeroFPR. We will run GCNM in two ways. In the first, its parameters are tuned per problem family by grid search, and we count the tuning budget against it. In the second, it uses the defaults of its paper. Our method gets the same data, the same linear-solver backend, and no per-family tuning.

On convex anchors, the strongest competitors are the residual rule of A globally convergent proximal Newton-type method in nonsmooth convex optimization with its reported best $p \in \{0.1, 0.5\}$, and GRNM and GDNM from Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization. The companion GDNM paper reports 22 iterations and 1.23 seconds on a $1024\times1024$ Lasso, against 190,461 iterations for FISTA and 35.71 seconds for ADMM. For colon-cancer, duke, and leukemia there is no reported result on Lacuna for iteration counts or times. That paper states only that it outperforms IRPN and PNOPT, so we will rerun it ourselves.

The key ablation isolates the feedback. It keeps everything identical but freezes $\mu_k \equiv c$, which amounts to porting the convex residual rule unchanged to the nonconvex setting. A second ablation drops the residual factor ($p=0$) and leaves a pure ratio-driven Levenberg–Marquardt-style shift.

Beating the baselines means three things. At default meta-parameters, our method must be within a factor of 1.5 of per-family-tuned GCNM in time to reach a target residual. Its worst-to-best runtime ratio across the meta-parameter grid must be at least three times smaller than GCNM's. And it must beat the frozen-$\mu$ ablation on the nonconvex problems.

Why not just…?

Why not just grid-search $c$ and $p$ offline for each problem family? For a single fixed family this may well be enough, which is why tuned GCNM is a baseline and its tuning cost is counted. The question is transfer. The residual-rule paper already found that the best $p$ differs by a factor of five on one convex task. We will tune on one data split or problem size and evaluate on another, for example tuning at $\ell_0$-$\ell_2$ with $n=1024$ and testing at larger sizes and different sparsity levels. If the tuned parameters transfer as well as our rule, the adaptive rule offers no benefit and we will report that.

Why not just use the nonsmooth trust-region method, which already adapts its radius? A Trust-Region Method for Nonsmooth Nonconvex Optimization assumes convex $g$, and its truncation safeguard is built for $\ell_1$ and group penalties. It therefore does not cover the $\ell_0$ and Student's-$t$ problems that are our main targets. Its own update constants are also static. Where it does apply, on nonconvex sigmoid-loss classification on Gisette and CINA with an $\ell_1$ penalty, we will run it as an additional baseline under the same sensitivity grid over its constants.

Why not just fall back to a proximal gradient step whenever Newton fails? This is the hybrid design of A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization, and it does guarantee global convergence. The drawback is that each fallback discards the curvature information. Frequent fallbacks in indefinite regions would give first-order behavior exactly where regularization could have kept a useful Newton direction. We will implement a deterministic fallback variant and log how often it falls back and its time to target. If its fallbacks are rare and its speed matches ours, the simpler design wins.

Why not just port the convex residual rule as is? This is the most serious threat, and it is the frozen-$\mu$ ablation. If a fixed $c$ works across the grid on $\ell_0$ problems, our feedback layer is unnecessary. We expect it to fail through repeated line-search backtracking or stalling in regions of negative curvature, and we will measure the backtracking count to check this.

Proposed Experiments

The nonconvex core consists of three problem sets from the GCNM paper: $\ell_0$-$\ell_2$ sparse signal recovery, Student's-$t$ regression with an $\ell_0$ penalty, and Cameraman deblurring. These are augmented with sigmoid-loss classification on CINA and Gisette. The convex anchors check that nothing is lost where theory already exists: synthetic Lasso from $1024\times256$ to $4096\times4096$, and $\ell_1$-logistic regression on colon-cancer, duke breast-cancer, leukemia, and rcv1.

We will report time and iterations to a residual of $10^{-8}$, and Dolan–Moré performance profiles. For each method we will also report a sensitivity profile: the distribution of time-to-target over a fixed grid of 36 meta-parameter settings. The grid is fixed before any results are seen.

Three checks will decide the question. The first is whether the worst-to-best runtime ratio shrinks relative to GCNM on the $\ell_0$ problems. The second is whether the frozen-$\mu$ ablation degrades there while matching our method on convex Lasso, which is the specific failure mode that motivates the design. The third is whether $\mu_k$ actually stops changing near solutions and the observed local rate is superlinear. This last check tests whether the finite-switching lemma holds in practice.