PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Rates For Regularization Of Statistical Inverse Learning Problems

Gilles Blanchard, Nicole Mücke

arXiv:1604.04054v1stat.ML

TL;DR

The paper asks for optimal convergence rates in noisy inverse learning with random design and unknown sampling distributions. It unifies direct and inverse estimation through an RKHS representation and analyzes spectral regularization under source conditions. The resulting strong and weak minimax rates match in both n-exponents and the dependence on source radius and noise variance.

  • Problem

    The paper addresses the need for a complete minimax analysis covering direct and inverse learning, general spectral regularization, intermediate norms, and general random designs.

  • Method

    The paper reduces the inverse problem to RKHS learning through a partial-isometry representation and analyzes spectral regularization under source and eigenvalue-decay conditions.

  • Results

    The minimax lower bounds match the upper rates in the exponent of n and in the multiplicative dependence on source radius R and noise variance σ², with strong and weak versions.

  • Takeaways & Limitations

    The framework provides strong and weak minimax-optimal rates for a broad class of spectral regularization methods in both direct and inverse learning settings.

  • Takeaways & Limitations

    The regularization choice assumes that eigenvalue-decay, source-regularity, source-radius, and noise-variance parameters are known, while adaptivity is outside the paper’s scope.

Abstract

from arXiv · show

We consider a statistical inverse learning problem, where we observe the image of a function $f$ through a linear operator $A$ at i.i.d. random design points $X_i$, superposed with an additive noise. The distribution of the design points is unknown and can be very general. We analyze simultaneously the direct (estimation of $Af$) and the inverse (estimation of $f$) learning problems. In this general framework, we obtain strong and weak minimax optimal rates of convergence (as the number of observations $n$ grows large) for a large class of spectral regularization methods over regularity classes defined through appropriate source conditions. This improves on or completes previous results obtained in related settings. The optimality of the obtained rates is shown not only in the exponent in $n$ but also in the explicit dependency of the constant factor in the variance of the noise and the radius of the source condition set.

1. Introduction

The paper studies noisy inverse learning with random, potentially unknown design distributions by reducing direct and inverse estimation to a unified RKHS framework. It derives matching strong and weak minimax rates for spectral regularization, including dependence on source complexity and noise variance.

  • Setting: The observation model samples g = Af at i.i.d. design points and adds centered noise, while the learner estimates both g and f.The design distribution may be unknown and arbitrary within the statistical learning setting.
  • Unified formulation: The operator image is endowed with an RKHS structure, making direct L2(ν) estimation of g and inverse HK-norm estimation equivalent through a partial isometry.The kernel encapsulates the information about A.
  • Upper rates: Spectral regularization achieves upper convergence rates in intermediate norms, both with high probability and for moments of all orders, under source, eigenvalue-decay, and qualification conditions.The regularization parameter λn is chosen appropriately, with q ≥ r + s required for the stated bound.
  • Lower rates: The minimax lower bound matches the upper rate in the exponent of n and in the multiplicative dependence on source radius R and noise variance σ².The lower bounds are formulated in weak and strong asymptotic versions.
  • Relation to prior work: The contribution extends prior work by treating direct and inverse problems, intermediate norms, general spectral regularization, and lower bounds without requiring additional unlabeled data.Earlier results often focused on A = I, L2(ν)-norm rates, or restricted regularization classes.

2. Notation and Preliminaries

The preliminaries model the inverse problem through a Carleman operator and its induced RKHS, then formulate population and empirical normal equations for noisy random discretization. Eigenvalue decay and source conditions provide the structural basis for the rate analysis.

  • Basic setting: The setting assumes a standard Borel input space, real outputs, and a linear operator A from an infinite-dimensional separable Hilbert space H1 to functions on X.The image of A is subsequently given a natural Hilbert-space structure.
  • RKHS construction: The feature map Fx represents evaluations of Af, and the kernel K(x1,x2) = ⟨Fx1,Fx2⟩H1 generates the RKHS HK = Im(A).A is a partial isometry onto HK, so the inverse problem can be expressed in the induced RKHS.
  • Population problem: The population inverse problem is Sνf = g in L2(X,ν), where Sν is the Carleman operator induced by the sampling distribution.This geometry treats the output of A in the natural population space associated with ν.
  • Spectral structure: The compact operator Bν has decreasing positive eigenvalues µj, whose decay measures the problem’s spectral structure and depends on the sampling measure ν.The eigenvectors form the basis used in the spectral analysis.
  • Discretization: Empirical sampling replaces ν with the empirical distribution, producing Sx and noisy observations yj = g(xj) + εj that discretize the population problem.The associated empirical normal equation acts on H1 and can be viewed as a perturbation of the population normal equation.
  • Assumptions and equivalence: The framework imposes source conditions and eigenvalue-decay assumptions, while corresponding direct-learning and inverse-learning conditions are equivalent under the RKHS isometry.This equivalence lets the paper complete rates for HK-norm estimation, including simultaneous source and eigenvalue assumptions and lower bounds.

3. Main results: upper and lower bounds on convergence rates

The paper defines upper and weak/strong minimax rates to track convergence exponents and multiplicative dependence on noise variance and source-condition radius. Its main results establish matching upper and lower rates for spectral regularization, including strong minimax optimality under intersecting model conditions.

  • Rate definitions: The rate framework tracks both the exponent in n and multiplicative scaling with noise variance σ^2 and source-condition radius R.Upper, lower, and minimax rates are formulated over indexed model families and p-th moments of estimation error.
  • Rate definitions: Weak and strong minimax lower rates differ in how they constrain the sequence of minimax errors.A strong lower rate must be an upper bound up to order, whereas a weak lower rate excludes minimax errors that are little-o of the proposed rate.
  • Upper bounds: Theorem 3.4 gives an upper convergence rate for spectral-regularized estimators in Lp for every p > 0 and interpolation norms with parameter s.The estimator uses a regularization function whose qualification satisfies q ≥ r + s.
  • Minimax optimality: Corollary 3.6 states that the estimator sequence is strong minimax optimal over model classes whose sampling distributions lie in P<(b, β) ∩ P>(b, α).This combines the upper result with the corresponding strong lower bound under the stated intersection assumption.

4. Discussion

The discussion highlights exponential deviation inequalities, the unresolved problem of adaptivity, and new weak and strong minimax lower-bound notions under one-sided eigenvalue assumptions.

  • Non-asymptotic, high probability bounds: Non-asymptotic exponential deviation inequalities underlie the analysis of error moments of all orders.They also could support asymptotics in regimes where parameters depend on n.
  • Adaptivity: The regularization choice assumes known eigenvalue-decay, target-regularity, and noise-variance parameters, making the procedure non-adaptive.The authors identify adaptive selection of λ as outside this paper’s scope and study it separately using Lepski’s principle.
  • Weak and strong lower bounds: Weak and strong lower bounds correspond respectively to lim sup and lim inf behavior in n.The distinction is motivated by minimal one-sided power-decay assumptions on eigenvalues.
  • Weak and strong lower bounds: One-sided power decay drives minimax rates, while excluding arbitrarily abrupt relative eigenvalue variations helps distinguish weak from strong bounds.The authors relate this condition to one-sided regular variation and suggest relevance beyond two-sided power-decay settings.
  • Smoothness and source conditions: Source conditions expressed through powers of the operator Bν provide a natural regularity measure for the target function.This follows the established approach in kernel-based statistical learning and deterministic inverse problems.

5. Proof of Upper Rate

The upper-rate proof builds concentration and operator inequalities into a main error bound, then selects regularization to balance bias and noise terms. Its asymptotic corollary tracks key parameter scaling but requires sufficiently large n.

  • Preliminaries: The effective dimension is defined as N(λ) = tr((B̄ + λ)^−1B̄), capturing the operator-dependent complexity used in concentration analysis.Trace-classness of B ensures N(λ) is finite.
  • Main error bound: The proof combines concentration propositions with operator perturbation inequalities to establish a main probabilistic error bound.The resulting bound is stated to imply the convergence rate.
  • Main error bound: The estimator uses a spectral regularization function with qualification q ≥ r + s under source and model assumptions.The proof separately handles regularity regimes including r ≥ 1 and r < 1.
  • Asymptotic rate: The resulting high-probability upper bound holds for sufficiently large n under the stated source, noise, eigenvalue, and qualification conditions.The proof concludes by collecting the preceding bounds with probability at least 1 − η.
  • Asymptotic rate: The asymptotic corollary’s leading constant does not depend on R, σ, or M, but its threshold n0 may depend on all parameters.Consequently, the corollary may not apply when parameters such as R or σ vary with n; the non-asymptotic theorem is then needed.
  • Asymptotic rate: The asymptotic proof reduces the upper bound to the dominant bias term Rλ_n^r and noise term σλ_n^−b+1/2, then balances them through the proposed λ_n.Lower-order terms are disregarded after requiring n to be sufficiently large.

6. Proof of Lower Rate

The lower-rate proof constructs separated source-class alternatives with controlled Kullback–Leibler divergence and applies a Fano-type minimax reduction. This yields weak and strong lower bounds under eigenvalue-decay assumptions.

  • Minimax reduction: The proof applies a general minimax reduction by constructing many separated parameters whose induced distributions remain statistically close.The lower bound follows from a Fano-type proposition based on separation and Kullback–Leibler control.
  • Minimax reduction: The target distance is d_s(f1, f2) = ∥B^s(f1 − f2)∥H1, covering intermediate norms through s ∈ [0, 1/2].The alternatives are constructed within the source class Ων(r, R).
  • Model construction: The lower-bound model uses Gaussian conditional responses with variance σ² and a common design marginal ν.For each target f, the conditional response distribution has mean Af(x).
  • Model construction: Proposition 6.4 constructs source-class functions that are separated in the target distance, have controlled divergence, and form a sufficiently large finite family.These properties provide the three ingredients required by the minimax reduction.
  • Weak and strong lower bounds: The lower-rate theorem applies the finite-family construction along a sequence of scales and takes a limsup or liminf to obtain weak or strong asymptotic bounds.The strong version requires the stronger eigenvalue condition, while the weak version uses the broader one-sided class.
  • Weak and strong lower bounds: When the upper and lower eigenvalue classes overlap, the strong lower bound applies to the larger model family and matches the corresponding upper bound.The overlap is characterized by simultaneous lower and upper power bounds on the eigenvalues.

Appendix A. Proof of Concentration Inequalities

Appendix A derives concentration bounds for the random quantities used in the main propositions, repeatedly applying Proposition A.1 under the model and moment assumptions. These bounds hold with high probability and support subsequent estimates.

  • Concentration framework: Proposition A.1 controls Hilbert-space-valued random variables under assumptions involving constants L and σ.The proposition is stated for a random variable on a probability space with values in a real separable Hilbert space.
  • Auxiliary random variables: The proofs define auxiliary random variables in H1 and in the Hilbert-Schmidt operator space to represent the quantities being concentrated.The constructions include ξ1 for the data-dependent term and ξ2, ξ3 for operator-valued terms.
  • Assumption verification: Assumptions on the model and operator bounds provide the moment or norm controls needed to invoke Proposition A.1.The arguments use the model assumptions, Assumption 2.1, and boundedness or trace-class properties.
  • High-probability conclusions: With probability at least 1 −η, Proposition A.1 yields the concentration estimates required in Propositions 5.2–5.4.The appendix applies the result to both data terms and operator terms, including the estimate involving (B̄ + λ)^−1/2.
  • Neumann-series step: The proof of Proposition 5.4 combines the concentration estimate with a Neumann-series argument whose convergence requires a suitable norm condition.The appendix introduces Cη and uses an assumption ensuring convergence of the series.

Appendix B. Perturbation Result

Appendix B establishes a perturbation inequality for powers of nonnegative self-adjoint operators, including Schatten and operator-norm settings. The proof uses power-series expansions and iterative operator bounds.

  • Perturbation inequality: For 1 < r, the appendix bounds the difference between powers of two nonnegative self-adjoint operators by a constant C_r times their difference.The operators are bounded by a common a and belong to a Schatten class, with an operator-norm extension for bounded non-compact operators.
  • Motivation: The result is needed because t^r is not operator monotone when r > 1, so a scalar Lipschitz argument does not suffice.The appendix notes that the naive Lipschitz-based estimate can fail even for finite-dimensional positive matrices.
  • Power-series proof: The proof rescales to a = 1 and expands (1 − z)^r and (1 − z)^(r−1) into power series on the unit disk.Absolute convergence on the disk, including its boundary, is used to control the expansion coefficients.
  • Inductive estimate: An algebraic identity for T^(n+1) − S^(n+1), together with Schatten ideal bounds, yields an inductive estimate for powers of I − B1 and I − B2.The induction gives a factor n multiplying the Schatten-norm difference between B1 and B2.

Appendix C. Auxiliary technical lemmata

Appendix C develops auxiliary probability lemmas that convert tail bounds into stochastic and moment estimates. The arguments use quantile representations and integrate suitable monotone upper bounds.

  • Quantile construction: Lemma C.1 relates a nonnegative random variable to a monotone tail-bound function through a pseudo-inverse construction.The construction produces a transformed variable whose distribution is controlled by a uniform variable on [0, 1].
  • Moment bound: The resulting stochastic comparison allows expectations of the random variable to be bounded by integrating the monotone upper-tail function.The proof identifies the function as an upper bound on the relevant quantile function.
  • Piecewise tail bounds: Corollary C.2 handles piecewise logarithmic tail bounds with separate parameter sets on (t0, 1] and (0, t0].The assumptions use bounds of the forms a + b log t^−1 and a′ + b′ log t^−1.
  • Final bound: The auxiliary proof completes the estimate by bounding the gamma-function contribution with monotonicity and collecting the resulting terms.The appendix uses a coarse monotonicity bound for t^p e^−t.
Loading 1604.04054v1…