Composite Minimization with Gap Smoothness
Descriptions may be stale. Consult the linked Lean sources.
Composite Minimization with Gap Smoothness
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and differentiability). The
function
Assumption 2 (Minimizer and initialization). There
exists
Assumption 3 (Gap-dependent upper model). For every
Assumption 4 (Exact proximal access). There is a map
The oracle returns
After the allotted calls, the output must satisfy
Results
In a real Hilbert space
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CompositeGapAccelerated
(Ours) |
|||
| (2) RCSAG (Lobanov et al. 2026), Thm. 9, noise-free specialization | (1): Scope extends to
nonsmooth composite objectives and constraints, including |
(1): Extra logarithmic
factors on the smooth overlap, including the restart logarithm on |
|
| (3) (LongTails 2026), repository result | (1): Total-gap curvature
replaces gradient-norm curvature; no |
||
| (4) Derived bound: Moreau smoothing + (Lobanov et al. 2026), Thm. 9 | (1): Removes |
(1): Extra logarithms.
General total rates are not comparable without control of |
|
| (5) (Lobanov 2026), Thm. 5 | (1): Extends to composite
constraints; needs only initial-distance radius |
(1): Extra logarithmic
factors when |
Abbr: