Stochastic Gradient Descent for Kernel-Based Maximum Correntropy Criterion Authors: Tiankai Li, Baobin Wang, Chaoquan Peng, Hong Yin, Martin Trapp, Pierre Alquier Published: 2024 ABSTRACT AbstractMaximum correntropy criterion (MCC) has been an important method in machine learning and signal processing communities since it was successfully applied in various non-Gaussian noise scenarios. In comparison with the classical least squares method (LS), which takes only the second-order moment of models into consideration and belongs to the convex optimization problem, MCC captures the high-order information of models that play crucial roles in robust learning, which is usually accompanied by solving the non-convexity optimization problems. As we know, the theoretical research on convex optimizations has made significant achievements, while theoretical understandings of non-convex optimization are still far from mature. Motivated by the popularity of the stochastic gradient descent (SGD) for solving nonconvex problems, this paper considers SGD applied to the kernel version of MCC, which has been shown to be robust to outliers and non-Gaussian data in nonlinear structure models. As the existing theoretical results for the SGD algorithm applied to the kernel MCC are not well established, we present the rigorous analysis for the convergence behaviors and provide explicit convergence rates under some standard conditions. Our work can fill the gap between optimization process and convergence during the iterations: the iterates need to converge to the global minimizer while the obtained estimator cannot ensure the global optimality in the learning process.Keywords: stochastic gradient descent, maximum correntropy criterion, non-Gaussian, convergence rateMSC: 62J02 1. Introduction Non-Gaussian noise and outliers are ubiquitous in many real-life applications, and robustness analysis plays an important role in the fields of signal processing and machine learning [1,2,3,4,5,6,7,8,9]. For regression problems, the classical least squares (LS) method is the most widely used tool. The LS method refers to the framework of second-order statistics due to its minimization of the variance of the prediction error, and the success of the LS method depends heavily on the assumption of Gaussianity. However, the LS method has poor performance when data may be contaminated by non-Gaussian noise or outliers. This motivates the application of MCC into robust regression problems as the correntropy loss can capture high-order moment information contained in the data. Due to its robustness to non-Gaussian noise, MCC has found wide applications in solving optimization problems in various scientific and engineering areas such as signal processing, regression analysis, feature selection, and data clustering; see [10,11,12,13,14,15,16,17,18,19,20,21] and the references therein. Stochastic gradient descent (SGD) is a popular optimization method to solve large-scale computation problems due to its low memory requirement, computational complexity, and promising learning performances; see [22,23,24]. As an iterative method, SGD calculates a gradient randomly based on a random event and updates iterates along the direction of the negative gradient. Theoretical properties of SGD are well studied for optimization with both convex and strongly convex loss functions, but the existing theoretical results in the non-convex setting are not mature. Recently, non-convex optimization with SGD has attracted significant interest from researchers regarding the development of deep neural nets. In the paper, we employ SGD to solve the optimization problems induced by kernel-based MCC. As the correntropy loss is not convex, a rigorous theoretical foundation for applying SGD to MCC is not clear and will be investigated in the work. Kernel methods are efficient tools for dealing with non-linear features in models. Here, the learning process of the kernel MCC method is associated with a Mercer kernel K. The function K:X×X→R is said to be a Mercer kernel if it is continuous, symmetric and positive semidefinite on X×X. It induces a reproducing kernel Hilbert space (RKHS) HK [25], which is defined to be the completion of the linear span of {Kx=K(·,x),x∈X} with the inner product 〈K(·,x),K(·,u)〉K=K(x,u),∀x,u∈X. and the reproducing property So, the following holds In this paper, we attempt to present the convergence analysis of the kernel version of SGD applied to the correntropy loss, where σ>0 is the robustness parameter. Assume X∈Rd is a vector of explanatory variables, Y∈R is the response variable. Given a prediction function f, the correntropy loss ϕσ provides a measure of the error prediction error E=f(X)−Y, that is The purpose of the maximum correntropy criterion is to find a good predictor by maximizing (3). Given a set of independent and identically distributed (i.i.d.) observations, z={(xi,yi)}i=1T, the implementation of MCC by SGD in an RKHS HK is defined with an initial value of f1=0 and the updating rule where ut=f(xt)−yt and ηt>0 are the step size. In a previous work [7,9], an analysis of the implementation of MCC mainly focuses on the convergence of {ft} to the regression function E(Y|X=x), which is the value of the conditional mean of the output Y. However, in a non-parametric context, the target function of MCC varies with the choice of the robustness parameter σ. In the following paper [26,27], the authors established a sound theoretical foundation for MCC and provided a full analysis of the prediciton ability of MCC. They showed that MCC indeed belonged to the robust regression scheme when σ was large enough, but when σ→0, the target function of MCC was a modal regression fucntion; that is, maxy∈Yp(y|X=x) (p(·|X=x) denotes the condtional density function). Thus, this paper will investigate the convegence ability of SGD applied to MCC for any σ>0. The contributions of the work are as follows: (a)This work establishes the theoretical foundations for SGD applied to MCC. Some important convergence properties are provided, in which the role of the robustness parameter σ is presented. This work establishes the theoretical foundations for SGD applied to MCC. Some important convergence properties are provided, in which the role of the robustness parameter σ is presented. (b)We introduce the Polyak–Łojasiewicz (PL) condition to derive the explicit convergence rates of algorithm (4). A global linear convergence rate is achieved when the step size ηt is chosen properly. We introduce the Polyak–Łojasiewicz (PL) condition to derive the explicit convergence rates of algorithm (4). A global linear convergence rate is achieved when the step size ηt is chosen properly. The rest of the paper is organized as follows. In Section 2, after introducing necessary notations and assumptions that underlie our analysis, we provide and discuss our main theorems. Some discussions on the kernelized MCC are provided in Section 3. We provide the simulations in Section 4. Section 5 is devoted to the technical proof. We conclude this paper with Section 6. 2. Main Results This paper investigates the convergence of algorithm (4) in a non-parametric context. Some necessary notations and assumptions are given. Let ρ be a Borel probability measure on the product space Z:=X×Y. The samples z=zi:=(xi,yi)i=1T⊂Z are drawn independently according to ρ. Let ρX be the marginal distribution of ρ on X, and ρ(y|x) be the conditional distribution on Y given x∈X. Associated with (ϕσ,ρ), the generalization errorE for f:X→Y is given by which is well defined for any measurable function f. We assume that there exists a function f∗ that maximizes the expected correntropy error. In this sense, the goal of MCC learning is to find an approximation of f∗ through only the training set z=zi:=(xi,yi)i=1T when measure ρ is unknown. The prediction ability to algorithm (4) is estimated by E(f∗)−E(fT+1). In the rest of the work, we denote the gradient of the functional E(f) in a RKHS HK by ∇E(f). Define {ft} by algorithm (4) and take the step size ∑t=1∞ηt2<∞. Then, the following statements holds. (a) The generalization error E(f∗)−EE(ft+1) is uniformly bounded. More precisely, there is some constant C, such that E(f∗)−EE(ft+1)≤C(1+σ−4),t=1,⋯,T. The generalization error E(f∗)−EE(ft+1) is uniformly bounded. More precisely, there is some constant C, such that E(f∗)−EE(ft+1)≤C(1+σ−4),t=1,⋯,T. (b) There is some constant C>0, such that inft=1,⋯,TE∥∇E(ft)∥K2≤C(1+σ−4)∑t=1Tηt−1, There is some constant C>0, such that inft=1,⋯,TE∥∇E(ft)∥K2≤C(1+σ−4)∑t=1Tηt−1, where the constant C will be given explicitly in the proof. Statement (a) tells us that the error E(f∗)−EE(ft) converges to a bounded random variable without any boundness requirement on ft appearing in previous work [22,28]. That is because of the so-called redescending property of the correntropy loss. We say that loss ℓ(·) satisfies the redescending property if ℓ′(·) is non-decreasing near the origin, but decreasing towards 0 far from the origin. At present, there are a great deal of papers to describe the redescending property in robustness analysis [29,30]. Statement (b) shows that after T iterations, there exists a single iterate, such that its gradient converges to 0 if we choose the step size ∑t=1∞ηt=∞. Explicit rates are provided in the following corollary by instantiating the step sizes. Define {ft} by algorithm (4), we have (a) If ηt=t−1+ϵ for any 0<ϵ<1, then inft=1,⋯,TE∥∇E(ft)∥K2=OT−1+ϵ. If ηt=t−1+ϵ for any 0<ϵ<1, then inft=1,⋯,TE∥∇E(ft)∥K2=OT−1+ϵ. (b) If ηt=t−12logt, then inft=1,⋯,TE∥∇E(ft)∥K2=OT−12logT. If ηt=t−12logt, then inft=1,⋯,TE∥∇E(ft)∥K2=OT−12logT. As we see, the convergence rate of algorithm (4) varies with the step size and can achieve the order O(T−1), as presented in statement (a). In the following, we improve our convergence analysis by imposing the Polyak–Łojasiewicz (PL) condition, which has been explored to show fast convergence rates for SGD without convexity or strong convexity, see [31,32]. We say that E(f) satisfies Polyak–Łojasiewicz (PL) condition if the following holds for some μ>0 for any measurable function f:X→Y. This condition was originally introduced by Polyak [33] and is commonly used in non-convex gradient descent analysis [32]. It simply requires that the gradient grows faster than a quadratic distance between the generalization error, and is a sufficient condition to guarantee a global linear convergence rate for the gradient descent. In this work, we use the PL condition to provide a full analysis of SGD for MCC implementation. Define {ft} by algorithm (4) and suppose (5) holds. (a) If ∑t=1∞ηt2<∞ and ∑t=1∞ηt=∞, then limt→∞E(f∗)−EE(ft+1)=0. If ∑t=1∞ηt2<∞ and ∑t=1∞ηt=∞, then limt→∞E(f∗)−EE(ft+1)=0. (b) If ∑t=1∞ηt2<∞ and ∑t=1∞ηt=∞, then limt→∞∥∇E(ft)∥K2=0. If ∑t=1∞ηt2<∞ and ∑t=1∞ηt=∞, then limt→∞∥∇E(ft)∥K2=0. (c) If there exists some t0∈N, such that for any t≥t0, ηt≤σ24, then E(f∗)−EE(ft+1)≤∏j=1t1−ηjκ−2μ2E(f∗)−E(f1). If there exists some t0∈N, such that for any t≥t0, ηt≤σ24, then E(f∗)−EE(ft+1)≤∏j=1t1−ηjκ−2μ2E(f∗)−E(f1). Statements (a) and (b) establish sufficient conditions to guarantee almost certain convergence in SGD applied to MCC. Statement (c) tells us that with a constant step size of ηt≡σ24, algorithm (4) has a global linear convergence rate O1−σ2κ−2μ8T. It also shows that the value of the robustness parameter σ plays an important role in the choice of stepsize for deriving fast convergence rates. 3. Discussions Recent theoretical works on the global solutions to SDG generated by nonconvex losses are limited. Inspired by the work of [34,35], MCC is based on a smooth loss that can be utilized in the theoretical analysis and sufficient convergence conditions can be derived for MCC. Thus, a fine theoretical foundation kernel-based MCC is established in the work, allthough no convexity property assumption has been imposed on the optimization problems. We show that the usual bounded gradient assumptions on nonconvex learning can be removed without affecting the convergence rates. By using a condition referred to as PL inequality, we find that the last iteration of SGD with kernel-based MCC can enjoy fast convergence speeds. To the best of our knowledge, this work provides the first theoretical analysis of MCC that establishes a global linear convergence rate. We review some work related to the kernelized MCC. In linear additive noise models, the studies by [7,26,35] investigated regression models associated with correntropy-induced losses, demonstrating that the scale parameter in the learning process balances the convergence rates of the regression model with its robustness. However, their approaches rely solely on batch algorithms, which are limited in streaming data scenarios and large-scale computational settings. Moreover, the convergence rates achieved in their work are noticeably inferior to those established in our study (see Theorem 2). We turn to the theoretical works on the gradient descent in training kernelized MCC. In the works of [10,21,36], the authors focussed on the learning performance and convergence ability in terms of the target functions, defined as the conditional mean E(Y|X=x). But, it has been proved in [26] that in MCC models, for a good generalization ability and robustness properties, the minimizer of the generalization error E(f) is not necessarily E(Y|X=x). Our work does not impose extra conditions on the target functions and can apply to general learning schemes. In addition, our analysis relaxes thethe requirement for the choice of σ, which must be sufficiently large in [10,21,36]. 4. Simulation Validation In this section, we provide some experimental results to confirm our theoretical results. These experiments are simulated from the regression model yi=f∗(xi)+ϵ, where f∗(xi)=xi(1−xi) and the random samples xi are drawn independently according to the uniform distribution U[−1,2]. To carry out the experiments, the noise ϵ is generated as follows. Gaussion noise: ϵ∼N(0,0.12); Gaussion noise: ϵ∼N(0,0.12); outlier noise: 90% noise ∼N(0,0.12), 10% noise ∼U[−1,1]; outlier noise: 90% noise ∼N(0,0.12), 10% noise ∼U[−1,1]; skewed noise: ϵ=z1−z2, where z1,z2∼Exp(0.2); skewed noise: ϵ=z1−z2, where z1,z2∼Exp(0.2); GMM noise: 90% noise ∼N(0,0.12), 10% noise is generated by the following density probability GMM noise: 90% noise ∼N(0,0.12), 10% noise is generated by the following density probability We generate a dataset of 1000 samples for the above four types of noise. See Figure 1. Comparison of four types of noises with 1000 samples. We chose the Gaussian kernel function G(x,u)=exp−∥x−u∥22 for the kernel MCC. We applied SGD to the kernel MCC with stepsizes of η=0.1 and σ=0.1. For each type of noise, we ran the SGD for T = 1000 times. The generalization errors E(ft) with iterations t are plotted in Figure 2. It is observed that for different types of noise, the generalization errors decreased rapidly as iterations progressed. This shows the efficiency of SGD for MCC in dealing with non-Gaussain noise. This coincides with our theory. Comparison of generalization errors for different noises. The vertical coordinate denotes generalization errors and the horizontal coordinate denotes the iteration time. 5. Proofs Now, we provide the proofs for our main results. As ϕσ′(u)=−2uσ2exp−u2σ2, we know It follows that for any u,v∈R, Applying the inequality above with u=ft+1(x)−y, v=ft(x)−y, then by (1) Taking the expectation with respect to z=(x,y) on both sides, and using (4) For the term |ϕσ′(f(xt)−yt)Kxt|2, using (2), we know where the last inequality is obtained by te−t≤1 for any t>0. Putting it into (9) yields Noting that ft is independent of zt, then by taking the conditional expectation with respect to zt, we derive Taking the conditional expectation with respect to zt−1,zt−1,⋯,z1 sequentially yields This implies that An application of the inequality recursively provides So, we can obtain that for any t∈N, where C:=max{1,4κ2∑j=1∞ηj2} and the last inequality is obtained by E(f)≤1 for any measurable function f:X→Y. Then, statement (a) holds. Now, we provide statement (b). Inequality (11) also provides A summation of the aforementioned inequality then implies So, we obtain Then, statement (b) holds. □ We know that for any t∈N, Using statement (b) of Theorem 1 with γ=1−ϵ implies that statement (a) holds. Statement (b) can be similarly proven. □ For the proof of statement (a), we use estimate (11). Adding E(f∗) on both sides provides Note that the relation (2), then ∥∇E(ft)∥∞≤κ∥∇E(ft)∥K This together with (5) yields Using the inequality recursively from t=1 to T, then The part of the first term limT→∞exp−κ−2∑t=1Tηt=0 due to ∑t=1∞ηt=∞. The part of the second term ∑t=1Tηt2∏j=t+1T goes to zero, as T→∞ due to Lemma 11 in [37]. The the proof of (a) is complete. For the proof of statement (b), we recall an elementary inequality in [24]. For any positive functional ℓ(f),f∈HK, if the gradient of ℓ is L-Lipschitz continuous with respect to HK, then Let ℓ(f)=E(f∗)−E(f), then by (6), we obtain and for any f,g∈HK, it follows that by using (2). The gradient of the functional ℓ(f) is 4κ2σ2-Lipschitz continuous in HK. Note that ∇E(f)=∇E(f)−E(f∗)=∫z−ϕσ′(f(x)−y)Kxdρ as ∇E(f∗)=0. Then, we obtain using (13) with L=4κ2σ2. Replacing f with ft, then from statement (a), we can derive Then, the proof of statement (b) is complete. For the proof of statement (c), we take the expectation with respect to z1,⋯,zt and add E(f∗) on both sides of (9). So, we have When there exists t0, such that for any t≥t0, ηt≤σ24, we have 2ηt2σ2≤12ηt and Using (2) and (5) again, we obtain Applying the estimate iteratively from t=1 to T, we obtain the conclusion for statement (c). The proof is finished. □ 6. Conclusions and Future Works This paper studies the stochastic gradient method with correntropy loss functions. More precisely, we study how convergence properties can be achieved through a suitable choice of step size in robustness learning. We also use the PL condition to provide a global linear convergence rate. These results refine the previous work and provide a theoretical foundation for SGD with MCC. Two related questions are worthwhile for future research. First, our analysis provides very useful insights on the application of SGD for MCC. The simulation is also consistent with our theory. However, the optimal selection of σ is unknown in practice. It is necessary to develop empirically applicable parameter selection strategies for optimal σ. Secondly, with the development of deep learning, various stochastic gradient methods are continuously emerging that accelerate the training progress, such as Adam [38], AdaGrad [39], RMSProp [40], and AMSGrad [41]. Non-convexity [42,43,44] of the MCC loss function will bring major challenges in the theoretical analysis. The techniques used in this paper may also be applied to other stochastic gradient methods. Meanwhile, our error bounds already imply linear convergence rates. It is yet unknown whether the non-convexity can be overcome in the error analysis and similar convergence results can be derived in other stochastic gradient methods. This will be considered in future research. Author Contributions Formal analysis, C.P.; Writing—original draft, T.L.; Writing—review & editing, H.Y.; Supervision, B.W. All authors have read and agreed to the published version of the manuscript. Institutional Review Board Statement Not applicable. Data Availability Statement The data supported by this study can be found in the article. Conflicts of Interest The authors declare no conflicts of interest. Funding Statement This work is supported by the National Natural Science Foundation of China (Grant No. 12071356), the Natural Science Foundation of Hubei Province in China (Grant No. 2024AFC020) and the Fundamental Research Funds for the Central Universities, South-Central MinZu University (Grant No. CZY23010). Footnotes Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. References Associated Data Data Availability Statement The data supported by this study can be found in the article.