An interesting theoretical result on gradient descent complexity. I missed it before.
https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
https://arxiv.org/abs/2011.01929
https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
https://arxiv.org/abs/2011.01929
Quanta Magazine
Computer Scientists Discover Limits of Major Research Algorithm | Quanta Magazine
The most widely used technique for finding the largest or smallest values of a math function turns out to be a fundamentally difficult computational problem.
❤8🔥7👍1
Just in case, a (very short) video generation is here.
Pika Beta is now publicly available
https://twitter.com/pika_labs/status/1684836399764373504?t=NVtOyyh5UZDTJwVNUArFjA&s=19
Join Beta: discord.gg/pika
Website: pika.art
Pika Beta is now publicly available
https://twitter.com/pika_labs/status/1684836399764373504?t=NVtOyyh5UZDTJwVNUArFjA&s=19
Join Beta: discord.gg/pika
Website: pika.art
Discord
Join the Pika Discord Server!
Video on command. | 922270 members
❤1👍1🔥1
On the Universality of Linear Recurrences Followed by Nonlinear Projections
Antonio Orvieto, Soham De, Caglar Gulcehre, Razvan Pascanu, Samuel L. Smith
Статья: https://arxiv.org/abs/2307.11888
Развитие темы, начатой в работе про LRU (https://news.1rj.ru/str/gonzo_ML/1734). Там показали, что рекуррентность может быть и без нелинейности, и что связка линейного рекуррентного слоя и position-wise MLP работает достаточно хорошо. Текущая работа -- это ещё work in progress, разбирающая эту тему дальше.
Как и в той работе, рассматривают диагональную комплексную матрицу и рекуррентность вида:
x_k = Λx_{k−1} + Bu_k,
То есть скрытое состояние x здесь комплексное. Далее оно проецируется в действительные выходы y:
y^hat_k = ℜ[Cx_k]
и оттуда отправляется в positionwise MLP y_k = ϕ^hat(y^hat_k) = ϕ(x_k).
Эта модель описывает одиночный блок и LRU, и глубоких SSM, включая диагональные варианты S4.
Для рекуррентных сетей ранее были хорошо изучены аппроксимирующие способности сетей с ReLU. А вот линейные не особо исследовались как неинтересные. В текущей работе авторы фокусируются на последовательностях конечной длины и показывают, что достаточно широкие линейные RNN не образуют узкого места, и архитектура сохраняет универсальность при использовании поэлементного MLP.
Основная мысль в том, что RNN часть (случайно инициализированная, привет reservoir computing!) занимается компрессией входного сигнала. А если мы можем идеально восстановить исходный сигнал, то MLP может параметризовать любую нелинейную функцию над этой последовательностью (ну при соблюдении определённых условий типа компактности).
Неформально, то что пытаются доказать авторы, звучит так:
Assume finite-length sequence data is generated from a sequence-to-sequence model such that Assumption B (compactness of the input) holds. Consider a randomly initialized linear recurrent network of size N, with N large enough depending on the sparseness of the input set (Assumption A). Then, there exists a wide enough MLP which, if applied pointwise to the RNN hidden states, leads to perfect reconstruction of the system’s output.
Дальнейшая углублённая работа планируется в этом направлении.
Из интересного кстати, комплексные числа здесь явно помогают побороть плохое обусловливание при восстановлении оригинальных данных из скрытого состояния.
В приложении много всяких теорем для любителей.
Antonio Orvieto, Soham De, Caglar Gulcehre, Razvan Pascanu, Samuel L. Smith
Статья: https://arxiv.org/abs/2307.11888
Развитие темы, начатой в работе про LRU (https://news.1rj.ru/str/gonzo_ML/1734). Там показали, что рекуррентность может быть и без нелинейности, и что связка линейного рекуррентного слоя и position-wise MLP работает достаточно хорошо. Текущая работа -- это ещё work in progress, разбирающая эту тему дальше.
Как и в той работе, рассматривают диагональную комплексную матрицу и рекуррентность вида:
x_k = Λx_{k−1} + Bu_k,
То есть скрытое состояние x здесь комплексное. Далее оно проецируется в действительные выходы y:
y^hat_k = ℜ[Cx_k]
и оттуда отправляется в positionwise MLP y_k = ϕ^hat(y^hat_k) = ϕ(x_k).
Эта модель описывает одиночный блок и LRU, и глубоких SSM, включая диагональные варианты S4.
Для рекуррентных сетей ранее были хорошо изучены аппроксимирующие способности сетей с ReLU. А вот линейные не особо исследовались как неинтересные. В текущей работе авторы фокусируются на последовательностях конечной длины и показывают, что достаточно широкие линейные RNN не образуют узкого места, и архитектура сохраняет универсальность при использовании поэлементного MLP.
Основная мысль в том, что RNN часть (случайно инициализированная, привет reservoir computing!) занимается компрессией входного сигнала. А если мы можем идеально восстановить исходный сигнал, то MLP может параметризовать любую нелинейную функцию над этой последовательностью (ну при соблюдении определённых условий типа компактности).
Неформально, то что пытаются доказать авторы, звучит так:
Assume finite-length sequence data is generated from a sequence-to-sequence model such that Assumption B (compactness of the input) holds. Consider a randomly initialized linear recurrent network of size N, with N large enough depending on the sparseness of the input set (Assumption A). Then, there exists a wide enough MLP which, if applied pointwise to the RNN hidden states, leads to perfect reconstruction of the system’s output.
Дальнейшая углублённая работа планируется в этом направлении.
Из интересного кстати, комплексные числа здесь явно помогают побороть плохое обусловливание при восстановлении оригинальных данных из скрытого состояния.
В приложении много всяких теорем для любителей.
Telegram
gonzo-обзоры ML статей
Resurrecting Recurrent Neural Networks for Long Sequences
Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, Soham De
Статья: https://arxiv.org/abs/2303.06349
Продолжаем про RNN. У нас было про LEM (https://t…
Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, Soham De
Статья: https://arxiv.org/abs/2303.06349
Продолжаем про RNN. У нас было про LEM (https://t…
👍12❤6