Blog
2026
Embedded Files
Algorithmic fundations of deep learning and new compressed sensing error bounds
July 1st, 2026Algorithmic fundations of deep learning and new compressed sensing error bounds
Summer 2026 has been very productive so far and two preprints have just appeared in the arXiv!
The first paper (https://arxiv.org/abs/2606.26705) stems from a collaboration with Anastasis Kratsios, Bum Jun Kim, Greg Cousins, and Haitz Sáez de Ocáriz Borde. We propose a new framework for deep neural network approximation theory that shifts the focus from function classes to algorithmic complexity. Rather than considering classic notions of regularity (Sobolev, Besov, holomorphic, etc.), our theory takes into account which elementary operations is the function made of and how are they composed, using the language of circuit complexity.
In the second preprint (https://arxiv.org/abs/2606.26459), Avi Gupta, Ben Adcock and I propose an imporved classs of recovery error bounds for compressed sensing. This allows for more efficient numerical function approximation schemes in high dimensions through an optimized choice of the truncation set with rigorous error control. We apply our general analysis to the cases of weighted Wiener and anisotropic Sobolev spaces.
The classical approximation theory perspective based on function spaces (black box) vs. the algorithmic complexity lens (grey box) adopted in our new paper (see Figure 2 therein). Visualization by Anastasis Kratsios.
The stories we tell (and those we don't)
June 30, 2026The stories we tell (and those we don't)
I'd like to feature an article by Kseniya Garaschuk (U Fraser Valley) I found very inspiring, entitled "The stories we tell":
https://notes.math.ca/en/article/the-stories-we-tell/
It's about the narrative of "math geniuses" and "revolutionary thinkers" that we too often emphasize in our talks and lectures. Real science is a different thing and relies more on communities than single prodigies.
Some excerpts that stuck with me:
"In our efforts to inspire, we often construct narratives that unintentionally exclude."
"The problem is [...] the stories we tell. Not only do we highlight the prodigies, the once-in-a-generation thinkers, but we also compress careers into neat timbits of brilliance."
"[...] if our goal is not only to inspire but to invite, then we need to include different kinds of “heros” and tell their stories too. Stories not just about trailblazers and firsts, but about typical paths into the discipline and the many people who follow them."
Highly recommended reading for STEM academics, professionals, and enthusiasts.
Four mathematicians featured in the article by Garaschuk. Left to right, top to bottom: Carl Friendrich Gauss, Srinivasa Ramanujan, Sophie Germain, and Emmy Noether.
Every definable neural network can learn from finite data
May 10, 2026Every definable neural network can learn from finite data
A new preprint in collaboration with Anastasis Kratsios, Greg Cousins, Haitz Sáez de Ocáriz Borde, and Bum Jun Kim is out!
https://arxiv.org/abs/2605.07097
We show that every definable neural network can successfully perform classification and regression from a finite dataset, in the sense of Probably Approximately Correct (PAC) learnability. Definability is formalized using o-minimality, a notion borrowed from logic and model theory. Notably, virtually all the architectures and individual components considered in practice are definable in this sense (...incredible, but true!). This inlcudes MLPs, CNNs, GNNs, and transformers with fixed sequence length. A key implication of our results is that finite-sample PAC learnability should be considered a baseline rather than a differentiator between neural networks architectures, since it holds for practically every model.
The class of definable neural network considered in our theory follows the structure of a 𝔾-Neural Network. This includes MLPs, CNNs, GNNs, and transformers with fixed sequence length. For more info, see Figure 1 and Definition 2.4 in the paper. Illustration by Anastasis Kratsios.
A short tour of operator learning
March 3, 2026A short tour of operator learning
I am happy to announce a new paper just uploaded to the arXiv with Nicola Rares Franco and Nick Nelsen:
https://arxiv.org/abs/2603.00819
We provide a concise (12-page) survey of recent theoretical developments in operator learning, a fast-evolving research area at the intersection of numerical analysis, statistical learning and approximation theory. The goal is to learn operators between function (e.g., Hilbert) spaces, motivated by applications such as Partial Differential Equations (PDEs) with paramteric coefficients. In our paper, we review recently established converence rates for holomorphic operators and fundamental learnability limits for different operator classes according to the mimimax framework. We conclude by identifying promising research avenues for future work.
This "mini survey paper" is my entry point in the field and writing it with Nick and Nicola has been a great learning experience. I hope this paper will be useful to researchers who want to get started in operator learning theory!
One of the operator learning frameworks considered in the paper is the composition of an encoder, a trained multilayer perceptron, and an decoder.
From compression to depth
February 18, 2026From compression to depth
Yesterday I had the pleasure to give a talk for CodEx, an online seminar series organized by John Jasper, Emily King, Dustin Mixon, and Michael Perlmutter. My talk, entitled "From compression to depth: generative compressive sensing and deep greedy unfolding for signal reconstruction", is available on YouTube. In it, after providing a brief historical overview of the last four decades of research in sparsity, compressed sensing and deep learning for signal reconstruction, I illustrate of some of my recent research in these areas. Specifically, I feature my recent work on generative compressed sensing [Berk et a. (2022), Berk et al. (2023)] and deep greedy unfolding [Taheri, Colbrook, B. (2024), Taheri, Colbrook, B. (2025)].
I also presented a similar version of this talk in the Department of Scientific Computing Colloquium at Florida State University earlier in Ferbuary, hosted by Nick Dexter.
Google Sites
Report abuse