6 papers
How AI settled the complexity of the oldest SGD algorithm
MichaÅ DereziÅski, Xiaoyu Dong
In 1937, Stefan Kaczmarz proposed a simple algorithm for solving systems of linear equations. This algorithm turned out to be the earliest known example of stochastic gradient desc…
Well-Conditioned Oblivious Perturbations in Linear Space
Shabarish Chenakkod, MichaÅ DereziÅski, Xiaoyu Dong +1
Perturbing a deterministic -dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the co…
Pontryagin's Principle for Leakage-Immune Adiabatic Quantum State Transfer
Xiao-Yu Dong, Xi-Lai Wang, Wen-Long Ma
The standard stimulated Raman adiabatic passage (STIRAP) protocol enables high-fidelity quantum state transfer in an ideal three-level system via adiabatic following of a dark stat…
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
MichaÅ DereziÅski, Xiaoyu Dong
We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algori…
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
Shabarish Chenakkod, MichaÅ DereziÅski, Xiaoyu Dong
We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings, up to sub-polylogarithmic factors: For an…
Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
Shabarish Chenakkod, MichaÅ DereziÅski, Xiaoyu Dong
An oblivious subspace embedding is a random matrix such that, for any -dimensional subspace, with high probability preserves the norms of all vectors in th…