← All setups

Bounded Scalar Convex — Bounded Scalar Convex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Bounded Scalar Convex Optimization · Lean proof

Bounded Scalar Convex Optimization

We consider minimizing a convex, H-Lipschitz function f:R→R on C=[a,b], where a≤b and H>0. A given point x0∈C lies within distance R≥0 of a minimizer x⋆∈C. The oracle returns a random scalar bounded in absolute value by H, whose conditional mean given past oracle randomness is a subgradient on C; replies may be dependent. For ε>0, the goal is a measurable, always feasible output x¯ with integrable objective gap and EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Cf(x). The algorithm receives a,b,H,R,ε, and x0, with the parameter ranges given above. Its randomness is independent of the oracle randomness.

Our assumptions:

Assumption 1 (Convexity and Lipschitz continuity). For every x,y∈C and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),|f(x)−f(y)|≤H|x−y|.

Assumption 2 (Initial distance). There exists x⋆∈C such that f(x⋆)≤f(x)for every x∈C,|x0−x⋆|≤R.

Assumption 3 (Bounded conditional subgradients). Let ξ=(ξn)n≥0 denote the oracle’s random samples with joint law ν, and let Fn=σ(ξ0,…,ξn−1). At call n, the scalar reply has the form Gn(h,x,ξn), where h∈(R×R)n is a history of query–reply pairs and x∈R is the query. For each n, the map Gn is jointly measurable in its history, query, and sample arguments.

For every Fn-measurable history hn and every Fn-measurable query Xn taking values in C for every realization, define gn=Gn(hn,Xn,ξn),sn=Eν[gn∣Fn]. These replies satisfy |gn|≤Hν-a.s.,f(Xn)+sn(y−Xn)≤f(y)for all y∈C,ν-a.s. The second inequality holds simultaneously for every y∈C outside a single null set for each choice of n,hn,Xn. The bound on gn ensures its integrability.

The oracle is defined for real queries; its boundedness and conditional subgradient guarantees apply to queries in C. After the allotted oracle calls, the output x¯ must be measurable and belong to C for every realization. Its objective gap must be integrable under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Proved result

max{1,⌈25⋅H2⋅R2ε2⌉+}

OracleTemplate.Convergence LongTails.Setups.BoundedScalarConvex.spec OracleTemplate.BoundedScalarConvex.budget

Relevant previous results

  • Angelia Nedić and Soomin Lee. On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging. 2014; consulted 2013 preprint v1. Complexity: O(1+D2(C2+ν2)/ε2) fixed stochastic subgradient calls for expected objective gap ≤ε, using Euclidean mirror descent with weighted averaging. Here D is the feasible-set diameter, C bounds mean subgradients, and ν2 bounds conditional error second moments; on [lower,upper]∩[x0−R,x0+R], D≤2R and C,ν≤H.