PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence rates of sub-sampled Newton methods

Murat A. Erdogdu, Andrea Montanari

arXiv:1508.02810v2stat.ML

TL;DR

The paper studies how to obtain quantitative convergence guarantees for sub-sampling-based second-order optimization in the regime n ≫ p. It proposes NewSamp, which combines sub-sampling with low-rank Hessian estimation and eigenvalue thresholding. The method has composite quadratic-then-linear convergence, with theoretical results covering parameter selection and prior sub-sampling algorithms.

  • Problem

    Sub-sampling can make second-order optimization more feasible, but quantitative convergence guarantees for sub-sampled curvature methods are missing.

  • Method

    NewSamp uses sub-sampled Hessians with low-rank approximation and eigenvalue thresholding to construct a stabilized curvature estimate.

  • Results

    NewSamp exhibits composite convergence, starting quadratically and becoming linear near the optimum, while the analysis provides convergence rates for different sub-sampling schemes.

  • Takeaways & Limitations

    The method provides a sub-sampling-based second-order approach with reduced per-iteration cost and theory-guided parameter choices in the target n ≫ p regime.

  • Takeaways & Limitations

    For support vector machines, the theorems' Lipschitz condition does not apply, although the method is empirically demonstrated to work under that setting.

Abstract

from arXiv · show

We consider the problem of minimizing a sum of $n$ functions over a convex parameter set $\mathcal{C} \subset \mathbb{R}^p$ where $n\gg p\gg 1$. In this regime, algorithms which utilize sub-sampling techniques are known to be effective. In this paper, we use sub-sampling techniques together with low-rank approximation to design a new randomized batch algorithm which possesses comparable convergence rate to Newton's method, yet has much smaller per-iteration cost. The proposed algorithm is robust in terms of starting point and step size, and enjoys a composite convergence rate, namely, quadratic convergence at start and linear convergence when the iterate is close to the minimizer. We develop its theoretical analysis which also allows us to select near-optimal algorithm parameters. Our theoretical results can be used to obtain convergence rates of previously proposed sub-sampling based algorithms as well. We demonstrate how our results apply to well-known machine learning problems. Lastly, we evaluate the performance of our algorithm on several datasets under various scenarios.

1 Introduction

The paper targets large-scale convex optimization where sub-sampling can reduce second-order costs but lacks quantitative convergence guarantees. It introduces NewSamp, combining sub-sampling with low-rank eigenvalue thresholding to obtain composite convergence, explicit coefficients, and reduced per-iteration complexity.

  • Motivation: NewSamp addresses the missing theoretical guarantees for sub-sampling-based curvature approximations.Sub-sampled Hessians can approximate large-curvature directions poorly in flatter directions.
  • Convergence guarantees: NewSamp has a composite convergence rate: quadratic at start and linear near the minimizer.The paper proves a bound with explicitly given, data-computable coefficients.
  • Convergence guarantees: 1−(λ∗_p/λ∗_1) is replaced by a milder asymptotic linear-convergence coefficient for NewSamp.The paper reports that this can yield a large improvement for datasets with strong spectral features.
  • Algorithm properties: NewSamp achieves the stated results without step-size tuning by setting η_t = 1.The algorithm also supports theoretically guided parameter selection.
  • Computational cost: The per-iteration complexity of NewSamp is O(np + |S|p^2), where |S| is the sample size.This is presented as a reduced-cost alternative to classical second-order methods in the n ≫ p regime.
  • Evaluation and scope: The paper evaluates NewSamp on four datasets and compares it with well-known optimization methods.The theoretical results also apply to previously proposed sub-sampling algorithms.

2 NewSamp : A Newton method via sub-sampling and eigenvalue thresholding

NewSamp combines sub-sampled Hessians with low-rank eigenvalue thresholding to stabilize curvature estimates and reduce computation. Its iterations are descent steps with quadratic convergence initially and linear convergence near the minimizer.

  • Motivation: Classical second-order methods face Hessian-computation and Hessian-inversion costs in the n ≫ p ≫ 1 regime.The paper identifies costs of O(np^2) for computing the Hessian and O(p^3) for inverting it.
  • Eigenvalue thresholding: NewSamp computes a truncated SVD of the sub-sampled Hessian and replaces eigenvalues below the rank threshold with the next eigenvalue.This produces a stabilized curvature matrix based on a low-rank approximation.
  • Computational structure: The thresholded low-rank approximation also reduces the cost of computing the inverse curvature matrix.The resulting matrix is described as a scaled identity plus a rank-r matrix.
  • Algorithm parameters: NewSamp uses step sizes, sub-sample sizes, and rank threshold r as algorithm inputs, with near-optimal choices discussed from the theory.Projection onto the feasible set is assumed to be efficient and is mainly used for theoretical purposes.
  • Observed convergence: NewSamp is a descent algorithm with quadratic convergence at first that transitions to linear convergence near the minimizer.Larger sub-samples produce better convergence rates and reduce the slope of the linear phase.

3 Theoretical results

The paper analyzes NewSamp under independent and sequentially dependent sub-sampling, showing composite convergence and deriving conditions for convergence and parameter selection. The analysis explains how sub-sample size, eigenvalues, step size, and sampling dependence affect the linear and quadratic terms.

  • Sub-sampling schemes: NewSamp is analyzed under independent and sequentially dependent sub-sampling schemes, including uniform, fixed, and progressively constructed sub-samples.The dependent scheme may use increasing sample sizes or previously unused data, while remaining independent of randomness in the dataset.
  • Convergence guarantees: With high probability, the updates satisfy a composite convergence bound combining linear and quadratic terms under convexity, Lipschitz, and bounded-Hessian assumptions.The independent-sampling result is stated in Lemma 3.1 and generalized through Theorem 3.2; the dependent-sampling result requires i.i.d. observations and conditions on θ* belonging to C.
  • Independent sub-sampling: Small sub-sampled Hessian eigenvalues can make simple sub-sampled Hessian methods unstable, whereas NewSamp is designed to remedy this issue through its low-rank construction.The problematic smallest eigenvalue may be arbitrarily small and can inflate both convergence coefficients.
  • Independent sub-sampling: For quadratic functions, the quadratic coefficient vanishes, so NewSamp converges linearly; the linear term is strongly affected by sub-sample size.The quadratic term is governed by the Lipschitz constant, while the linear term depends significantly on the sub-sampling size.
  • Sequentially dependent sub-sampling: Under dependent sub-sampling, the quadratic coefficient remains unchanged, but the linear-term bound is worse because it uses a uniform bound over the convex parameter set.The corresponding quadratic-function corollary retains the dependent-sampling probability guarantee.
  • Coefficient approximations: For sufficiently large sub-samples, the iteration-dependent coefficients are approximated by their optimal-point analogues, with an error bound δ under quadratic-function assumptions.The analysis also supplies sufficient convergence conditions and notes that fixed sub-samples make the linear coefficient independent of iteration.
  • Parameter selection: The recommended sample size is O((K/λ*_p)^2 log(p)), while the suggested step size shrinks an upper-bound choice toward 1 and may optimally exceed 1.The recommended sample size scales quadratically with the condition number.

4 Examples

The paper applies NewSamp's convergence analysis to generalized linear models and linear support vector machines. It gives curvature and regularity conditions for GLMs and identifies smooth-loss and large-support-vector settings where NewSamp is applicable to SVMs.

  • Generalized Linear Models: Generalized linear model maximum likelihood estimation is formulated as minimizing a negative log-likelihood determined by the cumulant generating function.The formulation covers canonical-link GLMs, including ordinary least squares, logistic regression, and Poisson regression.
  • Generalized Linear Models: The GLM gradient and Hessian are available explicitly, and the Hessian is always positive definite because the cumulant-function second derivative is an observation variance.The paper uses these properties to analyze NewSamp on GLM problems.
  • Generalized Linear Models: For GLMs, the stated NewSamp guarantee assumes bounded and Lipschitz-continuous Φ^(2), bounded covariates, a convex parameter set, and constant step size η_t = 1.Under these assumptions, Corollary 4.1 gives a probability guarantee for the NewSamp iterate.
  • Generalized Linear Models: The GLM second-derivative bound is quite loose for Poisson regression because its cumulant generating function grows exponentially.This is identified as a limitation of the stated GLM bound rather than of the model formulation itself.
  • Support Vector Machines: A linear SVM can be trained through a primal margin-maximization problem, with Hinge-p, Huber, or smoothed losses used in the formulation.The paper focuses on Hinge-2 loss and defines support vectors at each iteration.
  • Support Vector Machines: With Hinge-2 loss, the SVM Hessian is normalized by the number of support vectors, and NewSamp applies efficiently when that number is large.The authors note that the Lipschitz condition used by their theorems does not apply to this SVM setting, although they report empirical effectiveness regardless.

5 Experiments

The experiments evaluate NewSamp on logistic regression and SVM, comparing it with classical optimization methods under selected parameter settings. NewSamp consistently performs strongly, outperforming competitors across SVM scenarios while remaining competitive with BFGS for logistic regression.

  • Experimental setup: Experiments evaluate NewSamp on Logistic Regression and Support Vector Machines with quadratic loss.The study uses both real and synthetic datasets and compares NewSamp with several optimization methods.
  • Experimental setup: NewSamp parameters follow the guidelines from Section 3.4, while batch methods use constant step sizes selected for fastest convergence.Stochastic-method parameters are optimized separately.
  • Scope: The experiments use moderate p values so Newton’s Method remains implementable; comparisons become more favorable to NewSamp for larger p.The datasets include UCI real datasets and synthetic Gaussian data.
  • Results: In logistic regression, stochastic algorithms converge quickly initially but slow near the minimizer, while BFGS comes closest to NewSamp.The comparison includes GD, AGD, Newton’s Method, BFGS, L-BFGS, SGD, and AdaGrad.
  • Results: In SVM, Newton’s Method is closest to NewSamp, but NewSamp outperforms its competitors in all scenarios.Figure 2 summarizes performance across datasets, with NewSamp shown in red.

6 Conclusion

The paper proposes NewSamp, a sub-sampling-based second-order method using low-rank Hessian estimation for the regime n ≫ p. Its convergence is composite, and experiments on real and synthetic datasets demonstrate its performance against classical optimization methods.

  • Contribution: NewSamp is a sub-sampling-based second-order method that uses low-rank Hessian estimation.The method targets settings where n is much larger than p.
  • Contribution: NewSamp has O(np + |S|p2) complexity per iteration, with |S| denoting the sample size.This complexity is substantially tied to the sampled Hessian rather than the full second-order calculation.
  • Convergence: For two widely used sub-sampling schemes, NewSamp starts with quadratic convergence and transitions to linear convergence near the optimum.The conclusion describes this as a composite convergence rate.
  • Evaluation: Numerical experiments on real and synthetic datasets compare NewSamp with classical optimization methods and demonstrate its performance.

A Proofs of Theorems and Lemmas

The appendix develops concentration and convergence arguments for sub-sampled Hessian updates, using matrix inequalities and assumptions on the optimization problem. These steps yield probabilistic bounds and parameter choices governing convergence.

  • Convergence control: The governing convergence term is bounded through triangle-inequality and Lipschitz arguments, then controlled with high-probability estimates.The analysis combines these bounds with covering-net arguments for random iterates.
  • Concentration bounds: The proofs use matrix concentration inequalities to control sub-sampled Hessian errors under sampling with or without replacement.Matrix Hoeffding’s inequality handles independent sampling, while Operator-Bernstein bounds are used for sampling without replacement.
  • Parameter selection: The analysis selects parameters so the relevant error term decays at a target rate of O(1/p).The appendix states that the required choice of ϵ produces the desired exponential decay behavior.
  • Probabilistic guarantees: Under the stated assumptions, the update bounds hold with probability at least 1 − e−p in the general sub-sampling setting.A related bound for the governing term is also stated with probability at least 1 − 2/p.
  • Applications: For logistic-regression-type losses, the assumptions are verified using bounds involving the data norm, Lipschitz constants, and the sub-sample size.The proof then applies the main convergence theorem.

B Properties of composite convergence

The appendix analyzes NewSamp’s composite convergence by measuring the ℓ2 distance between the current iterate and the optimum. This distance is modeled as the sum of linearly and quadratically converging terms.

  • Composite convergence: NewSamp’s composite convergence bounds the ℓ2 distance to the optimum by the sum of a linear term and a quadratic term.
  • Notation: The distance variable ∆t denotes the ℓ2 distance from the iteration-t point to the optimum.The appendix introduces this quantity to study the composite convergence rate.

B.1 Local asymptotic rate

The local analysis shows that composite convergence is eventually governed by its linear term once the initial point lies within the stated basin.

  • An initial distance Δ0 < (1 − ξ1)/ξ2 ensures convergence to the minimizer.The proof establishes that Δt → 0 under this condition.
  • As the iterate approaches the minimizer, the linear term dominates the composite convergence rate.The nonlinear contribution becomes sufficiently small for large t.
  • The proof concludes by taking the limit of the resulting recursion.

B.2 Number of iterations

The iteration analysis splits composite convergence into quadratic and linear regimes, then combines their bounds and minimizes the resulting upper bound over an admissible threshold.

  • The total iteration count matters because total complexity combines iterations with per-iteration cost.
  • The initial-distance condition defines an admissible interval for the tolerance threshold δ.The condition is Δ0 < (1 − ξ1)/ξ2.
  • The total number of iterations needed to reach tolerance ϵ is upper bounded by T(δ*), after minimizing T(δ) over the admissible set.
  • In the initial regime, the quadratic term dominates with coefficient (ξ1/δ + ξ2).
  • After the transition, the linear term dominates with coefficient (ξ1 + ξ2δ).

C Choosing the step size ηt

The step-size analysis uses the convergence-rate expression and eigenvalue information already computed by NewSamp to construct an adaptive, near-optimal step size without forming the full Hessian.

  • The proposed adaptive procedure addresses step-size selection when the dataset is too large to test many candidate values.
  • The convergence rate is governed by a quantity whose first component can be optimized over ηt.
  • For Newton’s method, the corresponding convergence-rate quantity equals 1.
  • NewSamp relates the relevant full-Hessian quantity to the leading eigenvalues of Qt because it avoids computing the full Hessian.Full-Hessian computation would cost O(np2).
  • The eigenvalue estimators are corrected according to the sampling behavior and whether p/2 exceeds the rank threshold r.
  • For p/2 > r, the suggested step size uses eigenvalues already computed to construct Qt and is generally larger than 1.

D Further experiments and details

The paper supplements its theoretical analysis with simulations and dataset experiments examining NewSamp’s rank, convergence behavior, and coefficient values across optimization settings.

  • Further experiments: Additional simulations analyze how the rank threshold affects NewSamp using r-spiked models with r = 3, 10, and 20.The r = 3 case was included for comparison, with results summarized in Table 2.
  • Further experiments: In logistic regression, stochastic algorithms converge quickly at first but slow near the minimizer, while BFGS and LBFGS approach NewSamp most closely.For r = 20, BFGS and NewSamp perform similarly, although NewSamp remains better.
  • Further experiments: In SVM optimization, Newton’s method is the closest competitor to NewSamp.
  • Useful lemmas: The supplementary lemmas establish covering and matrix-concentration tools used in the theoretical analysis.
  • Further experiments: Figure 3 plots elapsed seconds against the log ℓ2-distance to the true minimizer, with NewSamp shown in red.
  • Further experiments: Figure 4 examines the coefficients ξ1 and ξ2 across datasets.
Loading 1508.02810v2…