Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

We thank the reviewer for the meticulous review and are incredibly grateful for the reviewer's effort in finding typos. We have fixed the typos and hope that they do not overshadow our core contributions: providing the tight lower bound for uniformly convex and high-order Hölder smooth functions. We sincerely hope that the reviewer can kindly consider raising the score if the following helps address some of the concerns.

The main issue for me that causes confusion in section 4 ... omitting $p$. I was wondering if there was a reason for this, as it is not discussed and in this setting $p \geq 1$, therefore for me it is not trivial to remove it.

This is just a typo and we have added $p$ back throughout the derivation. We would kindly note that even though $p \geq 1$, it is nevertheless a constant and does not affect the order of our lower bound. That is, we indeed provide the tight lower bound in the $q > p + \nu$ setting.

Line 783, Line 230, Line 934, Line 293, Line 296, Line 317, Line 1011, 1019

For lines 783, 230, 934, 293, 296, and 1011, we have fixed these typos. For line 1019, we have added the reference to Lemma 3 (ii). For line 317, we are indeed referring to Lemma 14 (i) in which the gradient of the smoothed function is explicitly defined.

For Section 5, I only have one question. Concerning lines 402,403, what do you mean by scaling of $\tilde{f}$ and how does this imply directly that all of the properties of $\tilde{f}$ translate to properties of $f$. This seems a little bit informal to me.

By definition, $f$ is a scaling and rotation of $\tilde{f}$. Specifically, for $\mathbf{v}\_1, \cdots, \mathbf{v}\_{\tilde{T}}$, we can write for $V = [\mathbf{v}\_1, \cdots, \mathbf{v}\_{\tilde{T}}]$, $f(\mathbf{x}) = \frac{H}{2^{p+\nu+1} (p+\nu-1)!}\tilde{f}(V\mathbf{x})$, where $V$ is an orthonormal matrix. Therefore, the properties of $\tilde{f}$ translate to properties of $f$ with different constants. This is the same trick applied in [Arjevani et al. 2019], e.g., Eq. (10), Eq. (21).

Missing citation

We thank the reviewer for pointing us to related papers. While we focus on the deterministic setting, we have also included this reference.

As written, the proofs hold for deterministic algorithms. The authors do not discuss what is the algorithm class their lower bound holds for, and specifically I believe their results hold for deterministic (or more generally, zero-respecting) algorithms.

We thank the reviewer for pointing this out. Indeed we consider deterministic algorithms in this paper. We have now specified the algorithm class in Theorem 1 and 2. We also thank the reviewer for bringing up the adaptability to randomized algorithms. We will add relevant discussion in the revised version, and omit for now to keep the line number consistent.

What seems to be preventing a lower bound for the symmetric $q = p+\nu$ case? Why do both proof techniques break? It would be great if the authors discuss this in the paper.

We thank the reviewer for expressing interest in our future work. Here we briefly elaborate on the challenges lying ahead in this direction. In the $q=p+\nu$ case, one would expect a linear convergence rate of $\Omega\left(\left(\frac{H}{\sigma}\right)^\frac{2}{3(p+\nu)-2} \log \left(\frac{1}{\epsilon}\right)\right)$ according to the high-order upper bound in [Song et. al., 2022], as well as the first-order lower bound $\Omega\left(\left(\frac{H}{\sigma}\right)^\frac{1}{2} \log \left(\frac{1}{\epsilon}\right)\right)$ [Nesterov, 2018, Section 2.1.4.] when $p=1$ and $\nu=1$. The asymmetric cases do not naturally yield a linear rate when $q=p+\nu$. On top of achieving linear convergence, one would also expect a tight dependence on the condition number, e.g., $\sqrt{\frac{H}{\sigma}}$ in the first-order setting. Such a result, i.e., the factor $\sqrt{\frac{H}{\sigma}}$, is derived from solving a quadratic equation with the closed-form quadratic formula, as demonstrated in Eq. (2.1.33) Section 2.1.4. in [Nesterov, 2018]. Yet in high-order scenarios, the natural extension would involve solving a high-ordered equation, for which there is no closed-form formula. As a result, we are in the process of searching for alternative ways to derive the linear convergence lower bound for the $q=p+\nu$ case with a tight dependence on the condition number.

Minor comments

We have added the word "operator", and the $L$-Lipschitzness is assumed at the beginning of Lemma 1.

We thank the reviewers for acknowledging our contributions. Here we provide further clarifications to address the reviewer's questions and concerns.

One might argue that there isn't much technical novelty, as the two lower bound constructions are adaptations of previous know lower bounds (essentially the Nemirovski function and the Nesterov function), with relatively similar analyses to prior works. Personally, I do not think this should prevent acceptance, as the authors explain what are the key differences, and the optimization community would benefit from these lower bounds being published.

We appreciate the reviewer for acknowledging our differences and novelties, as we believe that the Nemirovski function and the Nesterov function serve more as general frameworks for proving lower bounds, and numerous papers on lower bounds in various settings (e.g., deterministic and stochastic, first-order and high-order, etc.) build on these constructions. It is the specific techniques applied along the way that allow for achieving tight results under different settings, e.g., in our $q>p+\nu$ case, the application of the newly proposed truncated Gaussian smoothing, the choice of $\ell\_\infty$ truncation, and proving its smoothing properties in Lemma 1, which we believe is technically non-trivial.

In line 168 it is argued that Gaussian smoothing is dim-free, whereas uniform (over an l2 ball) is not. I believe this might be wrong, since they are essentially the same. Gaussian smoothing is nearly the same as uniform smoothing over an l2 ball with radius $\sqrt{d}$, since the distributions are nearly the same by concentration of measure. So it's just that the authors seem to be comparing a $\delta$-approximation smoothing to a $\delta\sqrt{d}$-approximation, which clearly wouldn't have the same smoothing parameters. Is this the case, or am I missing something? Similarly, I believe the same is true for softmax smoothing, which isn't really dim-free since the approximation parameter has a $\log d$ factor. So making is $\delta$-approximate would mean that the smoothness constant is $\log d / \delta$, no? This is a milder logarithmic dependence as opposed to polynomial, but still not entirely dim-free.

We would kindly note that we are not saying uniform smoothing over any $\ell\_2$-ball is dimension-dependent, but over a unit $\ell\_2$-ball (in lines 161 to 163), that is, a $\ell\_2$-ball with radius 1, in contrast to the radius $\sqrt{d}$ the reviewer proposed. Indeed, uniform smoothing over an $\ell\_2$-ball with radius $\sqrt{d}$ is also dimension-free by setting $u=\sqrt{d}$ in Lemma 8 of [Duchi et. al. 2012], which justifies why Gaussian smoothing is also dimension-free. And by "dimension-free", we mean exactly that there is not a $d$ factor in the smoothness constants in Lemma 9 of [Duchi et. al. 2012] with $u$ not dependent on $d$ or Theorem 7 of [Bullins 2020] with $\mu$ not dependent on $d$. Furthermore, the $\delta$ in our paper measures the radius of the local region, i.e., $\Vert\mathbf{x} - \mathbf{x}_s\Vert \leq \frac{\delta}{2}$ in lines 300-301, not the approximation error of $g(\mathbf{x}) - G(\mathbf{x})$ in lines 233-234 Lemma 3 (ii).

Nevertheless, we agree that there is a connection between the approximation and the smoothness constant, where one can move the $d$ in the smoothness constant to approximation error by controlling the degree of smoothing, e.g., as the reviewer pointed out, for softmax smoothing, by setting the $\mu = \frac{1}{\log d}$ in Theorem 7 of [Bullins 2020], the approximation error $f(\mathbf{x}) \leq f^{softmax}(\mathbf{x}) \leq f(\mathbf{x}) + p\mu \log d$ reduces to a constant $p \mu \log d = p$ whereas the smoothness constant becomes $d$-dependent. With that said, we regard the parameter controlling the degree of smoothing as a constant parameter to begin with in this paper.

In addition, the question raised by the reviewer has led the authors to further examine whether uniform smoothing within an $\ell\_2$-ball with radius $\sqrt{d}$ would work, e.g., Lemma 8 of [Duchi et. al. 2012] is identical to our Lemma 14 if $u = \sqrt{d}$. The answer is negative because the radius of the local region would then be $d$-dependent, i.e., $\Vert \mathbf{x} - \mathbf{x}_s \Vert\_2 \leq 2\sqrt{d}$ in lines 300-301. This is where the $\delta$ in lines 300-301 becomes $d$-dependent, (instead of the approximation error the reviewer referred to) and breaks the derivation there.

We thank the reviewer for acknowledging our contributions and providing constructive comments. To further address the reviewer's comments, we would like to clarify and justify the differences between our work and previous works.

The construction of the hard instances, although novel (e.g. using the truncated Gaussian for the smooth), inherits some ideas used previously. For instance, the function in line 218 - line 220 is also used in [1].

While the reviewer has rightfully pointed out that [1] follows similar initial steps to construct a hard function, we would kindly note that such construction serves more as a general framework for proving lower bounds, and is adopted not only in [1] but also in [2-4] for results under a wide variety of problem settings, and even dates back to earlier works [5]. Though this framework is quite important in general for proving lower bounds, it is the specific techniques applied along the way of construction that allow for achieving tight results under different settings, e.g., in our $q>p+\nu$ case, the application of the newly proposed truncated Gaussian smoothing. The choice of $\ell\_\infty$ truncation as well as proving its smoothing properties in Lemma 1, as we believe, is fairly mathematically involved and technically non-trivial. We have briefly summarized the above in lines 137-143, and are happy to further highlight our novelties in the revised version.

Questions: Is the norm in (in line 201 and many other places) the operator norm?

Yes. We have further specified in Section 3 line 110 that $\Vert \cdot \Vert$ denotes $\ell\_2$ operator norm.

References:

[1] Nikita Doikov. Lower complexity bounds for minimizing regularized functions. arXiv preprint arXiv:2202.04545, 2022.

[2] Crist ´obal Guzm ´an and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1–14, 2015.

[3] Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Conference On Learning Theory, pp. 774–792. PMLR, 2018.

[4] Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-optimal lower bounds for convex optimization for all orders of smoothness. Advances in Neural Information Processing Systems, 34:29874–29884, 2021.

[5] Arkaddii S Nemirovskii and Yu E Nesterov. Optimal methods of smooth convex minimization. USSR Computational Mathematics and Mathematical Physics, 25(2):21–30, 1985.

We thank the reviewer for acknowledging our contributions and expressing interest in our future work on the $q=p+\nu$ case. Here we briefly elaborate on the challenges lying ahead in this direction. In the $q=p+\nu$ case, one would expect a linear convergence rate of $\Omega\left(\left(\frac{H}{\sigma}\right)^\frac{2}{3(p+\nu)-2} \log \left(\frac{1}{\epsilon}\right)\right)$ according to the high-order upper bound in [Song et. al., 2021], as well as the first-order lower bound $\Omega\left(\left(\frac{H}{\sigma}\right)^\frac{1}{2} \log \left(\frac{1}{\epsilon}\right)\right)$ [Nesterov, 2018, Section 2.1.4.] when $p=1$ and $\nu=1$. On top of achieving linear convergence, one would also expect a tight dependence on the condition number, e.g., $\sqrt{\frac{H}{\sigma}}$ in the first-order setting. Such a result, i.e., the factor $\sqrt{\frac{H}{\sigma}}$, is derived from solving a quadratic equation with the closed-form quadratic formula, as demonstrated in Eq. (2.1.33) Section 2.1.4. in [Nesterov, 2018]. Yet in high-order scenarios, the natural extension would involve solving a high-ordered equation, for which there is no closed-form formula. As a result, we are in the process of searching for alternative ways to derive the linear convergence lower bound for the $q=p+\nu$ case with a tight dependence on the condition number. We will incorporate the discussion in the revised version and omit it for now to keep the line number consistent.

References:

Song et. al. Unified acceleration of high-order algorithms under general holder continuity. SIAM Journal on Optimization, 2022

Nesterov, Yurii. Lectures on convex optimization. 2018.