Source-linked AI summary
Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
Peng Xu, Fred Roosta, Michael W. Mahoney
TL;DR
The paper addresses non-convex optimization when Hessian information and subproblem solutions are approximate, especially in large-scale finite-sum problems. It analyzes trust-region and cubic-regularization variants under relaxed inexact-Hessian conditions and develops randomized sub-sampling constructions. The resulting methods retain the exact variants’ worst-case second-order iteration complexity, while cubic regularization requires a fixed, potentially strict Hessian tolerance.
Problem
Large-scale non-convex optimization makes Hessian operations and exact subproblem solutions costly, motivating methods that use approximations without losing iteration-complexity guarantees.
Method
The paper analyzes trust-region and adaptive cubic-regularization methods with inexact Hessians and approximate subproblem solutions, then constructs finite-sum Hessian approximations through uniform and non-uniform randomized sub-sampling.
Results
The proposed algorithms match the exact variants’ worst-case iteration complexity for approximate second-order criticality, including finite-sum methods using appropriate Hessian sub-sampling.
Takeaways & Limitations
Relaxed Hessian conditions permit theoretically guaranteed randomized approximate-Hessian constructions for non-convex finite-sum trust-region and cubic-regularization methods.
Takeaways & Limitations
Adaptive cubic regularization lacks convergence guarantees with adaptive Hessian tolerance and therefore requires a fixed tolerance ε ∈ O(√εg, εH), which can be computationally unattractive.
Abstract
from arXiv · showhide
We consider variants of trust-region and cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under mild conditions on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve $ ε$-approximate second-order optimality which have shown to be tight. Our Hessian approximation conditions constitute a major relaxation over the existing ones in the literature. Consequently, we are able to show that such mild conditions allow for the construction of the approximate Hessian through various random sampling methods. In this light, we consider the canonical problem of finite-sum minimization, provide appropriate uniform and non-uniform sub-sampling strategies to construct such Hessian approximations, and obtain optimal iteration complexity for the corresponding sub-sampled trust-region and cubic regularization methods.
1 Introduction
The paper develops trust-region and cubic-regularization methods for large-scale non-convex optimization using inexact Hessians and approximate subproblem solutions. It establishes relaxed Hessian conditions, extends them to randomized finite-sum settings, and preserves the exact methods’ second-order iteration complexity.
- Motivation: Trust-region and cubic-regularization methods are studied as Newton-type approaches for smooth, non-convex problems where exact Hessian operations can be inefficient at scale.The motivation is to reduce iteration costs through suitable gradient or Hessian approximations while maintaining iteration complexity.
- Inexact Hessian framework: The proposed inexact-Hessian conditions are weaker than many existing conditions and support a priori construction through randomized numerical linear algebra techniques.The paper presents these conditions as enabling practical approximate-Hessian constructions with theoretical guarantees.
- Finite-sum optimization: For finite-sum minimization, uniform and non-uniform Hessian sub-sampling schemes address Hessian operations that are computational bottlenecks when n ≫ 1.The resulting trust-region and cubic-regularization variants have theoretical convergence guarantees for non-convex finite-sum problems.
- Scope of optimality: Approximate (εg, εH)-optimality does not necessarily imply closeness to a local minimum unless additional strict-saddle structure is assumed.Under the strict-saddle property, sufficiently small tolerances guarantee vicinity to a local minimum.
- Convergence results: The inexact-Hessian algorithms achieve the same worst-case iteration complexity for approximate second-order criticality as their exact-Hessian counterparts.The paper also reports optimal iteration complexities for the sub-sampled finite-sum variants.
2 Algorithms and Convergence Analysis
The paper analyzes trust-region and cubic-regularization methods using inexact Hessians and approximate subproblem solutions under standard Hessian regularity. It establishes optimal termination complexity and explains how adaptive tolerances and relaxed conditions support practical approximations.
- Algorithmic framework: The proposed trust-region and adaptive cubic-regularization algorithms incorporate inexact Hessian information to obtain (εg, εH)-optimal solutions.Both methods are analyzed for generic non-convex optimization under the paper’s inexact-Hessian framework.
- Assumptions and limitations: The Hessian regularity assumption is weaker than global Hessian Lipschitz continuity, but the paper notes that the latter is currently the only practical sufficient verification condition known.The analysis assumes bounded and Lipschitz continuous Hessian behavior along the piece-wise linear path generated by the iterates.
- Algorithmic framework: Approximate subproblem solutions use Cauchy and Eigen directions instead of requiring exact minimization.A two-dimensional reduced subspace containing these directions can provide an approximate solution satisfying the required conditions.
- Trust-region convergence: Theorem 1 states that the inexact-Hessian trust-region method achieves optimal worst-case iteration complexity and terminates with (ǫg, ǫT + ǫH)-optimality.The result matches the optimal iteration complexity previously obtained in the literature.
- Trust-region convergence: The trust-region method allows per-iteration Hessian tolerance ǫt ≤ O(max{ǫH, ∆t}), while guaranteeing the trust-region radius does not become too small.Crude approximations are permitted when ∆t is large, with accuracy becoming order ǫH near optimality.
- Cubic-regularization convergence: The adaptive cubic-regularization method achieves optimal iteration complexity under Conditions 3 and 4, with termination satisfying (ǫg, ǫ + ǫH)-optimality.Condition 4 permits cruder subproblem solutions when the gradient is large and uses step length to determine inexactness near saddle points.
3 Finite-Sum Minimization
The paper applies relaxed inexact-Hessian requirements to large-scale finite-sum minimization, using uniform and non-uniform random sampling to reduce Hessian costs while retaining probabilistic convergence guarantees.
- Approximate Hessian construction: Random sampling constructs approximate Hessians that probabilistically satisfy the paper’s relaxed inexact-Hessian condition.The construction uses randomized matrix approximation techniques and supports a priori guarantees.
- Motivation: Finite-sum problems make Hessian evaluations and matrix-vector products computational bottlenecks when n and d are large.The paper targets settings where n ≫ 1 and Hessian operations dominate subproblem costs.
- Computational benefit: Subsampling offers significant computational savings when the sample size is much smaller than n.The approximate Hessian is formed from randomly selected component contributions according to a prescribed distribution.
- Uniform sampling: Uniform sampling provides a probabilistic sample-size guarantee under bounded component Hessians and uniform index selection.Lemma 16 applies when the component Hessians satisfy the stated global bounds and indices are sampled with or without replacement.
- Non-uniform sampling: Non-uniform sampling can require smaller samples than uniform sampling, especially when component Hessian bounds are highly skewed.The advantage is characterized through bK, which can be much smaller than Kmax, and the resulting approximation satisfies Condition 1 probabilistically.
- Convergence analysis: The subsampled trust-region and cubic-regularization methods achieve probabilistic approximate second-order guarantees with optimal worst-case iteration complexity.At termination, the gradient norm is at most ǫg and the minimum Hessian eigenvalue is at least −(ǫ + ǫH), with probability 1 −δ.
4 Conclusion
The paper develops efficient trust-region and adaptive cubic-regularization variants for non-convex optimization with approximate subproblems and Hessian information, matching exact-method iteration complexity up to constants.
- Contributions: The proposed variants achieve approximate second-order criticality with iteration complexities matching those of exact variants up to constants.Both subproblem solutions and curvature information are approximated.
- Finite-sum application: Uniform and non-uniform Hessian subsampling provide efficient constructions for large-scale finite-sum optimization.The resulting methods have probabilistically established optimal iteration complexity.
- Scope and limitation: The analysis assumes exact gradient information rather than an approximated gradient.The paper notes that inaccurate gradients could increase total iterations despite reducing per-iteration cost.
- Scope and limitation: The paper focuses on theoretical foundations, while extensive empirical evaluations are given elsewhere.The stated scope is theoretical development of randomized algorithms.
Appendix A: Intrinsic dimension and improving the sampling complexity (24)
The appendix improves the non-uniform sampling complexity by replacing ambient dimension with the intrinsic dimension of a positive semidefinite matrix associated with the Hessian approximation.
- Intrinsic dimension: Intrinsic dimension t(A) = tr(A)/∥A∥ measures how many spectral dimensions of a positive semidefinite matrix are significant.It satisfies 1 ≤ t(A) ≤ rank(A) ≤ d.
- Improved sampling complexity: The non-uniform sampling bound can be improved by replacing dimension d with the intrinsic dimension of AT|B|A.This quantity may be smaller than the ambient dimension and provides a sharper complexity characterization.
- Improved sampling complexity: Lemma 18 establishes the improved non-uniform sampling result using the intrinsic-dimension bound.The proof applies a matrix Bernstein inequality formulated with intrinsic dimension.
Appendix B: Computation of Approximate Negative Curvature Direction
The appendix explains how to compute an approximate negative-curvature direction efficiently using matrix-vector-product methods applied to a shifted positive semidefinite matrix.
- Negative-curvature computation: When λmin(H) ≤ −ǫH, the method seeks a vector u whose curvature under H is sufficiently negative.The target condition is ⟨u, Hu⟩ ≤ −νǫH∥u∥2 for ν ∈ (0, 1).
- Negative-curvature computation: Lanczos and shift-and-invert methods can compute the direction using only matrix-vector products on ˜H = KH − H.With probability 1 −δ, the resulting vector satisfies the required negative-curvature inequality under the stated parameter choice.