% English research-group presentation; compile with pdfLaTeX.
\documentclass[aspectratio=169,11pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,booktabs}

\definecolor{AcademicBlue}{RGB}{26,57,86}
\definecolor{AcademicTeal}{RGB}{0,105,112}
\setbeamercolor{structure}{fg=AcademicBlue}
\setbeamercolor{frametitle}{fg=AcademicBlue,bg=white}
\setbeamercolor{title}{fg=AcademicBlue}
\setbeamercolor{alerted text}{fg=AcademicTeal}
\setbeamercolor{block title}{fg=white,bg=AcademicBlue}
\setbeamercolor{block body}{fg=black,bg=AcademicBlue!5}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{itemize items}[circle]
\setbeamertemplate{footline}{%
  \hfill\usebeamerfont{page number in head/foot}%
  \insertframenumber\,/\,\inserttotalframenumber\hspace{4mm}\vspace{3mm}}
\setbeamersize{text margin left=8mm,text margin right=8mm}
\setbeamerfont{frametitle}{size=\Large,series=\bfseries}
\setbeamerfont{title}{size=\LARGE,series=\bfseries}
\newcommand{\papersource}[1]{\par\smallskip{\scriptsize\color{gray}#1\par}}
\newcommand{\arxivlink}{\href{https://arxiv.org/abs/2410.10101v4}{arXiv:2410.10101v4}}
\newcommand{\neuripslink}{\href{https://papers.nips.cc/paper_files/paper/2025/hash/e033b7666615284bba1db00f4f029322-Abstract-Conference.html}{NeurIPS 2025 Main Conference}}

\title[Learning linear attention]{Learning Linear Attention in Polynomial Time}
\subtitle{Convex regression, identifiable functions, and bounded computation}
\author{\small Paper by Morris Yau, Ekin Aky\"urek, Jiayuan Mao,\\Joshua B. Tenenbaum, Stefanie Jegelka, Jacob Andreas}
\date{\small \arxivlink\quad (v4, 23 Oct 2025)\\Research group discussion, 3 Nov 2026}

\begin{document}

\begin{frame}
  \titlepage
  \vspace{-2mm}
  \begin{center}
    \small Published at \neuripslink.\\
    No verifiable public implementation located (3 Nov 2026).
  \end{center}
\end{frame}

\begin{frame}{Expressibility leaves a learning problem open}
  \begin{block}{The gap}
    A hand-designed Transformer can simulate a computation; examples do not tell us how to recover that computation efficiently.
  \end{block}
  \begin{itemize}
    \item Nonconvex attention parameters obscure the global optimum.
    \item Multiple functions may fit the observed inputs equally well.
    \item The paper asks for an efficient learner and a data-dependent test of functional uniqueness.
  \end{itemize}
  \papersource{Yau et al., Sec. 1, PDF pp. 1--2.}
\end{frame}

\begin{frame}{Three claims form the paper's argument}
  \begin{enumerate}
    \item \textbf{Learning:} linearize a single-layer multi-head linear attention model, solve regression, recover heads by SVD.
    \item \textbf{Identification:} a full-rank feature moment matrix makes all exact fits compute the same function.
    \item \textbf{Application:} represent bounded computation histories autoregressively, then apply the learning and identification results.
  \end{enumerate}
  \vspace{2mm}
  \begin{block}{Scope}
    Last-token squared-loss regression for one layer without softmax.
  \end{block}
  \papersource{Yau et al., Secs. 2--3, PDF pp. 3--6.}
\end{frame}

\begin{frame}{The model is nonlinear in its parameters}
  \begin{block}{Multi-head linear attention (MHLA)}
    \[
      Z\in\mathbb R^{d\times n},\quad V_h,Q_h\in\mathbb R^{d\times d},\quad
      \widehat y_\Theta(Z)=\sum_{h=1}^{H}V_hZ(Z^\top Q_hz_n).
    \]
  \end{block}
  \begin{itemize}
    \item $z_n$ is the last input token; $\widehat y\in\mathbb R^d$.
    \item $Q_h$ fuses key and query projections; no softmax is applied.
    \item Variable sequence length $n$ is allowed at fixed embedding dimension $d$.
  \end{itemize}
  \papersource{Definition 2.1 and Eq. (5), PDF p. 3.}
\end{frame}

\begin{frame}{A fixed cubic feature map exposes linear prediction}
  \[
    S=ZZ^\top,\qquad
    \mathcal X(Z)_{j,(k,\ell)}=S_{jk}z_{\ell n}
    =\langle z_{j:},z_{k:}\rangle z_{\ell n}.
  \]
  \vspace{1mm}
  \[
    \widehat y_a(Z)=\sum_{h,j,k,\ell}
       V_{h,aj}Q_{h,k\ell}\mathcal X(Z)_{j,(k,\ell)}.
  \]
  \begin{itemize}
    \item The input feature has fixed size $d\times d^2$, independent of $n$.
    \item The network is linear in the \emph{combined} coefficients, although not in each head's matrices.
  \end{itemize}
  \papersource{Eqs. (5), (7)--(8), PDF pp. 3--4.}
\end{frame}

\begin{frame}{Head count becomes a matrix-rank constraint}
  \[
    W_\Theta=\sum_{h=1}^{H}
       \operatorname{vec}(V_h)\operatorname{vec}(Q_h)^\top
       \in\mathbb R^{d^2\times d^2},
    \qquad \operatorname{rank}(W_\Theta)\le H.
  \]
  \begin{block}{Key step}
    Allow an unrestricted $W$. Its regression objective is convex, and any resulting $W$ has rank at most $d^2$.
  \end{block}
  \begin{itemize}
    \item SVD expresses $W$ as at most $d^2$ outer products.
    \item Folding each pair of vectors yields attention heads with exactly the same input--output function.
  \end{itemize}
  \papersource{Sec. 2.1, PDF p. 4; Algorithm 1, PDF p. 3.}
\end{frame}

\begin{frame}{Algorithm 1: regression followed by SVD}
  \begin{enumerate}
    \item From each sequence, compute $\mathcal X(Z_i)$ and the output-coordinate features $X_{i,a}$.
    \item Solve ordinary least squares:
      \[
        \widehat W\in\arg\min_W\sum_{i=1}^{N}\sum_{a=1}^{d}
        \bigl(\langle W,X_{i,a}\rangle-y_{i,a}\bigr)^2.
      \]
    \item Factor $\widehat W=\sum_{h=1}^{\widehat H}u_hv_h^\top$; fold $u_h,v_h$ into $\widehat V_h,\widehat Q_h$.
  \end{enumerate}
  \vspace{1mm}
  \alert{Result:} $\widehat H\le d^2$ and the recovered MHLA predicts exactly as $\widehat W$.
  \papersource{Algorithm 1, PDF p. 3; proof in Appendix D, pp. 17--18.}
\end{frame}

\begin{frame}{Theorem 2.2 states an agnostic risk bound}
  \begin{block}{As stated in the paper}
    With i.i.d. samples and squared loss, the returned $\widehat\Theta$ satisfies, with probability at least $1-\delta$,
    \[
      R(\widehat\Theta)-\min_{\Theta\in\Omega_H}R(\Theta)
      \le\epsilon,\qquad
      R(\Theta)=\mathbb E\|\widehat y_\Theta(Z)-y\|^2.
    \]
  \end{block}
  \[
     N=O\!\left(\frac{d^4+\log(1/\delta)}{\epsilon}\right),\qquad
     T=O\!\left(\frac{Nd^4n_{\max}}{\epsilon}\right).
  \]
  \smallskip
  \small No realizable-label assumption; output width may grow to $d^2$ heads.
  \papersource{Theorem 2.2, PDF pp. 3--4. Statistical assumptions are revisited later.}
\end{frame}

\begin{frame}{A low training loss does not identify a function}
  \begin{block}{Question}
    Can two empirical minimizers agree on every training sequence but disagree on a new sequence?
  \end{block}
  \begin{itemize}
    \item Raw $(V_h,Q_h)$ values are redundant: rescaling and reallocation across heads can preserve predictions.
    \item The relevant object is a coefficient vector $p(\Theta)$ in a \emph{nonredundant} input-feature basis.
    \item Identification asks whether the dataset determines that coefficient vector.
  \end{itemize}
  \papersource{Sec. 2.2, PDF p. 5; Appendix A, pp. 13--14.}
\end{frame}

\begin{frame}{The certificate checks the rank of cubic features}
  \[
    \mathcal H(Z)_{\{j,k\},\ell}
      =\langle z_{j:},z_{k:}\rangle z_{\ell n},
      \qquad j\le k,
  \]
  \[
    \psi=\binom d2d+d^2=\frac{d^2(d+1)}2,\qquad
    \Lambda_D=\frac1N\sum_{i=1}^{N}\mathcal H(Z_i)\mathcal H(Z_i)^\top.
  \]
  \begin{block}{Certificate}
    $\lambda_{\min}(\Lambda_D)>0$: the observed features span the whole relevant feature space.
  \end{block}
  \small At least $N\ge\psi$ samples are necessary for this empirical matrix to be full rank.
  \papersource{Lemma 2.3, PDF p. 5; Algorithm 2 and Lemma A.3, pp. 13--14.}
\end{frame}

\begin{frame}{Full rank turns exact fit into equality everywhere}
  \small
  \begin{enumerate}
    \item For each output coordinate, $\widehat y_{\Theta,a}(Z)=\langle p_a(\Theta),\mathcal H(Z)\rangle$.
    \item If data are generated by $\bar\Theta$, every empirical minimizer has zero residual.
    \item For $\Delta p_a=p_a(\Theta)-p_a(\bar\Theta)$:
      \[
        0=\frac1N\sum_i\langle\Delta p_a,\mathcal H(Z_i)\rangle^2
        =\Delta p_a^\top\Lambda_D\Delta p_a
        \ge\lambda_{\min}(\Lambda_D)\|\Delta p_a\|^2.
      \]
    \item Hence $\Delta p_a=0$, so the two models agree on \emph{all} input sequences.
  \end{enumerate}
  \papersource{Lemma A.3 and proof, PDF pp. 13--14, 19.}
\end{frame}

\begin{frame}{Realizable and agnostic identification differ}
  \begin{columns}[T]
    \begin{column}{0.47\textwidth}
      \begin{block}{Realizable data}
        Full rank + exact fit implies every empirical minimizer equals the generating function on all inputs.
      \end{block}
    \end{column}
    \begin{column}{0.47\textwidth}
      \begin{block}{Arbitrary labels}
        With at least $d^2$ heads, full rank makes the least-squares \emph{optimal function} unique; no ground-truth function is assumed.
      \end{block}
    \end{column}
  \end{columns}
  \vspace{3mm}
  Small $\lambda_{\min}$ also signals sensitivity to finite fitting error and numerical noise.
  \papersource{Lemmas A.3 and A.6, PDF pp. 13--15, 20.}
\end{frame}

\begin{frame}{Associative memory supplies an interpretable test}
  \[
  Z=\begin{bmatrix}k_1&\cdots&k_d&q\\v_1&\cdots&v_d&\zeta\end{bmatrix},
  \qquad
  y=\begin{bmatrix}0\\\sum_{j=1}^{d}\langle q,k_j\rangle v_j\end{bmatrix}.
  \]
  \begin{itemize}
    \item Gaussian key/value vectors create identifiable examples; orthogonal key/value tables create rank-deficient ones.
    \item Mix the two sources to vary $\lambda_{\min}(\Lambda_D)$.
    \item Compare models using $\|p(\Theta)-p(\widehat\Theta)\|_F$: distance between \emph{functions}, not raw weights.
  \end{itemize}
  \papersource{Sec. 4.2, Eqs. (13)--(15), PDF pp. 7--8. $d=4$, $N=2^{14}$.}
\end{frame}

\begin{frame}{A larger certificate tracks better recovery}
  \centering
  \includegraphics[width=0.92\linewidth,height=0.74\textheight,keepaspectratio]{figures/fig2a_eigen_distance.pdf}
  \par\smallskip
  \small Algorithm 1: minimum eigenvalue increases, distance in $p$-space falls.
  \papersource{Original Fig. 2a, PDF p. 8. The vertical axis is function-coefficient distance, not test error.}
\end{frame}

\begin{frame}{Gradient-trained heads separate by certificate rank}
  \centering
  \includegraphics[width=0.92\linewidth,height=0.74\textheight,keepaspectratio]{figures/fig2b_sgd_distance.pdf}
  \par\smallskip
  \small Full rank: $\lambda_{\min}=0.06$; low rank: $\lambda_{\min}=0$.
  \papersource{Original Fig. 2b, PDF p. 8. Logarithmic distance axis; error bars: standard error over 3 runs.}
\end{frame}

\begin{frame}{Synthetic regression probes width versus depth}
  \begin{itemize}
    \item A randomly initialized one-layer linear-attention teacher generates targets from Gaussian sequences of length $T=100$.
    \item Compare multi-head linear attention, single-head multi-layer attention, a full Transformer, and Algorithm 1.
    \item Figure 1 reports mean squared prediction error against epochs; lower is better.
  \end{itemize}
  \begin{block}{Terminology in the paper}
    The body says ``SGD''; Appendix G.1 lists AdamW as the training optimizer.
  \end{block}
  \papersource{Sec. 4.1, PDF p. 6; Appendix G.1, p. 29.}
\end{frame}

\begin{frame}{$d=2$: four heads reach the convex baseline}
  \centering
  \includegraphics[width=0.92\linewidth,height=0.74\textheight,keepaspectratio]{figures/fig1_d2.pdf}
  \par\smallskip
  \small $N=512$; $m$ is head count and $n$ is layer count. MSE is on a log scale.
  \papersource{Original Fig. 1a, PDF p. 7. Shading: standard error over 3 runs.}
\end{frame}

\begin{frame}{$d=4$: sixteen heads converge near numerical precision}
  \centering
  \includegraphics[width=0.92\linewidth,height=0.74\textheight,keepaspectratio]{figures/fig1_d4.pdf}
  \par\smallskip
  \small $N=2048$; the $m=d^2=16$ curve reaches the convex baseline.
  \papersource{Original Fig. 1b, PDF p. 7. Other widths can also improve; more heads are not monotonic in every run.}
\end{frame}

\begin{frame}{A bounded Turing-machine history can be generated}
  \begin{enumerate}
    \item Encode a machine's transition table and input as orthogonal token and position vectors.
    \item Use attention heads for lookup, copy, and conditional updates.
    \item Autoregressively write each new tape/state snapshot as another history segment.
  \end{enumerate}
  \vspace{2mm}
  \begin{block}{Construction, not an optimization experiment}
    The same one-layer MHLA module is reused at each generation step; embedding width scales with the predeclared computation bounds.
  \end{block}
  \papersource{Sec. 3, PDF pp. 5--6; Appendices B and F, pp. 16, 23--28.}
\end{frame}

\begin{frame}{The UTM result has explicit size conditions}
  \[
    H=O(\widehat n\widehat\Phi\widehat\Sigma),\qquad
    d=O\!\bigl(\widehat n\widehat\Phi\widehat\Sigma
       \max(\widehat\Sigma,\widehat{\mathcal Q})\bigr).
  \]
  \begin{itemize}
    \item Bounds cover input length $\widehat n$, steps $\widehat\Phi$, alphabet $\widehat\Sigma$, and states $\widehat{\mathcal Q}$.
    \item Distributional trajectory learning uses a union bound across generated tokens.
    \item With an exact fit and the full-rank certificate, functional equality extends to every input \emph{within the bounded class}.
  \end{itemize}
  \papersource{Lemmas B.1, C.5, A.8; PDF pp. 15--17.}
\end{frame}

\begin{frame}{The DFA appendix tests a different architecture}
  \begin{block}{Task}
    Input: DFA transition table + word. Target: autoregressive state-transition history.
  \end{block}
  \begin{itemize}
    \item Varied: state count $Q$, word length $L$, or alphabet size $V$; the other two equal 4.
    \item Measure: training tokens $NL$ needed for 99\% next-token accuracy; lower is better.
    \item Trained model: a 4-layer, 16-head, width-2048 Llama-style \emph{full Transformer}.
  \end{itemize}
  \papersource{Appendix G.2 and G.4, PDF pp. 30--31; Fig. 4, p. 31.}
\end{frame}

\begin{frame}{DFA complexity raises the observed data demand}
  \centering
  \begin{columns}[c]
    \begin{column}{0.49\textwidth}
      \centering\includegraphics[width=\linewidth,height=0.62\textheight,keepaspectratio]{figures/fig4_states.png}
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering\includegraphics[width=\linewidth,height=0.62\textheight,keepaspectratio]{figures/fig4_alphabet.png}
    \end{column}
  \end{columns}
  \small State count and alphabet size generally increase the tokens needed for 99\% accuracy.
  \papersource{Cropped from original Fig. 4, PDF p. 31. These are full-Transformer results.}
\end{frame}

\begin{frame}{Word length shows a less monotonic DFA trend}
  \centering
  \includegraphics[width=0.65\linewidth,height=0.70\textheight,keepaspectratio]{figures/fig4_length.png}
  \par\smallskip
  \small For $Q=V=4$, the required tokens $NL$ fluctuate across tested word lengths.
  \papersource{Cropped from original Fig. 4, PDF p. 31. A finite plotted range does not establish an asymptotic rate.}
\end{frame}

\begin{frame}{Read the guarantees at their precise scope}
  \begin{itemize}
    \item Convex regression solves the \emph{expanded} class: up to $d^2$ heads, one layer, linear attention, squared loss.
    \item The all-input certificate needs full feature rank and an exact realizable fit; arbitrary labels yield uniqueness of the optimal function only in the wide class.
    \item Theorem 2.2 states a distribution-free squared-risk sample rate, but Appendix D only invokes generic VC theory; bounded-loss or moment conditions needed for that statistical step are not specified.
    \item Figure 4 studies a full Transformer, so it is a separate empirical illustration of DFA learning.
  \end{itemize}
  \papersource{Theorem 2.2, PDF pp. 3--4; Appendix D, pp. 17--18; Lemma A.6, p. 20; Appendix G.4, p. 31.}
\end{frame}

\begin{frame}{Take-home messages}
  \begin{enumerate}
    \item A cubic feature map converts MHLA prediction into linear regression; SVD turns the solution into at most $d^2$ attention heads.
    \item A full-rank moment matrix certifies that exact fits are the same function on every input.
    \item Bounded automaton computations connect these two ideas to algorithm learning; synthetic experiments probe their mechanisms.
  \end{enumerate}
  \vspace{3mm}
  \begin{block}{Research direction}
    Keep a checkable function certificate while extending beyond single-layer ungated linear attention.
  \end{block}
  \papersource{Yau et al., Secs. 2--4 and 6, PDF pp. 3--9.}
\end{frame}

\begin{frame}{Paper and publication links}
  \begin{itemize}
    \item Morris Yau et al., \emph{Learning Linear Attention in Polynomial Time}. \arxivlink\ (v4; this presentation uses the arXiv PDF).
    \item \neuripslink, \emph{Advances in Neural Information Processing Systems 38}; \href{https://doi.org/10.52202/085713-5109}{DOI: 10.52202/085713-5109}.
    \item No verifiable public implementation located as of 3 Nov 2026.
  \end{itemize}
  \vspace{4mm}
  \small Figures 1, 2, and 4 are reproduced from the arXiv v4 author source and labeled at their original PDF pages.
\end{frame}

\end{document}