Strong-Growth Second-Order Finite-Sum Optimization
Descriptions may be stale. Consult the linked Lean sources.
Strong-Growth Second-Order Finite-Sum Optimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Second-order regularity). Each
component
Assumption 2 (Strong growth). For every
Assumption 3 (Initial objective gap). The given
point
Queries may use any index
After the allotted oracle calls, the required simultaneous accuracy
criterion is
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CoupledCubicStrongGrowth
(Ours) |
|||
| (2) Full-batch cubic regularization, (Shen et al. 2019), Table 1 | (1): removes |
(1): adds strong growth
and RMS Hessian regularity; probability |
|
| (3) STR2 (Shen et al. 2019), Cor. 5.1, Estimator 6 | (1): removes |
(1): adds strong growth;
linear dimension cost can lose when |
|
| (4) PSGD (Roy et al. 2020), Thm. 3.1(a) | Gradient-only oracle; half the iterates
satisfy second-order accuracy with probability |
(1): selected certified output instead of an unselected collection; drops population gradient smoothness and relative sub-Gaussian tails. | (1): requires component
Hessians and RMS Hessian regularity; fixed confidence instead of
adjustable |
Abbr: