Learning to Learn

Poly-Attention — A Better Attention Mechanism That's Still Fast Poly-Attention — A Better Attention Mechanism That's Still Fast Most improvements to the Transformer's self-attention mechanism work at the level of approximation — finding faster ways to compute the same pairwise dot products. Sparse attention, linear attention, flash attention: all of these keep the fundamental computation the same and just make it cheaper. They share an assumption: pairwise token interactions are the right thing to compute, and the goal is to do it faster. A recent paper from Columbia University — Poly-Attention: A General Scheme for Higher-Order Self-Attention (Chakrabarti, Pitassi, Alman, 2026) — makes a different move. It asks whether pairwise interactions are expressive enough , proves they often aren't, and then builds a unified mathematical framework for richer attention mechanisms. The punchline is a new mechanism called tree-attention that is simultaneously ...

Basis Change and Matrix Approximation with SVD Basis Change and Matrix Approximation with SVD 1. Basis Change In this section, we’ll see how a transformation matrix changes when we change the basis of a linear mapping. Let there be a linear transformation: $$ \phi: V \rightarrow W $$ where \( V \in \mathbb{R}^n \) and \( W \in \mathbb{R}^m \). Let the ordered bases for \( V \) and \( W \) be: $$ B = (b_1, \dots, b_n), \quad C = (c_1, \dots, c_m) $$ and the new bases be: $$ \tilde{B} = (\tilde{b}_1, \dots, \tilde{b}_n), \quad \tilde{C} = (\tilde{c}_1, \dots, \tilde{c}_m) $$ If \( A \) represents the transformation matrix of \( \phi \) with respect to the bases \( (B, C) \), and \( \tilde{A} \) is the corresponding matrix with respect to \( (\tilde{B}, \tilde{C}) \), we aim to relate \( A \) and \( \tilde{A} \). 1.1 Relationship between old and new bases Each new basis vector in \( \tilde{B} \) can be written as a linear combi...