← All setups

Nonconvex Optimization with Mixed Relative Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Mixed Relative Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ for Δ≥0. The oracle returns unbiased stochastic gradients, with second moments controlled by gradient magnitudes and noise increments controlled jointly by gradient magnitudes and query distance. Consecutive pairs of calls share a sample; samples across pairs are independent. For ε>0, the goal is a measurable output x¯∈E with E∥∇f(x¯)∥≤ε, averaging over sampling and algorithm randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Let Ω be a measurable sample space, and let M,r,σ≥0. The algorithm receives E, Ω, L, M, r, σ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Initial objective gap). The given point x0 satisfies f(x0)−f(x)≤Δ,x∈E.

Assumption 3 (Mixed relative noise). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. Define the centered error by e(x,ω)=g(x,ω)−∇f(x). For every x∈E, the random variable ∥e(x,ξ)∥2 is integrable for ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν∥e(x,ξ)∥2≤r∥∇f(x)∥2+σ2. Moreover, for every x,y∈E, the same sample is used in the noise-increment bound Eξ∼ν∥e(x,ξ)−e(y,ξ)∥2≤r(∥∇f(x)∥2+∥∇f(y)∥2)+M2∥x−y∥2.

Queries may be made at any point of E. Let (ξj)j≥0 be measurable, independent random variables with common law ν, independent of the algorithm’s randomness. At call k≥0, a query xk∈E receives g(xk,ξ⌊k/2⌋). Thus calls 2j and 2j+1 use the same sample ξj, including when the second query depends on the first reply. Each evaluation counts as one oracle call.

After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be integrable, and EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the sample sequence and the independent algorithm randomness.

Results

On a second-countable real Hilbert space with its Borel structure, f has L-Lipschitz gradient and f(x0)−inff≤Δ. Parameters L,ε>0 and r,M,σ,Δ≥0 are supplied. The jointly measurable oracle g is unbiased under a probability measure p; e(x,ξ)=g(x,ξ)−∇f(x) has integrable squared norm, with Ep∥e(x,ξ)∥2≤r∥∇f(x)∥2+σ2 and Ep∥e(x,ξ)−e(y,ξ)∥2≤r(∥∇f(x)∥2+∥∇f(y)∥2)+M2∥x−y∥2. IID samples are shared within consecutive call pairs. Target: measurable X with integrable gradient norm and ∫∥∇f(X)∥dP≤ε, where P includes sampling and algorithm randomness.

Comparison for MixedRelativeSmoothNonconvex.
Result Oracle complexity Novelty Limitations
(1) MixedRelativeSmoothNonconvex (Ours) (⋆⋆⋆) (review) O(1+(1+r)LΔ+σ2ε2+min{MσΔε3,LΔσ2ε4})
(2) SGD (Khaled and Richtárik 2020), Cor. 1 (A=0, B=1+r, C=σ2). O(1+(1+r)LΔε2+LΔσ2ε4) (1): No worse in order. For ε2<2LΔ, σ2≥(1+r)ε2, Mε≤Lσ, saving factor min{LΔ/ε2,Lσ/(Mε)}. Random-iterate target follows from (2)’s averaged bound. (1) needs the increment condition, shared-sample pairs and known M additionally; O(Td) storage and substantially larger leading constant.
(3) Normalized STORM (Liu et al. 2023), Thm. 3.3 / Cor. 3.4, L1=0. O(1+r+(1+r)L¯Δε2+(σ+rG0)1+rε+L¯σΔε3+σ2(σ+rG0)1+rε3)
Raw MSS; sample-gradient oracles on Rd. Batch size Θ(1+r) included. Target: mintE∥∇f(xt)∥≤ε.
(1): Rate replaces L¯ by centered M, removing σ3/ε3 startup dependence. For r=1, M=0, fixed positive L,L¯,Δ,σ: O(ε−2) versus O(ε−3). Scope includes rough relative noise without finite L¯; identical-output comparison unestablished. (1) uses growing batches and O(Td) storage; (3) has accuracy-independent batches. Generalized L1>0 smoothness is outside (1)’s scope.
(4) PAGE (Li et al. 2021), Cor. 4 (online). O(1+σ2+L¯Δε2+L¯σΔε3)
Expected gradient-call count; r=0, raw MSS, sample-gradient oracles on Rd.
(1): Matches known ε−3 rate at r=0; centered M≤L¯.

Abbr: Δ is the initial objective-gap bound; r,σ are relative and absolute noise parameters; M controls centered increments. Raw MSS means Ep∥g(x,ξ)−g(y,ξ)∥2≤L¯2∥x−y∥2, with L≤L¯ and an admissible M≤L¯. G0=∥∇f(x0)∥≤2LΔ. T counts iterations of (1); d denotes dimension when finite. Costs count individual oracle evaluations, including batches and paired evaluations. In the saving factor, Lσ/(Mε)=+∞ when M=0<σ.

Khaled, Ahmed, and Peter Richtárik. 2020. Better Theory for SGD in the Nonconvex World. https://doi.org/10.48550/arXiv.2002.03329.
Li, Zhize, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. 2021. “PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.” In Proceedings of the 38th International Conference on Machine Learning, edited by Marina Meila and Tong Zhang, vol. 139. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v139/li21a.html.
Liu, Zijian, Srikanth Jagabathula, and Zhengyuan Zhou. 2023. Near-Optimal Non-Convex Stochastic Optimization Under Generalized Smoothness. https://doi.org/10.48550/arXiv.2302.06032.

Lean setup