Certified Sketched Newton Steps Without Strong Convexity

Newton-type methods reach high-precision solutions of problems like sparse logistic regression in far fewer iterations than gradient methods. Each iteration, however, requires approximately solving a large linear or quadratic subproblem. Randomized "sketching" solvers make that subproblem cheap. A sketching solver works on small random compressions of the matrix instead of the whole thing. The price is that its answer is only probably good enough. The theory that makes Newton methods converge fast without strong convexity (a uniform bowl-shaped lower bound on the loss, which fails whenever features outnumber samples) has only been worked out for deterministic subproblem solvers. The theory for sketched Newton solvers assumes strong convexity. This proposal joins the two, and shows that the join costs almost nothing in guarantees.

The idea rests on one observation. Checking a matrix product exactly is as hard as computing it. Checking whether a Newton subproblem has been solved well enough is cheap: it takes one multiplication of a vector by the Hessian (the matrix of second derivatives) and one soft-thresholding step. We can therefore run a randomized inner solver until a computable certificate passes. This turns a Monte Carlo solver, which is correct with high probability, into a Las Vegas one, which is always correct when it stops and only has a random running time. The fast-convergence proof for error-bound problems then applies to every run, not merely with high probability. The research questions are how much inner work this costs in expectation as the problem becomes nearly singular near the solution, and whether the resulting method beats well-tuned deterministic and GPU baselines in wall-clock time.

Core Claim

The Inexact Regularized Proximal Newton method (IRPN) supplies the outer method. It targets composite problems $F(x)=f(x)+g(x)$, such as ℓ1-regularized logistic regression. It replaces strong convexity with the Luo-Tseng error bound, a condition that the distance to the solution set is controlled by a computable optimality residual. It uses a regularized Hessian $H_k=\nabla^2 f(x^k)+\mu_k I$, where $\mu_k$ shrinks with the residual, and obtains linear, superlinear or quadratic local rates depending on a parameter $\rho\in[0,1]$. Its analysis needs only that each inner solution $y$ satisfy an inequality. We state that inequality here in IRPN's style:

$$\|R_k(y)\| \le \eta\,\|R(x^k)\|^{1+\rho}.$$

The symbols are as follows. $R(x)=x-\mathrm{prox}_g(x-\nabla f(x))$ is the proximal-gradient residual of the true problem at $x$. $R_k(y)=y-\mathrm{prox}_g\big(y-\nabla f(x^k)-H_k(y-x^k)\big)$ is the same residual for the local quadratic model at step $k$. $\eta<1$ is a fixed constant.

Evaluating $R_k(y)$ costs one Hessian-vector product, $O(\mathrm{nnz}(A))$ for data matrix $A$, plus a soft-threshold. Our claim has three parts. First, any randomized inner solver gated by this test inherits IRPN's global convergence and local rates deterministically. Second, under the error bound, the expected inner work per outer step stays bounded as $\mu_k\to 0$, with an exponentially decaying tail, so the Las Vegas running time is predictable. Third, on problems with more features than samples and a flat spectral tail, a block-sketched inner solver built from dense GEMM calls (standard dense matrix multiplications) finishes faster in wall-clock time than conjugate-gradient or coordinate-descent inner solvers.

Why this, and how it differs from existing work

Two lines of prior work motivate the proposal, and each lacks exactly what the other provides. IRPN proves superlinear rates without strong convexity, but its inner solver is deterministic coordinate descent. NASketch computes streaming Newton directions with a momentum-accelerated sketch-and-project solver. It needs as few as 5 inner steps, where unaccelerated sketching needs 10 or more. Its proofs require global strong convexity and Lipschitz smoothness, and it runs a fixed number of unverified inner steps. We borrow its accelerated sketching as a candidate inner solver, but we replace the fixed step count with a certificate, and we drop the strong convexity assumption.

A third paper is the analogue on the first-order side. Randomized feasible descent under weak strong convexity shows that randomized coordinate methods converge linearly in expectation even with singular kernel matrices. It covers first-order steps only and gives guarantees only in expectation.

The case for certification, rather than a small failure probability, comes from two sources. Inexact subproblem optimization requires summable inner errors for convergence. A solver that fails independently with fixed probability per step eventually produces a large error over a long run. The graph-algorithms literature supplies the template of converting Monte Carlo methods to Las Vegas ones by maintaining a checkable certificate, as Reliable Hubs does for dynamic shortest paths.

That literature also warns about the verification bottleneck. Certifying algebraic outputs, such as the batch-update oracles in Sensitive Distance and Reachability Oracles, is as hard as computing them. Our point is that Newton subproblems escape this barrier, because the quantity we need to certify is a residual, not a product. Fast Matrix Multiplication with Sketching shows the alternative's cost. Its sample count grows as $1/\delta$, so driving the failure probability $\delta$ down without verification inflates the work.

The fast-matrix-multiplication direction sets a constraint, not a mechanism. Alman and Yu cut the leading constant of fast matrix multiplication to $n^{o(1)}$ yet concede it is not competitive at practical sizes. The ERM-in-matrix-multiplication-time solver reaches roughly $O(n^{2.38})$ by combining a robust central path with sketching, but is slower than cubic methods at every realistic size and has no verification. We therefore take only the lesson of Derezinski and Yang. They avoid building an explicit preconditioner (a transformation that makes the system easier to solve) and instead sample blocks well, reaching $\tilde O(n^2 + nk^{\omega-1})$ time, where $k$ is the number of singular values above a flat tail. We realize the $k^{\omega-1}$ term with ordinary GPU matrix multiplication, not galactic algorithms. Measuring where the crossover falls is part of the contribution.

Research Program

On the algorithm side, the inner solver handles the ℓ1-regularized quadratic model with randomized block proximal coordinate descent. Blocks of size $b$ are sampled by approximate leverage scores, and each block update is a dense $b\times b$ solve plus GEMMs. In the regime where features outnumber samples, the Hessian has the form $A^\top D A+\mu_k I$ with $A$ of rank at most $m$, the number of samples. We will also test a variant that sketches in the $m$-dimensional sample space through the Woodbury identity, which is exact on the current support set.

The solver is warm-started across outer steps. It evaluates the certificate every $c$ block steps, so verification overhead is a tunable fraction of inner work, and we will report that fraction. If the certificate fails after a budget, the solver doubles its sketch size and continues. It never returns an unverified direction.

On the analysis side, the deterministic outer rates follow directly from IRPN once the certificate holds. The open theoretical question is the expected inner cost. As $\mu_k\to 0$, the regularized Hessian becomes ill-conditioned in the directions it does not constrain. The sketch solver's linear rate depends on conditioning restricted to the relevant subspace, which is the range of the Hessian on the active support. We aim to show that the error bound controls this restricted conditioning, so that expected block steps per outer iteration are $O\big(\kappa_{\mathrm{eff}}\log(1/\|R(x^k)\|)\big)$ with a geometric tail. The logarithm reflects the linear convergence of the inner solver towards a tolerance polynomial in the residual.

If the bound fails, we will characterize the counterexample. A plausible one is an unstable support set. That would be a meaningful negative result for sketched Newton methods without strong convexity.

Baselines

The naive reference is FISTA, the accelerated proximal gradient method, as a do-nothing first-order option. It has no linear algebra overhead.

The strongest existing method on this exact question is IRPN with its deterministic inner solver, together with newGLMNET, which IRPN reports as matching or trailing it. IRPN reports that it "significantly outperformed" FISTA and SpaRSA in CPU time and iterations on colon-cancer, rcv1 and news20, and was "competitive or superior" to newGLMNET. No numeric runtime for these runs was found on Lacuna. We will therefore reproduce IRPN ourselves and treat our reproduction as the reference number.

We add IRPN with preconditioned conjugate gradient restricted to the support as a second deterministic inner solver. All methods share the same data, the same objective (ℓ1-regularized logistic regression, with regularization chosen to give fixed sparsity levels), the same hardware (one GPU plus the host CPU, with GPU-native implementations of FISTA and CG so that hardware is not the confound), and an equal tuning budget of 20 configurations each.

Beating these baselines means reaching relative objective gap $10^{-8}$ at least $1.5\times$ faster in wall-clock time than the best deterministic IRPN variant on two or more datasets, with zero uncertified directions.

Three ablations isolate the key ingredients. The first is NASketch-style fixed-step sketching: 5 inner steps with no certificate, and no $\mu_k$ adaptation beyond IRPN's. It isolates what the certificate adds. The second is an unregularized sketched Newton method with $\mu_k=0$. It isolates what the error-bound regularization contributes on singular problems. The third varies block size $b$ with the solver otherwise fixed, to locate the GEMM crossover.

For context in the dense setting, we will report a GPU exact solver in the style of ThunderSVM. ThunderSVM reports being over 100× faster than LibSVM on GPU, though for SVM training, not ℓ1 logistic regression.

Why not just…?

Why not just use IRPN with conjugate gradient, which is already deterministic and certified? This is the most serious threat. Conjugate gradient needs no sketching and has a residual stopping rule built in. On very sparse problems like news20, it may well win, because Hessian-vector products are cheap and the effective dimension is small. The case for sketching is the dense or flat-tailed regime. There, Derezinski and Yang show that sampling blocks well beats conjugate gradient by roughly a factor of $k$ in theory. The experiment on epsilon and on synthetic flat-tail spectra settles whether this holds in practice. If conjugate gradient wins everywhere, we will report that the certificate is the transferable contribution and sketching is not.

Why not just sketch with a tiny failure probability and skip verification? Over a fixed run of a few dozen outer steps, a failure probability of $10^{-6}$ is harmless. The real benefit of the certificate is adaptive stopping. Fixed-step sketching must be tuned for the worst outer iteration, while the certificate spends inner work only when conditioning demands it. The fixed-5-step ablation measures exactly this trade-off. If it matches our method in time with no failures observed, the Las Vegas guarantee is merely insurance, and we will say so.

Why not just run FISTA or coordinate descent, which already converge without strong convexity? Linear convergence is known for randomized coordinate methods under weak strong convexity, and they have no matrix overhead. IRPN's experiments on the same benchmarks nonetheless show first-order methods trailing at high precision. Our FISTA baseline checks whether that gap survives GPU implementation.

Why not use fast matrix multiplication directly? Alman and Yu, and the ERM solver's own authors, state that it is uncompetitive at realistic sizes. We use only GEMM-shaped blocks.

Proposed Experiments

The benchmarks are the LIBSVM datasets used by IRPN and COMRADE. They cover the regime where features outnumber samples and the Hessian is singular (colon-cancer with 2,000 features and 62 samples, rcv1 with 47,236 features and 20,242 samples, news20 with 1,355,191 features and 19,996 samples) and a dense case (epsilon with 2,000 features and 0.4M samples). We add synthetic ℓ1-logistic problems whose data spectra have a controlled flat tail, with $k$ swept from $n^{0.5}$ to $n$.

Metrics are wall-clock time and outer iterations to gap $10^{-8}$, inner block steps per outer step, certificate overhead as a share of time, the count of certificate failures resolved by extra inner work, and the empirical tail of the Las Vegas inner running time.

Three checks decide the proposal. First, inner steps per outer iteration should stay bounded as $\|R(x^k)\|\to 0$ on rcv1 and colon-cancer. Unbounded growth would falsify the expected-work claim. Second, on flat-tail synthetics, the speedup over conjugate gradient should grow with $n/k$ as the Derezinski-Yang bound predicts, and it should vanish when the tail is steep. Third, the uncertified fixed-step ablation should either stall or require more total inner work on the most ill-conditioned datasets. If it does neither, the certificate's practical value is limited to worst-case insurance.