Abstract: Learned denoisers play a fundamental role in various signal generation (e.g., diffusion models) and reconstruction (e.g., compressed sensing) architectures, whose success derives from their ability to leverage low-dimensional structure in data. Existing denoising methods, however, either rely on local approximations that require a linear scan of the entire dataset or treat denoising as generic function approximation problems, sacrificing efficiency and interpretability. We consider the problem of efficiently denoising a new noisy data point sampled from an unknown manifold $\mathcal M \in \mathbb{R}^D$, using only noisy samples. This work proposes a framework for test-time efficient manifold denoising, by framing the concept of "learning-to-denoise" as *"learning-to-optimize"*. We have two technical innovations: (i) *online learning* methods which learn to optimize over the manifold of clean signals using only noisy data, effectively "growing" an optimizer one sample at a time. (ii) *mixed-order* methods which guarantee that the learned optimizers achieve global optimality, ensuring both efficiency and near-optimal denoising performance. We corroborate these claims with theoretical analyses of both the complexity and denoising performance of mixed-order traversal. Our experiments on scientific manifolds demonstrate significantly improved complexity-performance tradeoffs compared to nearest neighbor search, which underpins existing provable denoising approaches based on exhaustive search.

Lay Summary:

Much progress in machine learning has come from making models bigger and feeding them more data using powerful computers. While this approach works, it uses a lot of energy and isn't sustainable in the long run. We believe there’s a better way: instead of just scaling up, we should focus on using the structure hidden in the data and the problem itself to build more efficient models.Our work focuses on denoising -- the process of removing noise from signals like images, videos, or scientific measurements. Denoising is a core building block in many signal generation and reconstruction models. However, most existing models typically use generic learners to approximate the denoising function without incorporating the inherent structure of the data or the problem into the architecture design.In reality, most data -- whether it's from medical imaging, astronomy, or neuroscience -- looks complex but actually follows simpler, low-dimensional patterns. In this work, we argue that we can use this structure to develop more computationally efficient denoisers, by reinterpreting denoising as an optimization problem. This leads to a provable method that is more efficient than standard approaches like nearest neighbor search and generic models such as autoencoders, while achieving similar performance. This suggests that this approach could be used as a foundational building block in broader learning architectures -- making them more efficient and transparent.