arXiv preprint ·
Wasserstein approximation of measures via orthogonal frames: statistical and computational complexities
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Dimension-reduction methods such as PCA identify a subspace capturing most of the variation in the data, but not a distinguished basis within it. Selecting a basis in which the samples are sparsely represented is a recurring task in unsupervised learning, addressed by methods in factor analysis, dictionary learning, and subspace clustering. We pose this task as Wasserstein approximation of the data distribution by measures supported on the axes of an orthogonal frame, which, in turn, reduces to a nonsmooth optimization problem over the orthogonal group $\mathrm{O}(d)$. We show that, under mild assumptions, both empirical risk minimizers and a locally initialized stochastic gradient method recover the population-optimal frame at the near-parametric rate $\widetilde{O}_d(n^{-1/2})$, where $n$ is the sample size. The main difficulty is that, although the population objective is smooth, the empirical objective is not-this mismatch precludes standard covering arguments. We overcome this issue by replacing Lipschitz continuity of the empirical gradient with a coarsely Lipschitz bound, a tool that may be of independent interest. Numerical experiments support our theoretical findings.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistics Theory
A Simple Presentation of Robust Membership Inference Attacks
Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
Second-order Sinkhorn Geometry and $\sqrt{n}$-Inference
Scalable Bayesian Quadrature via Operator-Adapted Features
Memorization Capacity of Invariant Convolutional Neural Nets
Get the few papers worth your time in Statistics Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.