Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Arvanitakis, Dionysis, Chatziafratis, Vaggos, Luo, Yiyuan
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Phylogenetic Reconstruction from Sampled Quartets
von: Arvanitakis, Dionysis, et al.
Veröffentlicht: (2026)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
von: Chatziafratis, Vaggos, et al.
Veröffentlicht: (2023)

Welfare Approximation in Additively Separable Hedonic Games
von: Bullinger, Martin, et al.
Veröffentlicht: (2025)

Provable Quantization with Randomized Hadamard Transform
von: Feng, Ying, et al.
Veröffentlicht: (2026)

Weighted Embeddings for Low-Dimensional Graph Representation
von: Bläsius, Thomas, et al.
Veröffentlicht: (2024)

Efficient and Provable Algorithms for Covariate Shift
von: Adil, Deeksha, et al.
Veröffentlicht: (2025)

Dynamic Spectral Clustering with Provable Approximation Guarantee
von: Laenen, Steinar, et al.
Veröffentlicht: (2024)

Provably learning a multi-head attention layer
von: Chen, Sitan, et al.
Veröffentlicht: (2024)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
von: Chowdhury, Agniva, et al.
Veröffentlicht: (2024)

Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
von: White, Nathan, et al.
Veröffentlicht: (2026)

High-Accuracy List-Decodable Mean Estimation
von: Chen, Ziyun, et al.
Veröffentlicht: (2025)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
von: Draganov, Andrew, et al.
Veröffentlicht: (2024)

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

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)

New Bounds for Kernel Sums via Fast Spherical Embeddings
von: Wagner, Tal
Veröffentlicht: (2026)

Active Learning for Decision Trees with Provable Guarantees
von: Moakhar, Arshia Soltani, et al.
Veröffentlicht: (2026)

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect
von: Peng, Dehua, et al.
Veröffentlicht: (2023)

Towards Fair Representation: Clustering and Consensus
von: Chakraborty, Diptarka, et al.
Veröffentlicht: (2025)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

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

Provably Extracting the Features from a General Superposition
von: Liu, Allen
Veröffentlicht: (2025)

High-Dimensional Gaussian Mean Estimation under Realizable Contamination
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2026)

A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
von: Chen, Tyler, et al.
Veröffentlicht: (2025)

Learning Juntas under Markov Random Fields
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

Reliable Learning of Halfspaces under Gaussian Marginals
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2024)

Testable Learning of General Halfspaces under Massart Noise
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2026)

Robust learning of halfspaces under log-concave marginals
von: Lange, Jane, et al.
Veröffentlicht: (2025)

Provably Learning from Modern Language Models via Low Logit Rank
von: Golowich, Noah, et al.
Veröffentlicht: (2025)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
von: Bairaktari, Konstantina, et al.
Veröffentlicht: (2025)

Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2025)

Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
von: Al-Jazzazi, Yousef, et al.
Veröffentlicht: (2025)

A Broader View on Clustering under Cluster-Aware Norm Objectives
von: Herold, Martin G., et al.
Veröffentlicht: (2025)

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
von: Guo, Anxin, et al.
Veröffentlicht: (2024)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
von: Makarychev, Konstantin, et al.
Veröffentlicht: (2025)

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
von: Chen, Tyler, et al.
Veröffentlicht: (2025)

Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
von: Chae, Woojin, et al.
Veröffentlicht: (2024)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
von: Sakaue, Shinsaku, et al.
Veröffentlicht: (2026)

Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond
von: Takakura, Shokichi, et al.
Veröffentlicht: (2025)

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
von: Chauhan, Rohan, et al.
Veröffentlicht: (2025)