Nonconvex Optimization with Heterogeneous Blocks
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Heterogeneous Blocks
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Block smoothness). The function
Assumption 2 (Initial objective gap). There exists
Assumption 3 (Stochastic gradients with blockwise
variance bounds). On call
After the allotted oracle calls, the output
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BlockHeterogeneousSgdUpperBound
(Ours) |
|||
| (2) Scalar-step SGD (Ghadimi and Lan
2013) Derived bound |
(1) replaces |
(1) needs individual block parameters. (2) uses aggregate smoothness and variance bounds and controls the expected squared Euclidean gradient norm. | |
| (3) SignSGD (Tao et al.
2026) Singleton blocks |
(1) covers arbitrary
blocks. For even |
(1) needs individual
|
|
| (4) AdaGrad (Jiang et al.
2025) Singleton blocks |
(1) replaces |
(1) tunes with |
|
| (5) LANTON (Hao et al.
2026) Euclidean-layer specialization |
(1) needs only block
variances. On the overlap, |
(1) gives expected
accuracy for Euclidean blocks. (5) bounds the
time-average of gradient norms with probability at least |
Abbr: