Uniform Convergence of Gradients for Non-Convex Learning and Optimization

Introduction

The last decade has seen a string of empirical successes for gradient-based algorithms solving large scale non-convex machine learning problems (Krizhevsky et al., 2012; He et al., 2016). Inspired by these successes, the theory community has begun to make progress on understanding when gradient-based methods succeed for non-convex learning in certain settings of interest (Jain and Kar, 2017). The goal of the present work is to introduce learning-theoretic tools to—in a general sense—improve understanding of when and why gradient-based methods succeed for non-convex learning problems.

In a standard formulation of the non-convex statistical learning problem, we aim to solve

Our precise technical contributions are as follows:

We bring vector-valued Rademacher complexities (Maurer, 2016) and associated vector-valued contraction principles to bear on the analysis of uniform convergence for gradients. This approach enables norm-based capacity control, meaning that the bounds are independent of dimension whenever the predictor norm and data norm are appropriately controlled. We introduce a “chain rule” for Rademacher complexity, which enables one to decompose the complexity of gradients of compositions into complexities of their components, and makes deriving dimension-independent complexity bounds for common non-convex classes quite simple.

We establish variants of the Gradient Domination condition for the population risk in certain non-convex learning settings. The condition bounds excess risk in terms of the magnitude of gradients, and is satisfied in non-convex learning problems including generalized linear models and robust regression. As a consequence of the gradient uniform convergence bounds, we show how to use any algorithm that finds approximate stationary points for smooth functions in a black-box fashion to obtain optimal sample complexity for these models—both in high- and low-dimensional regimes. In particular, standard algorithms including gradient descent (Nesterov, 2013), SGD (Ghadimi and Lan, 2013), Non-convex SVRG (Reddi et al., 2016; Allen-Zhu and Hazan, 2016), and SCSG (Lei et al., 2017) enjoy optimal sample complexity, even when allowed to take multiple passes over the dataset.

We show that for non-smooth losses dimension-independent uniform convergence is not possible in the worst case, but that this can be circumvented using a new type of margin assumption.

Notation

Gradient Uniform Convergence: Why and How

Before introducing our tools for establishing gradient uniform convergence, let us introduce a family of losses for which this convergence has immediate consequences for the design of non-convex statistical learning algorithms.

The population risk $L_{\mathcal{D}}$ satisfies the $(\alpha,\mu)$-Gradient Domination condition with respect to a norm $\left\|\cdot\right\|$ if there are constants $\mu>0$, $\alpha\in$ such that

where $w^{\star}\in\operatorname*{arg\,min}{}_{w\in\mathcal{W}}L_{\mathcal{D}}(w)$ is any population risk minimizer.

The case $\alpha=2$ is often referred to as the Polyak-Łojasiewicz inequality (Polyak, 1963; Karimi et al., 2016). The general GD condition implies that all critical points are global, and is itself implied (under technical restrictions) by many other well-known conditions including one-point convexity (Li and Yuan, 2017), star convexity and $\tau$-star convexity (Hardt et al., 2018), and so-called “regularity conditions” (Zhang et al., 2016); for more see Karimi et al. (2016). The GD condition is satsified—sometimes locally rather than globally, and usually under distributional assumptions— by the population risk in settings including neural networks with one hidden layer (Li and Yuan, 2017), ResNets with linear activations (Hardt and Ma, 2017), phase retrieval (Zhang et al., 2016), matrix factorization (Liu et al., 2016), blind deconvolution (Li et al., 2018), and—as we show here—generalized linear models and robust regression.

The GD condition states that to optimize the population risk it suffices to find a (population) stationary point. What are the consequences of the statement for the learning problem, given that the learner only has access to the empirical risk $\widehat{L}_{n}{}$ which itself may not satisfy GD? The next proposition shows, via gradient uniform convergence, that GD is immediately useful for non-convex learning even when it is only satisfied at the population level.

2 Vector Rademacher Complexities: The How

The starting point for our uniform convergence bounds for gradients is to apply the standard tool of symmetrization—a vector-valued version, to be precise. To this end let us introduce a normed variant of Rademacher complexity.

Given a vector valued class of function $\mathcal{F}$ that maps the space $\mathcal{Z}$ to a vector space equipped with norm $\left\|\cdot\right\|$, we define the normed Rademacher complexity for $\mathcal{F}$ on instances $z_{1:n}$ via

With this definition we are ready to provide a straightforward generalization of the standard real-valued symmetrization lemma.

For any $\delta>0$, with probability at least $1-\delta$ over the data $\left\{(x_{t},y_{t})\right\}_{t=1}^{n}$,

The key tool used to prove Theorem 1, which appears throughout the technical portions of this paper, is the vector-valued Rademacher complexity due to Maurer (2016).

The vector-valued Rademacher complexity arises through an elegant contraction trick due to Maurer.

We remark that while our applications require only gradient uniform convergence, we anticipate that the tools of this section will find use in settings where convergence of higher-order derivatives is needed to ensure success of optimization routines. To this end, we have extended the chain rule (Theorem 1) to handle Hessian convergence; see Appendix E.

Application: Smooth Models

In this section we instantiate the general gradient uniform convergence tools and the GD condition to derive optimization consequences for two standard settings previously studied by Mei et al. (2016): generalized linear models and robust regression.

To establish the GD property and provide uniform convergence bounds, we make the following regularity assumptions on the loss.

The quantities $C_{h}/C_{l}/C_{s}$ and $\mu_{h}/\mu_{l}/\mu_{s}$ are constants depending on $(B,R,C_{\sigma},c_{\sigma},\beta,\log(\delta^{-1}))$ but not explicitly on dimension (beyond logarithmic factors) or complexity of the class $\mathcal{W}$ (beyond $B$ and $R$).

Precise statements for the problem dependent constants in Theorem 3 including dependence on the norms $R$ and $B$ can be found in Appendix C.

We now formally introduce the robust regression setting and provide a similar guarantee.

Robust Regression

Similar to the generalized linear model setup, the robust regression setup satisfies three variants of the GD depending on assumptions on the norm $\left\|\cdot\right\|$ and the data distribution.

The constants $C_{h}/C_{l}/C_{s}$ and $\mu_{h}/\mu_{l}/\mu_{s}$ depend on $(B,R,C_{\rho},c_{\rho},\beta,\log(\delta^{-1}))$, but not explicitly on dimension (beyond $\log$ factors) or complexity of the class $\mathcal{W}$ (beyond the range parameters $B$ and $R$).

Gather $n=\frac{1}{\varepsilon^{2}}\wedge\frac{d}{\varepsilon}$ samples $\left\{(x_{t},y_{t})\right\}_{t=1}^{n}$.

See Appendix C.3 for the full theorem statement and proof.

Now is a good time to discuss connections to existing work in more detail.

The sample complexity $O\left(\frac{1}{\varepsilon^{2}}\wedge{}\frac{d}{\varepsilon}\right)$ for Proposition 3 is optimal up to dependence on Lipschitz constants and the range parameters $B$ and $R$ (Tsybakov, 2008). The “high-dimensional” $O\left(\frac{1}{\varepsilon^{2}}\right)$ regime is particularly interesting, and goes beyond recent analyses to non-convex statistical learning (Mei et al., 2016), which use arguments involving pointwise covers of the space $\mathcal{W}$ and thus have unavoidable dimension-dependence. This highlights the power of the norm-based complexity analysis.

In the low-dimensional $O\left(\frac{d}{\varepsilon}\right)$ sample complexity regime, Theorem 3 and Theorem 4 recovers the rates of Mei et al. (2016) under the same assumptions—see Appendix C.3 for details. Notably, this is the case even when the radius $R$ is not constant. Note however that when $B$ and $R$ are large the constants in Theorem 3 and Theorem 4 can be quite poor. For the logistic link it is only possible to guarantee $c_{\sigma}\geq{}e^{-BR}$, and so it may be more realistic to assume $BR$ is constant.

The GLMtron algorithm of Kakade et al. (2011) also obtains $O\left(\frac{1}{\varepsilon^{2}}\right)$ for the GLM setting. Our analysis shows that this sample complexity does not require specialized algorithms; any first-order stationary point finding algorithm will do. GLMtron has no guarantees in the $O\left(\frac{d}{\varepsilon}\right)$ regime, whereas our meta-algorithm works in both high- and low-dimensional regimes. A significant benefit of GLMtron, however, is that it does not require a lower bound on the derivative of the link function $\sigma$. It is not clear if this assumption can be removed from our analysis.

As an alternative approach, stochastic optimization methods for finding first-order stationary points can be used to directly find an approximate stationary point of the population risk $\left\|L_{\mathcal{D}}(w)\right\|\leq{}\varepsilon$, so long as they draw a fresh sample at each step. In the high-dimensional regime it is possible to show that stochastic gradient descent (and for general smooth norms, mirror descent) obtains $O\left(\frac{1}{\varepsilon^{2}}\right)$ sample complexity through this approach; this is sketched in Appendix C.3. This approach relies on returning a randomly selected iterate from the sequence and only gives an in-expectation sample complexity guarantee, whereas Theorem 9 gives a high-probability guarantee.

Also, note that many stochastic optimization methods can exploit the $(2,\mu)$-GD condition. Suppose we are in the low-dimensional regime with $\Sigma\succeq{}\frac{1}{d}I$. The fastest GD-based stochastic optimization method that we are aware of is SNVRG (Zhou et al., 2018), which under the $(2,O(d))$-GD condition will obtain $\varepsilon$ excess risk with $O\left(\frac{d}{\varepsilon}+\frac{d^{3/2}}{\varepsilon^{1/2}}\right)$ sample complexity.

This discussion is summarized in Table 1.

Non-Smooth Models

In the previous section we used gradient uniform convergence to derive immediate optimization and generalization consequences by finding approximate stationary points of smooth non-convex functions. In practice—notably in deep learning—it is common to optimize non-smooth non-convex functions; deep neural networks with rectified linear units (ReLUs) are the canonical example (Krizhevsky et al., 2012; He et al., 2016). In theory, it is trivial to construct non-smooth functions for which finding approximate stationary points is intractable (see discussion in Allen-Zhu (2018b)), but it appears that in practice stochastic gradient descent can indeed find approximate stationary points of the empirical loss in standard neural network architectures (Zhang et al., 2017). It is desirable to understand whether gradient generalization can occur in this setting.

The first result of this section is a lower bound showing that even for the simplest possible non-smooth model—a single ReLU—it is impossible to achieve dimension-independent uniform convergence results similar to those of the previous section. On the positive side, we show that it is possible to obtain dimension-independent rates under an additional margin assumption.

This result contrasts the setting where $\sigma$ is smooth, where the techniques from Section 2 easily yield a dimension-independent $O(\sqrt{n})$ upper bound on the Rademacher complexity. This is perhaps not surprising since the gradients are discrete functions of $w$, and indeed VC-style arguments suffice to establish the lower bound.

In the classical statistical learning setting, the main route to overcoming dimension dependence—e.g., for linear classifiers—is to assume a margin, which allows one to move from a discrete class to a real-valued class upon which a dimension-independent Rademacher complexity bound can be applied (Shalev-Shwartz and Ben-David, 2014). Such arguments have recently been used to derive dimension-independent function value uniform convergence bounds for deep ReLU networks as well (Bartlett et al., 2017; Golowich et al., 2018). However, this analysis relies on one-sided control of the loss, so it is not clear whether it extends to the inherently directional problem of gradient convergence. Our main contribution in this section is to introduce additional machinery to prove dimension-free gradient convergence under a new type of margin assumption.

Given a distribution $P$ over the support $\mathcal{X}$ and an increasing function $\phi:\left[0,1\right]\to\left[0,1\right]$, any $w\in\mathcal{W}$ is said to satisfy the $\phi$-soft-margin condition with respect to P if

We call $\phi$ a margin function. We define the set of all weights that satisfy the $\phi$-soft-margin condition with respect to a distribution $P$ via:

Of particular interest is $\mathcal{W}(\phi,\widehat{\mathcal{D}}_{n})$, the set of all the weights that satisfy the $\phi$-soft-margin condition with respect to the empirical data distribution. That is, any $w\in\mathcal{W}(\phi,\widehat{\mathcal{D}}_{n})$ predicts with at least a $\gamma$ margin on all but a $\phi(\gamma)$ fraction of the data. The following theorem provides a dimension-independent uniform convergence bound for the gradients over the class $\mathcal{W}(\phi,\widehat{\mathcal{D}}_{n})$ for any margin function $\phi$ fixed in advance.

Let $\phi:\left[0,1\right]\to\left[0,1\right]$ be a fixed margin function. With probability at least $1-\delta$ over the draw of the data $\left\{(x_{t},y_{t})\right\}_{t=1}^{n}$,

As a concrete example, when $\phi(\gamma)=\gamma^{\frac{1}{2}}$ Theorem 6 yields a dimension-independent uniform convergence bound of $O(n^{-\frac{1}{12}})$, thus circumventing the lower bound of Theorem 5 for large values of $d$.

Discussion

We showed that vector Rademacher complexities are a simple and effective tool for deriving dimension-independent uniform convergence bounds and used these bounds in conjunction with the (population) Gradient Domination property to derive optimal algorithms for non-convex statistical learning in high and infinite dimension. We hope that these tools will find broader use for norm-based capacity control in non-convex learning settings beyond those considered here. Of particular interest are models where convergence of higher-order derivatives is needed to ensure success of optimization routines. Appendix E contains an extension of Theorem 1 for Hessian uniform convergence, which we anticipate will find use in such settings.

In Section 3 we analyzed generalized linear models and robust regression using both the $(1,\mu)$-GD property and the $(2,\mu)$-GD property. In particular, the $(1,\mu)$-GD property was critical to obtain dimension-independent norm-based capacity control. While there are many examples of models for which the population risk satisfies $(2,\mu)$-GD property (phase retrieval (Sun et al., 2016; Zhang et al., 2016), ResNets with linear activations (Hardt and Ma, 2017), matrix factorization (Liu et al., 2016), blind deconvolution (Li et al., 2018)), we do not know whether the $(1,\mu)$-GD property holds for these models. Establishing this property and consequently deriving dimension-independent optimization guarantees is an exciting future direction.

Lastly, an important question is to analyze non-smooth problems beyond the simple ReLU example considered in Section 4. See Davis and Drusvyatskiy (2018) for subsequent work in this direction.

K.S acknowledges support from the NSF under grants CDS&E-MSS 1521544 and NSF CAREER Award 1750575, and the support of an Alfred P. Sloan Fellowship. D.F. acknowledges support from the NDSEG PhD fellowship and Facebook PhD fellowship.

References

Appendix A Preliminaries

The following is a weighted generalization of the vector-valued Lipschitz contraction inequality.

Same proof as Theorem 3 in Maurer (2016), with the additional observation that $\left\|z\right\|_{A_{t}}=\left\|A_{t}^{1/2}z\right\|_{2}$. ∎

Immediate consequence of Lemma 2, along with sub-additivity of the supremum. ∎

A.2 Bound for Vector-Valued Random Variables

A norm $\|\cdot\|$ is said to be $\beta$-smooth if the function $\Psi(x)=\frac{1}{2}\left\|x\right\|^{2}$ is $\beta$-smooth with respect to $\left\|\cdot\right\|$.

Let $\left\|\cdot\right\|$ be any norm for which there exists $\Psi$ such that $\Psi(x)\geq\frac{1}{2}\left\|x\right\|^{2}$, $\Psi(0)=0$, and $\Psi$ is $\beta$-smooth with respect to $\left\|\cdot\right\|$. Then

The reader may consult Pinelis (1994) for a high-probability version of this theorem.

The following spaces and norms satisfy the preconditions of Theorem 7:

Using Jensen’s inequality and the upper bound property of $\Psi$ we have

Applying the smoothness property at time $n$, and using that $\epsilon_{n}$ is independent of $\epsilon_{1},\ldots,\epsilon_{n-1}$:

The result follows by repeating this argument from time $t=n-1$ to $t=1$. ∎

Appendix B Proofs from Section 2

Let $\mathcal{G}\subseteq{}\left\{g:\mathcal{Z}\to\mathfrak{B}\right\}$ for arbitrary set $\mathcal{Z}$ and vector space $\mathfrak{B}$. Let $Z_{1},\ldots,Z_{n}\sim{}\mathcal{D}$ i.i.d. for some distribution $\mathcal{D}$. Let a norm $\left\|\cdot\right\|$ over $\mathfrak{B}$ be fixed. Then with probability at least $1-\delta$ over the draw of $Z_{1:n}$,

This follows immediately by applying Theorem 8 to the expanded function class $\mathcal{F}\vcentcolon=\left\{Z\mapsto{}\left\langle g(Z),v\right\rangle\mid{}g\in\mathcal{G},\left\|v\right\|_{\star}\leq{}1\right\}$. ∎

This is a direct consequence of McDiarmid’s inequality. Consider any vector-valued function class of functions $\mathcal{G}$. Let $Z_{1},\ldots,Z_{n}\sim{}\mathcal{D}$ i.i.d. for some distribution $\mathcal{D}$. Then McDiarmid’s inequality implies that with probability at least $1-\delta$ over the draw of $Z_{1:n}$,

Using the chain rule for differentiation we have

which establishes the result after expanding terms. All that must be verified is that the assumptions on the norm bounds for $\nabla{}G_{t}$ and $\nabla{}F_{t}$ in the theorem statement ensure the the Lipschitz requirement in the statement of Lemma 3 is met. ∎

Appendix C Proofs from Section 3

For all proofs in this section we adopt the notation $s\vcentcolon=\left\|w^{\star}\right\|_{0}$, and use $c>0$ to denote an absolute constant whose precise value depends on context.

For the general smooth norm pair setup in (14), Lemma 5 and Lemma 7 imply

where we recall $C_{\text{h}}=c\cdot\frac{B^{2}R^{2}C_{\sigma}^{3}\sqrt{\beta}+2C_{\sigma}^{2}BR\sqrt{\log(1/\delta)}}{c_{\sigma}}$ and $\mu_{\text{h}}=c\cdot{}\frac{BC_{\sigma}}{c_{\sigma}}$.

Consider the generalized linear model setup of Section 3.

When $\left\|\cdot\right\|/\left\|\cdot\right\|_{\star}$ are any dual norm pair, we have $\left(1,\frac{BC_{\sigma}}{c_{\sigma}}\right)$-GD:

Upper bound for excess risk. We first prove the following intermediate upper bound:

Letting $w\in\mathcal{W}$ be fixed, we have

We now consider the term inside the expectation. Since $\sigma$ is increasing we have

point-wise. We apply two lower bounds. First, $\sigma^{\prime}(\left\langle w,x\right\rangle)>c_{\sigma}$ by assumption. Second, Lipschitzness of $\sigma$ implies

Combining these inequalities, we also obtain the following inequality in expectation over $x$:

Lastly, since the model is well-specified we have

Proving the GD conditions. With the inequality (18) established the various GD inequalities follow in quick succession.

$\left(1,\frac{BC_{\sigma}}{c_{\sigma}}\right)$-GD: To prove this inequality, simply user Hölder’s inequality to obtain the upper bound,

What remains is to relate the gradient norm to the term $\left\|P_{\mathcal{X}}\left(w-w^{\star}\right)\right\|_{2}$. We proceed with another lower bound argument similar to the one used to establish (18),

Consider a particular draw of $x$ and assume $\left\langle w,x\right\rangle\geq{}\left\langle w^{\star},x\right\rangle$ without loss of generality. Using the mean value theorem, there is some $s\in\left[\left\langle w^{\star},x\right\rangle,\left\langle w,x\right\rangle\right]$ such that

In other words, by rearranging and applying Cauchy-Schwarz we have

Combining this inequality with (19), we have

By the assumption that $\left\|w\right\|_{1}\leq{}\left\|w^{\star}\right\|_{1}$, we apply Lemma 6 to conclude that 1) $w-w^{\star}\in\mathcal{C}(S(w^{\star}),1)$ and 2) $\left\|w-w^{\star}\right\|_{1}\leq{}2\sqrt{s}\left\|w-w^{\star}\right\|_{2}$. The first fact implies that

Combining this with the preceding inequality yields the result.

The following utility lemma is a standard result in high-dimensional statistics (e.g. Tibshirani et al. (2015)).

Let $S\vcentcolon={}S(w^{\star})$. Then the constraint that $\left\|w\right\|_{1}\leq{}\left\|w^{\star}\right\|$ implies

Rearranging, this implies $\left\|\nu_{S^{C}}\right\|_{1}\leq{}\left\|\nu_{S}\right\|_{1}$, so the first result is established.

For the second result, $\nu\in\mathcal{C}(S,1)$ implies $\left\|\nu\right\|_{1}=\left\|\nu_{S}\right\|_{1}+\left\|\nu_{S^{C}}\right\|_{1}\leq{}2\left\|\nu_{S}\right\|_{1}\leq{}2\sqrt{\left\lvert S\right\rvert}\left\|\nu_{S}\right\|_{2}\leq{}2\sqrt{\left\lvert S\right\rvert}\left\|\nu\right\|_{2}$. ∎

Let the norm $\left\|\cdot\right\|$ satisfy the smoothness property of Theorem 7 with constant $\beta$. Then the empirical loss gradient for the generalized linear model setting enjoys the normed Rademacher complexity bound,

Observe that $G^{\prime}_{t}(s)=2\left(\sigma(s)-y_{t}\right)\sigma^{\prime}(s)$ and $\nabla{}F_{t}(w)=x_{t}$, so our assumptions imply that that $\left\lvert G^{\prime}_{t}(s)\right\rvert\leq{}2C_{\sigma}$ and $\left\|\nabla{}F_{t}(w)\right\|\leq{}R$. We can thus apply Theorem 1 to conclude

For the first term on the left-hand side, observe that for any $s$, $\left\lvert G^{\prime\prime}_{t}(s)\right\rvert\leq{}2\left\lvert\sigma^{\prime\prime}(s)\right\rvert+2\left\lvert\sigma^{\prime}(s)\right\rvert^{2}\leq{}4C_{\sigma}^{2}$, so $G^{\prime}_{t}$ is $4C_{\sigma}^{2}$-Lipschitz. The classical scalar Lipschitz contraction inequality for Rademacher complexity (Lemma 1) therefore implies

Finally, by our smoothness assumption on the norm, Theorem 7 implies

C.2 Robust Regression

For the general smooth norm pair setup in (22), Lemma 8 and Lemma 9 imply

Where we recall $C_{\text{h}}=c\cdot\frac{B^{2}R^{2}C_{\rho}^{2}\sqrt{\beta}+C_{\rho}^{2}BR\sqrt{\log(1/\delta)}}{c_{\rho}}$ and $\mu_{\text{h}}=c\cdot{}\frac{BC_{\rho}}{c_{\rho}}$.

Consider the robust regression setup of Section 3.

When $\left\|\cdot\right\|/\left\|\cdot\right\|_{\star}$ are any dual norm pair, we have $\left(1,\frac{BC_{\rho}}{c_{\rho}}\right)$-GD:

Excess risk upper bound. To begin, smoothness of $\rho$ implies that for any $s,s^{\star}\in\mathcal{S}$ we have

Since this holds point-wise, we use it to derive the following in-expectation bound

since $\zeta$ is conditionally symmetric and $\rho^{\prime}$ is odd. We therefore have

On the other hand, using the form of the gradient we have

To lower bound the term inside the expectation, consider a particular draw of $x$ and assume $\left\langle w-w^{\star},x\right\rangle\geq{}0$; this is admissible because $h$, like $\rho^{\prime}$, is odd. Then we have

where the last line follows because $h(0)=0$ and $h^{\prime}(0)>c_{\rho}$. Since this holds pointwise, we simply take the expectation to show that

and consequently the excess risk is bounded by

Proving the GD conditions. We now use (C.2) to establish the GD condition variants.

$\left(1,\frac{BC_{\rho}}{c_{\rho}}\right)$-GD: Use Hölder’s inequality to obtain the upper bound,

Rearranging and applying Cauchy-Schwarz, we have

Combining this inequality with (28), we have

By the assumption that $\left\|w\right\|_{1}\leq{}\left\|w^{\star}\right\|_{1}$, we apply Lemma 6 to conclude that 1) $w-w^{\star}\in\mathcal{C}(S(w^{\star}),1)$ and 2) $\left\|w-w^{\star}\right\|_{1}\leq{}2\sqrt{s}\left\|w-w^{\star}\right\|_{2}$, and so

Rearranging, and applying the $\left\|w-w^{\star}\right\|_{1}\leq{}2\sqrt{s}\left\|w-w^{\star}\right\|_{2}$ inequality:

Combining the two inequalities gives the final result.

Let the norm $\left\|\cdot\right\|$ satisfy the smoothness property (see Theorem 7) with constant $\beta$. Then the gradient for robust regression satisfies the following normed Rademacher complexity bound:

Then $G^{\prime}_{t}(s)=\rho^{\prime}(s-y_{t})$ and $\nabla{}F_{t}(w)=x_{t}$, so our assumptions imply that that $\left\lvert G^{\prime}_{t}(s)\right\rvert\leq{}C_{\rho}$ and $\left\|\nabla{}F_{t}(w)\right\|\leq{}R$. We apply Theorem 1 to conclude

For the first term on the left-hand side, we have that for any $s$, $\left\lvert G^{\prime\prime}_{t}(s)\right\rvert=2\left\lvert\rho^{\prime\prime}(s-y_{t})\right\rvert\leq{}2C_{\rho}$, so $G^{\prime}_{t}$ is $2C_{\sigma}$-Lipschitz. Then the by scalar contraction for Rademacher complexity (Lemma 1),

Finally, the smoothness assumption on the norm (via Theorem 7) implies

For completeness, we show below that both models indeed have Lipschitz gradients, and so standard smooth optimizers can be applied to the empirical loss.

Generalized Linear Model. Observe that for any $(x,y)$ pair we have

Letting $f(s)=(\sigma(s)-y)\sigma^{\prime}(s)$, we see that the assumption on the loss guarantees $\left\lvert f^{\prime}(s)\right\rvert\leq{}3C_{\sigma}^{2}$, so we have

Robust Regression. Following a similar calculation to the GLM case, we have

Now let $f(s)=(\sigma(s)-y)\sigma^{\prime}(s)$, and observe that $\left\lvert f^{\prime}(s)\right\rvert\leq{}3C_{\sigma}^{2}$, so we have

