82 citations · 151 across the 23 of their papers we have counts for
24 papers
HyperVAttention: Efficient Sparse Attention with Spatio-Temporal Clustering for Video Diffusion
Dongyeun Lee, Amir Zandieh, Vahab Mirrokni +2
Video Diffusion Transformers (VDiTs) have demonstrated significant capabilities in high-fidelity video generation. However, their ability to produce long-duration videos is fundame…
ECO: Quantized Training without Full-Precision Master Weights
Mahdi Nikdan, Amir Zandieh, Dan Alistarh +1
Quantization has significantly improved the compute and memory efficiency of Large Language Model (LLM) training. However, existing approaches still rely on accumulating their upda…
TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
Amir Zandieh, Majid Daliri, Majid Hadian +1
Vector quantization, a problem rooted in Shannon's source coding theory, aims to quantize high-dimensional Euclidean vectors while minimizing distortion in their geometric structur…
PolarQuant: Quantizing KV Caches with Polar Transformation
Insu Han, Praneeth Kacham, Amin Karbasi +2
Large language models (LLMs) require significant memory to store Key-Value (KV) embeddings in their KV cache, especially when handling long-range contexts. Quantization of these KV…
Streaming Attention Approximation via Discrepancy Theory
Ekaterina Kochetkova, Kshiteej Sheth, Insu Han +2
Large language models (LLMs) have achieved impressive success, but their high memory requirements present challenges for long-context token generation. In this paper we study the s…
QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead
Amir Zandieh, Majid Daliri, Insu Han
Serving LLMs requires substantial memory due to the storage requirements of Key-Value (KV) embeddings in the KV cache, which grows with sequence length. An effective approach to co…
SubGen: Token Generation in Sublinear Time and Memory
Amir Zandieh, Insu Han, Vahab Mirrokni +1
Despite the significant success of large language models (LLMs), their extensive memory requirements pose challenges for deploying them in long-context token generation. The substa…
HyperAttention: Long-context Attention in Near-Linear Time
Insu Han, Rajesh Jayaram, Amin Karbasi +3
We present an approximate attention mechanism named HyperAttention to address the computational challenges posed by the growing complexity of long contexts used in Large Language M…
KDEformer: Accelerating Transformers via Kernel Density Estimation
Amir Zandieh, Insu Han, Majid Daliri +1
Dot-product attention mechanism plays a crucial role in modern deep architectures (e.g., Transformer) for sequence modeling, however, naïve exact computation of this model incurs q…
Fast Neural Kernel Embeddings for General Activations
Insu Han, Amir Zandieh, Jaehoon Lee +3
Infinite width limit has shed light on generalization and optimization aspects of deep learning by establishing connections between neural networks and kernel methods. Despite thei…
Near Optimal Reconstruction of Spherical Harmonic Expansions
Amir Zandieh, Insu Han, Haim Avron
We propose an algorithm for robust recovery of the spherical harmonic expansion of functions defined on the d-dimensional unit sphere using a near-optimal number…
Random Gegenbauer Features for Scalable Kernel Methods
Insu Han, Amir Zandieh, Haim Avron
We propose efficient random features for approximating a new and rich class of kernel functions that we refer to as Generalized Zonal Kernels (GZK). Our proposed GZK family, genera…
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time
David P. Woodruff, Amir Zandieh
We propose an input sparsity time sampling algorithm that can spectrally approximate the Gram matrix corresponding to the -fold column-wise tensor product of matrices using…
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
Karl Bringmann, Michael Kapralov, Mikhail Makarov +3
We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier -sparse vector from…
Scaling Neural Tangent Kernels via Sketching and Random Features
Amir Zandieh, Insu Han, Haim Avron +3
The Neural Tangent Kernel (NTK) characterizes the behavior of infinitely-wide neural networks trained under least squares loss by gradient descent. Recent works also report that NT…
Learning with Neural Tangent Kernels in Near Input Sparsity Time
Amir Zandieh
The Neural Tangent Kernel (NTK) characterizes the behavior of infinitely wide neural nets trained under least squares loss by gradient descent. However, despite its importance, the…
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling
David P. Woodruff, Amir Zandieh
To accelerate kernel methods, we propose a near input sparsity time algorithm for sampling the high-dimensional feature space implicitly defined by a kernel transformation. Our mai…
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
Michael Kapralov, Navid Nouri, Ilya Razenshteyn +2
Random binning features, introduced in the seminal paper of Rahimi and Recht (2007), are an efficient method for approximating a kernel matrix using locality sensitive hashing. Ran…
Dimension-independent Sparse Fourier Transform
Michael Kapralov, Ameya Velingker, Amir Zandieh
The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm.…
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco +3
Reconstructing continuous signals from a small number of discrete samples is a fundamental problem across science and engineering. In practice, we are often interested in signals w…
Beyond -Approximation for Submodular Maximization on Massive Data Streams
Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović +3
Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc., require extracting a small but representati…
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Haim Avron, Michael Kapralov, Cameron Musco +3
Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the sta…
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett +1
The problem of approximately computing the dominant Fourier coefficients of a vector quickly, and using few samples in time domain, is known as the Sparse Fourier Transform…
Reconstruction of Sub-Nyquist Random Sampling for Sparse and Multi-Band Signals
Amir Zandieh, Alireza Zareian, Masoumeh Azghani +1
As technology grows, higher frequency signals are required to be processed in various applications. In order to digitize such signals, conventional analog to digital convertors are…