Parameter-Free Composite Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Parameter-Free Composite Convex Minimization
We consider minimizing
Write
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 point and minimizer). The
given point satisfies
The oracle returns
After the allotted calls, the output must satisfy
Results
Minimize
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BacktrackingCompositeGeneralized
(Ours) |
Gradient and prox calls; all rejected trials included. |
||
(2) Accelerated proximal gradient (Li et al. 2026, Thm. B.1) Twice-differentiable |
Gradient and prox calls; |
(1): Updates need no
|
(1): Roughly threefold
call overhead per accepted step; |
(3) Accelerated GRAAL (Borodich and Kovalev 2025, Cor. 3) Special case: |
Gradient and value calls; requires |
(1): Composite scope; no
values (prox is closed form here); arbitrary |
(1): Constant-factor backtracking overhead. |
(4) AC-FGM (Li and Lan 2024, Cor. 1 and subsequent remark) Initial-search variant; closed convex |
Value, gradient and prox calls, including initialization; initial
curvature estimate |
(1): No function values;
explicit polynomial parameter dependence. Rates are not comparable: no
polynomial bound on |
(1): Repeated backtracking instead of initial search only. |
Abbr: