Statistical Learning and Inverse Problems: A Stochastic Gradient Approach
Authors: Yuri Fonseca
Yuri Saporito
Venue: NeurIPS 2022 Accept (2022)
Keywords: Statistical Learning
Inverse Problems
Stochastic Gradient Descent

Abstract: Inverse problems are paramount in Science and Engineering. In this paper, we consider the setup of Statistical Inverse Problem (SIP) and demonstrate how Stochastic Gradient Descent (SGD) algorithms can be used to solve linear SIP. We provide consistency and finite sample bounds for the excess risk. We also propose a modification for the SGD algorithm where we leverage machine learning methods to smooth the stochastic gradients and improve empirical performance. We exemplify the algorithm in a setting of great interest nowadays: the Functional Linear Regression model. In this case we consider a synthetic data example and a classification problem for predicting the main activity of bitcoin addresses based on their balances. 

Statistical Learning and Inverse Problems: A Stochastic Gradient Approach
Yuri R. Fonseca
Yuri F. Saporito School of Applied Mathematics Getulio Vargas Foundation Rio de Janeiro, Brazil yuri. sat.satppttofogg.. br
Decision, Risk and Operations Columbia University
New York, NY yf yfonseca23@gab. cow.bbi..cbbbbbaaac.c...a.
Abstract
Inverse problems paramount in Science and Engineering. In this paper, sider the setup of Statistical Inverse Problem (SIP) and demonstrate how Stochastic Gradient Descent (SGD) algorithms can be used solve linear SIP. We provide consistency and finite sample bounds for the excess risk. We also propose a modi- fication for the SGD algorithm where we leverage machine learning methods smooth the stochastic gradients and improve empirical performance. We exem- plify the algorithm Regression model. In this case we consider synthetic data example and a classifi- cation problem for predicting the main activity of bitcoin addresses based on their balances.
setting of great interest nowadays: the Functional Linear
Introduction
Inverse Problems (IP) might be described as the search of an unknown parameter (that could be function) that satisfies given, known equation. Considering the notation:
= =[f*+ noise,
where f and y are elements of given Hilbert spaces, would like to compute (or estimate) f given the data for some level of noise. Typically, IPs are ill-posed in the sense that the solution does not depend continuously the data. There are several very important and impressive examples of IPs in our daily lives. Medical imaging has been using IPs for decades and has shaped the area, for instance, Computerized Tomography (CT) and Magnetic Resonance Imaging (MRT). For introductory text, see Vogel 2002).
A vast literature of IPs is devoted deterministic problems where the noise term is also element of a Hilbert space and commonly assumed small in norm, which is not usually verifiable in practice. In this work, will take different avenue, known Statistical Inverse Problems (SIP). This approach a formalization of IPs within probabilistic setting, where the uncertainty all measurements are properly considered. Our focus in this work is propose direct and practical method for solving SIP problems and, at the same time, provide theoretical guarantees for the excess risk performance of the algorithm develop. Our algorithm is based gradient descent framework, where stochastic gradients (or base learners that approximate the stochastic gradients) are used to estimate general functional parameters.
The paper is organized as follows. We finish this section contextualizing our paper in the broad literature and stating main contributions. In Section 2 we formally introduce the learning problem that we analyze. In Section we provide examples of practical problems that fits within formulation. In Section we provide our main results and algorithms. Finally, in Section 5 we provide numerical examples and a real data application for a Functional Linear Regression problem
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(FLR). Due to space constraints, some of the figures, proofs and experiments were moved to the supplementary material.
1.1
Contribution
We provide novel numerical method to estimate functional parameters in SIP problems using stochastic gradients. More precisely, we extend the properties and flexibility of SGD and boosting algorithms to broader class of problems by bridging the gap between the IP and machine learning communities.
Whereas most of the IPs methods focus on regularization strategies to "invert" the operator A, we propose gradient descent type of algorithm to estimate the functional parameter directly. Our algorithm works in the same spirit as Stochastic Gradient Descent algorithms with sample averaging. While results of SGD are well understood in the context of regression problems in finite and infinite dimensions and SGD is well understood in deterministic IPs, SGD have not yet been considered under the SIP formulation.
We show that our procedure also ensures risk consistency in expectation and high probability under the statistical setting. Furthermore, we propose modification in our algorithm substitute the stochastic gradients by base learners similarly to boosting algorithms, Mason et al. [1999], |Friedman (2001). This modification improve common challenge faced by SIP problems: the discretization procedures of the operator A that arises in SIP.
1.2 Literature Review
Historically, SIP was first introduced [Suuakkovand and Khalfin [1964] where IPs from Mathematical Physics were recast into a statistical framework. For a more structured introduction, we forward the reader to Kaipio and Somersalo [2004). Several advances were made in the parametric approach to SIP, where the unknown function is assumed to be completely described by an unknown parameter living in a finite dimensional space, see for instance Evans and Stark [2022]. In our paper, however, will consider the nonparametric framework described in Cavalier [2008). In this setting, the IP as a search of an element of an infinite dimensional space.
When considering IPs (and SIP, in particular), there are several ways to regularize the problem in order deal with its ill poseddesssss. For instance, one could consider roughness penalty or a functional basis as in Tenorio [200T]. Additionally, one could examine Tikhonov and spectral cut-off regularizations as in Bissantz et al. 2007]. For many of those standard approaches, consistency under the SIP setting and rates of convergences were established. See for instance [Bissantz et al. (2004), Bissantz and Holzmann 2008). A thoroughly discussion of stochastic gradient algorithms is outside the scope of this work and refer the reader to Zinkevich] [2003]. Nesterov al. (2018) and references therein.
There have been numerous applications of Machine Learning (and Deep Learning. in particular) to solve IPs, in recent years. However, in our opinion, these applications are akin of the capabilities that these new techniques could bring to this area of research. Some attention have been given to imaging problems as in Jin et al. [2017] and Ongie et al. [2020]. Under deterministic IP, the paper Li (2220) studies the regularization and convergence rates of penalized neural networks when solving regression problems. See also Adler and Öktem [2017] and Bai et al. (2020). Other important references regarding SGD for deterministic IP Jre et al. 2021 Tang et al. 2019). Jin et al. 2022).
The main examples we bring in our paper is the class of Functional I Linear Regression (FLR). This problem has drawn the attention of the statistical, econometric and computer science communities in the past decade, see Cai and Hall (2006). Yao et al. (2005), Hall and Horowitz) [2007]. The usual methodology applied this problem is the well-known FDA. For example, one could consider prespecified functional basis to regularize the regression problem Goldsmith et al. [2011] or one could use the Functional Principal Component (FPC) basis, Morris [2015]. More recently, methods inspired in machine learning for standard linear regression problems were also extended to the FLR setting, see for instance James et al. 20099, Fan et al. (0155) for methods that are suitable for high dimensional covariates or interpretable in the LASSO sense. In this work we show how our modification to the SGD algorithm can be seen as an averaging of boosting estimators and can also be used estimate FLR models in the high-dimensional setting.

---

2
Problem Formulation
We start by fixing probability space (,,, P) and a vector space of inputs. We denote the random input by X (2,, P) taking values in X and consider the space space [X, (X)), (x))
henceforth referred to as (X),, of functions X _ Rdd with inner product (g), (00,92))210 (2()) = K9g (X), 92 [X) and norm [191 = (x)]1 [| < +o0, where (.--) and are the inner product and norm of R.d.
We also consider a Hilbert space Hi with inner product ) Finally, we consider an operator A H (X). This operator defines direct problem and we assume that it known. Given H., use the notation A[f] (2),), i... A[f) is square-integrabl function A[f] X - R
We are interested in solving the statistical inverse problem related to A: jointly observing samples of X taking values in X, we observe noisy samples of A[ for some fixed, unknown f HI, which we denote by Y:
Y (X) +,,
where c is a zero-ne mean random noise. The problem we will pore over in this paper is the estimation of f based on this given sample.
Let e IR x R + R. be a point-to-point loss function as, for example, the squared loss Ely, y') = ! lly - y'1l?, for regression, or the logistic loss function y log(1 + -e-ry' yyy", ) for classification. We define the populational risk as:
RA(f) &
and we would like to solve:
inf RA(f),
(2)
fEr
where F C H with fo E F. We will denote by 0 the partial derivative with respect to the second argument.
Given sample, we will study how to control the excess risk of functional estimator f of f":
RA(f)
inf RA(
JEF
Instead of taking the standard route of solving the Empirical Risk Minimization problem and later establishing results for (3) in Section we show how our algorithms allow us tackle (3) directly by constructing stochastic gradients directly for the populational risk.
3 Examples: motivation
Before we formalize our results, we first motivate the study of Eq. (1) with few of applications. Each of those problems have myriad of solutions on their own. For more information on those IPs, see, for instance, Vogell (2002).
Deconvolution. This type of inverse problems relate the values of Y and X through the following convolution equation:
/
Y
k(X w)f(w)dp(() +
where X = - Rd, H = L (W, B, (u) and the kernel k Rd R is known. In this case, we
define the operator as:
Alf[(x) = / - ((x--))f(wdd((m)
Functional Linear Regression. Consider the scalar, multivariate functional linear regression: let X = D(0, 2T) (the space of right-continuous with left limits functions taking values in [gdxk with
We denote by B(%) the Borel sigma algebra in X and by μx the distribution of the random variable X.

---

the sup norm) so that (92) is the space of stochastic processes with sample paths in D T)) and norm
X
E
sup [E|o,T]
|x(1)
(4)
Moreover, HH = (T), taking values in R and Y is given by the following model
Y= Y= X(s)f(s)ds+c
where f E H.. Here we changed the notation from w in order to keep the classical notation from FLR. In this case,
A[](x) - L'" x(s)[(s)ds.
The model can be easily extended to deal with Y taking label values such as classification problem as we will show in the numerical studies.
Due to space constraints, provide examples in the FLR setting. In the supplementary material, we demonstrate how the algorithms presented in Section 4.3 can also be applied deconvolution problems.
4 Theoretical Results and Algorithms
In this paper, we consider the following set of assumptions. Assumption 4.1.
1. A H - (X) is linear, bounded operator;
2. i is a convex and C2 function in its second argument;
3. There exists 0o such that, for all f.g E IH,
sup E (Alo(()), 8n (1/1)) + A[O(()) 0815
<0;
4. f arg min RA(f) and (f -o;;
5. llf - f'll D < cc.
Assumption is our strongest one, since it imposes that our operator is linear and bounded. Nev- ertheless, linear SIPs encompass wide class of problems of practical and theoretical interest for engineering, statistics and computer science communities among others, a few them presented in Section Moreover, the nonlinear case could be similarly studied with more cumbersome notation and assumptions. Assumption is standard for gradient based algorithms and is commonly assumed in many learning problems. Assumption 3 mild integrability condition of the loss function monly satisfied in many practical situations. For instance, in the squared loss case, this assumption becomes (X)) [] oo, which is automatically satisfied since A[g] e (X)).. Assumption is needed so the problem we analyze indeed has a solution. Assumption is stating that the diameter of the
finite.
One should notice that our set of assumptions does include the class of ill-posed (linear) inverse problems since do not need to assume that A is bijective. If that were the case, it is known that then A would have a bounded inverse, and then, the IP would not be ill-posed.
In the next sections we provide our theoretical results. Instead of following the common approach of minimizing the Empirical Risk Minimization problem, we show how to compute stochastic gradients in order to control directly for the excess risk 3 both in expectation and in probability.

---

4.1 Preliminaries
Our first result allows to compute the gradient of the populational risk at a given functional parameter f. Before we present it, note that, by linearity, A : HH - L (X) is differentiable and, for
every g E H., we have that the directional derivative of A[f] in the direction g is given by
()( = lim 5-0 5
(Als + 6g] A(l) = Alg]-
Note that the directional derivative does not depend on the point f that we are evaluating the gradient. Let A" denote the adjoint operator of A defined as the linear and bounded operator A" L (x) H such that
(A[S), h) L*(x) (S, (T()),, for allʃ HI and h E (x).
The following lemma holds true:
Lemma 4.2. Under 1, 2 and of Asssupttiin 4.1 we have that
VRa(J) [or] E HH,
where (x) E|0,e[Y, A(]]()) X X=
Proof. Firstly, define, for fixed (X, Y),
(6) (Y, Alf + (X))
+ 6A[gl(X)).
Then, we get the directional derivative of the risk function in direction by applying the Taylor formula for sb as function of around O:
DRA(f)(g)
lim 6-+0
(f 8g) - RA(f))
lim E 8-0
5 (Y)A))))))))
+500 ()ox(Alo(X)), Alo](X), O22
Alo)())
)
where comes from the Taylor formula and it is between -00 and 0o. for some fixed 0g > 0. Hence, by Assumption 3, we find
DRA(1 -R (E (O
By the definition of & and by conditioning in we find
( = (X), A[gl (X)) (Ø), Alg)) = (A" (651.g9..
Finally, we get that the descent direction RR (f) is given by A* E H..
4.2 Unbiased Estimator of the Gradient
In order to define unbiased estimator of the gradient VR consider the following assumption: Assumption 4.3.
1. H a Hilbert space of functions from W to R
2. There exists a kernel &b : X x W - I xa such that
A [ E w))()) H.
for all w W and E (X).
Several examples, including the Functional Linear Regression, we will verify in Section 5 satisfy this assumption. Additionally, there are two situations that encompass many important SIPs. The first one is restriction of the Hilbert space HI without restrictions on the operator A:
The adjoint of linear, bounded operator always exists.

---

Lemma 4.4, Assumption 4.3 is verified H. is Reproducing Kernel Hilbert Space (RKHS).
Proof. For simplicity of notation, we assume k Notice that, by the RKHS assumption. P- (X) + I. defined as (Pw (h) = A [m]](ww), for h E (X)), is an element of the dual of (X),, ie. there existis Mw < +:00 such that
(kw( A [w]]] S Mw [|A]||]]
Hence, by the Riesz Representation Theorem, there exists a kernel ( w) : X - Rd such that, for all (X)..
[h)) = (w
[X w), (X))(
desired.
Remark 4.5. If the RKHS H has kernel K, then & is given by Φ(x, w) = A[K(, w)](x). Indeed, by the definition of kernel in the RKHS and the definition of A", we find
A [']] (A" [A'[b, (s, w)) (h, A[K(, (2))
The second situation considers a different (and somewhat less restrictive) assumption for the Hilbert space and a particular, yet very general, class of operators A, called integral operators.
Lemma 4.6. TH (2,, B, n1) taking values in R* and A is integral operator of the form:
A[f(x)) = = =/x s(x, w) (l((()d((W))
where &p is kernel taking values in Bd such that spxx, L (W, B, p.), then Assumption 4.3 verified.
Proof.
By the definition of the adjoint operator, find (A(f) h)) E(AII)(X),
(f. (2))
=E < (XX, w) (w)d() 1) }
E [xp(X, w) ww)(w), du(w) = (x, -)xnn())))x)))))
Hence, we conclude A" A [h](w) E | (x(X)) which implies Assumption 4.3 with kernel (xx w) (xx, w)T.
Remark 4.7. The class of integral operators delivers several of the most important linear IPs. Addi- tionally, using Green's ' function formulation, some PDEs IPs could also be recast as integral equations. For instance, the recovery the initial condition of linear PDE with known Green function and observing the solution of the PDE at some future, fixed time.
Under Assumption 4.3 Lemma 4.2 implies the following very useful result that the cornerstone of method.
Corollary 4.8. If Assumption is verified, then the gradient of the risk function with respect given by
VRA(f(()) = EX w (X))
Because of the results above, it is possible to construct an unbiased estimator for the gradient for the risk function for any f. In fact, for given sample (x, y) and fixed function f. we define, for any w E W.
xw; = ((x, w) (21(x,,
(5)
Therefore, conditioning in X, we find
Elu (w: X, Y) [ X, w A EEE (wteeKXXW)))X(/,// XX EE d XX w EYO AIF] X E d X, w
(X) = (R)
The main benefit that with a single observation of (X, Y), we are able to compute an unbiased estimator for the gradient of the risk function under the true distribution.

---

4.3 Proposed Algorithms
Inspired by Corollary 4.8 we propose the following SGD algorithm for SIP problems that we called SGD-SIP: given an initial guess fu, for each step i, we compute, following Eq. (5), an unbiased estimator u, for the gradient of the loss function. Next, we update an accumulated functional parameter by taking stochastic gradient step in the direction of u, with step size o,, In the last step, we average all the accumulated gradient steps in the same spirit as Polyyk and Juditsky [1992]. The choice of the step size needs to satisfy two criteria: Σ O; sublinear in n, and n02 - 00 as
+ +00. We formally justify those desired properties in Theorem 4.9
Algorithm 1: SGD-SIP
input sample (x operator A, initial guess fo
output: fr
do
-fo:
for
S i S do
Compute us (w) 1(x,, w))2ely,, A(0--(())) 9. = 9 a,u;;
end
Set fn -i=1 96
Algorithm uses only one sample at time in order to estimate the gradient the true risk function. In order to preserve this property, we make the number of iterations equal to the sample size; it cannot be larger. This connects with the stopping rules in iterative algorithms in IP.
Algorithm has a limitation common to many approaches to Inverse Problems: one cannot hope to compute u; for every possible w; and some discretization of the operator needed, see Kaipio and Somersalo [007]. Since the SGD-SIP algorithm only computes the stochastic gradient in the points of discretization, it risks overfitting the data and provides non-smooth estimators. Next, we motivate Algorithm 2 in order to overcome the discretization problem by leveraging machine learning methods.
Consider that the space W was discretized in a grid of size The In order to fully estimate the function (w) for every E W, we consider hypothesis class H. and, in each step, we fit function hū E H. on the stochastic gradient u, in the discretized grid of W. Note that in this case, F will be given by the linear span of the class H. Each of these functions hद can be seen as a base-learner in the same spirit of Boosting estimators, widely used in standard regression problem in the context of SIP Mason et al. 1999. Friedman 2001]. Next we present our algorithm ML-SGD.
Algorithm 2: ML-SGD
input sample (x,, y;) discretization (wy}}= of W, operator A, initial guess fo
output: fm 9o
fo:
for 1 S S do
for 1 I j S the do
Compute us (w;) (x,,, w, w,)02((y,, ([::-1((x3)
end
hr E arg minl NEw ( h(:;)));
J. 9:-1 a,h;;
end
Set in
1 Σi #6:
The goal of ML-SGD is twofold. First, it allows us to interpolate the function h2 to points w not used in the discretization grid. Second, the ML procedure smooths the noise each gradient step calculation leading to smoother approximations that helps avoiding fver-fitting. We show in Section in the supplementary material the benefits of such an approximation when estimating the functional parameter fo in both simulated and empirical examples.
7

---

4.4 Main Result
Our main result is a finite sample bound for the expected excess risk of Algorithm [ extends to Algorithm i the case where the base learner are also unbiased estimators.
The result also
Theorem 4.9. Under Assumptions 4.1 4.3 and if the kernel satisfies C' = supxex || >)1 < +o
we have the following performance guarantee for Algorithm 1:
D²
M(A,F)
E (f( - inf Ra(f) feF
+
a4
2nan
where = -(B]) 11 < <0.
The proof of the theorem is provided in the supplementary material. Theorem 4.9 implies that we pick the decreasing sequence {a, (oi)/=1 so that na., oo (an, cannot decrease too fast) but fast enough so that 3, Ex= a; + 0, then we get the convergence result. For instance, one could take 0; = n for some fixed number 1) normally taken to be in (0, 1). In this case, the excess risk decreases in expectation with rate (n)/vn).
Theorem 4.9 also implies that the excess risk converges to zero in probability. For a; = n/ Vi is straightforward to check that
lim sup IP (RA(FN) inf RA(F) 00 0) = 0.
JEF
Finite sample bounds with high probability can also be provided under stronger assumptions about the stochastic gradients. See for instance Nemirovski et al. [2009]
5 Functional Linear Regression: numerical studies
In this section, we provide two applications of the Functional Linear Regression problem. We first demonstrate the performance of both algorithms in simulated data and next provide example for generalized linear models, applied to an classification problem using bitcoin transaction data. In Appendix B and Appendix [ also provide an additional numerical study in different type of Inverse Problem: The deconvolution problem.
As we have seen in Section 3 the operator in the FLR case is given by
A[f((x) / (s)ss
(6)
Remember that in this example we are denoting w by s. Hence, by Lemma 4.6 we find ()) E [X (x) (X)] One can easily verify that A*[s] E IH by the assumption that the norm of X is finite. Therefore, we have (xx,s) s) x" (s), and we find, as in Eq. (5)
us(s) = x" (s) Al. 1xxx)).
5.1 Synthetic Data
We will consider the simulation study presented in González-Manteigga and Martinez-Calvo [201]] Specifically, we set W = [0, 1]. (z) sin(4xz), and X simulated accordingly a Brownian motion in [0, 1]. We also consider a noise-signal ratio of 0.2. We generate 100 samples of X and Y with the integral defining the operator A approximated by finite sum of 1000 points in [0, 1]. We test for the same specification when f² oscillates between 1 and 1 in the points 0.25, 0.5, 0.75, 1. For the observed data used in the algorithm procedure, we consider a coarser grid where each functional sample is observed at only 100 equally-spaced times. For the ML-SGD algorithm, we used smoothing splines and regression trees as base learners. We compared the results with Penalized Functional Linear Regression (PFLR) with cubic splines and validaaion to select the number of basis expansion; we also compare with Landweber iteration method. In order to fit the PFLR model, we
This assumption is satisfied for all the examples analyzed in this paper.
8

---

used the package refund Goldsmith et al. [202]] available in R. Detailed numerical results with error bars are displayed
Aopeedii[Csshowwee that the ML-SGD algorithm is at least as competitive as state-of-the-are tailored specifically to FLR problems and superior to Landweber iterations, general method for Inverse Problems. In Figure [ we can see that both SGD-SIP and Landweher iterations achieve similar fit performance. PFLR with cubic splines and degree of freedom of 20 achieved a similar performance than ML-SGD with splines with 10 degrees freedom. Both essentially recovers the true function cº perfectly. Despite the smoothness of f ML-SGD with regression trees with 30 terminal nodes was also able to approximate f well. Here we focus only on the methods with best performance. ML-SGD with both regression trees and splines with 20 degrees of freedom were able to recover the true function as well as PFLR with cubic splines and 20 degrees freedom. In the appendix, simulations. Both Landweber iterations and the SGD algorithm are noisier and seems to overfit the data. We refer the reader Appendix C for detailed comparison among the methods.
provide bar plots with the MSE under both scenarios with error bars for different
model
model Landweber MLSGD-5p--200
Landwebor
NLSG p-53--11
MLSG D-Tre--33
PPLR, (20
(a)
(b)
Figure I: Fitted results for synthetic data. True values for fo are displayed black dots.
5.2 Real Data Application
Next we consider classification problem in the FLR setting. The data contains 3000 bitcoin addresses spanning from April 2011 I and April 2017 and their respective cumulative credit, which is described as 501 equally spaced observations for the first 3000 hours of each address, normalized in the interval [0. 1]. For each address, we also have a label describing if the address was used for criminal activity, commonly called darknet addresses. In Table we present summary of the data. We refer the reader to Appendix A for more information about the data set used that we make available online.
Table 1: Summary information for the bitcoin wallet observations.
category
obs
mean initial credit
mean final credit
Darknet Marketplace
1494
242
1255
Exchanges
381
807
14278
Gambling
371
95
2289
Pools
366
1086
14071
Services/others
388
184
3883
Here we use the cumulative credit curve at each point in time as the explanatory variables X E = D([0, 1)) and Y E {-1,1} as the predicted outcome for the indicator variable that the category is durknet (addresses associated with illegal activities). We propose the following model: log P-Y P S-" (())X(s) By using the log-likelihood of the negative binomial, one can include gradient with respect to the functional parameter directly Equation 77) in order to use framework. Other type of classification loss functions can also be used in the same spirit.

---

We compare the SGD-SIP and ML-SGD algorithm with PFLR. For the ML-SGD algorithm, we use two types of base learner, regression trees and cubic splines. The step sizes are taken to equal of the form O Vi), where i 1. 1.... nt is the current step of the algorithm and n the total number of steps/sample. For the PFLR algorithm, we use cubic splines with different degrees of freedom and quadratic penalty term. We highlight that those choices of splines and penalty term are widely used in the literature, see, for instance, Goldsmith et al. [201]. In Table 2
we provide 3-fold cross validation the accuracy and kappa metrics. The SGD-SIP Algorithm achieved the best average performance in terms of accuracy. The same performance is achieved by the Functional PLR with cubic splines with number of knots equal to 20 and penalization for the derivative the estimate, The ML-SGD algorithm with smooth splines with 20 degrees of freedom also achieved similar performance with smoother estimator. Although the benchmark is as good as the ML-SGD algorithm, we highlight here that PFLR is tailored to Functional Data Analysis problem, while approach is flexible for many different types of Linear SIP problems. Moreover, our algorithm can make use of only one sample each iteration, which makes it suitable also for online applications. We refer the reader to the supplementary material for results under different choices of step size, number knots and base functions for the PFLR model, other metrics and confusion matrices. In order to fit the PFLR mode, we used the package refund Goldsmith et al. 2021 available in R.
Table 2: Results for three fold cross-validation.
fold
fold _
fold_3
avg_ accuracy
ML-SGDD-plinn(k 20)
0.76
0.80
0.79
0.78
ML-SGD-spline(K 10)
0.72
0.74
0.74
0.73
ML-sGD-treeddetth 20)
0.78
0.77
0.78
0.78
SGD-SIP
0.79
0.77
0.82
0.79
FPLR(K 10)
0.76
0.75
0.73
0.75
FPLR(K 20)
0.77
0.81
0.80
0.79
Conclusion
In this work, provided a novel numerical method to solve SIP based stochastic gradients with theoretical guarantees for the excess risk. Moreover, we have shown how one can improve algorithmic performance by estimating base-learners for each stochastic gradient in the same spirit as boosting algorithms. Our framework can be applied in a variety of settings ranging from deconvolution problems, Functional Data analysis in both regression and classification problems, integral equations and other linear IPs related to PDEs. We demonstrate the performance of our method with numerical studies and also with real world application data and comparing with widely used techniques the FLR setting.
10

---

References
Curtis R Vogel. Computational methods for inverse problems. SIAM, 2002.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent in function space. In Proc. NIPS, volume 12, pages
1999.
Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of statisticx, pages 1189-1232, 2001.
V.N. Sudakowand and L.A. Khalfin. Statistical approach to ill-posed problems in mathematical geophysics. Sov Math.-Dokl, 157, 1964.
J. Kaipio and E. Somersalo. Statistical and Computational Inverse Problems. Springer, 2004.
Steven N Evans and Philip B Stark. Inverse problems as statistics. Inverse problems, 18(4):R55, 2002.
Laurent Cavalier. Nonparametric statistical inverse problems. Inverse Problems, 24(3):034004, 2008.
Luis Tenorio. Statistical regularization inverse problems. SIAM review, 43(2):347-366, 2001.
Nicolai Bissantz, Thorsten Hohage, Axel Munk, and Frits Ruymgaart. Convergence of general regularization methods for statistical inverse problems and applications. SIAM Journal Numerical Analysis, 45(6):2610- 2636, 2007.
Nicolai Bissantz, Thorsten Hohage, Axel Munk. Consistency and rates convergence of nonlinear tikhonov regularization with random noise. Inverse Problems, 20(6):1773, 2004.
Nicolai Bissantz and Hajo Holzmann. Statistical inference for inverse problems. Inverse Problems, 24(3): 034009, 2008.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. Proceedings of the 20th international conference on machine learning (icml-03) pages 928 936, 2003.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Kyong Hwan Jin, Michael T McCann, Emmanuel Froustey, and Michael Unser. Deep convolutional neural network inverse problems imaging. IEEE Transactions on Image Processing, 26(9):4509-45)) 2017.
Gregory Ongie, Ajil Jalal, Christopher Metzler, Richard G Baraniuk, Alexandros G Dimakis, and Rebecca Willett. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas in Information Theory, 1(1):39-56, 2020.
Housen Li, Johannes Schwab, Stephan Antholzer, and Markus Haltmeier. NETT: Solving inverse problems with deep neural networks. Inverse Problems, 36(6):065005, 2020.
Jonas Adler and Ozan Öktem. Solving ill-posed inverse problems using iterative deep neural networks. Inverse Problems, 1240077 2017.
Yanna Bai, Wei Chen, Jie Chen, and Weisi Guo. Deep learning methods solving linear inverse problems: Research directions and paradigms. Signal Processing, page 107729, 2020.
Bangti Jin, Zehui Zhou, and Jun Zou. On the saturation phenomenon stochastic gradient descent for linear inverse problems. SIAM/ASA Journal on Uncertainty Quantification, 9(4):1553-15588 2021.
Junqi Tang, Karen Egiazarian, and Mike Davies. The limitation and practical acceleration of stochastic gradient algorithms in inverse problems. In ICASSP 2019-201 2019 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7680-7684. IEEE, 2019.
Bangti Jin, Zehui Zhou, and Jun Zou. On the convergence of stochastic gradient descent for nonlinear ill-posed problems. SIAM Journal on Optimization, 30(2):1421-1450) 2020.
T Tony Cai and Peter Hall. Prediction in functional linear regression. The Annals of Statistics, 34(5):2159-211 2006.
Fang Yao, Hans-Georg Müller, and Jane-Ling Wang. Functional lincar regression analysis for longitudinal data. The Annals of Statistics, pages 2873-2903, 2005.
Peter Hall and Joel L Horowitz. Methodology and convergence rates for functional linear regression. The Annals of Statistics, 35(1):70 91, 2007.

---

Jeff Goldsmith, Jennifer Bobb, Ciprian M Crainiceanu, Brian Caffo. and Daniel Reich. Penalized functional regression. Journal of computational and graphical statisticx, 2004):80--51, 2011.
Jeffrey S Morris, Functional regression. Annual Review of Statistics and Its Application, 2:321-359, 2015.
Gareth M James, Jing Wang, and Ji Zhu. Functional linear regression that's interpretable. The Annals of Statisticy, 37(54))0033-2108, 2009.
Yingying Fan, Gareth M James, and Peter Radchenko. Functional additive regression. The Annals of Statistics, 43(5):226-22225, 2015.
Boris Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and opfimization, 30(4))838-855, 1992.
Jari Kaipio and Erkki Somersalo. Statistical inverse problems: discrctization, model reduction and inverse crimes. Journal of computational and applied mathematics, 198(2):493-504 2007.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1774-169, 2009.
Wenceslao González- González-Mantciga and Adela Martínez-Calvo. Bootstrap in functional linear regression. Journal of Statistical Planning and Inference, (41(1):453 461, 2011.
Jeff Goldsmith, Fahian Scheipl, Lei Huang, Julia Wrobel, Chongzhi Di, Jonathan Gellar, Jaroslaw Harezlak, Mathew W. Mcl.ea,, Bruce Swihart, I Luo Xiao, Ciprian Crainiceamu, and Philip T. Reiss. refund: Regression with Functional Data, 2021.
R- www..eprooec.ooorpaaaaaeeeereeee
package version
0.1-24.
Manuel Fehrero-Bande Wenceslao Gonzalez-Manteiga, Brenda Prallon, and Yuri F Saporito. Functional classification bitcoin addresses. arXiv preprint arXiv:2202. /2019, 2022.
12


Reviews:
[{"review_id": "omqYW6jDEcX", "reviewer": "Reviewer_ea5U", "summary": "In this paper, the authors propose an SGD approach to solve statistical inverse problems (SIPs). Formally, the problem is to find the parameter $f$ satisfying the relation $Y = A\\[f\\](X) + \\varepsilon$, where the operator $A$ is known, and $Y$ and $X$ are given observations. This can be achieved by minimizing the quantity $\\mathcal{R}_A(f) = E\\[ l(Y, A\\[f \\](X))\\]$, where $l$ is a loss function. For $A$ linear and bounded, and with additional (milder) assumptions, the authors are able to write the gradient of $\\mathcal{R}_A(f)$ as the average of a function $u_f$, whose expression has to be derived explicitly for the specific SIP considered. With this result at hand, the authors propose two algorithms to solve SIPs in the spirit of SGD, where the average giving the gradient is approximated by one sample at each iteration. Their main result proves a performance guarantee for such algorithms. The authors apply the proposed techniques to functional linear regressions, performing numerical tests both on synthetic and real data, and deconvolution (discussed in the supplementary material).", "questions": "I have the following questions/comments for the authors:\n\n1. I would appreciate it if the authors could comment on my concerns in the previous section. I believe that addressing these points in the main text would be beneficial for the paper.\n\n2. The presentation of numerical results could be improved. I believe that Figures 1 and 2 in section 5.2 are a little aimless, as they do not really support any claim in the paper (they take up quite some space, though). Moreover, the label font size in Figure 1 is too small and the x-axis has no scale (or ticks). It is unclear what's on the y-axis in Figure 2 ($f(s)$? If so, we don't know the real $f$ anyway...what is the point?). In any case, I would suggest combining the two figures and using the same format for both. The synthetic data experiments could be useful to test robustness against the signal-to-noise ratio.\n\n3. The sentence 'We highlight that those choices of splines and penalty term are widely used in the literature', line 230, might need a reference.\n\n4. I am not sure I understand what 'with only one observation' means in this sentence: 'The main benefit is that with only one observation we are able to compute an unbiased estimator for the gradient of the risk function under the true distribution', line 158/159. Can you clarify?\n\n5. I would change the article 'An' in the title with 'A'.\n\n6. Line 215 'where and each' -> 'where each'?\n\n7. Line 103/104 'to control directly to tackle (3) directly' -> 'to tackle (3) directly'?", "limitations": "The authors have partially addressed the limitations of their work, though there is space for improvement (see the section Strengths And Weaknesses).", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proposes an SGD approach to solve SIPs, thus providing, to the best of my knowledge, an original contribution (at least within the probabilistic formulation of inverse problems). The exposition is clear and compact (section 5 could be improved, though), and the related literature is well covered. \n\nMy main concerns with this work are the following:\n\n1. General applicability of the proposed method. Even considering the (not so week) Assumption 4.1, the proposed method crucially depends on the possibility of identifying the kernel $\\phi$ appearing in Lemma 4.3. The authors do not discuss the limitations associated with identifying $\\phi$, and only present applications where this is doable. Moreover, the proposed algorithms are designed (or, at least, presented) following Corollary 4.4, i.e. considering the squared loss function. It is unclear to me if Theorem 4.5 applies only under this corollary. \n\n2. Actual improvements over other methods. The comparisons proposed by the authors seem to suggest that their algorithms are at most as good as the FPLR (see Table 2). I wonder then what are the actual advantages of solving SIPs with the proposed SGD algorithms, particularly considering the previous point. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Y5Mx8KhRya", "reviewer": "Reviewer_m9Kg", "summary": "This paper studies a method of solving functional inverse problems. The problem set-up is (X,Y) are from a particular distribution, with Y = A[f](X) + noise, where f is some function defining the relationship between X and Y. The major example is: if X is a function on [0,1], then Y = int_0^1 f(t)X(t)dt + noise. The goal of the general problem is to find f.\n\nThe paper introduces a means of finding an appropriate f from a class of functions by stochastic gradient descent, emphasizing results for a particular context: functional linear regression. They review previous results and other techniques for solving stochastic inverse problems, define the problem rigorously, and present example problems. They then give the main algorithm, a sort of functional SGD, and identify issues with it due to functional complexity involving the kernel. To address this, they provide another algorithm which uses the iteratively improving f in the SGD algorithm to teach common ML learners, which are used to build f instead of a kernel. They provide probabilistic error bounds and show a probabilistic convergence rate of O(1/ \\sqrt(n)). They then present synthetic and natural experiments, with a comparison to another method.", "questions": "Questions:\n- On Theorem 4.5, you claim the result is independent of the dimensionality of the codomain of L_2(X) and L_2(W), the values of n and k in R^d and R^k. Your proof deals with d=1. Are you sure your results are independent of the value of d? If you are sure, perhaps you could include a comment about how all inferences are independent of the values of k and d?\n- Table 4 says SGD outperforms FPLR, but figure 3 indicates FPLR outperforms SGD. Is this an error? Furthermore, I find it odd that all FPLR have the same error in table 4. Are they the same function? (Aside: is SGD = SGD-SIP?)  This makes it look like some of your experimental results are incomplete or incorrect. Furthermore, the thoroughness of the deconvolution results are much less thorough than the FLR in the appendix. Please comment.\n- The order of convergence for the algorithm, O(1 / \\sqrt(n)), seems not so great, and the algorithm that has this guarantee looks jagged and compares poorly to the already established method. Can you comment on the order of convergence, and how it compares to other methods?\n\nMinor issues:\n- Can you provide a table for results of B2?\n- Is the equation at the bottom of page 3 a component-wise integral, since X takes values in R^d but f takes values in R? This may trouble readers if not mentioned. If this is true, is it necessary X take values in R^d?\n- On (138). If x is a specific realization of X, then I believe your conditioning is backwards: you want \\phi(x) = E(\\partial*l(Y,A[f](X))| X = x). Or do you write it the way you do because you use eq (1), with Y still a random variable of the noise, although is X specified? If this is the case, are you taking the expectation only over the noise, \\epsilon? On the other hand, if x is set and Y takes one value for a specified x, what distribution is the expectation over?\n- Dimensionally not accounted for in (117), (141), etc. EG: A(g)[X] in R^d, so (A[g](X))^2 not defined if d>1). Also, \\partial l(...)*A[g](X) is R^d x R^d, should you should use transpose or standard inner product?\n- Posed assuming the 1-d case, dropping the inner-product brackets (144,147,...). Not sure if this is notationally standard.\n- (147) A*[g](w) is in R^k, but E(\\Phi((X;w)g(X)) is in R^d. Even if d = 1, dimensions do not match. Is \\Phi in normally in R^{k x d}?\n\nTypos/minor issues:\n- Sentence in (64-66) is confusing, hard to understand.\n- \"a prespecified basis functions\" (74-75)\n- \"to control directly to tackle (3) directly\" (103-104)\n- \"Y is giving by\" (bottom of page 3)\n- \"also in deconvolutional problems\" (112)\n- indeed have a solution (128)\n- does not dependent (136)\n- a coarser grid where and each (214-215)\n- Broken references in (380)\n- Figure 3 says FPCR.", "limitations": "- This is my first time being exposed to the topic of the statistical inverse problem, so I am unfamiliar with some of the relevant literature.\nThey apply the method to standard quadratic loss, and only to FLR and deconvolution. I would like to see an exposition, even if brief, supporting the potential breadth of application. Even better, applications to more problems. This may due to my lack of familiarity with the subject.\n- However, a low rate of convergence for the excess risk, and some choppy graphs for algorithm 1 seem a liability, To be fair, this is made up for with strong and interesting theoretical results that could be built of of, and a strong showing for the ML-assisted algorithm.\n- Is it possible the ML-assist may not give much of a boost, or may do harm, if the kernel-sampling in not well suited to the ML-learners?", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n-great organization\n-clear examples\n-good mathematical exposition\n-solid theoretical results\n-clear writing\n-interesting and good experimental results\n-overall interesting problem\n\nweaknesses:\n- experimental results seem inconsistently or incompletely reported.\n- a few vagaries in mathematics (see questions)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P7IJ6j6PPdD-", "reviewer": "Reviewer_Vx5e", "summary": "This paper mainly focuses on the formulation of SIP (statistical inverse problem) and the method to solve SIP.\nIn the first part of this paper, the authors formulate SIP utilizing functional analysis. They also give some examples of SIP under this formulation.\n\nIn the second part, after showing how to calculate the gradient under this setting, they propose two SGD-based algorithm to solve SIP. They give a finite sample bound for the expected excess risk of their algorithms.\n\nIn the last part, the authors provide numerical results for two applications of the Functional Linear Regression problem. ", "questions": "1.In Lemma 4.3, you've mentioned that there exists a kernel \\Phi. Can this kernel be easily found in many SIP problems (other than functional linear regression)? \n\n", "limitations": "It might be interesting if the results can be extended to nonlinear SIP (or any other relaxation of Assumption 4.1).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The authors give a novel numerical method to solve SIP, which shows good originality. They give both theoretical analysis and real data experiments, which shows the good quality of this paper. \n\nWeakness: It seems that they do not show the intuition and advantage of their new method, which makes this paper somehow unclear. And the proof techniques are just classical convex optimization analysis. Therefore this paper lacks significance to some extent.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept