High-Dimensional Stationarity with Separable Noise
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Stationarity with Separable Noise
We seek a stationary point of a differentiable, possibly nonconvex
objective
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Stochastic gradients with separable
noise). On call
After the allotted oracle calls, the output
Results
On
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) SeparableNoiseLinfSmoothLowerBound
(Ours) |
Lower bound: |
||
| (2) SignSGD (Tao et al. 2026, Thm. 2) | Lower bound: |
(1) extends hardness to every randomized method and arbitrary output. Under the stated dimension and gap conditions, minibatch SignSGD attains the pointwise-noise minimax rate up to constants. | (2) uses fixed coordinate
caps |
| (3) Euclidean stationarity (Arjevani et al. 2022, Thm. 3, Eq. (23)) | Lower bound: |
(1) transfers Euclidean
hardness to |
(1) covers gradient-only access and requires a larger dimension. (3) allows exact values with each noisy gradient. The geometries preclude direct rate comparison. |
| (4) Matrix stationarity (Zhang and Lin 2026, Thm. 3.1) | Lower bound at |
(1) treats vector separable noise. (4) uses spectral-to-nuclear smoothness and nuclear-norm noise and stationarity. Rates are incomparable. | (1) requires finite
variances. (4) covers |
| (5) Matrix stationarity (Hübler et al. 2026, Thm. 3.7) | Lower bound at |
(1), (5): rates are incomparable under separable vector noise and nuclear-norm matrix noise. | (5) also covers |
| (6) Matrix stationarity (Hübler et al. 2026, Thm. E.9) | Lower bound at |
(1) covers unrestricted randomized methods in vector geometry. The matrix rate in (6) is incomparable. | (6) also covers |
Abbr: