Buchumschlag

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Peng, Dehua, Gui, Zhipeng, Wu, Huayi
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Machine Learning Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

On the Distance from Calibration in Sequential Prediction
von: Qiao, Mingda, et al.
Veröffentlicht: (2024)

Computational and Statistical Hardness of Calibration Distance
von: Qiao, Mingda
Veröffentlicht: (2026)

An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration
von: Arunachaleswaran, Eshwar Ram, et al.
Veröffentlicht: (2024)

Efficient Certificates of Anti-Concentration Beyond Gaussians
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2024)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
von: Rapoport, Emma, et al.
Veröffentlicht: (2025)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
von: Gao, Jie, et al.
Veröffentlicht: (2025)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
von: Silwal, Sandeep, et al.
Veröffentlicht: (2025)

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
von: Arvanitakis, Dionysis, et al.
Veröffentlicht: (2026)

Approximating the Total Variation Distance between Gaussians
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2024)

Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance
von: Wirth, Leoni Carla, et al.
Veröffentlicht: (2025)

On Computing Total Variation Distance Between Mixtures of Product Distributions
von: Feng, Weiming, et al.
Veröffentlicht: (2026)

Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
von: Peng, Pan, et al.
Veröffentlicht: (2025)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
von: Tong, Guangmo, et al.
Veröffentlicht: (2024)

Learning-Augmented Streaming Algorithms for Correlation Clustering
von: Dong, Yinhao, et al.
Veröffentlicht: (2025)

Average Sensitivity of Hierarchical $k$-Median Clustering
von: Li, Shijie, et al.
Veröffentlicht: (2025)

Calibration Error for Decision Making
von: Hu, Lunjia, et al.
Veröffentlicht: (2024)

Towards Optimal Robustness in Learning-Augmented Paging
von: Chen, Peng, et al.
Veröffentlicht: (2026)

Faster Graph Embeddings via Coarsening
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2020)

Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
von: Chen, Peng, et al.
Veröffentlicht: (2025)

Near-optimal Swap Regret Minimization for Convex Losses
von: Hu, Lunjia, et al.
Veröffentlicht: (2026)

The Cost of Parallelizing Boosting
von: Lyu, Xin, et al.
Veröffentlicht: (2024)

A Perfectly Truthful Calibration Measure
von: Hartline, Jason, et al.
Veröffentlicht: (2025)

Smooth Calibration and Decision Making
von: Hartline, Jason, et al.
Veröffentlicht: (2025)

Optimal Clustering with Dependent Costs in Bayesian Networks
von: Wu, Paul Pao-Yen, et al.
Veröffentlicht: (2023)

Truthful Calibration Errors for Multi-Class Prediction
von: Lu, Yuxuan, et al.
Veröffentlicht: (2025)

Efficient Diffusion Models for Symmetric Manifolds
von: Mangoubi, Oren, et al.
Veröffentlicht: (2025)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
von: Greenhut, Daniel, et al.
Veröffentlicht: (2025)

Improved Approximations for Hard Graph Problems using Predictions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Learning-Augmented Frequent Directions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
von: John, Philips George, et al.
Veröffentlicht: (2024)

Adversarial Attacks on Combinatorial Multi-Armed Bandits
von: Balasubramanian, Rishab, et al.
Veröffentlicht: (2023)

Hardness of High-Dimensional Linear Classification
von: Munteanu, Alexander, et al.
Veröffentlicht: (2026)

GPU Memory Usage Optimization for Backward Propagation in Deep Network Training
von: Hong, Ding-Yong, et al.
Veröffentlicht: (2025)

Towards counterfactual fairness through auxiliary variables
von: Tian, Bowei, et al.
Veröffentlicht: (2024)

Differential privacy from axioms
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Weak to Strong Learning from Aggregate Labels
von: Makhija, Yukti, et al.
Veröffentlicht: (2024)

Differentially Private Learning Beyond the Classical Dimensionality Regime
von: Dwork, Cynthia, et al.
Veröffentlicht: (2024)

Better Models and Algorithms for Learning Ising Models from Dynamics
von: Gaitonde, Jason, et al.
Veröffentlicht: (2025)