Covariance-Controlled Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Covariance-Controlled Smooth Convex Minimization
We minimize a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function
Assumption 2 (Initial distance). There exists
Assumption 3 (Stochastic gradient and covariance).
There are a probability measure
Queries may be made at any point of
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CovarianceAcceleratedHighProbability
(Ours) |
|||
| (2) Clipped accelerated
SMD (Nguyen et al.
2023), Thm. 4.1, |
(1): Statistical cost
|
(1): Deterministic
logarithm |
|
| (3) Derived bound (Zhang et al. 2026),
Thm. 2.2, |
(1): Matches statistical
term; deterministic |
(1): Requires smoothness
and second moments; does not cover nonsmooth objectives or moment orders
|
|
| (4) Clipped SGD (Das et al. 2024), Thm. 3 | As |
(1): Scope: pointwise
variance bounds suffice without a common covariance envelope. On the
overlap, acceleration and confidence coefficient |
(1): Computationally impractical, versus a streaming clipped-gradient implementation. |
Abbr: Costs count all raw stochastic-gradient calls.