Risk and parameter convergence of logistic regression

Introduction

Despite the simplicity of this setting, a general characterization of the gradient descent path has escaped the literature for a variety of reasons. It is possible for the data to be configured so that $\mathcal{R}_{\log}$ is strongly convex, in which case standard convex optimization tools grant the existence of a unique bounded optimum, and moreover a rate at which gradient descent iterates converge to it. It is also possible, however, that data is linearly separable, in which case $\mathcal{R}_{\log}$ has an infimum of 0 despite being positive everywhere; the optimum is off at infinity, and convergence analyses operate by establishing a maximum margin property of the normalized iterates $\nicefrac{{w_{j}}}{{|w_{j}|}}$ (Soudry et al., 2017), just as in the analysis of AdaBoost (Schapire and Freund, 2012; Telgarsky, 2013).

In general, data can fail to induce a strongly convex risk or a linearly separable problem. Despite this, there is still a unique characterization of the gradient descent path. Specifically, gradient descent is biased to follow an optimal ray $\mathinner{\left\{\bar{v}+r\cdot\bar{u}\ \mathrel{\mathop{\ordinarycolon}}\ r\geq 0\right\}}$, which is constructed as follows. First, as detailed in Section 2, the data uniquely determines (via a greedy procedure) a linearly separable subset, with a corresponding maximum margin predictor $\bar{u}$; gradient descent converges to $\bar{u}$ in direction, meaning $\nicefrac{{w_{j}}}{{|w_{j}|}}\to\bar{u}$. The remaining data span a space $S$; the empirical risk of the remaining data is strongly convex over bounded subsets of $S$, and possesses a unique optimum $\bar{v}$, to which the projected gradient descent iterates converge, meaning $\Pi_{S}w_{j}\to\bar{v}$.

(Convergence in risk.) For any step sizes $\eta_{j}\leq 1$ and any $t\geq 1$,

where $\mathcal{O}(\cdot)$ hides problem-dependent constants.

(Convergence in parameters; implicit bias and regularization.) The data uniquely determines a subspace $S$ and a vector $\bar{v}\in S$, such that if $\eta_{j}\mathrel{\mathop{\ordinarycolon}}=1/\sqrt{j+1}$ and $t^{2}=\Omega(n\ln(t))$, letting $\Pi_{S}$ denote orthogonal projection onto $S$ and $\bar{w}_{t}\mathrel{\mathop{\ordinarycolon}}=\operatorname*{arg\,min}\mathinner{\left\{\mathcal{R}(w)\mathrel{\mathop{\ordinarycolon}}|w|\leq|w_{t}|\right\}}$ denote the solution to the constrained optimization problem, then

If there are examples outside $S$, their projection onto $S^{\perp}$ is linearly separable with maximum margin predictor $\bar{u}\in S^{\perp}$, and

In particular, $\nicefrac{{w_{t}}}{{|w_{t}|}}\to\bar{u}$ and $\Pi_{S}w_{t}\to\bar{v}$.

This theorem captures implicit bias by showing that gradient descent follows the unique ray $\{\bar{v}+r\cdot\bar{u}\mathrel{\mathop{\ordinarycolon}}r\geq 0\}$, even though the risk itself may be minimized by any vector which lies in the relative interior of a convex cone defined by the problem. Similarly, the theorem captures implicit regularization by showing that the gradient descent iterates also track the sequence of constrained optima $(\bar{w}_{j})_{j\geq 1}$.

This section first builds up the case of general data with a few illustrative examples, including strongly convex and linearly separable cases. Thereafter, a complete construction and characterization of the optimal ray $\{\bar{v}+r\cdot\bar{u}\mathrel{\mathop{\ordinarycolon}}r\geq 0\}$ and related objects is provided in Theorem 2.1.

Risk convergence (Section 3).

The preceding section on problem structure reveals that the (bounded) point $\bar{v}+\bar{u}\mathinner{\left(\nicefrac{{\ln(t)}}{{\gamma}}\right)}$ achieves low risk; plugging this into a modified smoothness argument yields converge in risk with no apparent dependence on the optimum at infinity.

Parameter convergence (Section 4).

The preceding problem structure reveals $\mathcal{R}$ is strongly convex over bounded subsets of $S$, which gives convergence to $\bar{v}$ via standard convex optimization tools.

To prove $\nicefrac{{w_{j}}}{{|w_{j}|}}\to\bar{u}$, the first key to the analysis is to study not $\mathcal{R}$ but instead $\ln\mathcal{R}$, which more conveniently captures local smoothness (extreme flattening) of $\mathcal{R}$. To complete the proof, a number of technical issues must be worked out, including bounds on $|w_{t}|$, which rely upon an adaptation of the perceptron convergence proof. This proof goes through much more easily for the exponential loss, which is the main reason for its appearance in Theorem 1.1.

Related work (Section 5).

The paper closes with a discussion of related work.

1 Notation

which has made use of $L$ at varying input dimensions.

Gradient descent here will always start with $w_{0}\mathrel{\mathop{\ordinarycolon}}=0$, and thereafter set $w_{j+1}\mathrel{\mathop{\ordinarycolon}}=w_{j}-\eta_{j}\nabla\mathcal{R}(w_{j})$. It is convenient to define $\gamma_{j}\mathrel{\mathop{\ordinarycolon}}=|\nabla(\ln\mathcal{R})(w_{j})|=|\nabla\mathcal{R}(w_{j})|/\mathcal{R}(w_{j})$ and $\hat{\eta}_{j}\mathrel{\mathop{\ordinarycolon}}=\eta_{j}\mathcal{R}(w_{j})$, whereby

Moreover, let $\bar{w}_{t}\mathrel{\mathop{\ordinarycolon}}=\operatorname*{arg\,min}\mathinner{\left\{\mathcal{R}(w)\mathrel{\mathop{\ordinarycolon}}|w|\leq|w_{t}|\right\}}$ denote the solution to the corresponding constrained optimization problem.

Problem structure

This section culminates in Theorem 2.1, which characterizes the unique ray $\{\bar{v}+r\cdot\bar{u}\mathrel{\mathop{\ordinarycolon}}r\geq 0\}$. To build towards this, first consider the following examples.

Strong convexity.

An intermediate setting.

The general case.

Combining elements from the preceding examples, the general case may be characterized as follows; it appears in Figure 4, with all relevant objects labeled. In the general case, the dataset consists of a maximal linearly separable subset $Z$, with the remaining data falling into a subset over which the empirical risk is strongly convex. Specifically, $Z$ is constructed with the following greedy procedure: for each example $(x_{i},y_{i})$, include it in $Z$ if there exists $u_{i}$ with $\left\langle u_{i},x_{i}y_{i}\right\rangle>0$ and $\min_{j}\left\langle u_{j},x_{j}y_{j}\right\rangle\geq 0$. The aggregate $u\mathrel{\mathop{\ordinarycolon}}=\sum_{i\in Z}u_{i}$ satisfies $\left\langle u,x_{i}y_{i}\right\rangle>0$ for $i\in Z$ and $\left\langle u,x_{i}y_{i}\right\rangle=0$ otherwise. Therefore $Z$ can be strictly separated by some vector $u$ orthogonal to $Z^{c}$; let $\bar{u}$ denote the maximum margin separator of $Z$ which is orthogonal to $Z^{c}$.

Turning now to $Z^{c}$, any vector $v$ which is correct on some $(x_{i},y_{i})\in Z^{c}$ (i.e., $\left\langle u,x_{i}y_{i}\right\rangle>0$) must also be incorrect on some other example $(x_{j},y_{j})$ in $Z^{c}$ (i.e., $\left\langle v,x_{j}y_{j}\right\rangle<0$); otherwise, $(x_{i},y_{i})$ would have been included in $Z$! Consequently, as in Figure 2 above, the empirical risk restricted to $Z^{c}$ is strongly convex, with a unique optimum $\bar{v}$. The gradient descent iterates follow the ray $\{\bar{v}+r\cdot\bar{u}\mathrel{\mathop{\ordinarycolon}}r\geq 0\}$, which means they are globally optimal along $Z^{c}$, and achieve zero risk and follow the maximum margin direction $\bar{u}$.

Turning back to the construction in Figure 4, the linearly separable data $Z$ is the two red and blue circles, while $Z^{c}$ consists of data points on the vertical axis. The points in $Z^{c}$ do not affect $\bar{u}$, and have been adjusted to move $\bar{v}$ away from 0, where it rested in Figure 3.

Now using the notation $A_{i}=-y_{i}x_{i}^{\top}$, for $i\in Z$, the vector $-y_{i}x_{i}$ is collected into $A_{c}$, while for $i\in Z^{c}$, the vector $-y_{i}x_{i}^{\top}$ is put into $A_{S}$. The above constructions are made rigorous in the following theorem. The proof of Theorem 2.1, presented in the appendix, follows the intuition above.

The rows of $A$ can be uniquely partitioned into matrices $(A_{S},A_{c})$, with a corresponding pair of orthogonal subspaces $(S,S^{\perp})$ where $S=\textup{span}(A^{\top}_{S})$ satisfying the following properties.

(Separable part.) If $A_{c}$ is nonempty (and thus so is $A_{\perp}$), then $A_{\perp}$ is linearly separable. The maximum margin is given by

Risk convergence

Gradient descent decreases the risk as follows.

This proof relies upon three essential steps.

A slight generalization of standard smoothness-based gradient descent bounds (cf. Section 3).

A useful comparison point to feed into the preceding gradient descent bound (cf. Section 3): the choice $\bar{v}+\bar{u}\mathinner{\left(\nicefrac{{\ln(t)}}{{\gamma}}\right)}$, made possible by Theorem 2.1.

In more detail, the first step, a refined smoothness-based gradient descent guarantee, is as follows. While similar bounds are standard in the literature (Bubeck, 2015; Nesterov, 2004), this version has a short proof and no issue with unbounded domains.

Suppose $f$ is convex, and there exists $\beta\geq 0$ so that $1-\nicefrac{{\eta_{j}\beta}}{{2}}\geq 0$ and gradient iterates $(w_{0},\ldots,w_{t})$ with $w_{j+1}\mathrel{\mathop{\ordinarycolon}}=w_{j}-\eta_{j}\nabla f(w_{j})$ satisfy

The proof is similar to the standard ones, and appears in the appendix.

The second step, as above, is to produce a reference point $z$ to plug into Section 3.

Lastly, the smoothness guarantee on $\mathcal{R}$. Even though the logistic loss is smooth, this proof gives a refined smoothness inequality where the $j^{\textup{th}}$ step is $\mathcal{R}(w_{j})$-smooth; this refinement will be essential when proving parameter convergence. This proof is based on the convergence guarantee for AdaBoost (Schapire and Freund, 2012). Recall the definitions $\gamma_{j}\mathrel{\mathop{\ordinarycolon}}=|\nabla(\ln\mathcal{R})(w_{j})|=|\nabla\mathcal{R}(w_{j})|/\mathcal{R}(w_{j})$ and $\hat{\eta}_{j}\mathrel{\mathop{\ordinarycolon}}=\eta_{j}\mathcal{R}(w_{j})$.

Additionally, $|w_{t}|\leq\sum_{j<t}\hat{\eta}_{j}\gamma_{j}$.

This proof mostly proceeds in a usual way via recursive application of a Taylor expansion

A direct but important consequence is obtained by applying $\ln$ to both sides:

It follows that $\ln\mathcal{R}$ is smooth, but moreover has constant smoothness unlike $\mathcal{R}$ above.

Combining these pieces now leads to a proof of Theorem 3.1, given in full in the appendix. As a final remark, note that step size $\eta_{j}=1$ led to a $\widetilde{\mathcal{O}}(1/t)$ rate, whereas $\eta_{j}=1/\sqrt{j+1}$ leads to a $\widetilde{\mathcal{O}}(1/\sqrt{t})$ rate.

Parameter convergence

As in Theorem 1.1, the parameter convergence guarantee gives convergence to $\bar{v}\in S$ over the strongly convex part $S$ (that is, $\Pi_{S}w_{t}\to\bar{v}$ and $\Pi_{S}\bar{w}_{t}\to\bar{v}$), and convergence in direction (convergence of the normalized iterates) to $\bar{u}\in S^{\perp}$ over the separable part $S^{\perp}$ ($\nicefrac{{w_{t}}}{{|w_{t}|}}\to\bar{u}$ and $\nicefrac{{\bar{w}_{t}}}{{|\bar{w}_{t}|}}\to\bar{u}$). In more detail, the convergence rates are as follows.

(General case.) Suppose $\eta_{j}=1/\sqrt{j+1}$, and $t\geq 5$, and $\displaystyle\nicefrac{{\sqrt{t}}}{{\ln(t)^{3}}}\geq\nicefrac{{n(1+R)}}{{\gamma^{2}}},$ where $R\mathrel{\mathop{\ordinarycolon}}=\sup_{j<t}|\Pi_{S}w_{j}|=\mathcal{O}(1)$. Then

and if $A_{c}$ is nonempty, then $|\Pi_{S^{\perp}}w_{t}|=\Theta(\ln(t))$, and

Establishing rates of parameter convergence not only relies upon all previous sections, but also is much more involved, and will be split into multiple subsections.

The easiest place to start the analysis is to dispense with the behavior over $S$. For convenience, define

and note $\mathcal{R}(w)=\mathcal{R}_{S}(w)+\mathcal{R}_{c}(w)$.

Convergence over $S$ is a consequence of strong convexity and risk convergence (cf. Theorem 3.1).

By Theorem 2.1, $\mathcal{R}_{S}(\bar{v})=\bar{}\mathcal{R}$. Thus, by strong convexity, for $w\in\mathinner{\left\{w_{t},\bar{w}_{t}\right\}}$ (whereby $\mathcal{R}(w)\leq\mathcal{R}(w_{t})$),

The bound follows by noting $\mathcal{R}(w_{t})\leq\mathcal{R}(w_{0})\leq 1$, and alternatively invoking in Theorem 3.1. ∎

If $A_{c}$ is empty, the proof is complete by plugging $\eta_{j}=1/\sqrt{j+1}$ into Section 4. The rest of this section establishes convergence to $\bar{u}\in S^{\perp}$.

Before getting into the guts of Theorem 4.1, this section will establish bounds on $|w_{t}|$. These bounds are used in Theorem 4.1 in two ways. First, as will be clear in the next section, it is natural to prove rates with $|w_{t}|$ in the denominator, thus lower bounding $|w_{t}|$ with a function of $t$ gives the desired bound.

Note that this section focuses on behavior within $A_{c}$; suppose that $A_{c}$ is nonempty, since otherwise $A=A_{S}$ and Theorem 4.1 follows from Section 4. When $A_{c}$ is nonempty, the solution is off at infinity, and $|w_{t}|$ grows without bound. For this reason, these bounds will be on $w_{t}$ rather than $\Pi_{\perp}w_{t}$, since $|w_{t}-\Pi_{\perp}w_{t}|=|\Pi_{S}w_{t}|=\mathcal{O}(1)$ by Section 4.

On one hand, $\left\langle\Pi_{\perp}w_{t}-\bar{u}\cdot r,\bar{u}\right\rangle$ is upper bounded by $\mathinner{\!\left\lVert\Pi_{\perp}w_{t}-\bar{u}\cdot r\right\rVert}$, whose upper bound is given by the following lemma, which is a modification of Section 3 with $\mathcal{R}$ replaced with $\mathcal{R}_{c}$.

The proof is similar to that of Section 3, but inserts $\Pi_{\perp}$ in a few key places.

On the other hand, to lower bound $\left\langle\Pi_{\perp}w_{t}-\bar{u}\cdot r,\bar{u}\right\rangle$, notice that

To show that $w$ is close to $\bar{u}$ in direction, it is essential to lower bound $\left\langle\bar{u},w\right\rangle/|w|$, since

To control this, recall the representation $\bar{u}=-A^{\top}\bar{q}/\gamma$, where $\bar{q}$ is a dual optimum (cf. Theorem 2.1). With this in hand, and an appropriate choice of convex function $g$, the Fenchel-Young inequality gives for any $w_{t}$, $t\geq 1$, and any $w$ such that $g(Aw)\leq g(Aw_{t})$,

The significance of working with $w$ with $g(Aw)\leq g(Aw_{t})$ is to allow the proof to handle both $\bar{w}_{t}$ and $w_{t}$ simultaneously.

The other key idea is to use $g=\ln(L_{\exp}/n)$. With this choice, both preceding numerator terms can be bounded: $g^{*}(q)=\ln n+\sum_{i=1}^{n}q_{i}\ln q_{i}\leq\ln n$ for any probability vector $q$, whereas $g(Aw_{t})$ can be upper bounded by applying $\ln$ to both sides of Section 3, as eq. 3.2, yielding an expression which will cancel with the denominator since $|w_{t}|\leq\sum_{j<t}\hat{\eta}_{j}\gamma_{j}$.

To simplify this further, note $\eta_{j}\leq 1$ and Section 3 also imply

and moreover the definition $\gamma=\min\mathinner{\left\{|A_{\perp}^{\top}q|\mathrel{\mathop{\ordinarycolon}}q\geq 0,\sum_{i}q=1\right\}}$ (cf. Theorem 2.1) implies

To finish, invoke the preceding inequality with $w\in\{\bar{w}_{t},w_{t}\}$, noting that $|w_{t}|=|\bar{w}_{t}|$. To produce a rate depending on $t$ and not $|w_{t}|$, the lower bound on $|w_{t}|$ in Section 4.1 is applied with $|\bar{v}|=R=0$ and $n=n_{c}$ thanks to separability. The following proposition summarizes this derivation.

where $|w_{t}|\geq\min\mathinner{\left\{\ln(t)-\ln 2,\ {}\ln\mathinner{\left(\sum_{j<t}\eta_{j}\right)}-2\ln\ln t+2\ln\gamma\right\}}+\ln\ln 2$.

The scheme from the separable case does not directly work: for instance, the proofs relied upon $\gamma_{i}\geq\gamma$, but now $\gamma_{i}\to 0$. This term $\gamma_{i}$ arose by applying Section 3 to control $\ln\mathcal{R}(w_{t})$, which in the separable case decreased to $-\infty$, in the general case, however, it can be bounded below.

The fix is to replace $\mathcal{R}(w_{t})$ with $\mathcal{R}_{c}(w_{t})$, or rather $\mathcal{R}(w_{t})-\bar{}\mathcal{R}=\mathcal{R}(w_{t})-\inf_{w}\mathcal{R}(w)$; this quantity goes to 0, and there is again a hope of exhibiting the fortuitous cancellations which proved parameter convergence. More abstractly, by subtracting $\bar{}\mathcal{R}$, the proof is again trying to work in the separable case, though there will be cross-terms to contend with.

The first step, then, is to replace the appearance of $\mathcal{R}$ in earlier Fenchel-Young approach (cf. Section 4.2) with $\mathcal{R}(w_{t})-\bar{}\mathcal{R}$.

Note the appearance of the additional cross term $|\Pi_{S}(w)|$; by Section 4, this term is bounded.

The next difficulty is to replace the separable case’s use of Section 3 to control $\ln\mathcal{R}(w_{t})$ with something controlling $\ln(\mathcal{R}(w_{t})-\bar{}\mathcal{R})$.

Moreover, if there exists a sequence $(w_{j})_{j=t_{0}}^{t-1}$ such that the above condition holds, then

The proof of Section 4.3 is quite involved, but boils down to the following case analysis. The first case is that there is more error over $S$, whereby a strong convexity argument gives a lower bound on the gradient. Otherwise, the error is larger over $S^{c}$, which leads to a big step in the direction of $\bar{u}$.

A key property of the upper bound in Section 4.3 is that it has replaced $\gamma_{j}^{2}$ in Section 3 with $\gamma_{j}\gamma$. Plugging this bound into the Fenchel-Young scheme in Section 4.3 will now fortuitously cancel $\gamma$, which leads to the following promising bound.

As in the separable case, an extended amount of careful massaging, together with Section 3 and Section 4.1 to control the warm start, is sufficient to establish the parameter convergence of Theorem 4.1 in the general case.

Related work

The technical basis for this work is drawn from the literature on AdaBoost, which was originally stated for separable data (Freund and Schapire, 1997), but later adapted to general instances (Mukherjee et al., 2011; Telgarsky, 2012). This analysis revealed not only a problem structure which can be refined into the $(S,S^{\perp})$ used here, but also the convergence to maximum margin solutions (Telgarsky, 2013). Since the structural analysis is independent of the optimization method, the key structural result, Theorem 2.1 in Section 2, can be partially found in prior work; the present version provides not only an elementary proof, but moreover differs by providing $S$ and $S^{\perp}$ (and not just a partition of the data) and the subsequent construction of a unique $\bar{u}$ and its properties.

The remainder of the analysis has some connections to the AdaBoost literature, for instance when providing smoothness inequalities for $\mathcal{R}$ (cf. Section 3). There are also some tools borrowed from the convex optimization literature, for instance smoothness-based convergence proofs of gradient descent (Nesterov, 2004; Bubeck, 2015), and also from basic learning theory, namely an adaptation of ideas from the perceptron convergence proof in order to bound $|w_{t}|$ (Novikoff, 1962).

Another close line of work is an analysis of gradient descent for logistic regression when the data is separable (Soudry et al., 2017; Gunasekar et al., 2018; Nacson et al., 2018). The analysis is conceptually different (tracking $(w_{j})_{j\geq 0}$ in all directions, rather than the Fenchel-Young and smoothness approach here), and (assuming linear separability) achieves a better rate than the one here, although it is not clear if this is possible in the nonseparable case. Other work shows that not just gradient descent but also steepest descent with other norms can lead to margin maximization (Gunasekar et al., 2018; Telgarsky, 2013), and that constructing loss functions with an explicit goal of margin maximization can lead to better rates (Nacson et al., 2018). Another line of work uses condition numbers to analyze these problems with a different parameterization (Freund et al., 2017).

There is some work in online learning on optimization over unbounded sets, for instance bounds where the regret scales with the norm of the comparator (Orabona and Pal, 2016; Streeter and McMahan, 2012). By contrast, as the present work is not adversarial and instead has a fixed training set, part of the work (a consequence of the structural result, Theorem 2.1) is the existence of a good, small comparator.

The authors are grateful for support from the NSF under grant IIS-1750051.

References

Appendix A Omitted proofs from Section 2

Before proving Theorem 2.1, note the following result characterizing margin maximization over $S^{\perp}$.

Suppose $A_{\perp}$ has $n_{c}>0$ rows and there exists $u$ with $A_{\perp}u<0$. Then

Moreover there exists a unique nonzero primal optimum $\bar{u}$, and every dual optimum $\bar{q}$ satisfies $\bar{u}=-A_{\perp}^{\top}\bar{q}/\gamma$.

To start, note $\gamma>0$ since there exists $u$ with $A_{\perp}u<0$.

Combining this with the Fenchel-Rockafellar duality theorem (Borwein and Lewis, 2000, Theorem 3.3.5, Exercise 3.3.9.f),

and moreover every primal-dual optimal pair $(\bar{u},\bar{q})$ satisfies $A_{\perp}^{\top}\bar{q}\in\partial\left(\iota_{|\cdot|_{2}\leq 1}\right)(-\bar{u})$, which means $\bar{u}=-A_{\perp}^{\top}\bar{q}/\gamma$.

It only remains to show that $\bar{u}$ is unique. Since $\gamma>0$, necessarily any primal optimum has unit length, since the objective value will only decrease by increasing the length. Consequently, suppose $u_{1}$ and $u_{2}$ are two primal optimal unit vectors. Then $u_{3}\mathrel{\mathop{\ordinarycolon}}=(u_{1}+u_{2})/2$ would satisfy

but then the unit vector $u_{4}\mathrel{\mathop{\ordinarycolon}}=u_{3}/|u_{3}|$ would have $|u_{4}|>|u_{3}|$ when $u_{1}\neq u_{2}$, which implies $\max_{i}(A_{\perp}u_{4})<\max_{i}(A_{\perp}u_{3})=\max_{i}(A_{\perp}u_{1})$, a contradiction. ∎

(of Theorem 2.1) Partition the rows of $A$ into $A_{c}$ and $A_{S}$ as follows. For each row $i$, put it in $A_{c}$ if there exists $u_{i}$ so that $Au_{i}\leq 0$ (coordinate-wise) and $(Au_{i})_{i}<0$; otherwise, when no such $u_{i}$ exists, add this row to $A_{S}$. Define $S\mathrel{\mathop{\ordinarycolon}}=\textup{span}(A_{S}^{\top})$, the linear span of the rows of $A_{S}$. This has the following consequences.

To start, $S^{\perp}=\textup{span}(A_{S}^{\top})^{\perp}=\ker(A_{S})\subseteq\ker(A)$.

which again is in fact a chain of equalities.

For every $v\in S$ with $|v|>0$, there exists a row $a$ of $A_{S}$ such that $\left\langle a,v\right\rangle>0$. To see this, suppose contradictorily that $A_{S}v\leq 0$. It cannot hold that $A_{S}v=0$, since $v\neq 0$ and $\ker(A_{S})\subseteq S^{\perp}$. this means $A_{S}v\leq 0$ and moreover $(A_{S}v)_{i}<0$ for some $i$. But since $A\bar{u}\leq 0$ and $A_{c}\bar{u}<0$, then for a sufficiently large $r>0$, $A(v+r\bar{u})\leq 0$ and $(A_{S}(v+r\bar{u}))_{j}<0$, which means row $j$ of $A_{S}$ should have been in $A_{c}$, a contradiction.

Consequently, $L\circ A$ has compact sublevel sets over $S$ (Hiriart-Urruty and Lemaréchal, 2001, Proposition B.3.2.4).

the final inequality since the minimization is of a continuous function over a compact set, thus attained at some point, and the infimand is positive over the domain. Consequently, $L\circ A$ is strongly convex over compact subsets of $S$.

Since $L\circ A$ is strongly convex over $S$ and moreover has bounded sublevel sets over $S$, it attains a unique optimum over $S$.

Appendix B Omitted proofs from Section 3

To start, note how the three key lemmas provided in the main text lead to a proof of Theorem 3.1.

Consequently, by the choice $z\mathrel{\mathop{\ordinarycolon}}=\bar{v}+\bar{u}(\nicefrac{{\ln(t)}}{{\gamma}}$ and Section 3,

To fill out the proof, first comes the smoothness-based risk guarantee.

(of Section 3) Define $r_{j}\mathrel{\mathop{\ordinarycolon}}=\eta_{j}(1-\beta\eta_{j}/2)$. For any $j$,

Summing this inequality over $i\in\mathinner{\left\{0,\ldots,t-1\right\}}$ and rearranging gives the bound. ∎

Define $\hat{\eta}\mathrel{\mathop{\ordinarycolon}}=\eta\mathcal{R}(w)$ and suppose $\hat{\eta}\leq 1$; then $\mathcal{R}(w^{\prime})\leq\mathcal{R}(w)$ and

Combining this, the choice of $\eta$, and Appendix B,

a contradiction. Therefore $\mathcal{R}(w^{\prime})\leq\mathcal{R}(w)$, which in turn implies

Together, these pieces prove the desired smoothness inequality.

(of Section 3) For any $j<t$, by Appendix B and the definition of $\gamma_{j}$,

Applying this recursively gives the bound.

Appendix C Omitted proofs from Section 4

This section will be split into subsections paralleling those in Section 4.

To start, the proof of the smoothness-based convergence guarantee, but with sensitivity to $A_{c}$.

(of Section 4.1) Fix any $u\in S^{\perp}$. Expanding the square,

the last inequality making use of smoothness, namely Section 3. Therefore

Applying $\sum_{j<t}$ to both sides and canceling terms yields

Proving Section 4.1 is now split into upper and lower bounds.

(of upper bound in Section 4.1) For a fixed $t\geq 1$, define

where the last inequality comes from Section 4.

Proceeding with this plan, first note (similarly to the main text)

(of lower bound in Section 4.1) First note

Combining these steps, and invoking Theorem 2.1,

C.2 Parameter convergence when separable

(of Theorem 4.1 when $A=A_{c}=A_{\perp}$ (separable case)) Let $0<\epsilon\leq 1$ be arbitrary, and select $t_{0}$ so that $\mathcal{R}(w_{t_{0}})\leq\epsilon/n$. By Section 3, since $\eta_{j}\leq 1$, the loss decreases at each step, and thus for any $t\geq t_{0}$, $\mathcal{R}(w_{t})\leq\epsilon/n$. Now let $t\geq t_{0}$ and $\mathcal{R}(w)\leq\mathcal{R}(w_{t})$ with arbitrary $t$ and $w$. By Section 4.2 and Section 3,

For $j\geq t_{0}$, by Section 4.2 and $\gamma=\min\mathinner{\left\{|A_{\perp}^{\top}q|\mathrel{\mathop{\ordinarycolon}}q\geq 0,\sum_{i}q=1\right\}}$ (cf. Theorem 2.1),

Invoking eq. C.1 and eq. C.2 with $w=w_{t}$ or $\bar{w}_{t}$ (notice that in both cases $|w|=|w_{t}|$) gives

Next, $\epsilon$ and $t_{0}$ are tuned as follows. First, set $\epsilon\mathrel{\mathop{\ordinarycolon}}=\min\{4/|w_{t}|,1\}$; this is possible if the corresponding $t_{0}\leq t$, or equivalently $\mathcal{R}(w_{t})\leq 4/n|w_{t}|$. This in turn is true as long as $t\geq 5$ and

because then $(\ln t)^{2}\geq 2$, and since $\gamma\leq 1$, $|w_{t}|\leq 4\ln t/\gamma^{2}$ given by Section 4.1, Theorem 3.1 gives

By Theorem 3.1, $\mathcal{R}(w_{t_{0}})\leq\epsilon/n$ if

By Section 4.1, $|w_{t_{0}}|\leq\mathcal{O}\left(\ln(n/\epsilon)\right)/\gamma^{2}$. Together with eq. C.3,

where the constants hidden in the $\mathcal{O}$ do not depend on the problem. Combining this with the lower and upper bounds on $|w_{t}|$ in Section 4.1,

C.3 Parameter convergence in general

For convenience in these proofs, define $v_{t}\mathrel{\mathop{\ordinarycolon}}=\Pi_{S}w_{t}$.

The general application of Fenchel-Young is as follows.

Next, the adjustment of Section 3 to upper bounding $\ln(\mathcal{R}(w_{t})-\bar{}\mathcal{R})$, which leads to an upper bound with $\gamma\gamma_{i}$ rather than $\gamma_{i}^{2}$, and the necessary cancellation.

(of Section 4.3) The first inequality implies the second via the same direct induction in Section 3, so consider the first inequality.

Making use of Appendices B and B and proceeding as in Appendix B,

Next it will be shown, by analyzing two cases, that

In the following, for notational simplicity let $w$ denote $w_{j}$.

Suppose $\mathcal{R}_{c}(w)<r\mathinner{\left(\mathcal{R}(w)-\bar{\mathcal{R}}\right)}$. Consequently,

Then, since $4\mathinner{\left(\mathcal{R}(w)-\bar{\mathcal{R}}\right)}\leq 2\lambda(1-r)$,

Otherwise, suppose $\mathcal{R}_{c}(w)\geq r\mathinner{\left(\mathcal{R}(w)-\bar{\mathcal{R}}\right)}$. Using an expression inspired by a general analysis of AdaBoost (Mukherjee et al., 2011, Lemma 16 of journal version), and introducing $(1-\epsilon)$ by invoking Section 4.2 as in the separable case,

Next, the proof of the intermediate inequality by combining Section 4.3 and Section 4.3.

(of Section 4.3) By Section 3, since $\eta_{j}\leq 1$, the loss decreases at each step, and thus for any $t\geq t_{0}$, $\mathcal{R}(w_{t})\leq\epsilon/n$. Combining Section 4.3 and Section 4.3,

The pieces are in place to prove parameter convergence in general.

(of general case in Theorem 4.1) The guarantee on $\bar{v}_{t}$ and the $A_{c}=\emptyset$ case have been discussed in Section 4, therefore assume $A_{c}\neq\emptyset$. The proof will proceed via invocation of the Fenchel-Young scheme in Section 4.3, applied to $w\in\{w_{t},\bar{w}_{t}\}$ since $\mathcal{R}(\bar{w}_{t})\leq\mathcal{R}(w_{t})$.

It is necessary to first control the warm start parameter $t_{0}$. Fix an arbitrary $\epsilon\in(0,1)$, set $r\mathrel{\mathop{\ordinarycolon}}=1-\nicefrac{{\epsilon}}{{3}}$, and let $t_{0}$ be large enough such that

By Theorem 3.1 and the choice of step sizes, it is enough to require

Therefore, choosing $t_{0}=\widetilde{\mathcal{O}}\left(\frac{n^{2}}{\epsilon^{2}}\right)$ suffices.

Invoking Section 4.3 with the above choice for $w\in\mathinner{\left\{w_{t},\bar{w}_{t}\right\}}$,

Suppose $t\geq 5$ and $\sqrt{t}/\ln^{3}t\geq n(1+R)/\gamma^{4}$, where $R=\sup_{j<t}|\Pi_{\perp}w_{j}-w_{j}|=\mathcal{O}(1)$ is introduced in Section 4.1. As will be shown momentarily, $t$ satisfies (C.6) with $\epsilon\leq\nicefrac{{C}}{{|w_{t}|}}$ for some constant $C$, and therefore this choice of $\epsilon$ can be plugged into (C.7). To see this, note that Theorem 3.1 gives

where the last line uses Section 4.1. It can be shown similarly that other parts of (C.6) hold.

Continuing with Equation C.7 but using $\epsilon\leq\nicefrac{{C}}{{|w_{t}|}}$ and upper bounding $|w_{t_{0}}|$ via Section 4.1,

Lastly, controlling the denominator with the lower bound on $|w_{t}|$ in Section 4.1,