Neue Erkenntnisse: SGD mit gieriger Schrittweite konvergiert schneller

Ein neues arXiv‑Papier liefert einen wichtigen Durchbruch in der Analyse von SGD mit gieriger Schrittweite. Die Autoren untersuchen die letzte Iteration bei glatten quadratischen Funktionen im Interpolationsregime – ein Szenario, das den klassischen Randomized Kaczmarz‑Algorithmus sowie weitere beliebte lineare Gleichungslöser umfasst. Sie zeigen, dass die t‑te Iteration eine Konvergenzrate von O(1/t^{3/4}) erreicht, was die bisherige Schranke von O(1/t^{1/2}) von Attia, Schliserman, Sherman und Koren deutlich verbessert. Im Beweis führen die Forscher die Familie stochastischer Kontraktionsprozesse ein, deren Verhalten durch die Entwicklung einer deterministischen Eigenwertgleichung beschrieben wird. Durch eine sorgfältige diskrete‑zu‑kontinuierliche Reduktion wird die Gleichung analysiert und die neue Rate bewiesen.