Covariance-Bounded Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Covariance-Bounded Convex Minimization
We consider minimizing a convex,
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and Lipschitz continuity).
For every
Assumption 2 (Bounded minimizer). There exists
Assumption 3 (Stochastic subgradients and
covariance). There exist a probability measure
Queries may be made at any point of
Results
Convex, globally
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CovarianceSoftCutConvex
(Ours) |
|||
| (2) (Marsden et al. 2025, Cor. 3, v1); special case: directional exponential tails | (1): directional second moments replace exponential tails; includes finite-variance noise without third moments. Matches polynomial rate on the exponential-tail subclass. | (1): explicit |
|
| (3) (Marsden et al. 2025, Cor. 4, v1); trace-bounded noise | (1): noise term |
(1) needs directional
covariance bound; trace bound alone is insufficient. Anisotropic
covariance |
|
| (4) SGD (Marsden et al. 2025, secs. 1, v1); expected-gap bound plus Markov | (1): deterministic term
|
(1): noise logarithms,
directional covariance restriction, exact centroids; worse when |
Abbr: