# Optimal Regularization for a Data Source arXiv: https://arxiv.org/abs/2212.13597 ยท HTML: https://mlsanity.com/paper/2212.13597/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 29 of its 99 references that are in the map. - First posted on arXiv 27 Dec 2022. ## Builds on (most cited first, 29 of 29) - [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017) - [The Little Engine that Could: Regularization by Denoising (RED)](https://mlsanity.com/paper/1611.02862/) (2016) - [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018) - [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018) - [Adversarial Regularizers in Inverse Problems](https://mlsanity.com/paper/1805.11572/) (2018) - [Regularization by Denoising: Clarifications and New Interpretations](https://mlsanity.com/paper/1806.02296/) (2018) - [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015) - [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015) - [Sparse Modeling for Image and Vision Processing](https://mlsanity.com/paper/1411.3230/) (2014) - [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015) - [A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries](https://mlsanity.com/paper/1601.02049/) (2016) - [Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization](https://mlsanity.com/paper/1310.7991/) (2013) - [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015) - [Convolutional Dictionary Learning: A Comparative Review and New Algorithms](https://mlsanity.com/paper/1709.02893/) (2017) - [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014) - [Convolutional Dictionary Learning via Local Processing](https://mlsanity.com/paper/1705.03239/) (2017) - [Sparse Regularization via Convex Analysis](https://mlsanity.com/paper/1803.06765/) (2018) - [The Squared-Error of Generalized LASSO: A Precise Analysis](https://mlsanity.com/paper/1311.0830/) (2013) - [Optimal computational and statistical rates of convergence for sparse nonconvex learning problems](https://mlsanity.com/paper/1306.4960/) (2013) - [A Generative Variational Model for Inverse Problems in Imaging](https://mlsanity.com/paper/2104.12630/) (2021) - [Total Deep Variation: A Stable Regularizer for Inverse Problems](https://mlsanity.com/paper/2006.08789/) (2020) - [Sample Complexity of Dictionary Learning and other Matrix Factorizations](https://mlsanity.com/paper/1312.3790/) (2013) - [Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples](https://mlsanity.com/paper/2103.00394/) (2021) - [A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries](https://mlsanity.com/paper/1309.1952/) (2013) - [Nonconvex regularization for sparse neural networks](https://mlsanity.com/paper/2004.11515/) (2020) - [Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity](https://mlsanity.com/paper/1606.03841/) (2016) - [Convergence radius and sample complexity of ITKM algorithms for dictionary learning](https://mlsanity.com/paper/1503.07027/) (2015) - [A theory of optimal convex regularization for low-dimensional recovery](https://mlsanity.com/paper/2112.03540/) (2021) - [Learning Semidefinite Regularizers](https://mlsanity.com/paper/1701.01207/) (2017) ## Built on by (most cited first, 6 of 6) - [Weakly Convex Regularisers for Inverse Problems: Convergence of Critical Points and Primal-Dual Optimisation](https://mlsanity.com/paper/2402.01052/) (2024) - [Provably Convergent Data-Driven Convex-Nonconvex Regularization](https://mlsanity.com/paper/2310.05812/) (2023) - [Iso-Riemannian Optimization on Learned Data Manifolds](https://mlsanity.com/paper/2510.21033/) (2025) - [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024) - [Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints](https://mlsanity.com/paper/2510.03464/) (2025) - [Riemannian Archetypal Analysis: Interpretable non-linear data analysis on deformed star distributions](https://mlsanity.com/paper/2605.24113/) (2026) ## Abstract (arXiv) In optimization-based approaches to inverse problems and to statistical estimation, it is common to augment criteria that enforce data fidelity with a regularizer that promotes desired structural properties in the solution. The choice of a suitable regularizer is typically driven by a combination of prior domain information and computational considerations. Convex regularizers are attractive computationally but they are limited in the types of structure they can promote. On the other hand, nonconvex regularizers are more flexible in the forms of structure they can promote and they have showcased strong empirical performance in some applications, but they come with the computational challenge of solving the associated optimization problems. In this paper, we seek a systematic understanding of the power and the limitations of convex regularization by investigating the following questions: Given a distribution, what is the optimal regularizer for data drawn from the distribution? What properties of a data source govern whether the optimal regularizer is convex? We address these questions for the class of regularizers specified by functionals that are continuous, positively homogeneous, and positive away from the origin. We say that a regularizer is optimal for a data distribution if the Gibbs density with energy given by the regularizer maximizes the population likelihood (or equivalently, minimizes cross-entropy loss) over all regularizer-induced Gibbs densities. As the regularizers we consider are in one-to-one correspondence with star bodies, we leverage dual Brunn-Minkowski theory to show that a radial function derived from a data distribution is akin to a ``computational sufficient statistic'' as it is the key quantity for identifying optimal regularizers and for assessing the amenability of a data source to convex regularization.