← All setups

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 f:E→R on a real Hilbert space E. Its gradient is bounded by M>0, and it is τ-quasar-convex about a global minimizer x⋆, where τ∈(0,1]. A given point x0∈E satisfies ∥x0−x⋆∥≤R, where R≥0. The oracle returns the exact function value and a gradient perturbed by successive differences of a fixed vector sequence bounded by B≥0 and starting at zero. For ε>0, the goal is an output x¯∈E with f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, M, B, R, τ, ε, and x0.

Our assumptions:

Assumption 1 (Bounded gradient). The function f is Fréchet differentiable everywhere on E, with ∥∇f(x)∥≤M,x∈E.

Assumption 2 (Quasar-convexity and initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R, and f is τ-quasar-convex about this minimizer: τ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩,x∈E.

Assumption 3 (Signed-bias oracle). There is a fixed deterministic sequence (bk)k≥0 in E satisfying b0=0,∥bk∥≤Bfor every k≥0. On call k+1, for k≥0, a query at any x∈E returns (f(x),∇f(x)+bk+1−bk).

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

On a real Hilbert space, f is everywhere differentiable, ∥∇f(x)∥≤M, and a global minimizer x⋆ satisfies ∥x0−x⋆∥≤R and τ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for every x. Here M,ε>0, B,R≥0, and 0<τ≤1. Call k returns (f(x),∇f(x)+bk+1−bk) for one fixed, query-independent sequence with b0=0 and ∥bk∥≤B. The target is f(x^)−f(x⋆)≤ε almost surely under any seed law; (1) returns the best-valued queried iterate and succeeds for every seed.

Comparison for QuasarSignedBias.
Result Oracle complexity Novelty Limitations
(1) QuasarSignedBias (Ours) (review) O(1+R2M(M+B)τ2ε2) value-and-corrupted-gradient calls.
(2) (Jin 2020), Thm. 5.1; special case B=0, E=Rd O(1+R2G2τ2ε2) unbiased gradient calls; expected mean gap ≤ε. Deterministically G=M; exact values select the best iterate at the same total order. (1): Matches known rate at B=0. Scope: telescoping bias and Hilbert spaces; the argument for (2) is dimension-free. (1) needs exact values and excludes stochastic gradient noise permitted by (2).
(3) Derived bound, (Karimireddy et al. 2019), App. B.6; convex f, E=Rd O(1+R2M(M+B)ε2) corrupted-subgradient calls; averaged output. Deterministic subgradients bounded by M, residual ∥ek∥≤ηB, e0=0. (1): Scope extends convexity to quasar-convexity. Matches known rate for convex f, τ=1; formalizes the transferred virtual-iterate bound. (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 f, E=Rd O(1+R2σ2ε2(1+1−δδ)) stochastic subgradient calls and compressor applications; expected averaged gap ≤ε. Unbiased subgradients; δ-contractive compression. (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: M: gradient bound; B: cumulative-bias bound; R: initial distance bound; τ: quasar parameter; ε: objective accuracy; η: constant step size; ek: error-feedback residual. In (2), E∥g∥2≤G2; in (4), E∥g∥2≤σ2, 0<δ≤1, and ∥C(v)−v∥2≤(1−δ)∥v∥2.

Jin, Jikai. 2020. On the Convergence of First Order Methods for Quasar-Convex Optimization. https://doi.org/10.48550/arXiv.2010.04937.
Karimireddy, Sai Praneeth, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. 2019. “Error Feedback Fixes SignSGD and Other Gradient Compression Schemes.” In Proceedings of the 36th International Conference on Machine Learning, edited by Kamalika Chaudhuri and Ruslan Salakhutdinov, vol. 97. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v97/karimireddy19a.html.

Lean setup