Generalized Smoothness with Hessian-Vector Oracles
Descriptions may be stale. Consult the linked Lean sources.
Generalized Smoothness with Hessian-Vector Oracles
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Generalized smoothness). The function
Assumption 2 (Lower bound and initial gap). There
exists
Assumption 3 (Stochastic gradient and Hessian-vector
access). There exist a probability measure
Queries may use any
Results
On Euclidean
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GuardedAffineHessianTransport
(Ours) |
|||
| (2) RanSOM-E (Chayti and Fakhouri 2026), Theorem B.24, Remark B.26 | As |
(1): for |
(1) adds logarithmic
overhead and a large |
| (3) RanSOM-E (Chayti and
Fakhouri 2026), Remark B.26, |
Derived bound, including batches: |
(1): No established improvement in this regime. | (1): when |
| (4) RanSOM (Chayti and Fakhouri 2026), Corollary 4.8 / B.27 | Special case |
(1): Scope extends to generalized curvature and affine noise through guarded localization in expectation. Matches the accuracy exponent on the common setup. | (1): extra |
| (5) NSGD-Hess (Fradin et al. 2026), Theorem 5.1 | Special case |
(1): removes Lipschitz-Hessian regularity, weakens operator-norm moments to directional HVP moments, and permits generalized curvature and affine noise. Matches the leading accuracy exponent on the overlap. | (1): extra logarithms and
|
| (6) HystereticAffineHessianTransport
(Ours) |
|||
| (7) RanSOM-E (Chayti and Fakhouri 2026), Theorem B.24, Remark B.26; derived accuracy exponents | (6): Relative to (1): linear |
(6): extra logarithm and
large |
|
| (8) RanSOM (Chayti and
Fakhouri 2026), Corollary 4.8 / B.27; |
(6): Scope extends to generalized curvature and affine noise. | (6): extra log. If |
|
| (9) RanSOM-E (Chayti and
Fakhouri 2026), Remark B.26; |
(6): matches polynomial
accuracy dependence. Relative to (1), removes
accuracy-dependent localization overhead when |
(6): retains logarithm,
|
Abbr: HVP: Hessian-vector product; norms are
Euclidean or their induced operator norms.