PaperlayerView exact revision on arXiv

Source-linked AI summary

An Investigation of Newton-Sketch and Subsampled Newton Methods

Albert S. Berahas, Raghu Bollapragada, Jorge Nocedal

arXiv:1705.06211v4math.OCcs.LGstat.ML

TL;DR

The paper examines the trade-offs between Hessian subsampling and randomized Hadamard sketching for large finite-sum optimization problems, where approximate linear solves are needed. It compares iterative solvers and reports advantages for conjugate gradient over a stochastic-gradient iteration, alongside similar effective-gradient-evaluation performance for Newton-Sketch and SSN-CG on most problems.

  • Problem

    The relative trade-offs between Hessian subsampling and randomized Hadamard sketching, and the effectiveness of iterative solvers for practical large-variable, large-data problems, had not been investigated together.

    Source: §1 · p. 2

  • Method

    The study compares Hessian subsampling and randomized Hadamard sketching with inexact iterative linear solves, including conjugate gradient and a stochastic-gradient iteration.

    Source: §1 · p. 2

  • Results

    Conjugate gradient has superior properties to the stochastic-gradient iteration, while Newton-Sketch and SSN-CG perform on par on most problems in effective gradient evaluations.

    Source: §1 · p. 2, §4.1 · p. 9

  • Takeaways & Limitations

    The practical choice between Newton-Sketch and SSN involves a trade-off between statistical properties and computational cost.

    Source: Discussion · p. 5

    When component functions are highly dissimilar, a small SSN sample may not yield a useful Hessian approximation, and Newton-Sketch may be more effective.

    Source: Discussion · p. 5

Abstract

from arXiv · show

Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.

1 Introduction

The paper compares Hessian subsampling and randomized Hadamard sketching for finite-sum optimization, focusing on practical settings with many variables and data points. It studies inexact iterative solvers and argues that stochastic second-order information can be useful in practice.

1 Introduction

  • The study compares Hessian subsampling with randomized Hadamard sketching, which may give a better Hessian approximation but can be computationally expensive.The paper also contrasts conjugate gradient with a stochastic-gradient iteration for approximately solving the resulting linear systems.Source: §1 · p. 2
  • The practical focus is on problems with many variables and data points, where iterative solvers avoid inverting large matrices at every iteration.The authors report theoretical and computational comparisons of conjugate gradient and stochastic-gradient iterations, and derive complexity bounds for Hessian subsampling.Source: §1 · p. 2
  • Earlier Newton-Sketch analysis considered few variables, exact linear solves, and did not extensively report numerical results or compare against Hessian subsampling.The cited work assumes the square root of the Hessian can be computed at reasonable cost.Source: §1 · p. 2
  • The paper argues that stochastic second-order information can offer practical value despite the popularity of first-order methods.Source: §1 · p. 2

2 Stochastic Second Order Methods

The methods use sketching to construct stochastic Hessian approximations for finite-sum optimization, then solve the resulting systems inexactly. The section distinguishes Hadamard-based Newton-Sketch from component-Hessian subsampling and describes their trade-offs.

2 Stochastic Second Order Methods

  • With an exact gradient, the iteration's stochasticity comes entirely from the sketched Hessian approximation, and the algorithms use inexact linear-system solutions.The authors choose exact gradients to isolate Hessian approximations and enable direct comparison with first-order methods.Source: §2 · p. 3

Hessian-Sketch

  • Newton-Sketch projects a square-root Hessian into a lower-dimensional space; forming its approximation is cheaper than forming the full Hessian when m << n.The approach is not always viable because the square-root Hessian may not be readily computable.Source: Hessian-Sketch · p. 3

Hessian Subsampling

  • Hessian subsampling averages randomly selected component Hessians and solves the resulting system approximately, stopping once the solution is accurate enough to make progress.It can be motivated directly from the finite-sum structure, without randomized projections.Source: Hessian Subsampling · p. 4

Notation and Nomenclature

