PaperlayerView exact revision on arXiv

Source-linked AI summary

Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection

Charles-Alban Deledalle, Samuel Vaiter, Jalal M. Fadili, Gabriel Peyré

arXiv:1405.1164v2math.STstat.APstat.TH

TL;DR

Selecting continuous regularization parameters with SURE is costly by exhaustive search, while nonsmooth estimators can make SURE discontinuous and unsuitable for gradient descent. The paper uses finite differences to construct SUGAR, a risk-gradient estimate for quasi-Newton optimization; it is asymptotically unbiased and consistent for soft-thresholding.

  • Problem

    SURE can be discontinuous for nonsmooth estimators, ruling out standard descent schemes, while exhaustive parameter search can become prohibitively costly as parameter-space dimension grows.

    Source: §1 · p. 4

  • Method

    The paper forms a weakly differentiable finite-difference SURE approximation, explicitly computes its weak gradient as SUGAR, and uses that estimate for quasi-Newton parameter optimization.

    Source: §6 · pp. 28–29

  • Results

    The gradient estimate is asymptotically unbiased, and for soft-thresholding it is also consistent.

    Source: §3.1 · p. 10, §3.2 · p. 11, §6 · p. 29

  • Takeaways & Limitations

    Risk estimation adds operations, but the overall computation has the same complexity as the original iterative algorithm without risk estimation.

    Source: §4.2 · p. 16

    Theoretical guarantees for choosing the finite-difference step beyond the soft-thresholding analysis remain an open question.

    Source: §3.1 · p. 10, §6 · p. 29

Abstract

from arXiv · show

Algorithms to solve variational regularization of ill-posed inverse problems usually involve operators that depend on a collection of continuous parameters. When these operators enjoy some (local) regularity, these parameters can be selected using the so-called Stein Unbiased Risk Estimate (SURE). While this selection is usually performed by exhaustive search, we address in this work the problem of using the SURE to efficiently optimize for a collection of continuous parameters of the model. When considering non-smooth regularizers, such as the popular l1-norm corresponding to soft-thresholding mapping, the SURE is a discontinuous function of the parameters preventing the use of gradient descent optimization techniques. Instead, we focus on an approximation of the SURE based on finite differences as proposed in (Ramani et al., 2008). Under mild assumptions on the estimation mapping, we show that this approximation is a weakly differentiable function of the parameters and its weak gradient, coined the Stein Unbiased GrAdient estimator of the Risk (SUGAR), provides an asymptotically (with respect to the data dimension) unbiased estimate of the gradient of the risk. Moreover, in the particular case of soft-thresholding, it is proved to be also a consistent estimator. This gradient estimate can then be used as a basis to perform a quasi-Newton optimization. The computation of the SUGAR relies on the closed-form (weak) differentiation of the non-smooth function. We provide its expression for a large class of iterative methods including proximal splitting ones and apply our strategy to regularizations involving non-smooth convex structured penalties. Illustrations on various image restoration and matrix completion problems are given.

1 Introduction

The paper studies continuous-parameter selection for estimators of ill-posed inverse problems, where unknown signals are recovered from noisy, information-losing observations. It replaces difficult exhaustive SURE search with a differentiable risk-gradient estimate and develops derivative computations for iterative methods.

1 Introduction

  • Ill-posed recovery uses noisy observations and continuous parameters to estimate signals from measurements that lose information.The parameters control regularization, and the goal is to minimize expected reconstruction error.Source: §1 · pp. 1–3
  • The estimator framework covers convex variational problems with non-smooth regularizers and multi-parameter choices, as well as iterates of algorithms with parameter-dependent operators.The recovery mapping is assumed weakly differentiable in observations and parameters; proximal splitting methods are among the covered settings.Source: §1 · pp. 2–3
  • Because SURE is generally discontinuous in the parameters for non-smooth estimators, gradient descent is unavailable and exhaustive search can become prohibitive as parameter dimension grows.Derivative-free methods are also described as poorly scaling beyond two parameters.Source: §1 · p. 4

Contributions

  • The paper introduces SUGAR, a weak gradient of a finite-difference risk approximation that is asymptotically unbiased for the risk gradient and consistent for soft-thresholding.The estimate supports quasi-Newton optimization using first-order information.Source: Contributions · p. 4
  • A versatile procedure computes observation and parameter derivatives for iterative algorithms, including proximal splitting methods, and can extend to other weakly differentiable iteration operators.Illustrated methods include forward-backward, Douglas-Rachford, generalized forward-backward, and primal-dual algorithms.Source: Contributions · p. 4
  • Numerical simulations apply multi-parameter selection to image restoration and matrix completion problems.The paper reports these applications as numerical illustrations of the approach.Source: Contributions · p. 4

2 Overview on Risk Estimation

The overview presents SURE as an unbiased risk estimate based on degrees of freedom, then reviews ways to compute it when Jacobians are difficult or too large. Finite differences offer a black-box approximation whose chosen step makes the risk estimate weakly smooth in parameters, at the cost of bias.

2.1 Stein Unbiased Risk Estimator

  • Under weak differentiability and bounded weak partial derivatives, SURE uses an unbiased degrees-of-freedom estimate to estimate risk.The choice of weighting matrix A determines whether the target is prediction, projection, or estimation risk.Source: §2.1 · p. 5

2.2 Closed-form SURE

  • Closed-form Jacobians can be derived for some regularizers, but deriving and evaluating them is difficult in general and can be numerically unstable for large iterative problems.Using an approximate iterate's support in place of the true solution's support may be imprecise, especially for ill-conditioned problems.Source: §2.2 · p. 6

2.3 Monte-Carlo SURE

  • Monte-Carlo SURE estimates the Jacobian trace with a random directional derivative, avoiding costly full-trace computation in general settings.Its performance depends on the singular-value distribution of the operator; the authors report numerically accurate estimates for their recovery problems.Source: §2.3 · pp. 6–7

2.4 Iterative Differentiation for Monte-Carlo SURE

  • Iterative differentiation propagates directional derivatives through successive algorithm iterates to estimate degrees of freedom and SURE at an iterate.Prior work derived such expressions for forward-backward and split Bregman methods; the paper extends the approach to general proximal splitting algorithms.Source: §2.4 · p. 7

2.5 Finite-Difference SURE

  • Finite-difference SURE approximates the trace using perturbed observations, allowing the estimator to be treated as a black box when the step is sufficiently small.The step must balance approximation quality against numerical instability; evaluating one difference per data coordinate may be intractable at large dimension.Source: §2.5 · pp. 7–8
  • Choosing a positive finite-difference step introduces bias but makes the risk estimate weakly smooth in parameters, enabling quasi-Newton-style optimization.The paper frames this smoother objective as the key benefit of its grounded step choice.Source: §2.5 · p. 8

3 Risk Estimate Minimization

The section develops a finite-difference risk estimate whose weak gradient can guide parameter optimization where SURE is not differentiable. Under stated regularity assumptions, this gradient estimate is asymptotically unbiased; for soft-thresholding it is also consistent when the step size shrinks at an appropriate rate.

3.1 Stein’s Unbiased GrAdient Risk (SUGAR) Estimator

  • The weak gradient of the finite-difference SURE with respect to parameters is available in closed form, enabling quasi-Newton optimization of continuous parameter collections.Its computation uses Jacobians of the recovery mapping, which can be computed efficiently when that mapping comes from an iterative algorithm.Source: §3.1 · pp. 8–9
  • Under (A.1)–(A.3), as ε approaches 0, FD{µ}(y, ·, ε), normalized by P, can estimate the risk gradient, also normalized by P, provided P is large enough.Source: §3.1 · p. 10

3.2 SUGAR for Soft-tresholding

  • For soft-thresholding, normalized SUGAR is consistent when ε(P) tends to zero while P^-1 ε(P)^-1 also tends to zero.Equivalently, ε(P) must not decrease faster than the inverse dimension; the result applies at Lebesgue points λ > 0.Source: §3.2 · p. 11
  • The MSE-minimizing step appears to scale as Cσ/P^α for 0 < α < 1, while steps decreasing faster than 1/P yield diverging MSE as dimension grows.For fixed dimension, the reported MSE is finite at positive ε and increases as ε approaches zero; the optimal constants depend on µ0, σ, and λ.Source: Figure 1 · p. 12, §3.2 · p. 13

4 Differentiation of an Iterative Scheme

The section develops closed-form weak derivatives for iterates of fixed-point algorithms, enabling SURE-based risk estimation and SUGAR-based risk-gradient estimation. It applies the approach to proximal splitting methods, including primal and primal-dual algorithms.

4 Differentiation of an Iterative Scheme

  • Closed-form derivatives of iterative estimates with respect to observations and parameters support SURE risk estimation and SUGAR gradient estimation across proximal splitting methods.The framework covers iterates of fixed-point operators with auxiliary variables and a non-expansive reconstruction map.Source: §4 · p. 13

4.1 Iterative Weak Differentiability

  • Lipschitz iteration maps and initialization yield weakly differentiable iterates, while convergence of their weak Jacobians remains open in the general case.For proximal splitting examples, the relevant maps are 1-Lipschitz; weak differentiability follows by induction and the chain rule.Source: §4.1 · p. 14

4.2 Computation of SUREA MC for Risk Optimization

  • Directional derivatives computed recursively provide an unbiased risk estimate at each iterate without changing the algorithm’s global complexity.The method uses weak directional derivatives rather than explicitly storing the full observation Jacobian.Source: Figure 2 · p. 14, §4.2 · pp. 15–16

4.3 Computation of SUGARA FDMC for Risk Optimization

  • The full weak parameter Jacobian enables an asymptotically unbiased risk-gradient estimate with small computational overhead and unchanged complexity.Forward accumulation is practical when the parameter dimension is much smaller than the data dimension.Source: Figure 3 · p. 15, §4.3 · pp. 16–17

4.4 Application to Generalized Forward Backward Splitting

  • Generalized forward-backward splitting covers structured convex objectives under smoothness and proximal-operator assumptions, with forward-backward and Douglas-Rachford as special cases.The stated step-size condition for convergence is 0 < ν < 2/L.Source: §4.4 · p. 17

4.5 Application to Primal-dual Splitting

  • The primal-dual application handles objectives H(x,y,θ) + G(K(x),y,θ), and its convergence parameters satisfy τξ∥K∥² < 1.The authors choose this scheme and generalized forward-backward splitting for their flexibility and the range of problems they handle.Source: §4.5 · pp. 18–19

5 Examples and Numerical Results

The examples apply risk-gradient optimization to nuclear-norm matrix completion, total-variation deblurring, and multi-scale wavelet regularization. Across these cases, the reported SURE-based objectives support parameter selection, including scale-specific tuning for wavelets.

5 Examples and Numerical Results

  • The numerical examples apply closed-form proximal-operator derivatives to nuclear-norm, total-variation, and multi-scale wavelet regularizations to optimize one or more continuous parameters.The examples cover matrix completion, image deblurring, and compressed sensing.Source: §5 · p. 19, §5.2 · p. 22, §5.3 · p. 24

5.1 Implementation Details

  • The experiments use 100-iteration proximal-splitting algorithms, finite-difference step ε = 2σ/P^0.3, and BFGS as an example quasi-Newton optimizer.The authors note that other first-order methods may be considered, particularly when the risk has several local minima.Source: §5.1 · pp. 19–20

5.2 Nuclear Norm Regularization

  • A rank-57 matrix-completion solution had relative error 0.45, about a factor of two better than the least-squares estimate, and BFGS reached the optimum in 5 iterations.The finite-difference SURE and Monte Carlo SURE were visually equivalent estimates of prediction risk in this example.Source: §5.2 · p. 22, Figure 4 · p. 23

5.3 Total-Variation Regularization

  • 24.98 dB PSNR (+3.94 dB) was obtained for the total-variation deblurring solution selected by GSURE, although it remained somewhat blurred and showed staircasing.BFGS reached the optimum in 4 iterations; the projection-risk estimate and its finite-difference approximation deviated from the projection risk by similar amounts.Source: §5.3 · p. 25, Figure 5 · p. 25

5.4 Weighted ℓ1-analysis Wavelet Regularization

  • With three wavelet decomposition levels, increasing the number of per-scale parameters improved PSNR, whereas increasing levels with one global parameter did not.At the selected λ⋆, PSNR was maximal or not far from its maximum; the text reports automatic adaptation to image regularity when using per-scale parameters.Source: Table 1 · p. 26, §5.4 · pp. 27–28

6 Conclusion

The paper uses a finite-difference approximation to make risk-based optimization of multiple continuous parameters feasible for weakly differentiable estimators. It derives a weak gradient estimator with asymptotic unbiasedness, while noting unresolved step-size and optimization issues.

6 Conclusion

  • Finite differences for estimating degrees of freedom yield a weakly differentiable risk estimator whose explicitly computed gradient is asymptotically unbiased.The estimate is described as numerically smooth enough for quasi-Newton optimization.Source: §6 · pp. 28–29
  • The authors give an explicit weak-gradient computation strategy for a large class of iterative weakly differentiable algorithms, including proximal splitting methods.They exemplify the methodology on popular proximal splitting methods.Source: §6 · p. 29
  • The finite-difference step size was guided by analysis of soft-thresholding; guarantees such as consistency or optimality in more general cases remain open.The influence of step size on gradient-estimate smoothness and quasi-Newton performance also remains open.Source: §6 · p. 29
  • The approach is sensitive to local minima in the risk over the parameter collection, and extensions to non-weakly differentiable estimators or non-Gaussian noise remain future work.The authors also identify higher-dimensional parameter spaces and quasi-Newton settings as areas for possible improvement.Source: §6 · p. 29

A Proofs of Section 3

The appendix proofs establish asymptotic unbiasedness for the gradient estimator and consistency for soft-thresholding. They rely on weak differentiation, control of limits and integrals, and the soft-thresholding derivative structure.

A Proofs of Section 3

  • The asymptotic unbiasedness argument for SUGAR follows from the definition of the weak derivative and a proof strategy that orders limits, integration, and differentiation under the stated assumptions.The appendix also applies this strategy to the finite-difference degrees-of-freedom gradient.Source: A Proofs of Section 3 · pp. 29–30
  • The proof justifies exchanging limits and integration using integrable bounds and dominated convergence.The appendix also uses Fubini's theorem where the established integrability conditions apply.Source: A Proofs of Section 3 · pp. 31–32
  • The soft-thresholding weak Jacobian is diagonal, with entries +1, 0, or -1 across the specified threshold regions.The finite-difference derivative is evaluated piecewise using this weak derivative.Source: A Proofs of Section 3 · p. 32
  • For soft-thresholding, consistency follows from asymptotic unbiasedness and vanishing variance as the data dimension grows.The proof invokes Chebyshev's inequality.Source: A Proofs of Section 3 · p. 33

B Regularity of the proximal operator of a gauge

This appendix develops regularity results for proximal operators of gauges. For compact convex bodies containing the origin in their interior, the proximal mapping is Lipschitz in its positive parameter, and the result extends to compositions of such operators.

B Regularity of the proximal operator of a gauge

  • The appendix defines a gauge for a closed convex set containing the origin and records that the gauge equals the support function of the polar set.It also states that a closed convex set containing the origin is recovered by taking the polar twice.Source: B Regularity of the proximal operator… · pp. 33–34
  • For a compact convex set containing the origin in its interior, the proximal operator of its gauge is Lipschitz continuous in the positive parameter, uniformly over the input.The proposition states that its Lipschitz constant is independent of y.Source: B Regularity of the proximal operator… · p. 34
  • For a collection of such gauges, the corresponding composition of proximal operators satisfies a bound involving the parameter differences and the individual Lipschitz constants.The corollary extends the regularity result to multiple positive parameters.Source: B Regularity of the proximal operator… · p. 35

C Proofs of Section 4

The appendix derives weak-derivative formulas for mappings and iterative sequences by applying the chain rule. The parameter-direction argument requires Lipschitz continuity with respect to the parameters.

C Proofs of Section 4

  • Proposition 3 derives the formula for the mapping in (16) by applying the chain rule to Lipschitz-continuous mappings.Source: C Proofs of Section 4 · p. 35
  • Proposition 4 repeats the argument in the parameter direction when the required Lipschitz continuity with respect to θ holds.Source: C Proofs of Section 4 · p. 35
  • For the sequence of iterates, the proof applies the chain rule successively and uses Lipschitz continuity of the involved mappings to obtain the formula.Source: C Proofs of Section 4 · p. 35
Loading 1405.1164v2…