Gradient Descent for Gaussian Recovery
Descriptions may be stale. Consult the linked Lean sources.
Gradient Descent for Gaussian Recovery
We study recovery of two unknown means
Write
Our assumptions:
Assumption 1 (Target geometry). The target means
satisfy
Queries may be made at any
Our result is algorithm-specific: we analyze constant-step gradient
descent. The algorithm chooses an initialization
Define the squared matching error by
Results
Teacher and student are equal-weight, two-component Gaussian mixtures
in
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) UntiedReverseFisherGlobalGD
(Ours) |
Step |
||
| (2) GD (Tyurin 2026),
Cor. 2.5; single teacher ( |
(1): Scope: extends
constant-step GD recovery from |
(1): Logarithmically
worse accuracy term; mirrored random start and one stopping time, versus
arbitrary starts and deterministic accuracy for every |
|
| (3) GD (Tyurin 2026),
Thm. E.1 (explicit Thm. 3.2), |
Large-sphere initialization: Each student reaches squared distance |
(1): Scope: covers |
(1): Only two student and
teacher components; no coverage of |
Abbr: