High-Dimensional Blockwise Stochastic Stationarity
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Blockwise Stochastic Stationarity
We seek a stationary point of a differentiable, possibly nonconvex
function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Scale and block dimensions). Write
Assumption 2 (Blockwise quadratic bound and initial
gap). The function
Assumption 3 (Stochastic gradient oracle). At each
query
After the allotted oracle calls, the output
Results
On
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BlockHeterogeneousLowerBound
(Ours) |
|||
| (2) (Arjevani et al. 2022), Thm. 3 and Sec. 1.3 | (1): Equal |
(1) needs the accuracy
and dimension conditions in every block. (2) needs
sufficient dimension and |
|
| (3) (Jiang et al. 2025), Thm. 5 | (1) retains the noiseless
order for every randomized algorithm on high-dimensional blocks. With
noise, its additional term dominates when |
(1) requires large blocks
and small |
|
| (4) AdaGrad (Jiang et al. 2025), Thm. 4 | (1) establishes the same polynomial dependence for arbitrary randomized algorithms and outputs on high-dimensional blocks, matching the block-SGD upper bound there up to constants. | (1) excludes scalar blocks. The AdaGrad-specific lower bound in (4) has an additional logarithmic factor. |
Abbr: