Strengths:

• The proposed algorithm and its analysis seem to be novel and interesting, especially from the theoretical perspective.
• Some design choices (such as double sampling and the conservative configuration) are motivated by the theoretical analysis.

We thank the reviewer for their thoughtful and encouraging review. We are glad that the novelty of our ideas, as well as the theory-driven design choices, were found to be interesting.

Weaknesses:

• The theoretical analysis offers limited insight into the practical effectiveness of clipped SGD...
• The empirical performance of the proposed algorithm might be sensitive to the choices of stepsize and threshold, which depend on unknown problem-specific constants...

We indeed aim to position this paper as theoretical, focusing on the complexity of $(L_0,L_1)$-smooth optimization and how proper clipping helps to achieve it. Our main contribution is obtaining an additive dependence on $L_1$ and a non-exponential dependence on $L_1 R_0$, for both Clipped SGD and Clipped Adaptive SGD.

Questions:

How does $R$ ("$x^\star$ with distance at most $R$ from initialization $x_0$") in Assumption 1 differ from $R_0 ≔ \lVert x_0 − x^\star \rVert$?

The difference lies in what each symbol represents:

• $R$ is used as part of our formal setup to describe a constrained optimization setting; together with the algorithm’s projection, it is an effective bound on the problem domain. AdaGrad-like algorithms require such settings.
• $R_0$ represents the initial distance to the optimum. Note that $R_0$ may be smaller than $R$, so it is preferable for the bounds to depend on $R_0$ rather than $R$.

Why are stepsize $\eta_t$ and threshold $c$ tuned independently in the experiments (by two-dimensional grid search), considering that they depend on the same set of problem constants?

We chose our tuning approach with standard practices in mind. Note that the approach is sufficient in order to answer the questions we introduce in section 4. Tuning $\eta_t$ and $c$ by tuning $L_0$, $L_1$, etc. is an interesting idea that we can consider for our next revision. However, note that directly using our formulation of $\eta_t$ and $c$ is still not trivial, as it depends on other theoretical quantities.

Some previous work under convexity and the $(L_0,L_1)$-smoothness use a weaker definition of $(L_0,L_1)$-smoothness from Zhang et al. (2020a) that does not require $f$ to be twice-differentiable. Can the result in this paper be established under this weaker assumption?

We believe they can: the $(L_0,L_1)$-smoothness definition is used only in lemmas 1 & 2, which were proven in prior work without assuming twice-differentiability (see footnote on page 4).

In Lemma 12, the authors first provide a bound for $\Sigma_t \alpha_t \Delta_t$ and then state, "If we also assume the setting of Lemma 10, then" and provide a different bound. But its proof proceeds by using results from Lemma 10 (in line 871).

The reference to lemma 10 in line 871 is an inexact justification on our side, and can be easily fixed (we can provide further explanation if you wish). In our next revision we will make this clearer.

• Theorem 1: $\delta \in (0,1) \to \delta \in (0,1/2)$?
• Lemma 13: Some of the $\Sigma_{t=0}^T$ should be $\Sigma_{t=0}^{T-1}$?

You are correct, thank you for your careful reading! We will fix these in our next revision.

Thanks for your response. I think it might be helpful to include a table comparing the convergence rate established in this paper with those from relevant prior work, along with the dependence on constants, the assumptions, and some remarks. This could make it easier for readers to clearly understand the contributions of this work.

Weaknesses:

1. In line 7 of the algorithm, the authors use projection onto the Ball of radius $R$ for adaptive methods. The value of $R$ depends on $|x_0 - x_*|$, which basically means you need the knowledge of $x_*$. This makes the algorithm impractical as the knowledge of $x_*$ is not known a priori.

We do not need to know the optimum itself, but rather a bound on the initial distance from it.

2. All the algorithms require the knowledge of the total number of iterations $T$ to set the step sizes. This is not ideal in practice.
3. The algorithms also need the knowledge of $\sigma$ or the variance of the gradient estimator to set the step size. This won't be available in practice.

We indeed aim to position this paper as theoretical, focusing on the complexity of $(L_0,L_1)$-smooth optimization and how proper clipping helps to achieve it. Our main contribution is obtaining an additive dependence on $L_1$ and a non-exponential dependence on $L_1 R_0$, for both Clipped SGD and Clipped Adaptive SGD.

In general, it is very standard in optimization research to set the stepsize using $R_0$, $T$ and $\sigma$, and results of this sort are considered of value. Avoiding them is usually tackled in dedicated future work. We consider our “conservative” variations, which are independent of $L_1$, as a stepping stone towards this.

4. In contribution point 4, the author mentions the advantage of clipped SGD over SGD in numerical experiments. However, I do not observe any advantage of clipping in the experiments.

The synthetic experiments in the appendix show an advantage, but we agree that it is not clear how much the advantage persists in real-world losses. Thank you for noticing this. We will correct this point in our next revision.

Questions:

1. Why do you need $\mathcal{T}_1$ in the algorithm. I couldn't find where you used it.

You are right in your observation that it is not necessary to maintain it. The reason we denote it explicitly in the algorithm is to make the later analysis easier to follow.

2. Where do you use assumption 3? This appears to be a very strong assumption.

We conduct most of the analysis itself under assumption 3, and then use a reduction to lift our results to hold under (the weaker) assumption 4. See lines 149-153, 229-237.

Strengths:

1. The paper makes a good theoretical contribution, providing clear convergence bounds for clipped SGD in the context of convex, stochastic (L0, L1)-smooth functions.
2. The theoretical presentation is both clear and well-organized. Key ideas are succinctly explained, and the overall structure of the paper is logical and easy to follow.

We thank the reviewer for their thoughtful and encouraging review. We are glad that the contributions, proofs, and presentation were found to be clear and compelling.

Weaknesses:

1. ... additional experiments on more complex tasks and larger datasets would improve the generalizability of the conclusions.
2. The double-sampling technique, while theoretically sound, seems to provide limited practical benefits. Additionally, the paper introduces several variations of SGD with clipping (standard, implicit, and adaptive), but it is not immediately clear which method performs best under different real-world conditions or how to select the most efficient one in practice.

We indeed aim to position this paper as theoretical, focusing on the complexity of $(L_0,L_1)$-smooth optimization and how proper clipping helps to achieve it.

On the matter of the several variations, please note the following.

• In analyzing an AdaGrad-like stepsize, we provide support for the common practice of using Adam with clipping.
• Our experiments show that all variations have similar performance, which is a useful observation in itself.

Typo: Line 152 contains two semicolons.

Thank you for the careful reading! We will fix this typo in the next revision.

Questions:

1. The paper discusses gradient clipping but does not offer detailed guidance on how to select the clipping threshold, particularly in real-world settings where data and gradients may vary. Could the authors provide more practical advice on how to tune the threshold in practice?

The most straightforward approach is to employ standard hyperparameter tuning (grid search) to tune the threshold, which for some reason is rarely performed. An observation which might prove useful is that our thresholds either scale like $\sqrt{T}$ (“standard” clipping) or remain constant (“conservative” clipping for sufficiently large $T$).

2. Are the assumptions (particularly the distance bound R and the Sub-Gaussian noise assumption) used in this paper standard and commonly accepted in the literature on related topics?

The distance bound $R$ is standard in analyses of AdaGrad and its variants. The noise assumption is also standard when proving high-probability bounds and appears in published work. In the context of $(L_0,L_1)$-smooth optimization, see [37], [42] and [43]; the last two the even stronger bounded noise assumption.

Motivation of the work:

The introduction is, unfortunately, very poorly structured... As a result, the paper fails to provide sufficient motivation for the problem it addresses.

We respectfully disagree with this assessment, and it seems that no other reviewer shares this opinion.

• We begin by providing motivation for studying gradient clipping, introducing the concept of $(L_0,L_1)$-smoothness, and highlighting its significance in the context of gradient clipping.
• We then briefly mention an interesting pattern observed in non-convex analyses (the low-order dependence on $L_1$).
• We move on to discuss the motivation and challenge of analysing the stochastic convex setting.
• Then we list our contribution and briefly describe the double-sampling technique.

For instance, what is the practical or theoretical motivation for focusing on light-tailed noise and high-probability convergence? Why is double sampling used, and what is the intuition behind this choice? These and other important aspects remain unclear.

The choices you mention are not rooted in an underlying motivation, but rather as a means to realize our goal, which is understanding the theoretical complexity of $(L_0,L_1)$-smooth optimization. As such, we believe that it is more appropriate to discuss them in section 3 (lines 145-153, 160-165).

Having said that, we can revise the introduction to note the following:

• High-probability guarantees are generally favorable compared to in-expectation guarantees.
• The choice of double-sampling is motivated by the challenge of bias in gradient clipping.
• Assuming light tails follows published work such as [37], [42] and [43] which, even under this assumption, contribute insightful ideas and are considered valuable.

Clarity of Claims:

... most of the results appear to follow from previously known techniques. As such, the contributions may be viewed as incremental...

While the general outline of the proof may appear familiar, our argument relies on a novel choice of clipping threshold that allows us to decouple the effects of gradient clipping and gradient noise (Lemma 6), as well as careful use of concentration inequalities (Lemma 8) that are essential for enabling the case-splitting argument at the core of our proof.

To evaluate the novelty of these techniques we note that:

• These techniques do not appear in analyses of clipped-SGD under generalized smoothness in the non-convex case.
• Prior published work have already studied the convex generalized smooth setting, yet they do not manage to remove the exponential dependence on $L_1 R_0$.

... the authors state (lines 117–118) that their results in the case $\sigma = 0$ are consistent with state-of-the-art results for the deterministic regime. However, this statement is inaccurate. For instance, the recent work [link] offers significantly stronger guarantees in the convex setting. This is especially evident in the regime where $L_0=0$: while the current paper suggests convergence only to a limiting neighborhood (an asymptote), the aforementioned work shows linear convergence to the exact solution.

Could you please explain why, in the case $L_0 = \sigma = 0$, you think our paper suggests convergence only to a limiting neighborhood? When plugging these values to theorem 3, it shows the sub-optimality gap is 0. That is, we show convergence to the exact solution in a constant number of iterations, where the constant is any solution to the inequality $T \geq \log(T) (L_1 R_0)^2$.

Moreover, at the end of page 3, the authors claim that linear convergence is not observed asymptotically. This statement, in the context of $L_0 = 0$, is misleading.

Indeed, that claim is stated for the general $(L_0,L_1)$-smooth case. We can alter it in our next revision to highlight the difference between the general case and $L_0=0$.

Comparison with Relevant Prior Work:

... lacks direct comparisons between the results obtained in this paper and those in prior literature...

We compare our work to existing literature in lines 108-119. Let us reiterate the key point from that part: a crucial factor that affects all known bounds in the stochastic setting is the dependence on either $\Delta$ or $M$, both of which may be exponential in $L_1 R_0$. One of the main novelties in our work is surpassing this exponential dependence.

In addition, I strongly recommend citing and discussing the following recent papers, which are highly relevant to the topic: [link] and [link].

We would be happy to discuss the first paper in our next revision. The second paper was released after the neurips deadline, so we think it is fair to view it as subsequent to our work.

Let us elaborate on the first paper: it studies stochastic mirror descent under $\ell$-smoothness (a generalization beyond $(L_0,L_1)$-smoothness), and shows a convergence rate with an implicit exponential dependence on $L_1 R_0$. This dependency can be deduced by looking at their proof: eqn. 202 (page 62) relies on $L_{t-1}$, a function of the initial gradient norm. The authors claim that this quantity is $O(1)$, but it is only because they treat the initial gradient norm as $O(1)$.

Experiments:

The current experimental section does not meet the expectations for a machine learning conference. The empirical results are limited to a synthetic example, with no experiments on real-world datasets or practical tasks where the proposed methods could demonstrate their relevance.

Our main experiments are not synthetic; they use two real-world datasets and test the (practical) task of linear regression.

Moreover, there are no comparisons with prior or related work, which makes it difficult to assess the empirical advantages or limitations of the proposed approach.

Since we tune $\eta$, prior clipping methods are essentially equivalent to single-sampling clipping, which we do test. We also compare our methods to SGD/Adaptive SGD without clipping.

Questions:

• On line 115, the authors claim to provide the first convergence results for stochastic convex optimization with generalized smoothness, but this is not correct. There are a number of papers considering a stochastic formulation of the problem.

Our exact claim is that we provide “the first rate… without exponential dependence on $L_1 R_0$”. If you believe this is incorrect, please show an example and we will make sure to correct this in our next revision.

• It follows from the problem statement that the authors consider a deterministic optimization problem (see line 133). Can the authors explain where the stochasticity comes from?
• Line 141 suggests that the oracle is stochastic, but due to the lack of a definition of the oracle, it is not obvious that the oracle is stochastic. The presence of stochasticity should be explicitly stated, e.g., $\mathcal{G}(x,\xi)$ or otherwise.

Stochasticity comes from the gradient oracle (as explicitly stated). Our notation is consistent with work such as Zhang et al. (2019).

• Assumption 2 contains a very restricted assumption of double differentiability. Is it possible to use a relaxation of the assumption, e.g., see [link]? Assumption 1.2 of [link]?

It is probably possible to relax this, as it only affects basic smoothness lemmas.

• The motivation for the light noise is not clear as is the nature of the noise itself from Section 3. It seems to be of more interest to the ML community if the authors consider the heavy tails assumption. Will there be a difference with work [link]?

We leave heavy tails for future work.

• Could the authors please clarify in what sense the method can be considered adaptive, given that the threshold parameter $c$ still appears to depend on the constants $L_0$ and $R$?

The use of the word “adaptive” comes from $\eta_t$ resembling Adaptive SGD (aka AdaGrad-Norm).

Additionally, could you elaborate on why the constant $L_1$ disappears from the final bounds? A more detailed explanation would be greatly appreciated.

The intuition is that, roughly speaking, every time clipping occurs we decrease the distance to the minimum by $\Omega(1/L_1^2)$ (see Claim 2 in the proof sketch and think of $T$ as a fraction of $(L_1 R_0)^2$). Therefore, there can be at most $(L_1 R_0)^2$ such iterations. The rest of the trajectory behaves as though the function was $L_0$-smooth.