Cover Image

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jacobs, Peter Matthew, Phillips, Jeff M.
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
by: Wang, Jie, et al.
Published: (2024)

Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance
by: Jacobs, Peter Matthew, et al.
Published: (2025)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
by: Buhai, Rares-Darius, et al.
Published: (2024)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
by: Wein, Alexander S.
Published: (2025)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

On the Computational Hardness of Transformers
by: Saha, Barna, et al.
Published: (2026)

Proximity to Losslessly Compressible Parameters
by: Farrugia-Roberts, Matthew
Published: (2023)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
by: Hollender, Alexandros, et al.
Published: (2023)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

Privately Estimating Black-Box Statistics
by: Steinke, Günter F., et al.
Published: (2025)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
by: Rohatgi, Dhruv, et al.
Published: (2025)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
by: Jacot, Arthur
Published: (2025)

Learning Quantum Processes with Quantum Statistical Queries
by: Wadhwa, Chirag, et al.
Published: (2023)

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
by: AbdElhameed, Marwan, et al.
Published: (2024)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

On the Computational Tractability of the (Many) Shapley Values
by: Marzouk, Reda, et al.
Published: (2025)

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
by: Lu, Yiyang, et al.
Published: (2025)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

Computational Complexity Evaluation of Neural Network Applications in Signal Processing
by: Freire, Pedro, et al.
Published: (2022)

Local vs. Global Interpretability: A Computational Complexity Perspective
by: Bassan, Shahaf, et al.
Published: (2024)

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
by: Pedramfar, Mohammad, et al.
Published: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
by: Li, Xiaoyu, et al.
Published: (2025)

Provably Overwhelming Transformer Models with Designed Inputs
by: Stambler, Lev, et al.
Published: (2025)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
by: Hu, Jerry Yao-Chieh, et al.
Published: (2024)

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
by: Liang, Yingyu, et al.
Published: (2024)

Lossless Model Compression via Joint Low-Rank Factorization Optimization
by: Zhang, Boyang, et al.
Published: (2024)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
by: Xu, Ruihan, et al.
Published: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Certifiable Boolean Reasoning Is Universal
by: Li, Wenhao, et al.
Published: (2026)

Hidden costs for inference with deep network on embedded system devices
by: Lee, Chankyu, et al.
Published: (2026)

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
by: Klivans, Adam R., et al.
Published: (2026)

Polyhedral Instability Governs Regret in Online Learning
by: Li, Yuetai, et al.
Published: (2026)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)