Buchumschlag

Streaming Attention Approximation via Discrepancy Theory

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kochetkova, Ekaterina, Sheth, Kshiteej, Han, Insu, Zandieh, Amir, Kapralov, Michael
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning Artificial Intelligence 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

SubGen: Token Generation in Sublinear Time and Memory
von: Zandieh, Amir, et al.
Veröffentlicht: (2024)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
von: Indyk, Piotr, et al.
Veröffentlicht: (2025)

Sublinear Time Low-Rank Approximation of Hankel Matrices
von: Kapralov, Michael, et al.
Veröffentlicht: (2025)

Spectral Clustering in Birthday Paradox Time
von: Kapralov, Michael, et al.
Veröffentlicht: (2026)

TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
von: Zandieh, Amir, et al.
Veröffentlicht: (2025)

DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
von: Chee, Jerry, et al.
Veröffentlicht: (2025)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
von: Musco, Cameron, et al.
Veröffentlicht: (2024)

Spectral Clustering with Side Information
von: Fichtenberger, Hendrik, et al.
Veröffentlicht: (2025)

Extremely Simple Streaming Forest
von: Xu, Haoyin, et al.
Veröffentlicht: (2021)

Constructing Decision Trees from Data Streams
von: Pham, Huy, et al.
Veröffentlicht: (2024)

Approximate Lifted Model Construction
von: Luttermann, Malte, et al.
Veröffentlicht: (2025)

Polynomial-Time Approximability of Constrained Reinforcement Learning
von: McMahan, Jeremy
Veröffentlicht: (2025)

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
von: Harris, Blake, et al.
Veröffentlicht: (2024)

Positional Attention: Expressivity and Learnability of Algorithmic Computation
von: de Luca, Artur Back, et al.
Veröffentlicht: (2024)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

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

AlgoSelect: Universal Algorithm Selection via the Comb Operator
von: Yao, Jasper
Veröffentlicht: (2025)

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

Self-Supervised Graph Learning via Spectral Bootstrapping and Laplacian-Based Augmentations
von: Bini, Lorenzo, et al.
Veröffentlicht: (2025)

Differentially Private Kernel Density Estimation
von: Liu, Erzhi, et al.
Veröffentlicht: (2024)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
von: Kannan, Ravindran, et al.
Veröffentlicht: (2024)

Limits of Approximating the Median Treatment Effect
von: Addanki, Raghavendra, et al.
Veröffentlicht: (2024)

Are Graph Neural Networks Optimal Approximation Algorithms?
von: Yau, Morris, et al.
Veröffentlicht: (2023)

On the Streaming Complexity of Expander Decomposition
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Connectivity Augmentation
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
von: Thejaswi, Suhas, et al.
Veröffentlicht: (2024)

Learning Linear Attention in Polynomial Time
von: Yau, Morris, et al.
Veröffentlicht: (2024)

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
von: Feng, Guhao, et al.
Veröffentlicht: (2023)

Parallel Sampling via Counting
von: Anari, Nima, et al.
Veröffentlicht: (2024)

New Algorithmic Directions in Optimal Transport and Applications for Product Spaces
von: Beigi, Salman, et al.
Veröffentlicht: (2025)

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
von: Li, Dongyue, et al.
Veröffentlicht: (2025)

Optimizing Text Search: A Novel Pattern Matching Algorithm Based on Ukkonen's Approach
von: Guan, Xinyu, et al.
Veröffentlicht: (2025)

Online Learning with Probing for Sequential User-Centric Selection
von: Xu, Tianyi, et al.
Veröffentlicht: (2025)

Demand Selection for VRP with Emission Quota
von: Najar, Farid, et al.
Veröffentlicht: (2025)

Fast EXP3 Algorithms
von: Sato, Ryoma, et al.
Veröffentlicht: (2025)

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

Uncovering Fairness through Data Complexity as an Early Indicator
von: Ferreira, Juliett Suárez, et al.
Veröffentlicht: (2025)

Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
von: Brita, Catalin E., et al.
Veröffentlicht: (2025)

Learning-Augmented Online Bipartite Fractional Matching
von: Choo, Davin, et al.
Veröffentlicht: (2025)

Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance
von: Liu, Zhouyang, et al.
Veröffentlicht: (2025)