Quasar-Convex Minimization with Signed Bias
Descriptions may be stale. Consult the linked Lean sources.
Quasar-Convex Minimization with Signed Bias
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Bounded gradient). The function
Assumption 2 (Quasar-convexity and initial
distance). There exists
Assumption 3 (Signed-bias oracle). There is a fixed
deterministic sequence
After the allotted oracle calls, the output must satisfy
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) QuasarSignedBias (Ours) (review) | |||
| (2) (Jin 2020), Thm. 5.1;
special case |
(1): Matches known rate
at |
(1) needs exact values and excludes stochastic gradient noise permitted by (2). | |
| (3) Derived bound, (Karimireddy et al.
2019), App. B.6; convex |
(1): Scope extends
convexity to quasar-convexity. Matches known rate for convex |
(1) requires differentiability and exact values; best-iterate selection replaces averaging without improving the guarantee. | |
| (4) EF-SGD (Karimireddy et al.
2019), Thm. III; convex |
(1): Scope permits nonconvex quasar-convex objectives and bounded telescoping bias without a compressor. No rate improvement established; arbitrary bias and compressor-generated errors are not generally comparable. | (1) requires exact values, differentiability, deterministic errors and query-independent cancellation; no concrete application of this exact error model is established. |
Abbr: