Bounded Scalar Convex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Bounded Scalar Convex Optimization
We consider minimizing a convex,
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and Lipschitz continuity).
For every
Assumption 2 (Initial distance). There exists
Assumption 3 (Bounded conditional subgradients). Let
For every
The oracle is defined for real queries; its boundedness and
conditional subgradient guarantees apply to queries in
Results
Convex,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BoundedScalarConvex (Ours) (review) | |||
| (2) Linear-decay SGD (Liu and Zhou 2026, Thm. 3.4, v4) | (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) | Independent-noise restriction. |
(1): |
(1) is scalar; (3) allows arbitrary dimension. |
| (4) Constant-step scalar SGD (Beretta et al. 2026, Thm. 2, Eq. (2), v1) | Bounded-reply overlap; additive, state-independent i.i.d. noise, |
(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.