{'fraction_non_alphanumeric': 0.03510644070249055, 'fraction_numerical': 0.008500786774946192, 'mean_word_length': 4.524028374462984, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Framework of Learning Through Empirical Gain Maximization

We develop in this paper a framework of empirical gain maximization (EGM) to address the robust regression problem where heavy-tailed noise or outliers may present in the response variable. The idea of EGM is to approximate the density function of the noise distribution instead of approximating the truth function directly as usual. Unlike the classical maximum likelihood estimation that encourages equal importance of all observations and could be problematic in the presence of abnormal observations, EGM schemes can be interpreted from a minimum distance estimation viewpoint and allow the ignorance of those observations. Furthermore, it is shown that several well-known robust nonconvex regression paradigms, such as Tukey regression and truncated least square regression, can be reformulated into this new framework. We then develop a learning theory for EGM, by means of which a unified analysis can be conducted for these well-established but not fully-understood regression approaches. Resulting from the new framework, a novel interpretation of existing bounded nonconvex loss functions can be concluded. Within this new framework, the two seemingly irrelevant terminologies, the well-known Tukey's biweight loss for robust regression and the triweight kernel for nonparametric smoothing, are closely related. More precisely, it is shown that the Tukey's biweight loss can be derived from the triweight kernel. Similarly, other frequently employed bounded nonconvex loss functions in machine learning such as the truncated square loss, the Geman-McClure loss, and the exponential squared loss can also be reformulated from certain smoothing kernels in statistics. In addition, the new framework enables us to devise new bounded nonconvex loss functions for robust learning.


Introduction, Motivation, and Preliminaries
In this paper, we are concerned with robust regression problems where conditional distributions may have heavier-than-Gaussian tails or be contaminated by outliers. In machine learning and statistics, regression procedures are typically carried out through Empirical Risk Minimization (ERM) or its variants. Denote X as the input variable taking values in X ⊂ R d and Y the output variable taking values in R. Given n i.i.d observations z = {(x i , y i )} n i=1 and choosing a hypothesis space H, ERM can be formulated as where ℓ : R → R + is a loss function that measures the point-wise goodness-of-fit when using f (x) to predict y. Several frequently employed loss functions for regression with continuous output include the square loss, the absolute deviation loss, as well as the check loss. The resulting ERM schemes learn, respectively, the conditional mean, the conditional median, and the conditional quantile function. Under the additive noise model where ε denotes the noise variable, these ERM schemes can also be deduced from maximum likelihood estimation (MLE) by assuming a Gaussian, Laplace, or asymmetry Laplace prior distribution of the noise variable, respectively. In this sense, these ERM schemes are essentially MLE-based, though in practice the prior distributional assumptions may not be imposed explicitly or may even be abandoned. To deal with robust regression problems, various M-estimators such as the Tukey regression estimator and the truncated least square estimator, which can be viewed as generalized maximum likelihood estimators, are proposed in robust statistics. Carrying over from robust estimation of location parameters in parametric statistics, the idea of M-estimation is to implement MLE based on heavy-tailed noise distributions. In the machine learning context, the nonparametric counterparts of these M-estimators are also frequently used for robust prediction, especially in the area of computer vision.
While maximum likelihood estimates are efficient and often lead to effective regression estimators, their disadvantages are also obvious. To explain, let us consider again the n-size sample z generated by the regression model (2). Denoting p ε|X as the density of the noise variable ε conditioned on X, the likelihood of drawing the sample z given the parameter "f " from the "parameter space" H is L(z; f ) = n i=1 p ε|x i (y i − f (x i )). In MLE, one aims at seeking the optimal "parameter" f z in H such that this likelihood is maximized, i.e., In other words, the purpose of searching for the optimal "parameter" f z is achieved by maximizing the product of the likelihood functions of all the observations. Taking a logarithm operation to the product leads to the log-likelihood log L(z; f ) and further brings us ERM schemes induced by the square loss and the least absolute deviation loss when the noise is assumed to be Gaussian and Laplace, respectively. MLE is known to be (asymptotically) more efficient than other estimators when the noise distribution is correctly specified. However, in the machine learning context, the premise that the noise distribution is known a priori is seldom the case and more often than not, is not realistic. On the other hand, one of the shortcomings of MLE lies in that it is sensitive to abnormal observations. This could be understood intuitively from the formula (3), where the maximization of the product obviously encourages equal importance of all the observations. Specifically, the maximization does not allow the zeroness of the likelihood of any observation no matter whether the observation is abnormal or not. This could be problematic in practice where the acquired data are frequently contaminated. To address the non-robustness problem of MLE based methodologies, tremendous efforts have been made in the literature of statistics, machine learning, as well as other data science areas.

Problem Formulation
Our study in this paper starts from a family of robust learning approaches of the form where H is the hypothesis space and p ε|X the density of the noise ε|X. Since p ε|X is unknown in practice, we consider its surrogate p σ by ignoring the dependence of ε on X and the norming constant. Then, the scheme can be generalized to the form where we call p σ : R → R + a gain function if it is unimodal, attains its peak value at 0, and is integrable. Correspondingly, the scheme (5) is termed as Empirical Gain Maximization (EGM), a systematic investigation of which will be the main focus of this paper.

Motivating Scenarios
Our development of the EGM framework and the introduction of gain function are inspired by the following motivating scenarios that find tremendous real-world applications in robust estimation across numerous data science fields.
Motivating Scenario I: Tukey Regression. The well-known Tukey regression based on Tukey's biweight loss, proposed in [3], can be equivalently formulated as an EGM scheme (5) associated with the gain function which we call triweight gain function. Tukey regression has found numerous applications in a great variety of data science areas where robustness is a concern; see e.g., [26,42,7,52,6,4,8,14].
Motivating Scenario II: Truncated Least Square. The truncated least square regression can be equivalently formulated as an EGM scheme associated with the Epanechnikov gain function The related studies and applications of truncated least squares regression, to name a few, can be found in [29,59,33,36,39].
Motivating Scenario IV: Maximum Correntropy. The maximum correntropy criterion [40,44], motivated by maximizing the information gain measured by correntropy between the input variable X and output variable Y , is equivalent to an EGM scheme with the Gaussian gain function This gain function was also proposed as a goodness-of-fit measurement in various contexts of robust estimation under different terminologies such as the Welsch's loss [17], the inverted Gaussian loss [35], the exponential squared loss [54], and the reflected normal loss [49]. Its theoretical properties were recently investigated in [24,23,21,20] from a statistical learning viewpoint.
Further details of the above gain functions and their correspondences to bounded nonconvex loss functions will be discussed in Section 3 below. What are common behind the above four robust learning schemes are that (1) all of them can be naturally formulated into the EGM framework (5) with the associated gain function either the kernel of a common probability distribution or a common smoothing kernel; (2) they are all introduced in order to pursue robustness in estimation procedures with a scale parameter σ controlling the robustness; (3) they all have extremely wide applications in robust estimation problems from science to technology. However, in a distribution-free setup, their learning performance, especially the relationship between their learnability, robustness, and the scale parameter, has not been well assessed. In this sense, they are well-established learning schemes but not fully-understood ones; and (4) they were usually treated as M-estimators and interpreted from an ERM viewpoint or further traced to MLE. However, such interpretations, on one hand, cannot reveal the working mechanism of the resulting estimators and so cannot fully explain their robustness, on the other hand, cannot help discover new learning schemes of the same kind.

Objectives and Contributions
By introducing gain functions and developing an EGM framework, the objectives of this study are not solely to develop new robust learning schemes but rather to (1) present a unified analysis of the several well-known robust regression estimators and study their performance from a learning theory viewpoint; (2) pursue novel insights and interpretations of these estimators, which could help explain their robustness merits; (3) develop a learning theory framework as well as novel machineries for analyzing robust regression schemes that fall into the same vein; and (4) devise and explore more new robust regression estimators that are of the same kind. It turns out that our newly developed framework can fulfill these objectives effectively. Our main contributions are summarized as follows: • Motivated by several widely used robust regression schemes, we introduce gain function as an alternate measurement of goodness-of-fit in regression and develop an EGM framework. It is shown that maximizing empirical gain in regression can be viewed as maximizing the summation of the likelihood functions. Unlike the product of likelihood functions in MLE, summation does not encourage the equal importance of all observations but allows even the zeroness of the likelihoods of abnormal ones. This observation may better explain the robustness of these regression schemes.
• Interestingly, the newly developed framework subsumes a bunch of well-known robust regression schemes, especially those listed in the motivating scenarios, such as the celebrated Tukey regression, the classic truncated least square regression, and the widely employed Geman-McClure regression in computer vision. We stress here that under the new framework, Tukey regression estimators can be obtained via EGM induced by triweight gain function, which comes from the triweight kernel; truncated least square estimators can be deduced from EGM associated with Epanechnikov gain function, which comes from the Epanechnikov kernel; and Geman-McClure regression estimators can be derived from EGM with Cauchy gain function, which results from the Cauchy kernel. Such findings provide us an alternative understanding of these robust regression schemes. That is, these M-estimators may be interpreted more naturally as minimum distance estimators.
• We conduct a unified learning theory analysis of EGM schemes. In the learning theory literature, convex regression schemes have been extensively studied. However, studies and assessments of nonconvex ones, such as Tukey regression, truncated least square regression, and Geman-McClure regression, are still sparse though they have been extensively applied. Our study provides a unified learning theory assessment of these robust regression schemes. More specifically, we consider two different setups, namely, learning without noise misspecification and distribution-free learning. We show that when learning without noise misspecification, EGM estimators are regression calibrated while in a distribution-free setup, under certain conditions, EGM estimators can learn the underlying truth function under weak moment conditions.
• The present study brings us novel insights into existing bounded nonconvex loss functions. Furthermore, the correspondence between bounded nonconvex losses and gain functions allow us to introduce more new bounded nonconvex losses that enjoy similar properties. For instance, a generalized Tukey's loss may be formulated to cater to further needs in robust regression as well as classification problems.

Roadmap and Notation
The roadmap of this paper is as follows. In Section 2, we provide some first look at EGM by comparing it with ERM and interpreting it from a minimum distance estimation viewpoint. Section 3 exposes the way of defining gain functions and formulating EGM. Gain functions are exampled and categorized in this section. In particular, the correspondence between some representative bounded nonconvex losses and gain functions is also illustrated here. In Section 4, we look into EGM schemes by investigating fundamental questions in EGM based learning and conducting a unified learning theory analysis. We assess the learning performance of EGM estimators in different scenarios. Specifically, as an instantiation, we show that one can directly apply the developed theory to those well-established robust learning schemes mentioned in the motivating scenarios. Some further insights and perspectives are provided in Section 5. The paper is concluded in Section 6.
Intermediate lemmas and proofs of the theorems are provided in the appendix.
Throughout this paper, · 2 2,ρ denotes the L 2 -norm induced by the marginal distribution ρ X . C(X ) denote the space of bounded continuous functions on X . p Y |X stands for the conditional density of Y conditioned on X and p Y |X=x , or p Y |x for brevity, represents the conditional density of Y conditioned on X = x. For a set S (or an event), I S represents an indicator function that takes the value 1 on S (or when S occurs) and 0 otherwise. We also denote a b if a ≤ cb for some absolute constant c > 0.

A First Look at Empirical Gain Maximization
In this section, at an intuitive level, we present a first look at EGM by comparing it with the classical ERM. To this end, we first investigate situations where ERM based regression schemes fail and then look into EGM by interpreting it from a minimum distance estimation (MDE) as well as a maximum likelihood estimation (MLE) viewpoint.

EGM vs. ERM
As stated earlier, ERM based regression schemes can be traced to the MLE framework where one maximizes the product of the likelihoods of all the observations. That is, In (6), for any f ∈ H, maximizing the product of the likelihood functions encourages the equal importance of all the residuals y i − f (x i ), i = 1, · · · , n, and does not tolerate the zeroness of any likelihood no matter whether the residual is caused by an abnormal observation or not. In contrast, in EGM regression schemes, one maximizes the summation of the likelihood functions of the residuals. That is, Intuitively, maximizing the summation instead of the product allows small values or even zeroness of likelihood of certain residuals and so may significantly reduce the impact of those abnormal ones. Therefore, EGM may outperform ERM in terms of robustness to abnormal observations.

EGM: When MLE Meets MDE
To proceed with our comparison, for any measurable function f : X → R, we denote E f as the random variable defined by the residual between Y and f (X), i.e., E f = Y − f (X). Then, for any fixed f and any realization of X, say x, the density function of E f |x can be obtained by translating that of ε|x horizontally f ⋆ (x) − f (x) units. Consequently, the density of E f |x can be expressed as Similarly, we also have Moreover, reminded by [19], we know that defines the density of the random variable E f , and defines a density of the random variable ε.
Continuing our discussion in the introduction, the population version of the M-estimators resulting from the ERM scheme (1) and so the MLE (3) can be equivalently cast as Simple computations show that one also has where KL(p 1 , p 2 ) denotes the KL-divergence between the two distributions p 1 and p 2 and measures their discrepancy.
On the other hand, recall that the EGM estimator (5) originates from (4), which can be treated as an M-estimator. Therefore, the EGM scheme can still be interpreted from an MLE viewpoint. Meanwhile, note that the population counterpart of (4) is For any measurable functions f , we define the integrated squared density-based distance, dist(p E f , p ε ), between p E f and p ε as It is easy to see that the above distance between p E f and p ε defines a metric between p E f and p ε .
In particular, if f equals f ⋆ on X , then we have dist(p E f , p ε ) = 0. Notice that the data-generating model Y = f ⋆ (X) + ε defines a location family, which implies that Therefore, EGM can be interpreted both from an MLE viewpoint and from a minimum distance estimation viewpoint. To be brief, when MLE meets MDE, EGM estimators come into sight. Because of such dual interpretations, they may possess built-in merits such as robustness delivered by MDE and fast convergence rates inherited from MLE, as we shall explore later.

Formulating Empirical Gain Maximization and Gain Functions
In this section, we first detail the reasoning process that leads to EGM (5) and also the definition of gain functions. More gain functions will be exampled and categorized and their correspondences with bounded nonconvex losses will also be discussed.

Towards Making EGM based Learning Applicable
While the initial scheme (4) seems to be promising due to its merits in terms of robustness. However, one may encounter barriers in its implementation, the primary one of which is tractability. This is because in practice p ε is unknown in advance. Therefore, further efforts are needed to address this problem and make it practically applicable. One way of tackling this problem, inspired by existing studies in learning theory, is to find a tractable relaxation, which is the gain function p σ defined in Section 1.1. Listed below are several possible strategies that may be adopted for this purpose.
Assuming the Density. Recall that when MLE is used to estimate the conditional mean, the Gaussianity of the noise is usually assumed which leads to the least squares regression. If Laplace noise is assumed, then one comes to the least absolute deviation estimation which approaches the conditional median in regression. When moving attention to EGM, following the same way, one may also assume that the noise variable ε obeys a certain law such as the Gaussian or Laplace. In particular, with Laplace noise, we then have Under mild conditions, it can be shown that the resulting EGM estimator approaches the conditional median or the conditional mode function with properly chosen σ values. Similarly, with Gaussian noise, then one gets p σ (y i −f (x i )) = exp −(y i − f (x i )) 2 /2σ 2 and the resulting EGM scheme can be equivalently formulated as the maximum correntropy criterion stated in Motivating Scenario IV.
We arrive at the EGM scheme (5) from the scheme (4) by choosing p σ which is an assumed density and serves as a surrogate of the true noise density. However, we remark that, similar to MLE, EGM may still be practically effective even if the assumed noise density deviates from the ground truth, as shown in Section 4 below.
Learning the Density. Noticing that in (4), for any fixed f in H, we maximize the summation of the values of the unknown density p ε at n points y i − f (x i ), i = 1, · · · , n. When a learning machine f is utilized, the observations y i − f (x i ), i = 1, · · · , n, can be treated as realizations of the unknown noise variable defined by the residual Y − f ⋆ (X). Therefore, for each i, one could estimate the point-wise density p ε (y i − f (x i )) by using observations y j − f (x j ), j = 1, · · · , i − 1, i + 1, · · · , n, by means of the Parzen window density estimator. Explicitly, let K σ be a smoothing kernel with the bandwidth parameter σ, under mild conditions, one has the following estimate of p ε that serves as its relaxation The resulting EGM scheme can be formulated as Canonical smoothing kernels include Gaussian kernel, Laplace kernel, Epanechnikov kernel, uniform kernel, triangle kernel, etc. Interestingly, the above learning scheme is essentially equivalent to the one induced by the minimum error entropy algorithm [18,44] that was recently investigated from a learning theory viewpoint in [30,19,31,32,27].
Approximating the Density. Another way of dealing with the unknown density p ε is that one may directly approximate this density function. To this end, we recall that ε := Y −f ⋆ (X) is a one-dimensional random variable. As a mild assumption, one may assume that p ε is continuous on R. From the knowledge of approximation theory, we know that one can approximate this one-dimensional continuous function p ε arbitrarily well by using certain basis functions on R.
As an example, one may use the convex combination of the one-dimensional Gaussian kernel, which leads to where the coefficients w j are positive constants such that K j=1 w j = 1, K ≥ 1 a positive integer, and σ j > 0 for j = 1, · · · , K. Then, the resulting EGM is In particular, if K = 1, it reduces Gaussian EGM. We note that similar ideas have been investigated for robust learning, see e.g., [10].
In addition to the above-mentioned approaches to finding tractable relaxations of p ε , one may also use smoothing kernels from statistics since each smoothing kernel defines a density. By stretching or compressing a smoothing kernel vertically or horizontally, one may approximate the unknown density p ε . For illustration, we will provide more examples in the next subsection. It would be interesting to explore further techniques for finding such a relaxation.

Gain Function: Formal Definition and More Examples
With the preparations above, we are now ready to introduce a formal definition of gain functions which leads to the general EGM formulation (5). Definition 1 (Gain function). A function p σ : R → R + with a parameter σ > 0 is said to be a gain function if there exists a generating function φ : R → R + such that p σ (t) = φ (t/σ) for any t ∈ R and the following conditions are satisfied: (2) φ is non-decreasing on (−∞, 0] and non-increasing on [0, +∞).
The gain functions p σ is introduced as a surrogate of p ε . The scale parameter σ is used to stretch or compress the function φ so as to approximate the density. According to the definition, gain functions attain their peak value at the point 0. An intuitive explanation of this restriction is that one gains the most if a learning machine f fits y exactly at the point x. Remark 2. The terminology "gain function" in Definition 1 has been used in various disciplines. For instance, in game theory, gain function is better known as "pay-off function". It is a function defined on the set of situations in a game, the values of which are a numerical description of the utility of a player or of a team of players in a given situation. In economics, gain function is better known as "utility function". It is a function that measures preferences over a set of goods and services. Its value represents the satisfaction that consumers receive for choosing and consuming a product or service. In the present study, gain function is not referred to as the ones in game theory or economics, though it may be related to those terminologies. The introduction of gain function in the present study is directly inspired by the studies in [55,56] for robust statistical estimation.
Following Definition 1 and the discussions in Section 3.1, one can immediately write out a variety of gain functions. Example 1 (Triweight gain function). When taking the triweight kernel as the gain function, we have the triweight gain function Example 2 (Epanechnikov gain function). When taking the Epanechnikov kernel as a gain function, we come to Epanechnikov gain function Example 3 (Cauchy gain function). When considering the kernel of a Cauchy distribution with the location parameter 0, we obtain the Cauchy gain function Example 4 (Gaussian gain function). When considering the kernel of a standard Gaussian distribution, we have the Gaussian gain function Example 5 (Laplace gain function). Considering the kernel of a Laplace distribution with the location parameter 0, we have the Laplace gain function Example 6 (Cosine gain function). Using the cosine kernel as a gain function leads to the Cosine gain function Example 7 (Uniform gain function). Using the uniform kernel as a gain function gives the uniform gain function

Categorizing Gain Functions
As shown above, a variety of gain functions can be introduced in various ways for different purposes. For instance, Gaussian and Cauchy gain functions may be employed in EGM to learn the conditional mean function in regression, while by means of the Laplace gain function one may learn the conditional median function. In this part, we make efforts to categorize gain functions by defining type α gain functions and strongly mean-calibrated gain functions. Definition 3. A gain function p σ is said to be of type α if there exist two nonnegative constants α and c such that It is easy to verify that • the triweight, Cauchy, Gaussian, and Cosine gain functions in Examples 1, 3, 4, and 6 are of type 2; • the Epanechnikov gain function in Example 2 is of exact type 2; • the Laplace gain function in Example 5 is of type 1; and

Gain Function
Mean-Calibration

Gaussian
Strong • the uniform gain function in Example 7 is of exact type 0.
Intuitively, a type 2 gain function may be used for mean regression while a type 1 gain function may be employed for median regression. As mean regression will be the main focus in what follows, among type 2 gain functions, we are particularly interested in strongly mean-calibrated ones as well as exactly mean-calibrated ones defined below. Definition 4. A gain function p σ is said to be strongly mean-calibrated if there exist a representing function ψ : R + → R + and absolute positive constants L 1 and L 2 such that p σ (t) := ψ(t 2 /σ 2 ) and the following two conditions hold In particular, a strongly mean-calibrated gain function p σ is said to be exactly mean-calibrated if ψ ′ (t) is a constant function on (0, 1).
As per the above definition, the type 2 gain functions listed in Examples 1-4 and 6 can be further categorized as in Table 1. Clearly, not all type 2 gain functions are strongly mean-calibrated. The following proposition further reveals the relations between strongly mean-calibrated and (exact) type 2 gain functions. Proposition 5. A strongly mean-calibrated gain function must be of type 2, and an exactly meancalibrated gain function must be of exact type 2.
Proof. Let p σ be a strongly mean-calibrated gain function. According to Definition 4, there exists a representing function ψ such that p σ (t) = ψ(t 2 /σ 2 ). Applying the mean value theorem, we know that for any 0 < u < 1, it holds that where 0 < ξ < u. To show that p σ is of type 2, it suffices to prove that there exists a positive constant c such that This is obvious if we set c = −ψ ′ (0) > 0 and recall that ψ ′ (u) is L 2 -Lipschitz on [0, 1). Replacing u with t 2 /σ 2 , we have proved that p σ is of type 2. The conclusion that an exactly mean-calibrated gain function must be of exact type 2 is obvious.
As we shall see later, EGM schemes induced by strongly mean-calibrated gain functions are asymptotically mean calibrated in regression and their sharp error bounds can be established, which explain the name of such gain functions. It should be remarked that the conditions for strongly meancalibrated gain functions are sufficient ones to ensure the (asymptotic) mean calibration properties of the resulting EGM estimators and to establish fast convergence rates. In fact, such conditions can be relaxed to much weaker ones if one is only interested in regression consistency. Likewise, one can also further categorize type 1 gain functions and investigate their behaviors in median regression, which is beyond the scope of the present study.

Interpreting Bounded Nonconvex Losses as Gain Functions
In recent years, bounded nonconvex loss functions are playing more and more important roles in machine learning applications especially in computer vision as it is commonly accepted that the boundedness of a loss function is essential for outlier resistance, see e.g., [41,48]. Several canonical bounded nonconvex losses that are frequently employed in robust estimation problems include truncated square loss, Tukey's biweight loss, Geman-McClure loss, exponential squared loss, and Andrews loss. Interestingly, within the EGM framework, these bounded nonconvex losses can be naturally interpreted as gain functions. Such correspondences are detailed as follows and are also summarized in Table 2. Example 1 ′ (Tukey's biweight loss). The well-known Tukey's biweight loss for robust estimation was introduced in [53] and is defined as otherwise.
It can be deduced from the triweight gain function in Example 1 and leads to the triweight EGM in Motivating Scenario I. Example 2 ′ (Truncated square loss). The truncated square loss proposed in [29] is given as It is also known as the skipped mean loss or Talwar loss. The truncated square loss can be translated from the Epanechnikov gain function in Example 2 and leads to the Epanechnikov EGM in Motivating Scenario II. Example 3 ′ (Geman-McClure loss). The Geman-McClure loss proposed in [25] is defined as follows Clearly, it can be derived from the Cauchy gain function in Example 3 and leads to the Geman-McClure regression in Motivating Scenario III.

Gain Function Related Examples
Tukey's biweight loss  Example 4 ′ (Exponential squared loss). The exponential squared loss is defined as It can be derived from the Gaussian gain function in Example 4 and leads to the Gaussian EGM in Motivating Scenario IV. Example 5 ′ (Exponential absolute loss). The exponential absolute loss studied in [38] and [11] is defined as It can be derived from the Laplace gain function in Example 5. Example 6 ′ (Andrews loss). Andrews loss was introduced in [1] and has been applied in robust estimation in statistics and machine learning. It takes the form and can be derived from the Cosine gain function in Example 6. Example 7 ′ (Box loss). Box loss takes the following form Corresponding to the uniform gain function in Example 7, this loss function was employed to perform modal regression in [37] and the resulting EGM scheme also gives the maximum consensus problem in computer vision, see e.g., [12,13].
Following the same way, one can translate more bounded nonconvex losses, such as the wellknown Hampel's loss [28], into gain functions. Interestingly, such translations bridge the two seemingly irrelevant sets of tools, e.g., the triweight kernel and the Tukey's biweight loss, the Epanechnikov kernel and the truncated square loss, the Cauchy density function and the Geman-McClure loss. One benefit of such translations is that they allow us to interpret those ERM based estimators more naturally from a minimum distance estimation viewpoint, which can help explain their robustness.

A Sober Look at Empirical Gain Maximization
In this section, we take a sober look at EGM. To this end, we first propose several fundamental questions that are raised when assessing EGM from a learning theory viewpoint. We then assess the performance of EGM estimators in two different setups, namely, the distribution-free setup and the setup where the noise distribution is correctly specified. We also conduct case studies by applying our theoretical results to the motivating scenarios.

Fundamental Questions in Learning with EGM
Recalling that in the ERM scheme (1), in order to assess the out-of-sample prediction ability of f z , one evaluates the excess generalization error where the expectation is taken jointly w.r.t. X and Y and serves as the oracle of the ERM scheme induced by the loss function ℓ. When the loss function ℓ is chosen as the square loss, one has f M, ℓ = f ⋆ with f ⋆ being the conditional mean function. In particular, in this case, one also has the following relation When ℓ is a general convex loss, under certain noise assumptions, one may still be able to characterize the oracle f M, ℓ and further show that the oracle is the underlying truth f ⋆ . Moreover, the convergence Eℓ(Y −f z (X)) → Eℓ(Y −f ⋆ (X)) may also imply the convergence of f z −f ⋆ 2 2,ρ . In the statistical learning literature, the related studies that address the above concerns for ERM schemes induced by convex losses have been conducted extensively and theoretical frameworks have been well developed, see e.g., [15,51].
However, for EGM schemes, the story becomes more complicated due to the nonconcavity of gain functions and the involvement of the parameter σ. For any measurable function f : X → R, we denote its generalization gain associated with the gain function p σ as and refer to the empirical counterpart as its empirical gain. Moreover, we denote the quantity G σ (f M,σ )−G σ (f ) as the excess generalization gain of f , where f M,σ := arg max f ∈M G σ (f ) serves as the oracle of EGM induced by the gain function p σ . With the above notations, the following fundamental questions regarding theoretical assessments of EGM arise naturally:

Question 1. Which gain function p σ should one choose?
This question is somewhat similar to the one that was proposed in the context of ERM, namely, which loss function one should choose for ERM, and was investigated in [45,50] in some scenarios. It is generally accepted that each loss function has its own merits in learning and the choice of the loss function for ERM may rest upon the learning task confronted. For instance, the square loss may be chosen if one is interested in mean regression; the least absolute deviation loss may be preferred in performing median regression; while the check loss may be a good option for quantile regression. Likewise, in the context of EGM, while a general answer to this question is not obtainable, the choice of the gain function may also need to be discussed case-by-case. For instance, the Gaussian gain function may be adopted for robust mean regression; the Laplace gain function may be used to perform median regression robustly; while the asymmetry Laplace gain function may be utilized for robust quantile regression.

Question 2.
What is the oracle f M,σ ?
Clearly, the oracle f M,σ is defined in association with the parameter σ. Different σ values may lead to different oracles, which together with the non-concavity of EGM, promotes barriers to the characterization of f M,σ . It would be interesting to give a full characterization of f M,σ under various circumstances. For instance, regarding Gaussian EGM, some efforts were made towards this direction in [22]. However, due to the dependence on the parameter σ, the oracle f M,σ may be far from the underlying truth function f ⋆ that one intends to approach and so may not be much informative. In particular, characterizing the oracle f M,σ and its relation with f ⋆ may be much involved. This same situation also arises when seeking an answer to the following fundamental question.

Question 3. How to bound the excess generalization gain
Following the clue of learning theory studies on ERM, the above questions also arise naturally. However, as mentioned above, due to the introduction of the parameter σ, the oracle f M,σ may drift away from f ⋆ . In this case, bounding the excess generalization gain G σ (f M,σ ) − G σ (f z,σ ) may again not be much informative and its convergence may not imply the closeness between f z,σ and f ⋆ . In fact, following the study in [50], under some stringent assumptions on the noise variable ε, one may conclude that f M,σ is the same as f ⋆ . However, given that in the machine learning context distribution-free learning is preferred, we prefer not to impose such assumptions on the noise.
In what follows, we shall make efforts to address Questions 2 and 3 above. To this end, recall that the purpose of EGM is to learn the truth function f ⋆ . Though, the target hypothesis f M,σ may vary due to different choices of the σ values. Therefore, what really matters here is the location function f ⋆ rather than the target hypothesis f M,σ . This inspires us to directly take f ⋆ as the target hypothesis and redefine the excess generalization gain of f z,σ as G σ (f ⋆ ) − G σ (f z,σ ). With this redefinition, our main concerns in EGM based learning are then switched to the following ones: (1) Whether the excess generalization gain G σ (f ⋆ ) − G σ (f z,σ ) decays to zero? (2) Whether

Distribution-Free Learning with EGM
We first investigate learning performance of EGM estimators in a distribution-free setup, where distributional assumptions on the noise are absent while certain moment conditions may be imposed. To this end, we first introduce two assumptions, one on the capacity of H and the other on the tail behavior of the distribution of Y . Assumption 1. H ⊂ C(X ) and there exist positive constants q and c such that where the covering number N (H, η) is defined as the minimal k ∈ N such that there exist k balls in C(X ) with centers in H and radius η covering H. Assumption 2. There exists some ǫ > 0 such that E|Y | 1+ǫ < +∞.
Assumption 1 is typical in learning theory and is introduced here to control the complexity of the hypothesis space H. Assumption 2 is a weak assumption on the distribution of the response variable. Note that under the boundedness assumption of f ⋆ , the finiteness of the (1 + ǫ) moment condition on Y is equivalent to the finiteness of that of the noise Y − f ⋆ (X). It is rather weak as it admits the case where the noise has infinite variance.
Our first result for EGM is concerned with its mean regression calibration property, namely, While a general answer to this question may be negative, the following theorem tells us that some weak form of regression calibration can be obtained with an adaptive selection of σ values. Theorem 6. Let f ⋆ = E(Y |X) be bounded by M . Let Assumption 2 hold, σ ≥ max{2M, 1}, and p σ be a strongly mean-calibrated gain function. For any bounded measurable function f : where c 0 = −ψ ′ (0) > 0, θ ǫ = min{ǫ, 2}, and c ǫ is a positive constant that is independent of f and will be given explicitly in the proof. Moreover, if p σ is exactly mean-calibrated, then the above inequality holds with θ ǫ = ǫ.
As Theorem 6 applies to f z,σ , we say that f z,σ is asymptotically mean calibrated. That is, when σ is adjusted according to the sample size n and its value diverges, the bias term between G σ (f ⋆ ) − G σ (f z,σ ) and f z,σ − f ⋆ 2 2,ρ shrinks to 0, yielding the calibration property. We next establish error bounds and convergence rates of f z,σ . In particular, we consider two cases, namely, when the gain function p σ is strongly mean-calibrated and when p σ is exactly meancalibrated, respectively. To this end, we introduce to characterize the approximation ability of the tuple (H, ρ, L 2 ρ X ) to learn f ⋆ . When p σ is strongly mean-calibrated, the established error bounds and convergence rates are as follows. Theorem 7. Let Assumptions 1 and 2 hold and σ > max{2M, 1}. Let f z,σ be produced by EGM (5) associated with a strong mean-calibrated gain function p σ . For any 0 < δ < 1, with probability at least 1 − δ, it holds that where With properly chosen σ values, an immediate corollary is as follows. Corollary 8. Under the assumptions of Theorem 7, let f ⋆ ∈ H and σ be chosen as σ := n ϑ 1 (ǫ,q) , where Then for any 0 < δ < 1, with probability at least 1 − δ, it holds that where θ ǫ = min{ǫ, 2}.
When p σ is exactly mean-calibrated, improved error bounds and rates can be established.
Theorem 9. Under the assumptions of Theorem 7, we further assume that p σ is exactly meancalibrated. Then for any 0 < δ < 1, with probability at least 1 − δ, it holds that where Corollary 10. Under the assumptions of Theorem 7, let f ⋆ ∈ H and σ be chosen as σ := n ϑ 2 (ǫ,q) , where Then for any 0 < δ < 1, with probability at least 1 − δ, it holds that Proofs of Theorems 7 and 9 are deferred to the appendix. Results in Corollaries 8 and 10 are immediate from the two theorems and so their proofs are omitted. Several remarks on the theoretical results are in order here.
• First, under the (1 + ǫ) moment condition, exponential type convergence rates for f z,σ are established by diverging σ values. These results demonstrate that EGM estimators can deal with regression problems in the presence of heavy-tailed noise since when 0 < ǫ < 1, the noise Y − f ⋆ (X) does not even admit finite variance.
• Second, these error bounds and convergence rates explicitly tell how the scale parameter σ in EGM influences the learnability of f z,σ . Such an influence is weakened when ǫ goes larger, which coincides with our intuitive understanding.
• Third, when p σ is strongly mean-calibrated, the tail of the noise distribution is sufficiently light, and when functions in H is smooth enough, asymptotic convergence rates of type O(n −2/3 ) can be obtained, suggesting the existence of a bottleneck phenomenon in learning f ⋆ . While when p σ is exactly mean-calibrated, such asymptotic convergence rates can be up to O(n −1 ). These findings and comparisons indicate the advantages of exactly mean-calibrated gain functions over strongly mean-calibrated ones.
• Fourth, these theoretical results can be immediately applied to the regression schemes in the motivating scenarios in Section 1.2. Such applications bring us novel results that deepen our understanding of these well-established but not fully-understood robust regression approaches. The instantiations and applications of the above theorems and corollaries will be detailed in Section 4.4.

Learning through EGM without Misspecification
It has been well understood that MLEs are asymptotically optimal when the likelihood function is correctly specified. Likewise, in the context of EGM, we also have a look at the case when the noise distribution is correctly specified and the gain function p σ results from the kernel of such a distribution. Theorem 11. Assume that the distribution of the noise Y − f ⋆ (X) is symmetric and is independent of X. Let p σ be the kernel of such a distribution and be symmetric and square integrable. Then f ⋆ is a global maximizer of the gain functional G σ (f ) and there exists an absolute constant C σ > 0 such for any bounded measurable function f : X → R, we have If, in addition, p σ is strongly mean-calibrated, then there exists an absolute constant C ′ σ > 0 such that We remark that correctly specifying the noise distribution could be a stringent and impractical requirement in real-world problems. However, the performance of EGM in this ideal situation helps better understand EGM schemes from a theoretical perspective. Theorem 11 indicates that when σ is specified correctly so that the gain function is the kernel of the noise distribution, the resulting EGM scheme is f ⋆ -regression calibrated, that is, Note that in (12), f ⋆ denotes the underlying truth function and is not necessarily the conditional mean function, but could be broadly any location function such as the conditional median function or the conditional mode function. Moreover, the theorem also indicates that when the noise distribution is correctly specified, EGMs induced by strongly mean-calibrated gain functions are essentially equivalent to the ERM induced by the square loss while at the same time, the former ones are capable of robust regression in the absence of light-tailed noise as have been illustrated in Theorems 7 and 9.
One may proceed with the establishment of error bounds and convergence rates of EGM by means of similar learning theory arguments and by recalling the regression calibration property developed in Theorem 11. In particular, it could be also shown that faster convergence rates are obtainable due to the equivalence of strongly mean-calibrated gain functions and the square loss in this case. Details are omitted due to their great similarity to the proofs of Theorems 7 and 9.

Case Studies and Applications
The generality of the EGM framework allows us to consider specific cases by choosing specific gain functions. When the conditional mean function is of interest, we investigate above the performance of EGM estimators associated with the gain functions that are strongly mean-calibrated or exactly mean-calibrated. The usefulness of the above-established theoretical results lies in that they can be directly applied to existing well-established but yet not fully-understood robust regression schemes

Gain Function Error Bounds and Rates
Tukey Regression Triweight (8) and (9) Truncated Least Square Epanechnikov (10) and (11) Geman-McClure Regression Cauchy (8) and (9) Maximum Correntropy Gaussian (8) and (9) and provide a statistical learning assessment on them. For instance, applying these results to the four regression schemes mentioned in the motivating scenarios in Section 1.2, we immediately obtain their error bounds and convergences rates, which are listed in Table 3. While one may also apply the theoretical results to other robust regression schemes, further exploration of the applications of the new framework and the theoretical results will be left for future research.

Further Insights and Perspectives
In this section, we provide further insights and perspectives by showing that the newly developed EGM framework enables us to devise more new bounded nonconvex loss functions. As further comparisons with ERM, we also stress that, in addition to the minimum distance estimation interpretation, the adaptiveness and the boundedness of gain functions differentiate EGM from ERM.

Devising New Bounded Nonconvex Losses from Gain Functions
As examplified in Section 3.4, the EGM framework allows us to translate bounded nonconvex losses into gain functions. Such correspondences also allow us to reformulate gain functions into bounded nonconvex losses. Noticing the richness and versatility of gain functions, various new bounded nonconvex losses can be obtained. Here we example an interesting instantiation of the idea by introducing generalized Tukey's loss The two power indices m, n control the smoothness of the loss function and with larger m and n values, the loss function becomes more smooth. In particular, the loss function turns to be more and more insensitive at the vicinity of t = 0 when the m and n values become larger and larger. The generalized Tukey's loss can be derived from the gain function p σ (t) = (1 − |t| m /σ m ) n and its introduction is inspired by the fact that when m = 2, n = 3, it reduces to the Tukey's biweight loss and when m = 2, n = 1, it gives the truncated square loss. One may explore other choices of m and n values, which leads to the following new bounded nonconvex losses: Tricube loss from the tricube gain function. The tricube loss is defined as It can be reformulated from the following Tricube gain function which results from the tricube smoothing kernel [46].
Quartic loss from the quartic gain function. The quartic loss is defined as It can be derived from the quartic gain function which comes from the quartic smoothing kernel.
Truncated absolute deviation loss from the triangle gain function. The truncated absolute deviation loss is defined as It can be derived from the following triangular gain function which results from the triangular smoothing kernel.
In addition, by hinging and translating the generalized Tukey's loss, one can also obtain a smoothened approximate of the 0− 1 loss for binary-valued regression, which may be of independent interest for robust classification.

Boundedness and Adaptiveness of Gain Functions Make a Difference
Further to our comparisons of EGM with ERM, we now rethink, in addition to the minimum distance estimation interpretation of EGM, what else makes the differences between the two types of learning schemes. In the above two panels, the dotted red curve with square marks denotes the conditional mode function fMO for the regression model (14). The dotted black curve with plus marks gives the conditional mean function fME. The dotted blue curve with ⊗ marks represents the learned Gaussian EGM estimator fz,σ.
Recall that a gain function can be translated into a bounded nonconvex loss and vice versa. As is commonly accepted, the boundedness of a loss function is essential in dealing with outliers in the response variable. On the other hand, EGM is association with a gain function p σ which serves as a surrogate of p ε and contains an integrated scale parameter σ. The introduction of this parameter provides flexibility and adaptiveness in learning.
In fact, apart from the boundedness of a gain function, it is its adaptiveness brought by the parameter σ that distinguishes EGM from ERM. This could be further illustrated by using the following toy example on Gaussian EGM, where we consider the regression model where x ∼ U (0, 1), f ⋆ (x) = 2 sin(πx), and κ(x) = 1 + 2x. The noise variable is distributed as ε ∼ 0.5N (−1, 2.5 2 ) + 0.5N (1, 0.5 2 ). With simple computations, we know that the conditional mean function is f ME (x) = 2 sin(πx), and the conditional mode function is approximately f MO (x) = 2 sin(πx) + 1 + 2x.
In our experiment, 200 observations are drawn from the above data-generating model for training and the size of the test set is also set to 200. The reconstructed curve is plotted in Fig. 1, in which the conditional mean function f ME and the conditional mode function f MO are also plotted. In our experiment, the hypothesis space H is chosen as a subset of a reproducing kernel Hilbert space induced by a Gaussian kernel, the bandwidth of which is selected through cross-validation. For the scale parameter σ in the gain function, we set σ = 0.05 in the left panel of Fig. 1 and σ = 10 in the right panel. In the two panels, the dotted blue curves with ⊗ marks are the learned Gaussian EGM estimators. Clearly, from the experiments, we see that with different choices, the Gaussian EGM estimators can approach different location functions. In fact, through numerical experiments, one can further show that in the presence of Cauchy noise, Gaussian EGM can still learn the truth function as demonstrated theoretically earlier. These empirical findings together with our theoretical results suggest that Gaussian EGM may possess more adaptiveness than ERM.

Conclusion
In this paper, a framework of learning through empirical gain maximization was developed to deal with robust regression problems. The development of such a framework was inspired by several wellestablished but yet not fully-understood regression schemes such as Tukey regression and Geman-McClure regression. Unlike ERM that can be traced to the framework of maximum likelihood estimation, empirical gain maximization can be interpreted from a minimum distance estimation viewpoint and thus may possess built-in robustness. To measure point-wise goodness-of-fit in regression problems, gain function was introduced. A list of gain functions was exampled and also carefully categorized. Interestingly, we showed that a variety of existing representative robust loss functions such as Tukey's biweight loss, the truncated squared loss, and the Geman-McClure loss can be reformulated as special cases of gain functions. A unified learning theory analysis was conducted to assess the performance of empirical gain maximization schemes in regression problems. The developed new framework and the conducted unified analysis not only help us better understand the existing non-convex robust regression schemes but also bring us new bounded nonconvex loss functions of the same kind.

Appendix: Lemmas and Collected Proofs
In this appendix section, we provide intermediate lemmas and detailed proofs of Theorems 6,7,9,and 11. Recall that for any bounded measurable function f : X → R, G σ (f ) and G σ,z (f ) denote the generalization gain and the empirical gain of f , respectively: For simplification of the analysis, we introduce the scaled generalization gain and correspondingly the scaled empirical gain .
We further denote f H,σ as the population version of f z,σ in H, namely, We first provide two lemmas that will be used in our proofs.

A.1 Lemmas
Lemma 12. Let ξ be a random variable on a probability space Z having variance v and satisfying |ξ − Eξ| ≤ B almost surely. Then for all ε > 0, .
Lemma 13. If a gain function p σ (t) is strongly mean-calibrated, then its representing function ψ(t) Proof. For any t 1 , t 2 ∈ R, if both t 1 ≥ 1 and t 2 ≥ 1, then by the fact that ψ(t 2 ) is L 1 -Lipschitz w.r.t. t, we have If both t 1 ≤ 1 and t 2 ≤ 1, since ψ ′ exists and is L 2 -Lipschitz continuous on [0, 1), we have for all Therefore, If t 1 < 1 and t 2 ≥ 1, then Combining all the three cases, we obtain the desired conclusion.
Lemma 14. Let Assumption 2 hold with some ǫ > 0. Let σ > max{2M, 1} and p σ be a strongly mean-calibrated gain function. For any measurable function f : Then where c 1 and c 2 are absolute positive constants independent of σ or f and will be given explicitly in the proof.
A.3 Proof of Theorem 7 Step 1: We first prove that, under Assumption 2, there are two absolute constants c ′ 3 and c ′ 4 (to be defined explicitly later) such that, for any γ ≥ c ǫ σ −θǫ and f ∈ H, there holds where and Θ(n, γ, σ) = , if ǫ > 1.

This proves
and the desired uniform concentration inequality (20) follows immediately from (18).
By Lemma 7.2 in [15], the equation has a unique positive solution γ ⋆ that satisfies , if ǫ > 1.
Let γ 0 = max(c ǫ σ −θǫ , γ ⋆ ). The uniform concentration inequality tells that holds for all f ∈ H with probability at least 1 − δ. Applying Young's inequality, holds for all f ∈ H with probability at least 1 − δ. Applying (21) particularly to f z,σ and f H,σ , we have and with probability at least 1 − δ.

A.4 Proof of Theorem 9
Theorem 9 can be proved analogously to Theorem 7. We omit the details.

A.5 Proof of Theorem 11
Proof. Since p σ (t) is the kernel of the distribution of Y − f ⋆ (X), there exists a constant c σ > 0 such thatˆ+ ∞ −∞ c σ p σ (t)dt = 1.
Further by the assumption that Y − f ⋆ (X) is symmetric and independent of X, we know p σ (t) is an even function and the density of Y |x is p Y |x (y) = c σ p σ (y − f ⋆ (x)) for all x ∈ X . Consider the function Then we see that Let p σ denote the Fourier transform of p σ , defined by Since p σ is even, p σ must be real. The Plancherel theorem tells that V (s) = 1 2πˆ+ ∞ −∞ ( p σ (ξ)) 2 e iξs dξ = 1 2πˆ+ ∞ −∞ ( p σ (ξ)) 2 cos(ξs)dξ.