Discussion

  • Newton-Sketch has superior statistical properties but higher computational cost, while SSN is simpler and less expensive but may be statistically inferior when component functions are highly dissimilar.In that setting, a small sample of component Hessians may not yield a useful approximation, and Newton-Sketch may be more effective.Source: Discussion · pp. 4–5
  • The comparison targets problems with many variables and large datasets, motivating careful implementation of how each method forms and solves its linear system.Source: Discussion · p. 5

3 Practical Implementations of the Algorithms

The implementations use iterative linear solvers to handle large-variable problems without direct solves. They compare conjugate gradient with a stochastic-gradient iteration, which is available only for subsampled Hessians.

3 Practical Implementations of the Algorithms

  • The implementations use iterative solvers tailored to each method because direct solvers are practical only when the variable dimension is not large.The compared solvers are conjugate gradient and a stochastic-gradient iteration inspired by, but not equivalent to, Robbins–Monro stochastic gradient.Source: §3 · p. 5

3.1 The Conjugate Gradient (CG) Method

  • Conjugate gradient can solve the systems using matrix-vector products without forming the coefficient matrix, and favorable eigenvalue distributions can make a useful solution possible in fewer than d iterations.SSN-CG requires no projection and costs T times maxCG Hessian-vector products per outer iteration; Newton-Sketch uses Hadamard projections and its reported costs are optimistic because some costs are ignored.Source: §3.1 · p. 5, Subsampled Newton · p. 6, Newton-Sketch · p. 6

3.2 A Special Stochastic Gradient Iteration

  • The stochastic-gradient iteration (SGI) is usable only with SSN, because the sketched Newton-Sketch Hessian cannot be efficiently decomposed into individual components.SSN-SGI uses cycles of length mSGI, with a randomly selected component at each inner iteration; its tuning parameters include the step length and cycle length.Source: §3.2 · p. 7

4 Numerical Study

The study compares practical Newton-Sketch and subsampled Newton methods with SVRG across several classification problems, testing solver choices and tuning methods for performance. Newton-Sketch and SSN-CG outperform SVRG on the more challenging problems, while SSN-CG beats SSN-SGI and matches Newton-Sketch on most problems by effective gradient evaluations.

4 Numerical Study

  • The study tests SSN with CG and stochastic gradient iteration, uses Armijo backtracking for step lengths, and compares both methods with SVRG.SVRG’s cycle combines a full gradient step with stochastic gradient-type iterations; its cycle cost is comparable to that of Newton-Sketch and SSN.Source: §4 · pp. 7–8

Experimental Setup

  • The experiments use logistic loss with ℓ2 regularization on binary classification data selected to vary in dimension and condition number.The tuning process tests iteration budgets and parameter combinations for each method.Source: §4 · p. 8, Experimental Setup · p. 8

4.1 Numerical Results

  • SSN-SGI is not competitive with SSN-CG: CG’s superior convergence outweighs the apparent advantage of using a new Hessian sample at each iteration.The comparison is based on the second column of Figure 1.Source: §4.1 · p. 8
  • Newton-Sketch and SSN-CG use similar optimal CG iteration counts, but Newton-Sketch’s optimal sketch has significantly fewer rows than SSN-CG’s number of subsamples.The paper attributes the sketch-size difference to small sketches capturing the true Hessian’s eigenvalues adequately on most test problems.Source: §4.1 · p. 9
  • Newton-Sketch and SSN-CG are much faster than SVRG on gisette and australian, all methods perform on par on australian-scale, and curvature’s added cost outweighs its benefits on rcv1.Across most problems, Newton-Sketch and SSN-CG perform on par by effective gradient evaluations; SSN-CG would have a dramatic CPU-time advantage.Source: §4.1 · p. 9, Figure 1 · p. 10
  • Figure 1 shows training error against iteration and effective gradient evaluations for four datasets, with method parameters tuned for best error by effective gradient evaluations.For SVRG, one iteration is a complete cycle; effective gradient evaluations sum function evaluations, gradient evaluations, and Hessian-vector products.Source: §4.1 · p. 8, Figure 1 · p. 10

5 Analysis

Under Assumptions A.1–A.4, SSN-CG converges locally at a linear rate with constant 1/2 when initialized near the solution. Its work depends on the maximum CG iteration count, which can be much smaller than d for favorable Hessian spectra.

Assumptions

  • Near the solution, SSN-CG converges linearly with constant 1/2 under the stated assumptions and CG-step condition.The result assumes α_k = 1 and a constant subsample size T across iterations, although the sample itself varies.Source: §5 · p. 11, Assumptions · pp. 12, 14

5 Analysis

  • The SSN-CG work bound depends on the maximum CG iteration count r̄, which can be much smaller than d for favorable eigenvalue distributions.Clustered spectra can make r̄ small; the analysis counts component gradient evaluations and Hessian-vector products, assuming their costs are equal.Source: Assumptions · p. 14
  • For gisette, MNIST, and cina, few CG steps can rapidly improve the linear-system solution; on cina, steps 20–24 improve accuracy by two orders of magnitude.The spectrum is least favorable for synthetic3, whose high condition number and wide eigenvalue range produce behavior similar to CG’s worst-case analysis.Source: Assumptions · pp. 14, 16, Figure 2 · p. 15
  • When CG requires d iterations, the Newton-Sketch and SSN-CG work bounds are similar, with Newton-Sketch slightly more costly.This comparison uses the analysis’s pessimistic bound on CG iterations.Source: Assumptions · p. 16

Assumptions

  • The analysis assumes enough data points for n > κ^2, given its implicit subsample-size and sketch-dimension restrictions.The SSN analysis also relies on positive-definite component Hessians; relaxes this but does not establish overall convergence.Source: Assumptions · pp. 11, 12, 16

6 Final Remarks

The paper compares Newton-Sketch and subsampled Hessian Newton methods on large-scale applications, where their relative performance had not been studied. They perform on par in effective gradient evaluations, but subsampled Hessian Newton is much faster in CPU time; both second-order methods generally outperform SVRG on some logistic regression problems.

6 Final Remarks

  • The two second-order methods perform on par in effective gradient evaluations, while subsampled Hessian Newton is much faster in CPU time.Newton-Sketch’s per-iteration cost is high because of linear-system construction.Source: §6 · pp. 16–17
  • CG is a more efficient linear-system solver than a first-order stochastic gradient iteration in the tests.The analysis quantifies CG’s role as an inner iterative solver.Source: §6 · p. 17
  • Both second-order methods are generally more efficient than SVRG on some logistic regression problems.Source: §6 · p. 17

A Complete Numerical Results

The appendix presents further numerical results on the datasets listed in Tables 1 and 2. It evaluates four methods for logistic regression using training error and effective gradient evaluations, with testing loss also reported for the first two experiment groups.

A Complete Numerical Results

  • The appendix presents further numerical results on the data sets listed in Tables 1 and 2.Table 1 is titled Synthetic Datasets; Table 2 is titled Real Datasets.Source: A Complete Numerical Results · p. 20, Table 1 · p. 20, Table 2 · p. 20
  • For logistic-regression classification experiments, the authors ran SVRG, Newton-Sketch, SSN-SGI, and SSN-CG on synthetic and popular machine-learning datasets, reporting training error and testing loss.Synthetic datasets varied in sample count and condition number, while popular machine-learning datasets varied in sample count, variable count, and condition number; datasets without provided test sets were randomly split 90%/10% for training and testing.Source: A Complete Numerical Results · p. 20
  • Training error is reported against iterations and effective gradient evaluations, with testing loss also reported for the first two experiment groups.Effective gradient evaluations sum function evaluations, gradient evaluations, and Hessian-vector products.Source: A Complete Numerical Results · p. 20

A.1 Performance of methods - Synthetic Data sets

On synthetic problems, Newton-Sketch and SSN-CG outperform SVRG and SSN-SGI, with Newton-Sketch slightly ahead of SSN-CG. The experiments use highly ill-conditioned synthetic datasets with wide eigenvalue spectra.

