Known-Value Convex Local Linear Optimization
Descriptions may be stale. Consult the linked Lean sources.
Known-Value Convex Local Linear Optimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Feasible set). The set
Assumption 2 (Convexity and quadratic upper model).
The function
Assumption 3 (Known minimum and initial distance).
There exists
The oracle supports two types of queries. At
After the allotted calls, the output must satisfy
Results
A real Hilbert space, a closed convex set
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) SplitBroxKnownValue
(Ours) |
|||
| (2) BroxGD (Richtárik et al. 2026, Thm. 3.2(ii), Cor. D.2) | (1): factor |
(1) needs exact |
|
| (3) Polyak-radius BroxGD (Richtárik et al. 2026, Thm. 3.5, Eq. (24)) | (1): |
(1) needs |
|
| (4) APMM (Deng et al. 2026, Alg. 1,
Thm. 2.1); |
(1) matches the accelerated order using point-only local LMOs, with no logarithmic search overhead. Different oracles prevent a direct cost comparison. | (1) needs |
|
| (5) CGS (Lan and Zhou 2016, Cor. 3, 2014
preprint); special case: bounded |
(1): for |
(1) needs |
Abbr: LMO: linear minimization oracle; local LMO:
one point minimizing a linear function on