RSN: Randomized Subspace Newton
RSN solves Newton systems in random subspaces and usually outpaces GD, AGD, and full Newton across six datasets.
Key Findings
Methodology
At iteration k, RSN samples S, forms the compressed Hessian SᵀH(x)S, and updates x⁺=x−(1/L̂)S(SᵀHS)†Sᵀg. This is simultaneously the exact minimizer of the relative-smoothness quadratic model over x+Range(S) and a Hessian-seminorm projection of the full Newton direction.
Key Results
- Under relative smoothness and relative convexity, E[f(xk)]−f*≤(1−ρμ̂/L̂)^k(f(x0)−f*), with ρ∈[0,1] measuring sketch coverage. Full Newton is recovered by S=I and ρ=1.
- Experiments used chemotherapy, gisette, news20, rcv1, real-sim, and webspam, with block-coordinate sketch sizes s=250, 500, 750, and 1000. RSN was generally fastest; on extremely sparse news20, AGD was about 20 seconds faster.
- With single-column sketches, s=1, each iteration needs only three scalar derivatives along one direction. If function evaluation is constant-cost, the per-iteration cost can be O(1), illustrating extreme scalability.
Significance
RSN addresses the memory and linear-system bottleneck that prevents classical Newton methods from serving extremely high-dimensional learning problems. It retains curvature adaptation and scale invariance, while replacing one massive solve with many small solves. The flexible sketch distribution also enables application-specific designs for medical imaging, genomics, and seismology.
Technical Contribution
The paper applies sketching directly to the current Hessian and solves an exact Newton model inside the sketched subspace. It introduces the nullspace-preserving condition, the expected projection operator, and the sketch condition parameter ρ, yielding global linear convergence for broad sketch families. When μ̂=0, it still proves an O(L̂R²/(ρk)) sublinear rate, with pseudoinverse support and compatible line search.
Novelty
Unlike Sketched Newton, whose sketch dimension may approach d, or SDNA, which assumes a global matrix upper-bounding the Hessian, RSN compresses the current Hessian itself under weaker relative assumptions. Its fundamental innovation is the unified interpretation of randomized subspace Newton steps as model minimization, Hessian projection, and constrained Newton-system projection.
Limitations
- The theory assumes convexity, twice differentiability, g(x)∈Range(H(x)), and nullspace-preserving sketches. It therefore does not establish guarantees for general nonconvex objectives or badly mismatched sketch distributions.
- Experiments cover logistic regression, block-coordinate sketches, and six datasets only. They do not systematically quantify Gaussian, Hadamard, Fourier, adaptive, or subsampled variants, nor do they report a universal speedup percentage.
Future Work
The authors propose combining RSN with data subsampling for problems that are both high-dimensional and data-abundant, exploiting fast Johnson–Lindenstrauss transforms, and constructing quasi-Newton-inspired sketches from previous descent directions. Adaptive sketch selection, preconditioning, and parallel implementations are natural extensions.
AI Executive Summary
Classical Newton optimization is attractive because it adapts to curvature and is invariant to rescaling, but its appeal collapses in huge feature spaces: forming and solving a generic Hessian system can cost O(d³), while even Krylov-based inexact Newton iterations may cost O(d²). Accelerated gradient descent avoids these systems, yet repeated full-gradient evaluations can dominate on dense data. Randomized Subspace Newton (RSN) offers a deliberately incomplete alternative: each iteration performs an exact Newton calculation in a small random subspace.
Given a sketch S, RSN computes SᵀHS and Sᵀg, then applies x⁺=x−(1/L̂)S(SᵀHS)†Sᵀg. The step minimizes the relative-smoothness quadratic model over the sketched subspace and equals a Hessian-seminorm projection of the full Newton direction. A parameter ρ, derived from an expected projection matrix, measures whether the sketches collectively cover useful curvature. The resulting global rate is (1−ρμ̂/L̂)^k; full Newton is the special case ρ=1.
On six LIBSVM/OpenML datasets, RSN with s=250–1000 was generally the fastest method among RSN, GD, AGD, and full Newton. The exception was extremely sparse news20, where AGD beat RSN with s=750 by roughly 20 seconds. The paper’s broader contribution is a tunable, scale-invariant second-order framework: practitioners trade sketch cost against curvature coverage rather than choosing between impractical full Newton and potentially slow first-order optimization.
Deep Analysis
Background
Newton methods offer affine and scale robustness, but full Hessian systems become prohibitive as d grows; inexact Newton methods still face O(d²)-type iterations. AGD is cheaper in memory but requires tuning and repeated gradient passes. Prior sketched or randomized second-order methods include Sketched Newton, SDNA, RBCN, and SON, yet they impose restrictive sketch-size, matrix-majorization, block-separability, or online-learning assumptions.
Core Problem
The objective is minx∈Rᵈ f(x) for a convex, twice-differentiable function with enormous feature dimension. The challenge is to exploit second-order information without forming or solving a d×d system, while preserving descent and obtaining a global convergence guarantee despite random, possibly singular, subspaces.
Innovation
RSN places randomness in the search subspace rather than replacing the Hessian with a noisy approximation. It solves the compressed system SᵀHS for arbitrary useful sketches, including s=1. The nullspace-preserving condition controls degeneracy, while ρ(x) equals the smallest positive eigenvalue of an expected projection under an exactness condition. This unifies algorithmic flexibility and convergence analysis.
Methodology
- �� Sample a fresh Sk∼D at xk.
- �� Evaluate gk and the compressed Hessian SkᵀHkSk.
- �� Compute λk=−(1/L̂)(SkᵀHkSk)†Skᵀgk and set xk+1=xk+Skλk.
- �� Interpret the step as minimizing T(x,xk) over xk+Range(Sk), or projecting the full Newton step in the Hk seminorm.
- �� Define G(x)=E[S(SᵀHS)†Sᵀ] and ρ to obtain E[f(xk)]−f*≤(1−ρμ̂/L̂)^kΔ0.
- �� For GLMs, H=(1/n)AΦ''Aᵀ+λI, enabling fast Johnson–Lindenstrauss sketches without full backpropagation.
Experiments
The study uses logistic regression, φi(t)=log(1+e^(−yit)), λ=10⁻¹⁰, and a stopping tolerance of ||∇f||<10⁻⁶. RSN is compared with GD, Nesterov AGD, and full Newton using exact Lipschitz constants and the same line search. Datasets span d=5,001 to 1,355,192 and n=158 to 350,000; RSN uses block-coordinate sketches with s=250–1000.
Results
RSN generally gives the best wall-clock and iteration performance on chemotherapy, gisette, rcv1, real-sim, and webspam, particularly for dense or moderately sparse data. Full Newton remains competitive on gisette when its linear algebra is affordable, but is infeasible at massive d. On news20, density 0.0003, AGD outran RSN with s=750 by approximately 20 seconds, revealing that extreme sparsity can favor first-order passes.
Applications
The method targets logistic and other generalized linear models in genomics, medical imaging, seismology, text classification, and sensor analytics. Users can select s according to memory and latency budgets and choose Gaussian, coordinate, subsampled Hadamard/Fourier, or fast JL sketches. Practical deployment requires convex objectives and efficient compressed-Hessian computation.
Limitations & Outlook
Guarantees rely on convexity, relative smoothness and convexity, the Hessian range condition, and sketch exactness. The experiments do not cover nonconvex neural networks, adaptive sketches, or simultaneous data subsampling. Larger s improves ρ but increases compressed-solve cost; sparse news20 shows that AGD can win. Future work should develop automatic sketch selection, preconditioning, parallelism, and joint sample-feature scaling.
Plain Language Accessible to non-experts
Imagine repairing an enormous factory. Full Newton optimization inspects every machine and every connection between machines before deciding on the best complete renovation. The plan can be extremely intelligent, but the inspection itself may require more time and storage than the factory can provide. Gradient methods are cheaper: they look at the overall noise and make a small adjustment, but may need many rounds.
RSN chooses a small group of machines at random. It carefully measures how those machines affect one another, calculates the best repair for that group, and then moves to another group next round. Each local plan is cheap, but the groups collectively cover the factory. The method also adjusts the size of its repair to the local stiffness: difficult, sensitive machinery receives a more informed change.
The group size is a practical dial. Small groups make rounds inexpensive; large groups capture more relationships but cost more. On six real datasets, this compromise was usually faster than AGD and far more practical than inspecting everything. Yet the result is not universal: on extremely sparse news20, AGD was roughly 20 seconds faster than RSN with s=750. The lesson is to match the sampling pattern to the factory’s structure.
ELI14 Explained like you're 14
Picture a giant video game city with millions of buildings. Full Newton is like pausing the game and checking every building and every road to find the perfect upgrade plan. Sounds awesome, right? But the game may freeze before the answer arrives. Gradient descent is like checking the city’s total score and upgrading based on that; it is simple, but can take many turns.
RSN picks one neighborhood at random. It studies which buildings matter most there, notices how crowded the roads are, and chooses a smart upgrade for that neighborhood. Next turn it picks another one. Because each neighborhood is small, the calculation is manageable. After enough turns, the whole city gets attention. The parameter s is the neighborhood size: 250, 500, 750, or 1000 in the experiments.
The researchers tested RSN on six real datasets and compared it with GD, AGD, and full Newton. RSN was usually fastest, except on super-sparse news20, where AGD was about 20 seconds faster. Even cooler: with s=1, RSN can move in just one direction per turn and may need only constant work if evaluating the function is constant-cost!
Is it magic? Not quite! It mainly comes with guarantees for well-behaved convex problems, and the random neighborhoods must collectively cover important directions. Future versions could choose neighborhoods intelligently and handle huge numbers of examples too.
Glossary
Randomized Subspace Newton
A Newton method that computes an exact model step only within a randomly selected low-dimensional subspace. It reduces the linear algebra dimension from d to the sketch size s.
The central algorithm proposed in the paper.
Sketching matrix
A matrix S that selects, embeds, or mixes directions into a smaller computational space. Its distribution controls both cost and expected curvature coverage.
A fresh S is sampled at every RSN iteration.
Relative smoothness
A curvature-aware upper bound using the Hessian metric at the reference point, with constant L̂. It generalizes ordinary Lipschitz-gradient assumptions.
It establishes the quadratic upper model and descent.
Sketch condition parameter ρ
A number between zero and one measuring how well the random subspaces cover effective Hessian directions. Larger ρ gives a better theoretical rate.
It appears in the global convergence theorem.
Nullspace preserving
The requirement Null(SᵀH(x)S)=Null(S), preventing the compressed system from inventing inappropriate degeneracy. It enables correct use of the Moore–Penrose pseudoinverse.
This is Assumption 3.
Open Questions Unanswered questions from this research
- 1 How can a system automatically choose sketch type and size to optimize the trade-off among ρ, sparsity, memory, and solve time? The paper supplies sufficient conditions but no universal adaptive policy.
- 2 Can RSN retain predictable convergence when both feature dimension and sample count are enormous and the Hessian is estimated from subsamples? Joint stochastic-error and sketch-error theory remains open.
Applications
Immediate Applications
High-dimensional logistic regression
Genomics, text classification, and medical-feature pipelines can replace full Newton with RSN, selecting s=250–1000 under a memory budget. Sparse matrix operations and compressed Hessians are prerequisites; the expected outcome is lower linear-system cost with curvature-aware updates.
Medical imaging optimization
Large image-derived feature vectors can use coordinate or fast JL sketches to retain useful curvature while avoiding a full Hessian. Convex losses, reliable gradients, and efficient evaluation of SᵀHS are required for practical deployment.
Long-term Vision
Second-order learning at both data scales
Combining RSN with minibatch subsampling, parallel sketches, GPUs, and communication-efficient solvers could support models with both massive feature spaces and massive datasets. The main obstacles are stochastic stability, adaptive sampling, and a unified complexity theory.
Abstract
We develop a randomized Newton method capable of solving learning problems with huge dimensional feature spaces, which is a common setting in applications such as medical imaging, genomics and seismology. Our method leverages randomized sketching in a new way, by finding the Newton direction constrained to the space spanned by a random sketch. We develop a simple global linear convergence theory that holds for practically all sketching techniques, which gives the practitioners the freedom to design custom sketching approaches suitable for particular applications. We perform numerical experiments which demonstrate the efficiency of our method as compared to accelerated gradient descent and the full Newton method. Our method can be seen as a refinement and randomized extension of the results of Karimireddy, Stich, and Jaggi (2019).