6 citations · 6 across the 6 of their papers we have counts for
7 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…
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…
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…
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 that…
Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1
A random matrix is an oblivious subspace embedding (OSE) with parameters , and , if for any -dimensional subspace $W\subseteq R…