Reproduce “Computing Approximate $\ell_p$ Sensitivities” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Swati Padmanabhan, David P. Woodruff, Qiuyi Zhang

Researchers from MIT, CMU, and Google developed efficient approximation algorithms for computing ℓp sensitivities of matrices, along with methods for estimating total and maximum ℓp sensitivities. Their approach reduces the computational cost of sensitivity estimation from individual per-row calculations to more efficient probabilistic approximations, demonstrating practical speedups and improved accuracy-runtime trade-offs on real-world datasets.

Key insights

  • Computing (1+ε)-approximate ℓp sensitivities is computationally equivalent to solving multiple ℓp regression problems, establishing a lower bound on complexity for highly accurate results.
  • ℓp subspace embeddings are crucial for reducing the effective row dimension of matrices, making subsequent sensitivity computations tractable and efficient.
  • Real-world datasets often exhibit lower intrinsic effective dimensionality, leading to smaller total ℓp sensitivities than theoretical worst-case bounds, which can be exploited for improved practical performance.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.