PaperlayerView exact revision on arXiv

Source-linked AI summary

Sub-sampled Newton Methods with Non-uniform Sampling

Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher Ré, Michael W. Mahoney

arXiv:1607.00559v2math.OCstat.ML

TL;DR

High-precision minimization is costly when forming and inverting the full Hessian, despite the value of second-order methods for ill-conditioned problems. The paper combines non-uniform Hessian subsampling with inexact Newton updates; it reports lower per-iteration complexity and better condition-number dependence than similar methods. These guarantees are local and require a suitable initial point.

  • Problem

    Forming and inverting a full Hessian is a major practical drawback of Newton’s method, although second-order methods are more robust to ill-conditioning than first-order methods.

    Source: §1 · p. 2

  • Method

    The paper proposes sub-sampled Newton methods using block norm squares or block partial leverage score sampling and permits inexact subproblem updates.

    Source: §1 · pp. 2–3

  • Results

    The algorithms have better condition-number dependence and lower per-iteration complexity than similar existing methods.

    Source: §6 · p. 18

  • Takeaways & Limitations

    Non-uniform sampling requires a smaller sample size than uniform sampling and is described as more robust to ill-conditioned problems.

    Source: §1 · p. 3

    The stated guarantees are local; global convergence can be addressed by using an existing globally convergent method before switching to the algorithm near the optimum.

    Source: §4 · p. 8

Abstract

from arXiv · show

We consider the problem of finding the minimizer of a convex function $F: \mathbb R^d \rightarrow \mathbb R$ of the form $F(w) := \sum_{i=1}^n f_i(w) + R(w)$ where a low-rank factorization of $\nabla^2 f_i(w)$ is readily available. We consider the regime where $n \gg d$. As second-order methods prove to be effective in finding the minimizer to a high-precision, in this work, we propose randomized Newton-type algorithms that exploit \textit{non-uniform} sub-sampling of $\{\nabla^2 f_i(w)\}_{i=1}^{n}$, as well as inexact updates, as means to reduce the computational complexity. Two non-uniform sampling distributions based on {\it block norm squares} and {\it block partial leverage scores} are considered in order to capture important terms among $\{\nabla^2 f_i(w)\}_{i=1}^{n}$. We show that at each iteration non-uniformly sampling at most $\mathcal O(d \log d)$ terms from $\{\nabla^2 f_i(w)\}_{i=1}^{n}$ is sufficient to achieve a linear-quadratic convergence rate in $w$ when a suitable initial point is provided. In addition, we show that our algorithms achieve a lower computational complexity and exhibit more robustness and better dependence on problem specific quantities, such as the condition number, compared to similar existing methods, especially the ones based on uniform sampling. Finally, we empirically demonstrate that our methods are at least twice as fast as Newton's methods with ridge logistic regression on several real datasets.

1 Introduction

The introduction motivates computationally efficient high-precision optimization where forming and inverting a full Hessian is costly. It proposes non-uniformly sub-sampled Newton methods with inexact updates, whose sampling and solver choices affect convergence and computational cost.

1 Introduction

  • High-precision empirical-risk minimization matters because its generalization error is within O(1/√n) additive error of that of the population-risk minimizer.The introduction notes that this motivates high-precision optimization when many data points are available.Source: §1 · p. 1
  • Inexact iterative solvers, including Conjugate Gradient, can reduce the cost of solving the sampled linear system when the dimension is large.The paper states that a few iterations can produce a high-quality approximate solution with less complexity.Source: §1 · pp. 2–3
  • Under certain conditions, the randomized Newton-type algorithm achieves local linear-quadratic convergence.The convergence constants depend on Hessian approximation quality and the solution quality of the inexact subproblem.Source: §1 · pp. 2–3
  • The methods use block norm squares or block partial leverage scores to approximate the Hessian, with sampling and solver choices affecting convergence and per-iteration cost.The paper frames the Hessian approximation as a matrix approximation problem.Source: §1 · pp. 2–3
  • Non-uniform sampling can require a smaller sample size than uniform sampling and is described as more robust to ill-conditioned problems.The comparison is tied to the sampling-size contribution to solve cost and to the condition-number dependence of the convergence constants.Source: §1 · p. 3

1.1 Related work

Prior work reduces Newton-method costs through uniform sampling, sketching, and stochastic subproblem solvers. This paper contributes non-uniform sampling strategies and local inexact-update analysis, and reports faster ridge-logistic-regression results than Newton’s methods.

1.1 Related work

  • Related randomized second-order methods include uniform sub-sampling, Newton Sketch, and LiSSA, while prior matrix-approximation work studies leverage-score and block-norm sampling.The cited literature also reports that uniform sampling may not guarantee spectral approximation when sample size depends only on the lower dimension.Source: §1.1 · p. 5

