Source-linked AI summary
Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
Mert Pilanci, Martin J. Wainwright
TL;DR
The paper addresses the cost of Newton’s method, whose Hessian computation and linear-system solves are difficult for large-scale optimization. It introduces Newton Sketch, a randomized Hessian approximation, and proves fast convergence with reduced complexity under stated assumptions. The method extends to constrained problems and several optimization applications, while its analyses remain bounded by local or sketch-family assumptions.
Problem
Newton’s method has strong convergence but its Hessian formation and linear-system solves create substantial computational challenges for large data dimensions.
Method
Newton Sketch replaces explicit Hessian computation with randomized projections or sub-sampling and combines the resulting updates with barrier methods for convex constraints.
Results
For self-concordant functions, Newton Sketch achieves linear-quadratic convergence with condition-independent guarantees and can reach O(nd log d log(1/δ)) total complexity when n ≥ d^2.
Takeaways & Limitations
Randomized Hadamard-based sketches can make second-order optimization substantially cheaper than classical Newton updates while retaining applications to constrained optimization.
Takeaways & Limitations
The convergence theory is local and depends on curvature and Hessian-Lipschitz constants that are seldom known in practice; the analysis also focuses on sub-Gaussian and randomized orthogonal-system sketches.
Abstract
from arXiv · showhide
We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, with convergence and complexity guarantees that are independent of condition numbers and related problem-dependent quantities. Given a suitable initialization, similar guarantees also hold for strongly convex and smooth objectives without self-concordance. When implemented using randomized projections based on a sub-sampled Hadamard basis, the algorithm typically has substantially lower complexity than Newton's method. We also describe extensions of our methods to programs involving convex constraints that are equipped with self-concordant barriers. We discuss and illustrate applications to linear programs, quadratic programs with convex constraints, logistic regression and other generalized linear models, as well as semidefinite programs.
1 Introduction
The paper motivates Newton Sketch as a randomized approximation that preserves second-order convergence while reducing the cost of Hessian-based updates. It develops complexity and convergence guarantees for unconstrained and constrained optimization.
- Motivation: Newton’s method offers faster convergence than first-order methods but requires expensive Hessian formation and linear-system solves.For data-matrix objectives, each Newton step can scale as O(nd^2), creating challenges at large n and d.
- Method: The Newton Sketch approximates the Hessian through a random projection instead of explicitly computing it.The paper analyzes fully and partially sketched variants using random projections and sub-sampling strategies.
- Complexity: With randomized Hadamard projections and m ≍ d, each iteration has complexity O(nd log d) when n ≥ d^2.This is linear in the input size nd and substantially below the O(nd^2) cost of a classical Newton step.
- Guarantees: For self-concordant functions, the method has linear-quadratic convergence with guarantees independent of function and data condition numbers.The analysis is affine invariant and also extends to convex constraints through barrier methods.
- Applications: The paper applies Newton Sketch methods to linear programs, constrained optimization, generalized linear models, and semidefinite programs.The paper also describes illustrative examples and extensions combining sketching with self-concordant barriers.
2 Background
The background reviews classical Newton convergence, randomized sketch constructions, and Gaussian width as a complexity measure for analyzing sketched updates. It emphasizes both computational trade-offs among sketch types and smaller widths for structured constrained problems.
- Classical Newton method: Newton’s method requires solving Hessian-defined linear systems, motivating randomized approximations for large-scale problems.The background contrasts the convergence benefits of Newton’s method with its computational burden.
- Classical Newton method: Classical Newton updates converge quadratically under suitable local regularity and initialization conditions.The assumptions include a twice-differentiable convex objective, Lipschitz Hessian, and an initial point sufficiently close to the minimizer.
- Randomized sketches: Sketch matrices are zero-mean and isotropically normalized, with options including row sampling, sub-Gaussian matrices, and randomized orthonormal systems.Row sampling may use probabilities based on row norms or leverage values.
- Randomized sketches: Sub-Gaussian sketches provide concentration properties but generally require O(mnd) operations to form SA with an unstructured random matrix.This creates a computational disadvantage relative to structured randomized orthonormal systems.
- Randomized sketches: Randomized orthonormal systems, including Hadamard and Fourier bases, enable faster matrix multiplication through structured transforms.For a fast matrix-vector multiplication routine, forming SM can take O(nd log m) time.
- Gaussian widths: Gaussian width measures the size of compact sets and can be substantially smaller for constrained cones than its worst-case dimension-based bound.For a subspace of dimension r < d, the width of its intersection with the sphere is at most √r.
3 Newton sketch and local convergence
The Newton Sketch replaces the Hessian in constrained Newton updates with a randomized projection, yielding cheaper iterations while retaining convergence guarantees. Its local behavior ranges from linear-quadratic convergence to linear convergence, with sketch dimensions governed by Gaussian width and potentially much smaller than the ambient dimension.
- Algorithm: The Newton Sketch solves convex optimization over a constraint set by replacing the exact Hessian in a constrained second-order Taylor minimization with a randomized sketch.The method applies to twice-differentiable convex objectives and supports fully or partially sketched Hessian updates.
- Computational complexity: For unconstrained updates, the sketched Newton step costs at most O(md2), compared with O(nd2) for standard Newton, and constrained problems can use m ≪d.Randomized Hadamard implementations additionally compute the sketched Hessian square root in O(nd log(m)) operations.
- Examples: For a two-dimensional linear program, all sketched trials converged to the optimum, while increasing m made the sketched central path approach the standard central path.The comparison used m ∈{d, 4d, 16d}.
- Sketch dimension: The sketch dimension is controlled by a Gaussian-width lower bound and can be substantially smaller for constrained problems than the worst-case min{n, d} scale.The tolerance ϵ and a universal constant enter the lower bound, while the constrained geometry determines the potentially smaller Gaussian width.
- Local convergence: Given a suitable initialization and sketch accuracy, the local error obeys a recursion that yields linear-quadratic convergence with exponentially high probability.With fixed tolerance, the convergence transitions between a quadratic regime for larger errors and a linear regime near the optimum.
- Examples: In portfolio optimization experiments, m = ⌈4s log d⌉ with m ≪min{d, n} was sufficient for linear convergence across six problem sizes.Here s bounds the number of nonzeros in the optimal solution, and the chosen sketch dimension satisfies the required lower bound.
4 Newton sketch for self-concordant functions
The paper develops global, high-probability Newton Sketch guarantees for self-concordant objectives and barriers, while reducing per-iteration computational cost relative to exact Newton steps. The analysis also extends to constrained and interior-point settings, with complexity depending on sketch and Hessian structure rather than unknown problem parameters.
- Unconstrained convergence: Global convergence holds with exponentially high probability when the sketch dimension satisfies a suitable lower bound, without initialization conditions.The iteration bound scales with log(1/δ) and inversely with a parameter determined by sketching and line-search settings.
- Method: The Newton Sketch replaces exact Hessian computation with a randomized approximation and uses backtracking line search to compute approximate Newton updates.The method supports fully and partially sketched Hessians in unconstrained and constrained problems.
- Unconstrained convergence: The convergence guarantees are independent of the function and problem parameters, including strong-convexity and Lipschitz parameters.This independence is stated for the self-concordant analysis and contrasts with estimates involving unknown curvature and Lipschitz constants in local theory.
- Complexity: For n > d, each Newton Sketch step costs at most O(d^3 + nd log d), versus O(nd^2) for Newton’s method.The sketched step is also smaller than typical first-order methods costing O(nd) whenever n > d^2.
- Constrained problems: Self-concordant barriers extend Newton Sketch to convex constraints by combining the objective with a barrier and optionally sketching only the objective Hessian.Structured barrier Hessians, such as diagonal-plus-rank-one or separable forms, can be retained exactly through partial sketching.
- Interior-point methods: In interior-point methods, alternative treatments of convex constraints have the same convergence guarantees, while computational complexity varies with data access and Hessian structure.The resulting worst-case iteration analysis includes a choice where r yields O(√r) iterations.
5 Applications and numerical results
The Newton Sketch is applied across generalized linear models, constrained optimization, semidefinite programs, portfolio optimization, and numerical comparisons. These applications exploit structured or partial Hessian sketches to reduce computational cost while retaining useful accuracy.
- Generalized linear models: For generalized linear models, Newton Sketch handles convex losses with constraints such as ℓ1-balls and nuclear norms.The method is formulated for constrained maximum-likelihood problems and supports structured solutions including sparsity and low rank.
- ℓ1-constrained optimization: For ℓ1-constrained problems with an s-sparse optimum, a sufficient sketch dimension is derived using restricted eigenvalue and loss-curvature quantities.The resulting choice is typically O(s log d) for common data distributions.
- ℓ1-constrained optimization: For typical sub-Gaussian data, the sketch size is O(s log d), while per-iteration costs can scale as O(s^2d log^2(d)) or O(sd log(d)).These costs are substantially smaller than conventional methods that do not exploit the tangent cone's intrinsic dimension.
- Semidefinite programs: For semidefinite metric learning, partial Hessian sketching yields Newton Sketch complexity O(m^2d^2), compared with O(nd^4) for a classical SDP interior-point solver.The data-dependent Hessian term is sketched while the barrier Hessian remains exact.
- Numerical comparisons: In logistic regression, Newton Sketch converges similarly to Newton per iteration but is fastest when performance is measured by wall-clock time.The randomized methods were averaged over 10 trials, and the sketch used m = 6d.
- Barrier methods: In the sketched barrier method, similar accuracy is obtained with significantly less computation time than the original barrier method.The method may require more iterations, but its total wall-clock time is smaller.
6 Proofs
The proofs establish high-probability convergence of Newton Sketch through sketching bounds, recursive error control, and a two-phase self-concordant analysis. The resulting iteration guarantees preserve Newton-like behavior while accommodating randomized Hessian approximations.
- Proof strategy: The proof reduces Newton Sketch convergence to a recursive bound on the iterate error and probabilistic control of sketch-dependent random variables.The analysis defines quantities controlling the sketched Hessian interaction and combines their bounds with the error recursion.
- Newton updates: The sketched Newton update replaces the exact Hessian inverse with an inverse involving the sketched Hessian approximation.In the unconstrained case, the updates are written explicitly in terms of ∇f(x), ∇2f(x), and the sketch matrix S.
- Newton updates: The analysis uses the approximate Newton decrement as a high-probability exit condition because classical Newton bounds do not directly apply to the sketched update.This connects the randomized update to the standard self-concordant convergence framework.
- Sketching guarantees: For self-concordant functions, sketch-dimension lemmas provide high-probability control for sub-Gaussian and randomized orthogonal-system sketches.These lemmas are combined with the recursion to establish the theorem's convergence claim.
- Two-phase convergence: When the Newton decrement is above a threshold, each iteration decreases the function value by at least a fixed ν with exponentially high probability.This establishes the first phase of the convergence analysis.
- Two-phase convergence: When the decrement is below the threshold, the analysis repeatedly applies a contraction bound to obtain the second phase of convergence.Self-concordance then relates the decrement control to function-value accuracy.
7 Discussion
The discussion presents Newton Sketch as a randomized approximation to Newton updates that extends to constrained problems and barrier methods. It emphasizes lower per-iteration complexity, parallel sketching, and open questions about sparse sketches and sketch-dimension limits.
- Scope and extensions: Newton Sketch extends iterative Hessian sketching from constrained least squares to twice-differentiable objectives with closed convex constraint sets.The paper also applies it within barrier methods for constrained optimization.
- Scope and extensions: Combining Newton Sketch with interior-point updates is reported to produce faster algorithms for many convex optimization problems involving self-concordant functions.The discussion connects the method's constrained extension to barrier-based optimization.
- Computational implications: Newton Sketch has lower per-iteration complexity than classical Newton, and can also beat first-order methods when n ≥d^2 or d ≥n^2 using the dual strategy.The advantage is emphasized for big-data regimes where one data dimension is much larger than the other.
- Computational implications: With randomized Hadamard transforms and O(nd) processors, sketching can be performed in O(log m) time while reducing central computation from O(m^2d + nd log m) to O(m^2d + log d).This makes the sketching scheme well-suited to parallel environments.
- Open problems: Open problems include analyzing coordinate or sparse sketches for sparse data matrices and determining lower bounds on the sketch dimension m.The paper leaves unresolved whether smaller sketches can preserve the stated convergence guarantees.
A Technical results for Theorem 2
The appendix develops technical bounds for comparing sketched and exact Newton steps, then derives a decrement bound using self-concordance along the Newton Sketch direction.
- Technical comparison: The analysis compares the sketched step vNSK with the exact Newton step vNE through their difference vector.Optimality and feasibility yield a basic inequality involving the sketched Hessian and gradient terms.
- Technical comparison: The event E(δ) holds with probability at least 1 − c1e−c2mδ2, providing the high-probability condition used for subsequent bounds.E(δ) is defined by Z1 ≥ 1 − δ and Z2 ≤ δ.
- Self-concordance: The function g(u) = f(x + uvNSK) is strictly convex and self-concordant, so its derivatives satisfy a Hessian-controlled bound.The derivative identities connect g′ and g′′ to the gradient and Hessian of f along vNSK.
- Self-concordance: The derivative identities convert the one-dimensional bound for g into the decrement bound (41).Specifically, g′(u) and g′′(u) are expressed through ∇f and ∇2f evaluated along the sketch direction.
A.3 Proof of Lemma 5
The proof of Lemma 5 controls the Newton Sketch decrement by combining approximation of the exact Newton step with a high-probability Hessian sandwich and self-concordant inequalities.
- Step approximation: The sketched and exact Newton steps differ by at most ϵλf(x) in the local Hessian seminorm.This approximation follows from Lemma 2 and is used throughout the decrement analysis.
- Step approximation: The gradient inner product satisfies −λf(x)2(1 + ϵ) ≤ ⟨∇f(x), vNSK⟩ ≤ −λf(x)2(1 − ϵ).The upper bound is given in (57), while the reverse-direction argument provides the lower bound.
- Conclusion: The proof establishes bound (44b) earlier and reduces the remaining work to inequality (44a).The argument then introduces eλ = (1 + ϵ)λf(x) and proves the required Hessian relation.
- Hessian control: With probability at least 1 − c1e−c2mϵ2, the Hessian along the sketched step satisfies the sandwich relation (59).The relation is obtained by combining Lemma 2 with the self-concordant Hessian bound.
- Hessian control: The decrement at xNSK is bounded by integrating the Hessian along the segment from x to x + vNSK.The proof decomposes the resulting expression into terms M1 and M2 and bounds each separately.
B Proof of Lemma 7
The proof of Lemma 7 repeats the comparison strategy for a constrained Newton Sketch problem, using optimality inequalities to control the difference between sketched and exact steps.
- Constrained step comparison: Optimality and feasibility for the sketched Newton problem imply Ψ(vNSK; S) ≤ Ψ(vNE; S).Introducing the step difference yields a basic inequality containing both the sketched quadratic term and the Hessian of g.
- Constrained step comparison: The exact Newton problem supplies a corresponding optimality and feasibility comparison for vNE and vNSK.The proof uses this second inequality together with the sketched comparison to proceed as in Lemma 2.
C Gaussian widths with ℓ1-constraints
This appendix bounds Gaussian widths for a broad class of ℓ1-constrained problems by exploiting sparsity-induced tangent-cone geometry and Gaussian supremum bounds.
- Problem setup: The lemma considers a twice-differentiable convex program with an ℓ1 constraint and a unique s-sparse optimal solution.The tangent cone at the optimum is then used to characterize the relevant directions.
- Tangent-cone geometry: The tangent cone at any s-sparse solution lies inside {z ∈ R^d | ∥z∥1 ≤ 2√s∥z∥2}.This containment provides the geometric restriction used in the Gaussian-width bound.
- Gaussian analysis: The analysis bounds Gaussian variables Qj using their variance upper bounds.The Qj are zero-mean Gaussian random variables.
- Gaussian analysis: Standard bounds on Gaussian suprema are applied to complete the Gaussian-width estimate.Combining these bounds with the preceding inequality yields the lemma’s claim.