A.1 Performance of methods - Synthetic Data sets

  • The four synthetic problems have condition numbers of 10^2–10^5 and wide eigenvalue spectra, a setting unfavorable to CG.The passage identifies high condition numbers as a setting where Newton methods show strength relative to first-order methods such as SVRG.Source: §A.1 · p. 21
  • Newton-Sketch and SSN-CG outperform SVRG and SSN-SGI on the synthetic datasets, and Newton-Sketch performs slightly better than SSN-CG.The authors attribute the latter difference primarily to highly dissimilar component functions and Newton-Sketch's use of information from all components; SVRG leads initially but quickly stagnates.Source: §A.1 · p. 21, Figure 3 · p. 22
  • Figure 3 compares training error by iteration, training error by effective gradient evaluations, and testing loss by effective gradient evaluations.Hyperparameters were tuned for best training error per effective gradient evaluation; the cost of forming Newton-Sketch linear systems is excluded.Source: Figure 3 · p. 22

A.2 Performance of methods - Machine Learning Data sets

Across 12 machine-learning datasets, the relative performance depends on problem characteristics: SVRG has a sweet spot, while curvature information helps on other problems where ill-conditioning slows SVRG. Newton-Sketch was not run on cov because constructing padded sketch matrices was too memory-intensive.

A.2 Performance of methods - Machine Learning Data sets

  • Across the machine-learning problems, SVRG outperforms the stochastic second-order methods on some datasets, while curvature helps on others where ill-conditioning slows SVRG.For those ill-conditioned problems, SVRG requires a very small step length to avoid divergence and consequently makes slow progress.Source: §A.2 · p. 23, Figure 4 · p. 24, Figure 5 · p. 25
  • Newton-Sketch was not run on cov because the large data-point count made the padded sketch matrices prohibitive in memory.Source: §A.2 · p. 23
  • Figures 4–6 cover 12 datasets: australian-scale, australian, reged, mushroom, ijcnn1, cina, ISOLET, gisette, cov, MNIST, rcv1, and real-sim.They report training error by iteration and effective gradient evaluations, and testing loss by effective gradient evaluations.Source: §A.2 · p. 23, Figure 4 · p. 24, Figure 5 · p. 25

A.3 Sensitivity of methods

Sensitivity experiments on four datasets suggest Newton-Sketch and SSN-CG are more robust to hyperparameter choices and easier to tune than SVRG and SSN-SGI. The figures omit SVRG and SSN-SGI runs that diverged.

A.3 Sensitivity of methods

  • Newton-Sketch and SSN-CG are empirically more robust to hyperparameter choices and easier to tune than SVRG and SSN-SGI.For almost all tested choices of m_NS, T, and maxCG, the two methods converge; parameter choices mainly affect convergence speed.Source: §A.3 · p. 27, Figure 7 · p. 28, Figure 8 · p. 29
  • The sensitivity experiments cover synthetic1, australian-scale, mushroom, and ijcnn1, varying each method's two hyperparameters.Each figure uses rows for methods and columns for the first and second hyperparameter; SVRG and SSN-SGI plots exclude regimes in which the methods diverged.Source: §A.3 · p. 27, Figure 7 · p. 28, Figure 8 · p. 29
  • For SVRG and SSN-SGI, an unsuitable step length can cause divergence or very slow progress, and those runs are excluded from the figures.Source: §A.3 · p. 27, Figure 7 · p. 28, Figure 8 · p. 29

B Eigenvalues

Across datasets and subsample sizes, the section compares eigenvalue spectra of true, subsampled, and sketched Hessians. Both approximations can capture the true spectrum at reasonable sizes, while sketched Hessians appear closer and have smaller error bars.

B Eigenvalues

  • The spectra were compared at matched subsample and sketch sizes, with T set equal to mNS for each figure.For each dataset and size, the procedure computed 10 subsampled and 10 sketched Hessians and averaged their eigenvalues.Source: B Eigenvalues · p. 32
  • Sketched Hessians appear closer to the true Hessian spectrum than subsampled Hessians across the reported datasets and sizes.The comparison concerns both average eigenvalues and error bars.Source: B Eigenvalues · pp. 32–33, Figure 11 · p. 33, Figure 15 · p. 34
  • The authors present these eigenvalue distributions to show that machine-learning problems appear to have favorable distributions for conjugate gradient.They attribute the closer sketched spectra to use of all component functions, whereas subsampled Hessians use a subset.Source: B Eigenvalues · p. 33

Related papers

Loading 1705.06211v4…