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,
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
Proved result
OracleTemplate.Convergence LongTails.Setups.BoundedScalarConvex.spec OracleTemplate.BoundedScalarConvex.budgetRelevant previous results
- Angelia Nedić and Soomin Lee. On Stochastic Subgradient
Mirror-Descent Algorithm with Weighted Averaging. 2014; consulted
2013 preprint v1. Complexity:
fixed stochastic subgradient calls for expected objective gap , using Euclidean mirror descent with weighted averaging. Here is the feasible-set diameter, bounds mean subgradients, and bounds conditional error second moments; on , and .