Radius-Constrained Composite Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Radius-Constrained Composite Convex Minimization
We minimize
Writing
Our assumptions:
Assumption 1 (Convexity). The set
Assumption 2 (Generalized smoothness). The function
Assumption 3 (Exact proximal minimization). There is
a map
Assumption 4 (Initial distance and minimizer
gradient). The given starting point satisfies
The oracle returns
After the allotted calls, the output must satisfy
Results
Minimize
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RadiusCompositeAccelerated
(Ours) |
|||
| (2) AGLS (Deng and Gao 2026), Thm. 6.1, Prop. 6.2. | (1): polynomial
dependence on |
(1) needs |
|
| (3) Derived bound (LongTails 2026): prox initialization and gap certificate. | (1): gain when |
(1) adds |
|
| (4) Gap-based acceleration (LongTails 2026). | (1): no initial objective-gap bound is needed. | Small known |
|
| (5) (Rudomanov et al. 2026), Thm. 3.7. | (1): scope extends to constrained composite objectives and minimizers with nonzero smooth-part gradient. | On the overlap, (1) has
|
Abbr: