Capped Hessian-Similar Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Capped Hessian-Similar Convex Minimization
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and strong
convexity). Each
Assumption 2 (Mean-square similarity). Define
Assumption 3 (Initial objective gap). There exists
Oracle access is organized into capped calls. A call selects a set
After the allotted calls, the output
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CappedHessianSimilarAccelerated
(Ours) |
|||
| (2) AccSVRS (Lin et al. 2023), Thm. 3.6 | (1): |
(1) requires convex
clients and exact proximal steps; (2) permits nonconvex
clients and inexact steps. Extra factor |
|
| (3) Derived bound: restarted, batched Acc-S-DANE (Jiang et al. 2024), Thm. 6 | (1): |
(1) needs exact proximal
steps; expected rather than deterministic accuracy. Extra factor |
|
| (4) Catalyst VM-SVRS
(Wang 2026),
Cor. 15; quadratic, individually |
(1): nonquadratic convex
clients; no |
(1) guarantees expected accuracy; (4) guarantees accuracy surely. |
Abbr: