Composite Minimization with Gap-Controlled Hessians
Descriptions may be stale. Consult the linked Lean sources.
Composite Minimization with Gap-Controlled Hessians
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). The set
Assumption 2 (Minimizer and initialization). There
exists
Assumption 3 (Feasible Hessian bound). At every
Assumption 4 (Exact proximal access). There is a map
The oracle supports two query types. For a gradient query at
After the allotted calls, the output must satisfy
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) FeasibleGapAccelerated
(Ours) |
|||
| (2) RCSAG (Lobanov et al. 2026), Thm. 9, zero noise | (1) Scope: constrained composite objectives; curvature control only at feasible points, without a stationary unconstrained minimizer. | (1) Extra logarithmic cost on the overlap; requires Hessian regularity instead of a first-order local model. | |
| (3) APG (Lu and Mei 2023), Thms. 1–2 | (1) No function values; explicit gap-curvature budget instead of an enlarged-ball Lipschitz constant. No established rate comparison in shared parameters. | (1) Needs |
Abbr: