Global polynomial-time estimation in statistical nonlinear inverse problems via generalized stability

Sven Wang · 2026

Read Global polynomial-time estimation in statistical nonlinear inverse problems via generalized stability by Sven Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09007.txt.

Introduction

Sven Wang gives fast ways to solve inverse tasks where the rule that links cause to data is not a straight line. Such tasks ask: what hid cause made the data we see. Score based picks lead to bumpy hills with many peaks. Slow chain search can take a vast time to cross those hills, so it fails in real use.

He gives picks that plug in a first guess, or fine a pick that fits a known law. Both can be run in set time bounds on a PC. He proves they stay close to truth as data grows. A reader who solves inverse tasks gets speed with proof, a pair that is oft hard to hold at once.

Catalog record

CREATORSven Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-09007

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Global polynomial-time estimation in statistical nonlinear inverse problems via generalized stability Sven Wang Abstract Non-linear statistical inverse problems pose major challenges both for statistical analysis and computation. Likelihood-based estimators typically lead to non-convex and possibly multimodal optimization landscapes, and Markov chain Monte Carlo (MCMC) methods may mix exponentially slowly. We propose a class of computationally tractable estimators—plug-in and PDE-penalized M-estimators—for inverse problems defined through operator equations of the form L f ​ u = g L_{f}u=g , where f f is the unknown parameter and u u is the observed solution. The key idea is to replace the exact PDE constraint by a weakly enforced relaxation, yielding conditionally convex and, in many PDE examples, nested quadratic optimization problems that avoid evaluating the forward map G ⁡ ( f ) G(f) and do not require PDE solvers. For prototypical non-linear inverse problems arising from elliptic PDEs, including the Darcy flow model L f u = ∇ ⋅ ( f ∇ u ) L_{f}u=\nabla\!\cdot(f\nabla u) and a steady-state Schrödinger model, we prove that these estimators attain the best currently known statistical convergence rates while being globally computable in polynomial time. In the Darcy model, we obtain an explicit sub-quadratic o ⁡ ( N 2 ) o(N^{2}) arithmetic runtime bound for estimating f f from N N noisy samples. Our analysis is based on new generalized stability estimates, extending classical stability beyond the range of the forward operator, combined with tools from nonparametric M-estimation. We also derive adaptive rates for the Darcy problem, providing a blueprint for designing provably polynomial-time statistical algorithms for a broad class of non-linear inverse problems. Our estimators also provide principled warm-start initializations for polynomial-time Bayesian computation. École Polytechnique Fédérale de Lausanne (EPFL) Institute of Mathematics [email protected] Contents 1 Main ideas and overview Non-linear inverse problems have recently drawn significant research interest in modern statistics, applied and pure mathematics, and scientific computing [ 58 , 43 , 49 , 6 , 29 , 28 ] . They arise whenever an unknown statistical parameter f\in\mathcal{F} can only be observed indirectly through a nonlinear forward map \mathcal{G}:\mathcal{F}\to\mathcal{H}, where \mathcal{F} denotes a high- or infinite-dimensional parameter space, and \mathcal{H} is the space where observations can be obtained, subject to measurement noise. Typical examples arise in medical imaging, geophysical fluid dynamics, and weather and climate modelling, where f encodes an unknown parameter of the physical system. In such cases, the observation space is a Hilbert space \mathcal{H}\subseteq L^{2}(\mathcal{O}) consisting of functions on a spatial or spatio-temporal domain \mathcal{O}\subseteq\mathbb{R}^{d} . In this paper, we consider statistical non-linear inverse problems where the data consist of noisy measurements Y_{i}=\mathcal{G}(f_{0})(X_{i})+\varepsilon_{i},\qquad i=1,\dots,N, (1) where f_{0}\in\mathcal{F} is some unknown ground truth data-generating parameter, X_{i}\in\mathcal{O} are design points, \varepsilon_{i}\in\mathbb{R} are independent (e.g. Gaussian) noise variables, and N\geq 1 denotes statistical sample size. In the key class of inverse problems studied in this paper, \mathcal{G} is described by the non-linear parameter-to-solution map of a partial differential equation (PDE) which describes the observed system. The parameter f plays the role of a coefficient function within the PDE, and \mathcal{G}(f)\in L^{2}(\mathcal{O}) denotes the observable solution [ 58 , 43 , 29 , 28 ] —we will introduce several concrete examples below. The main inferential task is to recover f_{0} from the data Z^{(N)}=(Y_{i},X_{i})_{i=1}^{N} given by ( 1 ). A secondary goal is given by the estimation of \mathcal{G}(f_{0}) , which constitutes a PDE-constrained regression problem over the (typically nonlinear) manifold of functions defined by the range of \mathcal{G} , \big\{\mathcal{G}(f):f\in\mathcal{F}\big\}\subseteq L^{2}(\mathcal{O}) . The relevance of the preceding framework has led to significant methodological advances in applied mathematics and statistics—notably, this includes widely used maximum-likelihood and regularization-based estimators [ 24 , 30 ] as well as Bayesian inversion techniques [ 58 , 43 ] . Devising statistical reconstruction methods which satisfy rigorous algorithmic guarantees has proven to be challenging. In practice, maximum likelihood and Bayes methods are reliant on the minimization of a (penalized) non-convex log-likelihood functional—for Gaussian noise equal to -\ell_{N}(f)=\frac{1}{2N}\sum_{i=1}^{N}[Y_{i}-\mathcal{G}(f)(X_{i})]^{2},\penalty\ \penalty\ \penalty\ \penalty\ \penalty\ f\in\mathcal{F}, (2) or on sampling from the high-dimensional non-log-concave Bayesian posterior distribution d\Pi(f|Z^{(N)})\propto\exp(\ell_{N}(f))d\Pi(f) using MCMC algorithms [ 14 , 55 , 38 ] . The difficulty in these tasks lies in the non-convexity of the negative log-likelihood ( 2 ), which is in turn due to the non-linearity of \mathcal{G} . This has rendered classical theory of convex optimisation [ 10 ] and log-concave sampling [ 16 , 18 ] inapplicable, whence the computation of the above estimators could a priori be exponentially or ‘NP’-hard [ 5 ] . While there has been a significant progress in establishing statistical consistency results and convergence rates [ 42 , 39 , 1 , 22 ] as well as Bernstein-von Mises type theorems [ 47 , 40 ] , the literature on algorithmic or computational guarantees—concerned with the question of how to numerically access statistical estimators— has remained relatively limited [ 46 , 8 , 43 , 23 ] and relies on strong assumptions (as will be discussed further below). The central guiding problem of this paper is to develop methods which both possess provable statistical guarantees and global polynomial-time computability , and can be summarized as follows. The notion of computational cost considered here is based on the number of elementary arithmetic operations (such as additions and multiplications of real numbers), and will be formalized below. Existence problem for polynomial-time estimation methods. Does there exist a sequence of estimators, i.e. measurable functions of the data \hat{f}_{N}=\hat{f}_{N}(Z^{(N)}) , which (i) have a polynomial statistical convergence rate, \forall N\geq 1:\penalty\ \penalty\ \mathbb{E}_{f_{0}}\|\hat{f}_{N}-f_{0}\|^{2}\leq CN^{-\gamma}\penalty\ \penalty\ \penalty\ \text{for some}\penalty\ \penalty\ \penalty\ C>0,\gamma>0,\penalty\ \penalty\ \penalty\ \text{and} (ii) have a computational cost c_{N}>0 growing at most polynomially as N\to\infty . Our main contribution is to propose and develop theory for two statistical procedures which we respectively call ‘PDE-penalized M-estimators’ and ‘plug-in M-estimators’, which extend classical M-estimation, are computationally tractable and do not require access to PDE solvers. These methods are based on enforcing PDE constraints weakly . As a key prototypical non-linear inverse problem, we consider the Darcy flow model, which has served as a main testbed for new theory and methodology in applied mathematics and statistics [ 58 , 14 , 43 , 58 , 43 , 1 , 22 , 42 , 13 , 35 ] . To the best of our knowledge, no provably polynomial-time statistical inversion method is currently available; thus our approach yields novel polynomial-time feasibility guarantees (see Theorem 1.1 below) for the Darcy model, with explicit sub-quadratic o(N^{2}) arithmetic runtime guarantees. A second example is given by a non-linear inverse problem for the Schrödinger equation, e.g. relevant in photoacoustic tomography [ 4 , 47 , 46 ] . A conceptual novelty of this paper is to introduce a new notion of generalized stability which extend classical stability stability beyond the range of the forward operator. These new estimates are key in our proofs and yield a unified approach to proving both (i) statistical convergence rates and (ii) global polynomial-time computability for the proposed generalized M-estimators. A further consequence is that our polynomial-time estimators provide principled warm-start initializations for high-dimensional Bayesian computation, thereby enabling polynomial-time algorithms for approximating posterior expectations and for posterior sampling in the models considered; see Section 1.4

Read the complete text