Composite Generalized Smooth Minimization
Descriptions may be stale. Consult the linked Lean sources.
Composite Generalized Smooth Minimization
We minimize
More precisely, define
Our assumptions:
Assumption 1 (Convexity and feasibility). The set
Assumption 2 (Generalized smoothness). The function
Assumption 3 (Solution and initial bounds). There
exists
Assumption 4 (Oracle access). The gradient oracle
returns
Gradient, subgradient, and projection calls are counted separately.
Oracle randomness may be dependent across calls, and subgradient replies
may depend on the query history; the algorithm’s randomness is
independent of the oracle’s randomness. After the allotted calls, the
output must satisfy
Results
Minimize
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GeneralizedGradientSliding
(Ours) |
Total: Gradients: |
||
| (2) Gradient sliding
(Lan 2016),
Cor. 1(a), arXiv v2. Derived bound: finite-dimensional localization to
|
Total: Gradients: Uses |
(1): gradient saving
|
(1): extra |
| (3) Normalized
subgradient (Grimmer
2019), Thm. 2, arXiv v3. Derived bound, |
Total and gradients: Includes |
(1): gradients |
(1): updates additionally
need |
Abbr: