Smoothing the Nonsmoothness

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

18,976 characters · 4 sections · 27 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

titlepage\begin{center} {\bf Smoothing the Nonsmoothness} {\sc Chaohua Dong$^{a}$, Jiti Gao$^{b}$, Bin Peng$^{b}$ and Yundong Tu$^{c}$} $^{a}$Zhongnan University of Economics and Law, China\\ $^{b}$Monash University, Australia\\$^{c}$Peking University, China \end{center} \begin{abstract} To tackle difficulties for theoretical studies in situations involving nonsmooth functions, we propose a sequence of infinitely differentiable functions to approximate the nonsmooth function under consideration. A rate of approximation is established and an illustration of its application is then provided. {\bf Key words}: Convergence rate; Generalized functions; Quadratic approximation; Regular function sequence \end{abstract}

Introduction

This paper proposes a unified smoothing technique that aims at providing a generic framework to tackle difficulties in theoretical analysis in the situations that involve nonsmooth functions. These situations mostly encountered are objective functions constructed by nonsmooth loss functions (e.g. least absolute deviation (LAD), quantile loss and Huber's loss) or approximations to some functions of interest using nonsmooth activation functions (e.g. ReLU) in machine learning. The relevant literature includes huber1964, koenker1978, bai1992, fanjq1994, Tianetal, xiao2009a, fan2018, degui2021, fernandes2021, zhouwx2022, hexm2023, just to name a few. In what follows, we give two well known examples to illustrate our concerns.

exampleConsider the rectified linear unit (ReLU) \begin{eqnarray} \rho(x) = x\vee 0, \end{eqnarray} which is widely adopted for different types of deep neural network studies. However, ReLU is piecewise linear, and it is not yet clear how to handle the accumulated non-differentiability through layers in both theory and practice. The concern raised here actually exists in some well known software packages. To the best of our knowledge, however, no satisfactory treatment has been offered. For example, the well known neuralnet in R does not even support the use of ReLU (FG2010). PyTorch does have ReLU and some of its variations included as the activation functions, but the explanation about the optimization process is very vague (https://pytorch.org/docs/stable/optim.html). Keras includes Adam algorithm and its variations (https://keras.io/api/optimizers/adam/), but Adam requires “a stochastic scalar function that is differentiable w.r.t. parameters...” (KingBa15), which clearly does not apply to ReLU.

exampleConsider a regression where an objective function is constructed using a nonsmooth function loss $\rho(\cdot)$ say to estimate unknown parameter. The most popular loss is the check function. Nonsmoothness of $\rho(\cdot)$ gives rise to difficulties in both theoretical analysis and computation especially when handling large datasets (hexm2023). As can be seen, hexm2023 propose a convolution-type smoothed quantile loss to replace the usual check function.

In this paper we are about to provide a unified approach through generalized functions to tackle a class of nonsmooth functions in statistics and machine learning. The class includes several commonly encountered losses such as quantile loss, LAD, Huber's loss and ReLU. Also, our treatment is independent of data that is advantageous over existing smoothing methods. Last but not least, we are able to establish a rate of convergence for a sequence of infinitely differentiable functions that can converge to the nonsmooth function. It is our knowledge that the relevant literature (see, for example, phillips1991, phillips1995) has not established such a rate of convergence. Because of this approximation rate the theoretical analysis that we shall show in Section (ref) below is in a solid ground.

Often, nonsmooth losses have second derivatives in generalized function sense (e.g. Dirac delta function) that however cannot be used directly in theoretical analysis. Nonetheless, their operation is valid under integration with certain conditions. For example, for any random variable $e$ with density function $f_e(x)$, ${\mathbb E}[\delta(e)]=\int \delta(x)f_e(x)dx=f_e(0)$, provided $f_e(x)$ is continuous at $x=0$, where $\delta(\cdot)$ is Dirac delta function. This motivates us to use a sequence of infinitely differentiable functions (regular sequence) to approximate any given nonsmooth function, and the derivatives of the regular sequence converge to the derivatives of the nonsmooth function in generalized function sense, so that in some suitable circumstance the nonsmooth function under consideration can be replaced by the regular sequence. This is the rationale of our approach.

In the sequel, Section 2 shows the smoothing method we propose, Section 3 gives one of its applications, and Monte Carlo simulations and all proofs of our theoretical results are given in an online material.

Generalized functions and smoothing technique

This section will show the rationale of the proposed smoothing technique based on a generalized function approach; we shall define a regular sequence for a given nonsmooth function, and establish its rate of convergence.

The following assumption describes a class of nonsmooth functions $\rho(\cdot)$ that we work with. As $\rho(\cdot)$ is convex, its subgradient $\psi(\cdot)$ always exists even though the value of $\psi(\cdot)$ at some points may not be unique; we allow $\psi(\cdot)$ to take any of them while the analysis in the sequel remains unchanged. The focus then rests on the second derivative of $\rho(\cdot)$ that may not exist in ordinary sense.

Assumption 2.1.

enumerate[(a)] • Suppose that $\rho(\cdot)$ is positive and convex, and has its only minimum at zero; moreover, it is a locally integrable function on the real line with the rate of diverging at infinity no faster than that of a polynomial. • $\rho(\cdot)$ satisfies Lipschitz condition $|\rho(x+u)-\rho(u)|\le C |x|$ for any $x, u\in \mathbb{R}$, where $C$ is an absolute constant.

By convexity, $\rho(\cdot)$ is a continuous function (see, for example, Corollary 10.1.1 of rockafellar1970). The other conditions in (a) ensure that the proposed generalized function approach is valid (see the definition of space $S$ in supplementary material), and these are certainly fulfilled by all loss functions encountered in the literature and ReLU. The Lipschitz condition in (b) plays a central role that depicts a technical requirement in the following analysis, and it is guaranteed by the boundedness of subgradient. Note also that it is satisfied by several most popular loss functions and ReLU. For example, when $\rho(u)=|u|$, we have $C=1$; when $\rho(u)$ is the check function with parameter $\tau\in (0,1)$, we have $C=\max(\tau, 1-\tau)$; when $\rho(u)$ is Huber's loss with parameter $c$, we have $C=c$; for ReLU $\rho(u)=\max(0, u)$, $C=1$.

To define the regular sequence of loss functions we need the following assumption.

Assumption 2.2.

enumerate[(a)] • Suppose that $\phi(\cdot)$ is nonnegative, symmetric and $\int \phi(u)dv=1$. • Suppose that $\phi(u)$ is infinitely differentiable, and $|u|^k\phi^{(\ell)}(u)\to 0$ for any nonnegative integers $k, \ell$ as $|u|$ approaches the boundary of the domain of $\phi(\cdot)$.

It is readily seen that any smooth and thin-tailed density satisfies this assumption, while the most popular one is the normal density. In addition, a bounded supported density function satisfies this assumption easily as long as it is infinitely differentiable. For example,

equation[equation omitted — 145 chars of source]

where $C$ is chosen to make the integration of $\phi(u)$ to be one. Note that the support of $\phi(u)$ can be changed to be any symmetric interval that however is not essential, and this assumption excludes densities such as uniform densities since they are not smooth on the real line. In addition, Assumption 2.2(b) ensures existence of all moments of $\phi(u)$, and coupled with Assumption 2.1, Assumption 2.2 (b) implies $\rho(u)\phi(u)\to 0$ as $|u|$ tends to the boundary of the domain of $\phi(\cdot)$.

Definition 2.1

Let $\rho(\cdot)$ and $\phi(\cdot)$ satisfy Assumptions 2.1 and 2.2, respectively. For a given positive integer $m$, define $\phi_m(u)=m\phi(mu)$, and

equation[equation omitted — 62 chars of source]

The function sequence $\{\rho_m(u)\}$ is called a regular sequence of $\rho(u)$.

Next, we establish some crucial results about a rate of convergence for a regular sequence of nonsmooth functions converging to the original nonsmooth function under consideration, which is used as a bridge between nonsmooth loss and its infinitely smooth approximation counterpart in the generalized function context.

theoLet $\rho(u)$ and $\phi(u)$ satisfy Assumptions 2.1 and 2.2, respectively, and $\rho_m(u)$ be the regular sequence of $\rho(u)$ given by (ref). Then, (1) $\rho_m(u), m=1,2,\cdots,$ are convex; (2) $\rho_m(u), m=1,2,\cdots,$ are differentiable with any order, and in particular, \begin{align} \rho_m'(u)=&-\int \rho(x)\phi_m'(x-u)dx, & \rho_m”(u)=&\int \rho(x)\phi_m”(x-u)dx, \end{align} and $\rho_m'(u)\to \psi(u)$ and $\rho_m''(u)\to \rho''(u)$ as $m\to\infty$ except on a set of measure zero; (3) $\sup_{u\in \mathbb{R}}|\rho_m(u)-\rho(u)|\le Cm^{-1}$ for some absolute constant $C$.

The proof is given in Appendix.

{\bf Remark 2.1}. \ Note that the assertion (1) confirms that all functions in the regular sequence of $\rho(u)$ remain convexity as $\rho(u)$ does. The assertion (2) is understandable in generalized function sense because $\phi_m(u)$ plays a role as a delta-convergent sequence, i.e. $\phi_m(x)\to \delta(x)$ as $m\to \infty$; see kanwal1983 and stein2003.

{\bf Remark 2.2}. \ The importance of Theorem (ref) is the rate of convergence: $\sup_{u\in \mathbb{R}}|\rho_m(u)-\rho(u)|\le Cm^{-1}$. To the best of our knowledge, the rate is the first one being established in the relevant literature. It is due to this rate that our analysis below is on a solid and rigorous ground. In Figure (ref), three losses and ReLU along with their regular sequences generated by standard normal density are plotted to visualize the approximations established in Theorem (ref) where, as can be seen, all kinks are smoothed and the regular sequences approach the respective functions well. Note also that the Lipschitz condition in Assumption 2.1 can be relaxed as $|\rho(x)-\rho(y)|\le C|x-y|^\alpha$ for $\alpha\in (0,1]$. All the results below under the relaxation hold with a change on the choice of $m$. \qed

figure[figure omitted — 159 chars of source]

For these particular nonsmooth functions and $\phi(u)$ given in (ref), we have the following results that improve Theorem (ref).

cor\it Suppose that $\rho_m(u)$ below is generated by $\phi(u)$ given in (ref). Let $\epsilon>0$ be given arbitrarily. \begin{enumerate}[(a)] • Let $\rho(u)=|u|$, $\rho(u)=u(\tau-I(u<0))$, or $\rho(u)=0\vee u$. There exists an integer $m_0=m_0(\epsilon)$ such that $\rho_m(u)=\rho(u)$ for all $m\ge m_0$ and all $|u|>\epsilon$, whereas (2) of Theorem (ref) remains true for $|u|\le \epsilon$, viz. $\sup_{|u|\le \epsilon}|\rho_m(u)-\rho(u)|=O(m^{-1})$ as $m\to \infty$. • For Huber's loss, $\rho_c(u)$, there exists an integer $m_0=m_0(\epsilon)$ such that $\rho_m(u)=\rho(u)$ for all $m\ge m_0$ and $|u|>c+\epsilon$, whereas (2) of Theorem (ref) is improved, viz. $\sup_{|u|\le c}|\rho_m(u)-\rho(u)|=O(m^{-2})$ as $m\to \infty$. \end{enumerate}

The proof of this corollary is given in Appendix. Because of compactness of the domain of $\phi(\cdot)$, for these nonsmooth functions the corollary claims $\rho_m(u)=\rho(u)$ for $|u|>\epsilon$ (or $|u|>c+\epsilon$) uniformly for all $m\ge m_0(\epsilon)$ for given $\epsilon>0$; also for Huber's loss the convergence rate has been improved to be $m^{-2}$ in $|u|<c$. Figure (ref) shows the plots of the three loss functions and ReLU with their regular sequences constructed from $\phi(u)$ in (ref). Apparently, Figure (ref) shows better approximation.

figure[figure omitted — 164 chars of source]

Application of the smoothing technique

To show the essence of the proposed smoothing technique, in this section we shall illustrate through a linear parametric regression. To do so, let us consider a linear regression of the form:

align[align omitted — 80 chars of source]

where the unknown parameter $\theta_0\in \Theta$, a compact subset of $\mathbb{R}^d$. The estimator of $\theta_0$ in the regression (ref) is defined by

equation[equation omitted — 130 chars of source]

where $\rho(\cdot)$ satisfies Assumption 2.1.

To analyse $\widehat{\theta}$, instead of considering minimization over $\theta\in\Theta$, we shall follow the literature to consider vectors $\beta$ in the tangent cone $T_{\Theta}(\theta_0)$ of $\Theta$ at $\theta_0$, that is, $\beta=\sqrt{n}(\theta-\theta_0)$ where $\theta\in\Theta$. The relevant literature includes bickel1974, badu1989, davis1992, charles1994, phillips1995 and gao2009.

We then focus on the minimization of $L_n(\theta)-L_n(\theta_0)$ instead of $L_n(\theta)$ in (ref), and write

align*[align* omitted — 119 chars of source]

Hereby, the objective function is reparametrized in $\beta\in \mathbb{R}^d$, and when $\widehat\beta$ minimizes $\tilde{L}_n(\beta)$, $\widehat\theta$ minimizes $L_n(\theta)$ where $\widehat\beta=\sqrt{n}(\widehat\theta -\theta_0)$.

theo\it Suppose that $\{e_i, x_i\}_{i=1}^n$ is an independent and identically distributed (i.i.d.) sequence, $e_i$ and $x_i$ are mutually independent, and the fourth moment of $x_i$ exists. Define \begin{equation} Q_n(\beta)=\left(-\frac{\displaystyle1}{\sqrt{n}}\sum_{i=1}^n\psi(e_i)x_i'\right)\beta +\frac{\Da}{\displaystyle2}\beta' \left(\frac{\displaystyle1}{\Dn} \sum_{t=1}^nx_ix_i'\right)\beta, \end{equation} where $a={\mathbb E}[\rho''(e_i)]>0$. Then, \begin{equation} |\tilde{L}_{n}(\beta)-Q_n(\beta)|=O_P(n^{-1/2}), \end{equation} for each $\beta$; and \begin{equation} \sup_{\|\beta\|\le c}|\tilde{L}_{n}(\beta)-Q_n(\beta)|=O_P(n^{-1/2}), \end{equation} for any $c>0$; moreover, \begin{equation} \sup_{\|\beta\|\le c_n}|\tilde{L}_{n}(\beta)-Q_n(\beta)|=o_P(1), \end{equation} for any $c_n=o(n^{1/4})$. Furthermore, define $\widehat\beta_Q$ as the minimizer of $Q_n(\beta)$, and suppose that ${\mathbb E}[\psi(e_i)]=0$ and the minimum eigenvalue of $\frac{\displaystyle1}{\Dn} \sum_{t=1}^nx_ix_i'$, $\lambda_{\min}>0$, for all large $n$. Then as $n\to\infty$ we have \begin{equation} \widehat{\beta}-\widehat\beta_Q=o_P(n^{-1/4}\log\log(n)). \end{equation}

The proof is regelated to Appendix. Theorem (ref) proposes a quadratic form $Q_n(\beta)$ and gives several approximation errors of $\tilde{L}_{n}(\beta)-Q_n(\beta)$ as well as the error between their minimizers. It is clear that

align*[align* omitted — 168 chars of source]

and it is the unique minimizer of $Q_n(\beta)$.

{\bf Remark 3.1}. \ As argued in pollard1991, quadratic approximation to objective function of M estimation avoids technical difficulty, such as stochastic equicontinuity in an asymptotic proof. Indeed, equation (ref) gives $\widehat{\beta}=\widehat\beta_Q+o_P(n^{-1/4}\log\log(n))$. Once one has the limit of $\widehat\beta_Q$ after specifying $\rho(\cdot)$, the limit of $\widehat\beta=\sqrt{n}(\widehat\theta -\theta_0)$ is available immediately that is the main purpose of the analysis for the estimator derived from the loss $\rho(\cdot)$. For example, if $\rho(u)=u(\tau-I(u<0))$, then $a=f_e(0)$, ${\mathbb E}[\psi(e_i)]^2={\mathbb E}[\tau-I(e_i<0)]^2=\tau(1-\tau)$; suppose moreover $\frac{\displaystyle1}{\Dn} \sum_{i=1}^nx_ix_i'\to_P\Sigma$, then $\widehat\beta_Q\to_D[\sqrt{\tau(1-\tau)}/f_e(0)]N(0, \Sigma^{-1})$ as $n\to\infty$ that is also the limit of $\sqrt{n}(\widehat\theta -\theta_0)$.

{\bf Remark 3.2}. \ fan2003 use quadratic approximation for smooth objective function and derive limit theory from this quadratic function. By contrast, the generalized function approach we propose mainly deals with nonsmooth loss functions.

Conclusion

In this paper, we propose a smoothing technique providing convenient and efficient tool to tackle difficulties in theoretical analysis in the situations that involve nonsmooth functions. Precisely, an infinitely differentiable sequence that converges to the nonsmooth function is proposed; convergence rate is established that facilitates theoretical analysis. An application is provided to illustrate the usefulness of the smoothing technique.

{

center[center omitted — 84 chars of source]

center[center omitted — 210 chars of source]

The supplementary material provides two sections, Monte Carlo simulations and the proofs of the theorems and corollary.