← All setups

Bounded Scalar Convex Optimization

Descriptions may be stale. Consult the linked Lean sources.

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⋆)]≤ε.

Results

Convex, H-Lipschitz f on C=[lower,upper]⊂R, with H>0, x0∈C, and a minimizer x⋆∈C satisfying |x0−x⋆|≤R, R≥0. Replies are jointly measurable in query and seed; at every query measurable with respect to the revealed-seed past Ft, |gt|≤H almost surely and EP[gt∣Ft]∈∂Cf(xt). No independence is assumed. Target: measurable xout∈C with integrable gap and ∫(f(xout)−f(x⋆))dP≤ε, ε>0. The setup imposes no algorithm restriction; (1) constructs constant-step projected SGD and returns its last iterate.

Comparison for BoundedScalarConvex.
Result Oracle complexity Novelty Limitations
(1) BoundedScalarConvex (Ours) (review) O(1+H2R2/ε2)
(2) Linear-decay SGD (Liu and Zhou 2026, Thm. 3.4, v4) O(1+H2R2/ε2) (1): Matches known rate and last-iterate guarantee; constant-step analysis instead of linear decay. No parameter-knowledge gain. (1) requires scalar, compact domains and bounded replies; (2) allows arbitrary dimension, unbounded domains and finite-variance noise.
(3) Scheduled SGD (Jain et al. 2019, Thm. 1, full version) O(1+H2D2/ε2)
Independent-noise restriction.
(1): R2 instead of D2; factor (D/R)2 when 0<R<D, ε≤HR. Allows adapted replies. (2) already removes diameter dependence. (1) is scalar; (3) allows arbitrary dimension.
(4) Constant-step scalar SGD (Beretta et al. 2026, Thm. 2, Eq. (2), v1) O(1+H2R2/ε2)
Bounded-reply overlap; additive, state-independent i.i.d. noise, L=H, σ≤H.
(1): Matches rate; extends constant-step last-iterate analysis to bounded, history-, state- and time-dependent replies. (1) requires bounded replies and compact intervals; (4) permits unbounded finite-variance noise and unbounded intervals.

Abbr: Costs count stochastic-subgradient calls. D=upper−lower; P is the oracle trajectory law; ∂C denotes relative subgradients. In (4), L is the Lipschitz bound and σ2 bounds noise variance.

Beretta, Guglielmo, Tommaso Cesari, Roberto Colomboni, and Andrea Paudice. 2026. New Bounds for the Last Iterate of the Stochastic subGradient Method. https://arxiv.org/abs/2606.24879v1.
Jain, Prateek, Dheeraj Nagaraj, and Praneeth Netrapalli. 2019. “Making the Last Iterate of SGD Information Theoretically Optimal.” In Proceedings of the Thirty-Second Conference on Learning Theory, edited by Alina Beygelzimer and Daniel Hsu, vol. 99. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v99/jain19a.html.
Liu, Zijian, and Zhengyuan Zhou. 2026. Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. https://arxiv.org/abs/2312.08531v4.

Lean setup