1.2 Main contributions

  • The paper uses block norm squares and block partial leverage scores, with sample sizes independent of n and resilience to extreme non-uniformity among the factor matrices.The cited contribution contrasts this with uniform sampling, which may require Ω(n) samples to capture Hessian information under extreme non-uniformity.Source: §1.2 · p. 5
  • The work extends analysis of inexact subproblem updates to local convergence and establishes a linear-quadratic solution-error recursion with improved condition-number dependence for its non-uniform strategies.For block partial leverage score sampling, the linear-term factor is O(√κ), compared with O(κ) for uniform sampling.Source: §1.2 · p. 5
  • The proposed algorithms are at least twice as fast as Newton’s methods in finding medium- or high-precision ridge logistic regression solutions on several real datasets.Other methods, including first-order methods, are reported to converge slowly.Source: §1.2 · p. 6

2 Background

The section fixes matrix and norm notation and states the regularity and Hessian-factorization assumptions used in the analysis.

2.1 Notation

  • A matrix with n blocks is represented through its block structure, while g, H, and eH denote the gradient, exact Hessian, and approximate Hessian.Source: §2.1 · p. 6
  • The paper uses Euclidean norms for vectors, spectral norms for matrices, and nnz(A) for the number of nonzero entries.Source: §2.1 · p. 6

2.2 Assumptions

  • The objective is assumed convex and twice differentiable, with an L-Lipschitz Hessian.Source: §2.2 · p. 6
  • The analysis assumes local strong convexity and smoothness, and defines the local condition number as κ = ν/μ.Source: §2.2 · p. 6
  • Each component Hessian has a factorization Hi(w) = Ai(w)^T Ai(w), with block size fixed independently of d and stated costs for computing Ai, Hi, and g.Source: §2.2 · p. 7

3 Main Algorithm: SSN with Non-uniform Sampling

The SSN algorithm repeatedly samples Hessian blocks from a non-uniform distribution, forms an approximate Hessian, and inexactly solves the resulting subproblem. It offers block norm squares and block partial leverage scores as sampling schemes.

3 Main Algorithm: SSN with Non-uniform Sampling

  • At each iteration, SSN constructs a non-uniform distribution, samples and rescales blocks to form an approximate Hessian, then uses a solver for an inexact subproblem update.Source: §3 · p. 7
  • Block norm squares sampling weights blocks by their magnitudes, extending row-norm sampling to capture the importance of sub-Hessians.Source: §3 · p. 8
  • Block partial leverage scores extend leverage-score sampling to block sampling with a regularization term Q, and reduce to ordinary leverage scores for single-row blocks when Q = 0.Source: §3 · p. 8

4 Theoretical Results

The theoretical analysis establishes local convergence conditions and examines how sampling and solver choices affect computational complexity. It treats two non-uniform sampling schemes and the role of inexact subproblem solves.

4 Theoretical Results

  • Total complexity depends on iteration count, full-gradient cost, distribution construction and sampling cost, and the cost of forming the approximate Hessian and solving the subproblem.Source: §4 · pp. 8–9

4.1 Sufficient conditions for local linear-quadratic convergence

  • Under the stated assumptions and a suitable initial point, the structural result gives a local error recursion when the Hessian approximation satisfies C1 or C2.Source: §4.1 · pp. 9–10
  • C2 is stronger than C1 and provides better convergence-constant dependence on the condition number; the subproblem solver must also produce an ε0-relative-error update.Source: §4.1 · p. 9

4.2.1 Construction

  • Approximate block partial leverage scores can be constructed in O(nnz(A) log n) time using a fast leverage-score approximation algorithm.Source: §4.2.1 · p. 10

4.2.2 Sampling size

  • Block partial leverage score sampling needs fewer than O(d log d / ε^2) blocks for the spectral approximation guarantee, with probability at least 1 − δ.Source: §4.2.2 · p. 11

4.3.1 Construction

  • Constructing the block norm squares sampling distribution takes O(nnz(A)) time.Source: §4.3.1 · p. 11

4.3.2 Sampling size

  • Block norm squares sampling yields the C1 matrix approximation guarantee with probability at least 1 − δ.Source: §4.3.2 · p. 11

4.4 Discussion on the choice of solver

  • For an unconstrained problem, direct solution costs O(sd^2), while conjugate gradient is advantageous when d is large and the system is fairly well-conditioned.Source: §4.4 · p. 12

4.5 Complexities

The section expresses total complexity in terms of iteration and per-iteration costs, then compares sampling schemes and related methods under specified settings.

4.5 Complexities

  • Total complexity is T times the sum of sampling-distribution construction cost and subproblem-solving cost, with the solution error specified separately by Lemma 7.Source: §4.5 · p. 12

4.6.1 Comparison between different sampling schemes

  • When the data blocks are highly non-uniform, uniform sampling can require Ω(n) samples, whereas block norm squares sampling needs the smallest sample size among the compared schemes.Source: §4.6.1 · p. 13
  • Leverage-score sampling has better dependence on local condition number κ in its convergence constants, while the paper notes that sampling-size bounds are upper bounds and can overestimate what works in practice.Source: §4.6.1 · p. 14

4.6.2 Comparison between various methods

  • The comparison with other methods targets a constant linear rate under unconstrained, unregularized conditions with CG; the cited methods use differently defined condition numbers, ordered κ(w) ≤ ˆκ(w) ≤ ¯κ(w).Source: §4.6.2 · p. 14