C.3 Further Discussion

We now sketch in more detail the relation between the rates of Theorem 3 and Theorem 4 and those of Mei et al. (2016). We focus on the fast rate regime, and on the case $R=\sqrt{d}$ (e.g., when $x\sim{}\mathcal{N}(0,I_{d\times{}d})$).

Uniform convergence. Their uniform convergence bounds scale as $O(\tau\sqrt{d/n})$, where $\tau$ is the subgaussian parameter for the data $x$, whereas our uniform convergence bounds scale as $O(R^{2}\sqrt{1/n})$. When $R=\sqrt{d}$ both bounds scale as $O(d\sqrt{1/n})$, but our bounds do not depend on $d$ when $R$ is constant, whereas their bound always pays $\sqrt{d}$.

Analysis of regularized stationary point finding for high-dimensional setting

Here we show that any algorithm that finds a stationary point of the regularized empirical loss generically succeeds obtains optimal sample complexity in the high-dimensional/norm-based setting. We focus on the generalized linear model in the Euclidean setting.

Let $r(w)=\frac{\lambda}{2}\left\|w\right\|^{2}_{2}$. Define $L_{\mathcal{D}}^{\lambda}(w)=L_{\mathcal{D}}(w)+r(w)$ and $\widehat{L}_{n}^{\lambda}(w)=\widehat{L}_{n}(w)+r(w)$. We consider any algorithm that returns a point $\widehat{w}$ with $\nabla{}\widehat{L}_{n}^{\lambda}(\widehat{w})=0$, i.e. any stationary point of the regularized empirical risk.

Consider the generalized linear model setting. Let $\widehat{w}$ be any point with $\nabla{}\widehat{L}_{n}^{\lambda}(\widehat{w})=0$. Suppose that $\left\|w^{\star}\right\|_{2}=1$ and $C_{\sigma},R>1$. Then there is some absolute constant $c>0$ such that for any fixed $\delta>0$, if the regularization parameter $\lambda$ satisfies

then with probability at least $1-\delta$,

Theorem 9 easily extends to the robust regression setting by replacing invocations of Lemma 7 with Lemma 9 and use of (18) with (C.2).

Using (18) and the definition of $w^{\star}$, along with the strong convexity of $r$, we get

Since $\left\langle\nabla L_{\mathcal{D}}(w),w-w^{\star}\right\rangle\geq{}0$, this is upper bounded by

Using the non-negativity of $\left\langle\nabla{}r(w),w-w^{\star}\right\rangle$ over $\widetilde{\mathcal{W}}$, and that $C_{\sigma}/c_{\sigma}>1$, this implies

Using that $\widehat{w}\in\widetilde{\mathcal{W}}$, and that $\nabla\widehat{L}_{n}^{\lambda}(\widehat{w})=0$, we have

where we have used additionally that the regularization term does not depend on data. Combining this bound with (31), and using that $\widehat{w}\in\widetilde{\mathcal{W}}$ and the elementary inequality $(a+b)^{2}\leq{}2(a^{2}+b^{2})$, we see that there exist constants $c,c^{\prime}>0$ such that

Expanding the definition of the regularized excess risk, this is equivalent to

Observe that if $\lambda>\sqrt{c\cdot\frac{R^{4}C_{\sigma}^{6}}{c_{\sigma}^{2}}\cdot\frac{1}{n}}$ the middle term in this expression is at most zero. We choose

Substituting choice this into the expression above leads to a final bound of

Recall that $\nabla{}\widehat{L}_{n}^{\lambda}(\widehat{w})=0$. This implies $\nabla\widehat{L}_{n}(\widehat{w})=-\lambda\widehat{w}$, and so $\left\|\nabla{}\widehat{L}_{n}(\widehat{w})\right\|_{2}\leq{}\lambda\left\|\widehat{w}\right\|_{2}\leq{}\lambda$. Using (18) we have

Using the bound on the empirical gradient above, we get

Using (12), (13), and Lemma 7, applied with $B=1$, we have that with probability at least $1-\delta$,

where all constants are as in Assumption 1.

(12), (13), and Lemma 7 imply that for any fixed $B$, with probability at least $1-\delta$,

since $B_{i}\leq{}e\left\|w\right\|_{2}$. ∎

Analysis of mirror descent for high-dimensional setting.

Here we show that mirror descent obtains optimal excess risk for the norm-based/high-dimensional regime in Theorem 3 and Theorem 4.

Focusing on the GLM, if we take a single pass over the entire dataset $\left\{(x_{t},y_{t})\right\}_{t=1}^{n}$ in order, the standard analysis for mirror descent starting at $w_{1}=0$ with optimal learning rate tuning (Hazan, 2016) guarantees that the following inequality holds deterministically:

Since each point is visited a single time, this leads to the following guarantee on the population loss in expectation

Consequently, if we define $\widehat{w}$ to be the result of choosing a single time $t\in\left[n\right]$ uniformly at random and returning $w_{t}$, this implies that

Combining this inequality with (18), we have

Likewise, combining the mirror descent upper bound with (C.2) leads to a rate of $O\left(RB\frac{C_{\rho}^{2}}{c_{\rho}}\sqrt{\frac{\beta}{n}}\right)$ for robust regression. Thus, when all parameters involved are constant, it suffices to take $n=\frac{1}{\varepsilon^{2}}$ to obtain $O(\varepsilon)$ excess risk in both settings.

Appendix D Proofs from Section 4

We first focus on the more technical case where $n\geq{}d$.

For simplicity, assume that $y_{t}=-1$ for all $t\in\left[n\right]$. Then it holds that

Before proceeding to the proof, let us introduce some auxiliary definitions and results. The following functions will be used throughout the proof. They are related by Lemma 11.

With probability at least $1-\delta$, simultaneously for all $w\in\mathcal{W}$ and all $\gamma>0$,

We only sketch the proof here as it follows standard analysis (see Theorem 5 of Kakade et al. (2009b)). The key technique is to introduce a Lipschitz function $\zeta_{\gamma}(t)$:

Let the margin function $\phi$ and $\delta>0$ be fixed. Define functions $\psi(\cdot)$, $\phi_{1}(\cdot)$, and $\phi_{2}(\cdot)$ as follows:

Now, conditioning on the events of Lemma 11, we have that with probability at least $1-\delta$,

where the second inequality holds with probability at least $1-\delta$ using Lemma 4. They key here is that we are able to apply the standard symmetrization result because we have replaced $\mathcal{W}(\phi,\widehat{\mathcal{D}}_{n})$ with a set that does not depend on data. Next, invoking the chain rule (Theorem 1), we split the Rademacher complexity term above as:

For $(\star\star)$, the definition of $\mathcal{W}(\phi_{2},\widehat{\mathcal{D}}_{n})$ implies

The quantity $(\star)$ can be bounded by writing it as

Final bound.

Assembling equations (33), (34), (35), and (36) yields

Appendix E Additional Results

As an application of Theorem 10, we give a simple proof of dimension-independent Rademacher bound for the generalized linear model setting.

Assume in addition to Assumption 1 assume that $\left\lvert\sigma^{\prime\prime\prime}(s)\right\rvert\leq{}C_{\sigma}$ for all $s\in\mathcal{S}$, and suppose $\left\|\cdot\right\|$ is any $\beta$-smooth norm. Then the empirical loss Hessian for the generalized linear model setting enjoys the normed Rademacher complexity bound,

It is easy to see that the same approach leads to a normed Rademacher complexity bound for the Hessian in the robust regression setting as well. We leave the proof as an exercise.

Assume in addition to Assumption 2 that $\left\lvert\rho^{\prime\prime\prime}(s)\right\rvert\leq{}C_{\rho}$ for all $s\in\mathcal{S}$, and suppose $\left\|\cdot\right\|$ is any $\beta$-smooth norm. Then the empirical loss Hessian for the robust regression setting enjoys the normed Rademacher complexity bound:

Combining the two terms gives the desired chain rule. ∎

Observe that $G^{\prime}_{t}(s)=2\left(\sigma(s)-y_{t}\right)\sigma^{\prime}(s)$, $\nabla{}F_{t}(w)=x_{t}$, $\nabla^{2}F_{t}=\boldsymbol{0}$, $G^{\prime\prime}_{t}(s)(s)=2(\sigma^{\prime}(s))^{2}+2y_{t}\sigma^{\prime\prime}(s)$, and $G^{\prime\prime\prime}(s)=4\sigma^{\prime}(s)\sigma^{\prime\prime}(s)+2y_{t}\sigma^{\prime\prime\prime}(s)$, which implies that $\left\lvert G^{\prime\prime\prime}_{t}(s)\right\rvert\leq{}6C_{\sigma}^{2}$. Using Theorem 10 with constants $L_{F,1}=R^{2},~{}L_{F,2}=0,~{}L_{G,1}=2C_{\sigma}^{2}~{}\text{and}~{}L_{G,2}=4C_{\sigma}^{2}$, we get