High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise

It would be helpful to include a discussion after each theorem to compare the bound with existing clipping method bounds.

We had such discussions in the original version of the paper and expanded them in the revised version.

How would the proposed algorithm perform in the centralized composite optimization problem? Would it yield better convergence bounds compared to existing bounds?

To the best of our knowledge, the results for the distributed methods proposed in our work are the only existing ones under Assumption 2 (even if we take into account the in-expectation convergence results). In the special case of $\alpha = 2$, our results match the SOTA ones from [1,2] since parallelization with linear speed-up follows for free under the bounded variance assumption (if the clipping is applied after averaging as it should be in the parallelized version of methods from [1,2] to keep the analysis from [1,2] unchanged).

References:

[1] E. Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2106.05958, 2021.

[2] E. Gorbunov, M. Danilova, D. Dobre, P. Dvurechenskii, A. Gasnikov, and G. Gidel. Clipped stochastic methods for variational inequalities with heavy-tailed noise. NeurIPS 2022.

We want to thank the reviewer once again for the feedback. We addressed all the concerns and comments raised by the reviewer below.

The significance can be enhanced by clarifying the motivation and theoretical improvements of the new clipping method, such as providing theoretical analysis to illustrate the efficiency of this gradient update. The contribution can be strengthened by including a discussion that compares the derived bounds in this paper with existing gradient clipping results.

We provided the motivation behind the construction of the gradient updates in our methods in Section 2 (before Theorem 2.2). We also compared our results with the existing ones in Tables 1 and 2, and also provide discussions after each theorem that relate our results to the existing ones. We have expanded the discussions in the revised version.

Numerical experiments.

We conducted preliminary experiments showing the superiority of the shift idea over the naive approach, see the revised submission. In the experiments, we consider a simple problem: $\min_{x \in B_r(\hat{x})} f(x)$ where $r = 1$, $\hat{x} = (3,3,\dots,3)^{\top} \in \mathbb{R}^10$ and $f(x) = \frac{1}{2}\|x\|^2$, $f_{\xi}(x) = \frac{1}{2}\|x\|^2 +\langle \xi, x\rangle$, where $\xi$ comes from the symmetric Levy $\alpha$-stable distribution $\alpha = \frac{3}{2}$. We use the following parameters: $\gamma = 0.001$, $x^0 = \hat{x} + r \frac{e}{\|e\|}$, where $e = (1,1,\dots,1)^{\top}$. We tried three values of $\lambda$: $0.1$, $0.01$ and $0.001$.

In our numerical experiments, we observe that the naive Prox-clipped-SGD converges slower than Prox-clipped-SGD-star and Prox-clipped-SGD-shift. Moreover, when the clipping level is small Prox-clipped-SGD converges extremely slow, while Prox-clipped-SGD-shifts takes some time to learn the shift and then converges to much better accuracy. We also see that the smaller clipping level is, the better accuracy Prox-clipped-SGD-star achieves. For Prox-clipped-SGD-shift we observe the same phenomenon when we reduce $\lambda$ from $0.1$ to $0.01$ . We expect the improvement in the accuracy even further if we decrease the stepsizes $\gamma$ and $\nu$ .

The obtained experimental results are in good correspondence with our theoretical findings. Due to the time limitations, we managed to finish only these experiments. However, in the final version, we would like to add more experiments with large-scale problems as well as experiments with distributed methods. We also point out that our main contributions are mostly theoretical.

The motivation for considering both composite optimization and variational inequality problems is unclear. These two problems appear to be independent and weakly connected. The contribution of addressing two problems appears incremental.

Minimization problems and variational inequalities are quite strongly related, though have important differences. For example, convex minimization of differentiable function $f(x)$ is equivalent to variational inequality with $F(x) = \nabla f(x)$. Therefore, one cannot say that these problems are unrelated. Moreover, under (star-)cocoercivity the analysis of SGDA-type methods share a lot of similarities with SGD-type methods, motivating to consider both problems together.

However, minimization problems have a lot of differences with variational inequalities. For example, simple gradient method is not necessary convergent for monotone Lipschitz variational inequalities. This motivates us to consider Extragradient-type methods that are specific methods for variational inequalities (though can be applied to minimization problems as well). Next, acceleration is not possible in general for (strongly-) monotone variational inequalities. Therefore, to get a complete study in the case of minimization, it is not sufficient to consider only variational inequalities formulation.

Finally, both problem types are important and appear in various applications. Therefore, we find it crucial to consider both minimization and variational inequalities problems. Such consideration provides a wider picture and more complete study of high-probability convergence of stochastic methods.

Assumption 1.

We thank the reviewer for the suggestion. We clarified this assumption in the revised version.

We want to thank the reviewer once again for a very detailed review.

On non-triviality of the extension to the distributed case.

We thank the reviewer for an excellent question! To illustrate the difficulty of the extension to the distributed case and how we circumvent this, let us consider two straightforward extensions of clipped-SGD to the distributed setup. The first one has the following update rule:

$x^{k+1} = x^k - \gamma \text{clip}\left( \frac{1}{n}\sum\limits_{i=1}^n \nabla f_{\xi_i^k}(x^k), \lambda_k\right).$

Then, one can apply the existing results for clipped-SGD (e.g., from [1] or [2]) under bounded $\alpha$-th moment assumption, but in this case, one needs to estimate constant $\sigma$ for $\frac{1}{n}\sum\limits_{i=1}^n \nabla f_{\xi_i^k}(x^k)$. If individual stochastic gradients $\nabla f_{\xi_i^k}(x^k)$ satisfy Assumption 1 with parameter $\sigma$, then $\frac{1}{n}\sum\limits_{i=1}^n \nabla f_{\xi_i^k}(x^k)$ also satisfies Assumption 1 with parameter $\sigma$. However, if we use this estimate, we will not get $\frac{1}{n}$ dependence of the statistical term in the complexity bound. Instead, one can apply Lemma 7 from [3], implying that $\frac{1}{n}\sum\limits_{i=1}^n \nabla f_{\xi_i^k}(x^k)$ satisfies Assumption 1 with parameter $\frac{2^{2-\alpha}d^{\frac{1}{\alpha}-\frac{1}{2}}\sigma}{n^{\frac{\alpha-1}{\alpha}}}$, where $d$ is the dimension of the problem. This approach leads to $\frac{1}{n}$ dependence on $n$ of the statistical term in the complexity, but it gives an additional factor of $d^{\frac{1}{\alpha-1} - \frac{\alpha}{2(\alpha-1)}}$ in the same term, i.e., the final bound becomes dimension-dependent, which is problematic for large-scale problems. Moreover, even for small dimensional heavy-tailed problems with $d = 1000$ and $\alpha = \frac{7}{6}$, this factor is $1000^{6 - \frac{7}{3}} > 1000^3 = 10^9$, which is a huge number.

The second straightforward extension of clipped-SGD to the distributed case has the following update rule:

$x^{k+1} = x^k - \gamma \frac{1}{n}\sum\limits_{i=1}^n \text{clip}\left(\nabla f_{\xi_i^k}(x^k), \lambda_k\right).$

In contrast to the first option, this version uses clipping and averaging in different order: it applies clipping first to the stochastic gradients on the workers and then averages the results from the workers. This method is a special case of our DProx-clipped-SGD-shift for $\Psi \equiv 0$ (unconstrained minimization), $\nu = 0$ and $h_1^0 = \ldots = h_n^0 = 0$ for all workers (no shifts). In particular, as we explain in the paper, for convex problems shifts are not needed for clipped-SGD to get our results. However, our proof significantly differs from the ones from [1, 2] even in this case: due to the distributed nature of the problem, we need to estimate new sums that do not have analogs in the non-distributed case. In particular, sum 6 from inequality (96) is completely new and requires a separate induction to estimate it (see the part of the proof after inequality (120)). This causes some extra technical challenges that do not appear in the non-distributed setup. We also point out that to achieve our results, we increased the clipping level $n$ times (see the motivation for this change in Appendix B after Lemma B.2). This change in the clipping level was not obvious beforehand. Moreover, this change also complicates the estimation of the sum 6 from inequality (96): if we apply Bernstein’s inequality directly to this sum, we will get that the summands are bounded by $\frac{8\gamma^2\lambda_l^2}{n} \sim n$ that leads to $n$-times worse bound than needed to achieve the desired result.

Moreover, since in the non-distributed unconstrained case, the existing high-probability results for clipped-SGD under (quasi-)strong convexity assumption use a decreasing clipping level, it is natural to use a decreasing clipping level for the distributed case as well under the same assumption. However, this leads to another problem: when $\lambda$ is small enough, the method described above cannot converge with constant stepsize even without any stochasticity. Indeed, since $\frac{1}{n}\sum_{i=1}^n \text{clip}(\nabla f_i(x^\ast), \lambda) \neq 0$ in general for small enough $\lambda$, the method does not have a fixed-point property, i.e., $x^\ast \neq x^\ast - \gamma \frac{1}{n}\sum_{i=1}^n \text{clip}(\nabla f_i(x^\ast), \lambda)$ in general. This necessitates decreasing stepsize $\gamma$ to achieve a predefined accuracy of the solution and leads to worse rates of convergence. The same issue is present in the case of accelerated methods since known results for clipped accelerated methods also use decreasing clipping levels [1].

We circumvent these issues by using properly constructed shifts $h_i^k$ that aim to learn $\nabla f_i(x^k)$. This idea was not presented in previous works on high-probability analysis and it is the key component of our methods.

We incorporated the above remarks into the paper.

On the logarithmic factors.

Since in this paper, we do not focus on improving the dependencies on $\varepsilon$ and $\delta$ under the logarithms, we have slightly worse logarithmic factors than in the results from [2], where a very particular case of non-distributed convex optimization is considered. In the appendices of the original submission, we provide the complete formulations of all results (including explicit dependencies on the logarithmic factors). In particular, in the case of DProx-clipped-SGD-shift, for convex problems the logarithmic factor in the complexity bound is given in (83) and equals $\log\left(\frac{1}{\beta}\left(\frac{\sigma \sqrt{V}}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}}\right)$ in front of the leading term, while the corresponding factor in complexity bound from [2] equals $\log\frac{1}{\beta}$. In particular, for $\alpha = \frac{3}{2}$, $\varepsilon = 10^{-6}$, $\delta = 10^{-6}$, $\sigma = 10^3$, $V = 10^6$ our logarithmic factor is $\approx 97$, while the one from [2] is $\approx 14$, i.e., it is just about $7$ times less, which is a minor difference, though the improvement of logarithmic factors is an important theoretical contribution (requiring some important changes in the analysis). Moreover, the result of [2] applies only to one of the many settings where our results hold.

On the structure of the proofs.

We have added a section to the main text that should help the readers to understand the proofs and navigate through them better.

Paper length and results for variational inequalities.

Following the reviewer’s request, we have improved the readability of the paper as follows: we moved all the results and discussions on the methods for solving variational inequalities to the appendix. We use the extra space in the main part to better explain our proofs and techniques.

References:

[1] Sadiev et al. High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. ICML 2023

[2] Nguen et al. Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv preprint arXiv:2304.01119. 2023.

[3] Wang et al. Convergence rates of stochastic gradient descent under infinite noise variance. NeurIPS 2021.

[4] Minsker, S. (2015). Geometric median and robust estimation in Banach spaces. Bernoulli, 21(4), 2308.

Readability of the results and, in particular, Theorem 2.2.

We thank the reviewer for the suggestion. To improve readability, we have split Theorem 2.2 into two parts (quasi-strongly convex case and convex case). These results are simplifications of the full statements provided in the appendix. We also show these results in Table 1 that can be considered as a simplified summary of the results obtained for minimization problems. We also added more technical details regarding the role of shifts to the main part of the paper (the intuitive explanation was also expanded). We hope that in the revised version of our paper, Theorem 2.2 (and other theorems) and technical details are clearer than before. If Reviewer Da4b has any further suggestions about improving the readability, we will be happy to incorporate them into the paper.

On the assumptions and boundedness of the iterates.

We have added to the revised version of the paper more explanations regarding our assumptions and more explanations on why it is sufficient to make our main assumtions only on a compact set. We emphasize that we do not need to assume the boundedness of the domain of the original problem.

Different constants to the ones from the results by Nguen et al. (2023).

After an additional examination of the results from [2], we found out that the correct dependence on $R$ is a bit more involved than we presented in Table 1. In the revised version, we have corrected it. The second term in the complexity bound for Clipped-SMD from [2] remains unchanged, while the first term depends on $\hat R^2 = R\left(2R + \|\hat x - x^\ast\| + \frac{\eta \sigma + \|\hat g\|}{L}\right)$, where $\hat x$ is some point from the domain, $\eta > 0$, and $\hat g$ is such that $\mathbb{P}\lbrace \| \hat g - \nabla f(\hat x) \| > \eta \sigma \rbrace \leq \epsilon$ for some $\epsilon \in (0,1)$, i.e., $\hat g$ is an estimate of $\nabla f(\hat x)$. The authors of [2] do not provide a particular suggestion of how to choose $\hat x$ in the general case. One reasonable choice is $\hat x = x^0$. Then, according to [4], it is sufficient to take $\mathcal{O}(\log \frac{1}{\epsilon})$ samples and compute a geometric median of them. In this case, the constants in the bound from [2] become equivalent to our constants (up to logarithmic factors) if $\gamma$ is chosen smaller than $\frac{\|x^0 - x^\ast\|}{\|\nabla f(x^\ast)\|}$. We have clarified this part in the revised version.

On the uniqueness of the solution.

We thank the reviewer for very good questions. In fact, we use the uniqueness of the solution only to make Assumptions~2, 4, 7, and 8 easier. We reformulated these assumptions to avoid the uniqueness of the solution in the revised version of the paper. Our proofs and results remain unchanged, and, in the definitions of constants $V$ and $M$ for DProx-clipped-SGD-shift and DProx-clipped-SSTM-shift, one can use the closest solution $x^\ast$ to the starting point $x^0$. We also emphasize that the authors of [2] do not consider quasi-strong convexity/quasi-convexity assumptions or refined smoothness assumptions like Assumption 2. Under standard smoothness and (strong) convexity assumptions, our proofs also do not require the uniqueness of the solution.

Zero-gradient in the accelerated result from Nguen et al. (2023) and comparison with our results.

When $\nabla f(x^\ast) = 0$ and $n = 1$, constants $M$ and $R$ are identical. Therefore, our result recovers the one from [2] as a special case. Next, as we explain above, we do not require the uniqueness of the solution under standard convexity and smoothness and also do not require the uniqueness of the solution at all in the revised version of our submission. This means that our results for the accelerated method are strictly more general than the corresponding ones from [2].

Unfortunately, the submitted review is not about our paper. In particular, the reviewer claims

The article introduces a class of soft clipping schemes

The numerical experiments in this paper are beautiful which shows that soft-clipping algorithms may offer regularization benefits in cases where other algorithms tend to overfit, encouraging the use of soft-clipping algorithms and further research in the field

Especially for the symbols $\w_k(w)$ without interpretation in Corollary 2, it’s hard for readers to understand and what insight the corollary hopes to provide.

Is it reasonable to assume that $\sum_{k=1}^\infty \alpha_k^2 < \infty$ and $\sum_{k=1}^\infty \alpha_k = \infty$ as stated in Theorem 1?

In fact, we do not introduce soft clipping schemes and do not study them in our work. In contrast, we use the standard gradient clipping and introduce new algorithms for composite and distributed problems and derive high-probability convergence results for them. Next, our paper does not have numerical experiments. We also do not have Corollary 2, symbols $\w_k(w)$, Theorem 1, and conditions $\sum_{k=1}^\infty \alpha_k^2 < \infty$ and $\sum_{k=1}^\infty \alpha_k = \infty$ mentioned in the review.

All of these aspects show that the review is written for a different paper and is unrelated to our work.

[1] Liu, Zijian, et al. "High probability convergence of stochastic gradient methods." International Conference on Machine Learning. PMLR, 2023.

[2] Li, Xiaoyu, and Francesco Orabona. "A high probability analysis of adaptive sgd with momentum." arXiv preprint arXiv:2007.14294 (2020).

[3] Cutkosky, Ashok, and Harsh Mehta. "High-probability bounds for non-convex stochastic optimization with heavy tails." Advances in Neural Information Processing Systems 34 (2021)

[4] Sadiev, Abdurakhmon, et al. "High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance." (2023).

[5] Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4), 1574-1609.

[6] Ghadimi, S., & Lan, G. (2012). Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4), 1469-1492.

[7] Nemirovskij, A. S., & Yudin, D. B. (1983). Problem complexity and method efficiency in optimization.

[8] Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., & Sra, S. (2020). Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33, 15383-15393.

[9] S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4), 1469-1492. 2012.

[10] S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4), 2061-2089. 2013.

[11] Sadiev et al. High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. ICML 2023.

[12] Nguen et al. Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv:2302.05437. 2023.

[13] Wang et al. Convergence rates of stochastic gradient descent under infinite noise variance. NeurIPS 2021.

The technical contribution is limited. The author uses gradient clipping to handle the $\alpha$-th moment, which is frequently used in recent papers. The $\alpha$-th moment condition is also widely studied. Combining the technique in gradient clipping and the technique in distributed composite minimization/distributed composite VIPs, most of the results in this paper are easily obtained.

What are the technical innovations of this paper compared to existing works? This paper seems to be a simple combination of existing techniques in related works

We politely disagree with the reviewer. Our contributions go far from just combining known techniques, though even a proper combination of existing techniques is not always obvious beforehand while the reviewer is trying to claim the opposite.

Before we elaborate on the technical difficulties in the extensions, we would like to discuss the algorithms’ design. Having a goal in mind of proper extension of the results from [11] to the composite and distributed problems, we were trying to use “Occam’s razor” principle: we did not want to change the existing technique without the necessity of doing it. In particular, we did not want to change the existing algorithms just for the sake of developing new methods and having different analyses. For example, in our opinion, Prox-clipped-SGD-star has a minor but extremely important difference from just Prox-clipped-SGD. Due to this visually tiny algorithmic difference, the analysis of Prox-clipped-SGD-star in the composite case is almost the same as the analysis of clipped-SGD in the unconstrained (non-composite) case. We believe that this idea is non-trivial beforehand. Our claim is justified by the fact the previous works (like [12]) also study constrained problems but do not achieve similar results in the strongly convex case and do not get the acceleration without an extra restrictive assumption that $\nabla f(x^\ast) = 0$.

Next, to get practical methods, we made an extra step forward and replaced $\nabla f(x^\ast)$ with a learnable shift $h^k$ and also generalized the method to the distributed setup. This is the moment when noticeable technical difficulties arise. First of all, we introduce a Lyapunov function to control not only the proximity of $x^k$ to $x^\ast$ but also the quality of shifts (see line 240). In the (quasi-) strongly (monotone) convex case, this leads to the need to estimate $\|\| h_i^{k+1} - h_i^\ast \|\|^2$ and also to apply Lemma B.2 we have to estimate $\|\| F_i(x^k) - h_i^k \|\|$ and connect it to the Lyapunov function and the clipping level (see inequality (200)). This leads to the non-trivial interplay between the coefficient in the second term in the Lyapunov function, the number of workers $n$, and the clipping level $\lambda_t$ that we also need to change (increase $n$ times) compared to the non-distributed case, see the discussion after Lemma B.3. Moreover, since the clipping level is $n$ times larger, we need to be very careful in the analysis of the sums like the ones appearing in (96), especially with sum (6) from inequality (96). We emphasize that they do not appear in the non-distributed case.

Nevertheless, we circumvented all of these difficulties and managed to obtain a linear speed-up in the distributed case, and in the composite non-distributed case, we managed to obtain direct analogs of the results from [11] obtained for the unconstrained problems without any sacrifice in the complexities. That is, for the first time in the literature, we achieve $1/n$ dependence in the statistical term (the one depending on $\sigma$) of our complexity bounds under bounded central $\alpha$-th moment assumption. Let us elaborate on the non-triviality of achieving $1/n$ factor. When $\alpha = 2$, the result is standard since the variance of the average of independent random variables scales as $1/n$, and one can simply replace $\sigma^2$ with $\sigma^2/n$. This is a key property of mini-batching in stochastic optimization. However, there are no dimension-independent analogs of this result in the literature for the case of $\alpha < 2$. The only result we are aware of is given in Lemma 7 from [13], and it has an extra factor of $d^{1-\frac{\alpha}{2}}$, where $d$ is the dimension of the problem. For huge-scale problems, this factor can be large even for $\alpha \approx 3/2$. In contrast, our rates are dimension-independent.

Although the reviewer silently replaced their review just two days before the deadline, we addressed all the comments by this reviewer. Our general response and responses below justify that Reviewer LB8P provided a review of extremely low quality.

High probability bounds do not bring some technical challenges than the in-expectation ones. After establishing the martingale difference sequences, the Freedman’s inequality is enough to give a high probability bound. In this line, there are numerous papers in recent years.

We politely disagree with the reviewer. We have multiple solid arguments justifying that deriving high-probability bounds is, in general, more challenging than obtaining in-expectation ones.

First of all, a large body of the optimization community has acknowledged the importance, interest, and difficulty to get high-probability convergence guarantees [1,2,3]. For instance, we can explicitly quote [1]:

high probability guarantees are significantly harder to obtain and they hold in more limited settings with stronger assumptions on the problem settings and the stochastic noise distribution.

to illustrate our point that high-probability convergence guarantees bring new challenges in contrast to in expectation proofs. We now develop the reasons behind this statement.

Argument 1: proofs in expectation are usually simpler. To prove in-expectation results, it is not needed to recursively upper-bound the distance to the solution/norm of the gradient of the objective: one can just take expectations and get rid of sums of inner product terms using unbiasedness (e.g., in the case of SGD / Accelerated SGD under bounded variance assumption, see [9]). Conversely, to apply Bernstein-Freedman, one needs either to assume that the problem is defined on a compact, which does not allow to consider an important class of unconstrained minimization problems, or to recursively bound the distance to the solution with high probability.

Argument 2: necessary additional assumption for convergence with high probability for standard methods. In many previous works on SGD, the high-probability analysis requires an additional assumption in comparison to in-expectation analysis: sub-Gaussian noise assumption [5,6]. This is not an artifact of the analysis – it is, in general, impossible to show good high-probability convergence for SGD; see Theorem 2.1 in [4]

Argument 3: the large gap in time between in-expectation results and high-probability ones is evidence of non-triviality. If high-probability analysis was that trivial to obtain, it would be done much earlier since Assumption 1.1 was known 40 years ago – in 1983, the first in-expectation results were already obtained in [7]. Next, in the non-convex case, the first in-expectation analysis appeared in December 2019 (the first version of [7]), but the first high-probability analysis appeared only in June 2021 [3] (then appeared in NeurIPS 2021; this fact indicates the importance of the problem for the community) and this analysis relies on the additional assumption and is also given for much more sophisticated method than clipped-SGD. If the extension was trivial, it would not require 1.5 years and many changes in the algorithm.