Treinamento de Atenção Tensorial: Aprendizagem Provavelmente Eficiente de Transformers de Ordem Superior

A Atenção Tensorial, uma atenção multi-visão capaz de capturar correlações de ordem elevada entre múltiplas modalidades, pode superar as limitações representacionais da atenção matricial clássica. Entretanto, a complexidade temporal (n³) da atenção tensorial representa um obstáculo significativo para sua implementação prática em transformers, onde n é o comprimento da sequência de entrada. Neste trabalho, provamos que o gradiente retropropagado do treinamento da atenção tensorial pode ser calculado em tempo quase linear n^{1+o(1)}, a mesma complexidade de sua computação direta sob a suposição de entradas limitadas. Fornecemos uma solução em forma fechada para o gradiente e propomos um método rápido de cálculo utilizando métodos de aproximação polinomial e truques de álgebra tensorial. Além disso, provamos a necessidade e rigidez de nossa suposição por meio de análise de dificuldade, mostrando que seu enfraquecimento leve torna o problema do gradiente insolúvel em tempo verdadeiramente subcúbico. Nossos resultados teóricos estabelecem a viabilidade do treinamento eficiente de transformers de ordem superior e podem facilitar aplicações práticas das arquiteturas de atenção tensorial.