120 citations · 253 across the 22 of their papers we have counts for
22 papers
Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
Krzysztof Choromanski, Arijit Sehanobish, Somnath Basu Roy Chowdhury +4
We present a new class of fast polylog-linear algorithms based on the theory of structured matrices (in particular low displacement rank) for integrating tensor fields defined on w…
SARA-RT: Scaling up Robotics Transformers with Self-Adaptive Robust Attention
Isabel Leal, Krzysztof Choromanski, Deepali Jain +11
We present Self-Adaptive Robust Attention for Robotics Transformers (SARA-RT): a new paradigm for addressing the emerging challenge of scaling up Robotics Transformers (RT) for on-…
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products
Tamas Sarlos, Xingyou Song, David Woodruff +2
Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting where we want to find a good rank approximation…
Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers
Krzysztof Marcin Choromanski, Shanda Li, Valerii Likhosherstov +7
We propose a new class of linear Transformers called FourierLearner-Transformers (FLTs), which incorporate a wide range of relative positional encoding mechanisms (RPEs). These inc…
Efficient Graph Field Integrators Meet Point Clouds
Krzysztof Choromanski, Arijit Sehanobish, Han Lin +13
We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus o…
FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features
Valerii Likhosherstov, Krzysztof Choromanski, Avinava Dubey +3
The problem of efficient approximation of a linear operator induced by the Gaussian or softmax kernel is often addressed using random features (RFs) which yield an unbiased approxi…
Chefs' Random Tables: Non-Trigonometric Random Features
Valerii Likhosherstov, Krzysztof Choromanski, Avinava Dubey +3
We introduce chefs' random tables (CRTs), a new class of non-trigonometric random features (RFs) to approximate Gaussian and softmax kernels. CRTs are an alternative to standard ra…
From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers
Krzysztof Choromanski, Han Lin, Haoxian Chen +7
In this paper we provide, to the best of our knowledge, the first comprehensive approach for incorporating various masking mechanisms into Transformers architectures in a scalable…
ES-ENAS: Efficient Evolutionary Optimization for Large Hybrid Search Spaces
Xingyou Song, Krzysztof Choromanski, Jack Parker-Holder +8
In this paper, we approach the problem of optimizing blackbox functions over large hybrid search spaces consisting of both combinatorial and continuous parameters. We demonstrate t…
Differentially Private Weighted Sampling
Edith Cohen, Ofir Geri, Tamas Sarlos +1
Common datasets have the form of elements with keys (e.g., transactions and products) and the goal is to perform analytics on the aggregated form of key and frequency pairs. A weig…
Rethinking Attention with Performers
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan +10
We introduce Performers, Transformer architectures which can estimate regular (softmax) full-rank-attention Transformers with provable accuracy, but using only linear (as opposed t…
Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan +8
Transformer models have achieved state-of-the-art results across a diverse range of domains. However, concern over the cost of training the attention mechanism to learn complex dep…
Stochastic Flows and Geometric Optimization on the Orthogonal Group
Krzysztof Choromanski, David Cheikhi, Jared Davis +12
We present a new class of stochastic, geometrically-driven optimization algorithms on the orthogonal group and naturally reductive homogeneous manifolds obtained from the ac…
Reinforcement Learning with Chromatic Networks for Compact Architecture Search
Xingyou Song, Krzysztof Choromanski, Jack Parker-Holder +6
We present a neural architecture search algorithm to construct compact reinforcement learning (RL) policies, by combining ENAS and ES in a highly scalable and intuitive way. By def…
Matrix-Free Preconditioning in Online Learning
Ashok Cutkosky, Tamas Sarlos
We provide an online convex optimization algorithm with regret that interpolates between the regret of an algorithm using an optimal preconditioning matrix and one using a diagonal…
Orthogonal Estimation of Wasserstein Distances
Mark Rowland, Jiri Hron, Yunhao Tang +3
Wasserstein distances are increasingly used in a wide variety of applications in machine learning. Sliced Wasserstein distances form an important subclass which may be estimated ef…
Linear Additive Markov Processes
Ravi Kumar, Maithra Raghu, Tamas Sarlos +1
We introduce LAMP: the Linear Additive Markov Process. Transitions in LAMP may be influenced by states visited in the distant history of the process, but unlike higher-order Markov…
Structured adaptive and random spinners for fast machine learning computations
Mariusz Bojarski, Anna Choromanska, Krzysztof Choromanski +6
We consider an efficient computational framework for speeding up several machine learning algorithms with almost no loss of accuracy. The proposed framework relies on projections v…
TripleSpin - a generic compact paradigm for fast machine learning computations
Krzysztof Choromanski, Francois Fagan, Cedric Gouy-Pailler +3
We present a generic compact computational framework relying on structured random matrices that can be applied to speed up several machine learning algorithms with almost no loss o…
Fastfood: Approximate Kernel Expansions in Loglinear Time
Quoc Viet Le, Tamas Sarlos, Alexander Johannes Smola
Despite their successes, what makes kernel methods difficult to use in many large scale problems is the fact that storing and computing the decision function is typically expensive…
A Sparse Johnson--Lindenstrauss Transform
Anirban Dasgupta, Ravi Kumar, Tamás Sarlós
Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work w…
Faster Least Squares Approximation
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan +1
Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets be the num…