5 Numerical Experiments

The experiments compare non-uniformly sampled Newton methods with other optimization methods on ridge logistic regression. Across the reported tests, non-uniform sampling is robust to worsening conditioning and can outperform Newton’s method in running time.

5 Numerical Experiments

  • The comparison included Newton, uniform and non-uniform SSN variants, LBFGS, gradient descent, and accelerated gradient descent.The study used logistic regression and reported datasets in Table 4; the algorithms were initialized at zero and CG solved subproblems to 10^-6 relative residual error.Source: §5 · pp. 15–16, Table 4 · p. 16
  • As condition numbers increased, uniform sampling deteriorated while non-uniform sampling—especially leverage-score sampling—remained robust.The experiments vary the regularization parameter λ on Adult; all sampling schemes performed similarly in well-conditioned cases.Source: §5 · p. 16, Figure 1 · p. 16
  • On CT Slice, non-uniform SSN reached high precision more quickly and remained more robust to increased ill-conditioning than uniform SSN and LBFGS.Figure 2 plots iterate relative error against time for two λ values, with κ = 386 and κ = 1.387 × 10^4.Source: §5 · p. 17, Figure 2 · p. 17
  • At least twice faster than Newton’s method on several real datasets, PLevSS and RNormSS achieved medium- or high-precision solutions.Figure 3 compares relative solution error with running time; its caption notes the sample size used for each method.Source: §5 · p. 17, Figure 3 · p. 18
  • When data points were highly non-uniform, uniform sampling performed poorly, as illustrated by Figure 3(b).The authors relate this case to a much higher average local condition number, κ̄, than κ.Source: §5 · p. 18, Figure 3 · p. 18

6 Conclusions

The paper concludes that its non-uniformly sampled Newton methods with inexact updates have lower per-iteration complexity and better condition-number dependence than similar existing methods. Numerical experiments demonstrate the theoretical advantages.

6 Conclusions

  • The proposed non-uniformly sampled Newton methods with inexact updates have lower per-iteration complexity and better condition-number dependence than similar existing methods.The authors state that numerical experiments demonstrate these theoretical advantages.Source: §6 · p. 18

A Results of Block Partial Leverage Scores

The section develops a guarantee for block partial leverage-score sampling as a way to approximate a regularized matrix product. Sampling and rescaling blocks yields a spectral approximation relative to A^T A + Q.

A Results of Block Partial Leverage Scores

  • Sampling blocks with probabilities based on block partial leverage scores and rescaling by 1/√p_i yields a spectral approximation to A^T A relative to A^T A + Q.The guarantee is expressed as −ε(A^T A + Q) ⪯ A^T S^T S A − A^T A ⪯ ε(A^T A + Q).Source: A Results of Block Partial Leverage… · p. 21

B.1 Proof of Lemma 7

The appendix establishes the error recursion for exact and approximate subproblem solves, then supports the leverage-score and matrix-approximation guarantees used in the analysis.

B.1 Proof of Lemma 7

  • Exact subproblem solves yield the error recursion under conditions C1 and C2, while approximate solves preserve the same constants C_l and C_q under condition (12).The approximate-solve recursion includes terms scaled by the solver’s relative error ε_0.Source: §B.1 · pp. 23, 25

B.2 Proof of Theorem 8

  • Approximate leverage scores can be computed in O(nnz(A) log n) time with high probability and a constant approximation factor.The proof constructs the augmented matrix in O(nnz(A)) time.Source: §B.2 · p. 25

B.3 Proof of Theorem 9

  • Theorem 9’s proof converts condition C2 into a standard matrix-product approximation guarantee and applies a corollary of Theorem 15.Lemma 16 supplies an equivalence between two conditions used in that conversion.Source: §B.3 · p. 25

B.4 Proof of Corollary 13

The Corollary 13 proof applies an error recursion to compare sampling schemes, while the Theorem 14 proof uses a matrix concentration bound to establish a Hessian-approximation condition.

B.4 Proof of Corollary 13

  • The error recursion bounds the next iterate’s distance by a quadratic term and a linear term in the current distance.The coefficients are (1 + ǫ0)Cq and ǫ0 + (1 + ǫ0)Cl, respectively.Source: §B.4 · p. 26
  • For leverage-score sampling, the proof sets s = Õ(dκ) after requiring ǫ ≤ min …, with the remaining bound omitted.It uses CG to target ǫ0 ≤ 0.01, with solve cost stated as Õ(sd√κ) in the local region.Source: §B.4 · pp. 26–27
  • The proof says block norm-squares sampling is handled similarly, but the supplied passage does not include its resulting bound.The proof’s displayed fragments do not support a more specific comparison.Source: §B.4 · p. 27

B.5 Proof of Theorem 14

  • With probability at least 1 − δ, matrix Bernstein gives a relative approximation of AᵀA, which implies condition (C1) because Q ⪰ 0.The stated inequality is ∥AᵀSᵀSA − AᵀA∥ ≤ ǫ∥AᵀA∥.Source: §B.5 · pp. 27–28

Related papers

Loading 1607.00559v2…