Weaknesses
$\underline{\text{General remarks}}$:
- First, I would like to make a somewhat subjective statement about the class: in my humble opinion, it seems a bit flawed as it does not respect fundamental homogeneity properties. Let me explain:
Let $f\in\mathcal{F}_{\ell}$ the class of $\ell$-smooth functions. For $\alpha, \lambda > 0$, define $g$ as $g(x)=\frac{\alpha}{\lambda^2}f(\lambda x)$ (assume wlog that their minimum is in 0, otherwise translate $f$, then create $g$).
We verify $\nabla g(x)=\frac{\alpha}{\lambda}\nabla f(\lambda x)$ and $\nabla^2 g(x)=\alpha\nabla^2 f(\lambda x)$,
hence $\|\nabla^2 g(x)\| = \|\alpha\nabla^2 f(\lambda x)\| \leq \alpha \ell( \|\nabla f(\lambda x)\|) = \alpha \ell( \frac{\lambda}{\alpha}\|\nabla g(x)\|)$.
Finally, $g\in\mathcal{F}_{\alpha \ell(\frac{\lambda}{\alpha} .)}$.
Let us assume that after some analysis of an algorithm like GD (this reasoning also applies to momentum), we find out that the step-size that achieves the best worst-case guarantee on the class $\mathcal{F}_{\ell}$ is $\gamma_{\ell}$.
Then, if I need to optimize $f$, I will use $x_{t+1} = x_t - \gamma_{\ell} \nabla f (x_t)$.
Now, instead I minimize $g$, I will use $x_{t+1} = x_t - \gamma_{\alpha \ell(\frac{\lambda}{\alpha} .)} \nabla g (x_t) = x_t - \gamma_{\alpha \ell(\frac{\lambda}{\alpha} .)} \frac{\alpha}{\lambda}\nabla f(\lambda x_t)$.
Note that $f$ and $g$ have the same minimum and if we introduce the iterates $y_t = \lambda x_t$, we have
$x_{t+1} = x_t - \gamma_{\ell} \nabla f (x_t)$ when minimizing $f$,
and
$y_{t+1} = y_t - \gamma_{\alpha \ell(\frac{\lambda}{\alpha} .)} \alpha\nabla f(y_t)$ when minimizing $g$.
In short, we need to have $\gamma_{\ell} = \alpha \gamma_{\alpha \ell(\frac{\lambda}{\alpha} .)}$, or again $ \gamma_{\alpha \ell(\frac{\lambda}{\alpha} .)} = \frac{\gamma_{\ell}}{\alpha}$.
Indeed, they both optimize their dynamics.
This shows that $\lambda$ has no impact on the optimal way to tune an algorithm. And we can stretch the function $\ell$ as much as we want and notice that probably only $\ell(0)$ matters, i.e. the smoothness constant in the optimum.
In particular, applied to the case where $\ell(x) = L_0 + L_1x$, it is clear that the optimal parameter cannot depends on $L_1$.
This observation is explained by the lack of homogeneity in the formula: when scaling a function, only $L_0$ is scaled, not $L_1.$
In $L$-smooth class, the worst-case function generally do not belong to the $L-\varepsilon$-smooth class. Hence there is a hierarchy of the classes, but here, it seems that by scaling a function, the worst-case dynamics does not depend on some part of the class definition, leading to useless specification.
This point can be further discussed. This is just some thoughts I had based on the class definition which I never used and I am aware from the related works section that some people are working with it. Thus I would be happy if authors could discuss this point.
However, based on this remark, my first guess was that the analysis would basically lead as the same analysis as when $\ell$ is constant, or $L_1=0$, which leads to my next point.
- Second, we indeed recover classical analyses everywhere in this paper. There indeed is an additional argument, that is the sequence of iterate stays in a compact and by regularity of $f$, we can bound the gradients, hence the hessians and conclude with all the classical analyses.
Indeed:
- Th4.2 and 4.3 use classical Lyap analyses.
- Lemma 4.1:
Using cocoercivity, authors prove $\|\nabla f(x_t)\|$ is decreasing.
Using the same proof, one could have that $\|x_t-x_\star\|$ is decreasing as well. And using descent lemma, we have that $f(x_t)$ is also decreasing.
Finally, we can prove the descent lemma without assumption of $\ell$-smoothness by just assuming the continuity of the hessian, and taking G as upper bound of $\lbrace \|\nabla^2 f(x)\| | x\in\mathcal{X} \text{ and } f(x)\leq f(x_0) \rbrace$ which is assumed to be a compact since authors assume that the function tends to infinity on the border of $\mathcal{X}$. We have the revisited descent lemma: $f(x_{t+1}) \leq f(x_t) - \eta\|\nabla f(x_t)\|^2 + \frac{1}{2}\eta^2 G \|\nabla f(x_t)\|^2$, and by taking $\eta$ sufficiently small, we insure in 1 calculus that
- 1) $f(x_t)$ is decreasing and that all the hessians keep being smaller than $G$.
- 2) the squared gradients are sommable, hence the classical complexity $O(1/\varepsilon^2)$ that is as in thm5.1, obtained in a much simpler way.
Of course, here we only assumed the hessian to be bounded, so $\ell$-smoothness + bounded gradients do the job.
In conclusion, in my opinion, most of the results are almost straightforward from what is known in the literature.
- Third, in my opinion, the stochastic assumption A4 is too strong. I am aware authors claim that some works in the literature assume even stronger assumption, but A4 is way too strong: no multiplicative noise, only additive. This paper claims generalizing smoothness, but linear regressions with MSE losses are not even covered by the section 5.2.
Plus, bounded variance are too easy to handle in general and leads to an analysis close the deterministic case.
Instead, authors should consider expected smoothness (or its equivalent in $\ell$-smoothness). Actually, under the assumption that there is a finite number of functions under consideration, I would guess we could generalize the same arguments as in the deterministic case to ensure all the hessians to be bounded on the optimization iterates and basically use classical SGD proof in the smooth case.
$~$
$\underline{\text{Minor}}$:
- Clarity:
- Assumption 1: First recall definition of « closed function »
- Also define « sub-quadratic »
- l.468: It took me a while to find where this proof was. Please do as for other propositions: state it right before the proof. In a general way, please state all theorems right before their proofs if reported in appendix. Use the « restatable » latex package too avoid renumbering.
- Proof of lemma B1: From convexity and local smoothness, authors apply the $\underline{\text{descent lemma}}$ on the $\underline{\text{Bregman divergence}}$ of the objective function to obtain local $\underline{\text{cocoercivity}}$. The proof is the same as for global smoothness. Yet, for completness and care of the neighborhood needed to obtain the cocoercivity, I understand that the proof is provided. However, It needs a reference to this classical result in the global smooth case and mention of the 3 underlined terms when used.
- l.550: Cocoercivity
- l.553: Bregman divergences
- l.562: Descent Lemma
- l.560: please introduce y: « let y [as in the lemma statement] »
- l.248: « Theorem 5.1 gives the classical $O(1/T)$ rate, or $O(1/\varepsilon^2)$ gradient complexity » -> $O(1/\sqrt{T})$. Authors do not clearly state if they are talking here about gradient norm or its square, but they need to be consistent when talking about rate and complexity.
- Typos:
- l.2: "Lipshitzness" -> Lipschitz continuity.
- l.76: "strong convex" -> strongly convex
- l.79: $\nabla$ is missing
- l.144: « $x = x_2 = x_t$ » ? I guess "$x$" needs to be removed
- l.169: « accelearted » -> accelerated
- l.570: 1/L -> 2/L
- Misc:
- Table 1: missing hline + be precise on the meaning of « - ».
- Table 1: for GD non convex: « Inf or $\Omega$ … » could be summed up as « $\Omega$ … ».
- l.121-122: Put 2) under 1). It should not exceed the current number of lines.