Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses

We highly appreciate your critical feedback. We will revise wordings based on your suggestions.

W1 (“arbitrary” stepsize). We understand that you have a concern that we should not say “GD converges” if it stays in EoS. How about rephrasing this as “large-stepsize GD attains an $\\epsilon$-optimal solution”?

W3 (benefit of large stepsize). We basically agree with the reviewer. When we are only interested in minimizing the training risk, the convergence rate provided in Theorem 5 does not improve with large $\\eta$. Therefore, we did not emphasize the benefit of large stepsize intentionally, but instead focus on the mechanism of convergence beyond the classical threshold $\\eta\\leq2/\\beta$.

W4 (SGD). In short, our GD convergence analysis can be directly extended to SGD case, and the convergence rate remains the same, thanks to the perceptron structure.

To consider the stochastic scenario, let’s suppose the same assumption as Wu et al. (2024, Assumption 2). The parameter is updated by $\\mathbf{w}\_{t+1}=\\mathbf{w}\_t - \\eta\\nabla L\_t(\\mathbf{w}\_t)$ with $L\_t(\\mathbf{w}) = \\ell(\\langle y_t\\mathbf{x}\_t, \\mathbf{w}\\rangle)$ ($\\ell$: Fenchel–Young loss), where a single data $(\\mathbf{x}\_t,y\_t)$ is sampled i.i.d. based on the following assumptions:

• $\\|\\mathbf{x}\\| \\leq 1$ almost surely
• there exist a margin $\\gamma > 0$ and a unit vector $\\mathbf{w}\_\*$ such that $\\langle y\\mathbf{x},\\mathbf{w}\_\*\\rangle \\geq \\gamma$ almost surely

The main idea of our proof is Eq. (4). The upper bound of $\\langle\\mathbf{w}\_t,\\mathbf{w}\_\*\\rangle$ can be shown by the split optimization technique (Eq. (5)), which can be extended to the stochastic scenario as shown in Wu et al. (2024, Lemmas 16 and 17). The lower bound of $\\langle\\mathbf{w}\_t,\\mathbf{w}\_\*\\rangle$ at l.214 also holds (almost surely) straightforwardly. Hence, our proof is almost directly extendable to the stochastic scenario as long as we suppose the above assumptions.

This point seems to be interesting in contrast to Wu et al. (2024). Their convergence rate is not accelerated for SGD because the modified descent lemma holds only for the deterministic case and the convergence radius is limited to $\\eta\\lesssim T$. In contrast, our convergence seems to hold for SGD and the convergence radius is not limited.

Q (mirror descent). Interesting question. Can you provide a reference where mirror descent has better dimension dependence than GD? One challenge to study this question is that we don’t have an explicit dimension dependence in Theorem 5. The dimension-related factor is hidden in the margin $\\gamma$ instead. So we should investigate whether mirror descent improves the dependency in $\\gamma$.

Thank you for the detailed response. This is a strong paper with a valuable contribution, and I recommend accepting the paper.

I appreciate your interesting response regarding the extension to the stochastic setting, and it is encouraging to hear that the results hold. I strongly encourage the authors to include the full analysis in the camera-ready version if possible, as it would significantly strengthen the paper.

In response to the wording, yes, I believe the rephrasing is much clearer.

Thank you for the time and effort. We will fix the grammatical errors and reorganize the paragraphs based on your feedback. Subsequently, we mainly focus on answering your questions.

W1 (downstream regret). Upon the acceptance, we will expand Section 2 with an extra page to describe the preliminary of the connection between a surrogate loss and a downstream task. We initially said "regret with respect to a downstream task" (lines 110–113) is beyond our scope because we pay more attention to the optimization aspect. The study of a downstream task performance is certainly relevant, so we will remove the phrase “beyond our scope.”

Q1 (non-separable data). Our proof relies on the recursive expansion of $\\langle\\mathbf{w}\_t,\\mathbf{w}\_\*\\rangle$ (l.214), where the linear separability is used. Note that the linear separability implies $\\langle\\mathbf{w}\_\*,\\mathbf{z}\_{i\\_t-1}\\rangle \\geq \\gamma$, which yields the first lower bound. Without the linear separability, this recursive step becomes infeasible. We may introduce some additional assumptions on the data distribution to rescue this step, which seems an interesting open question.

Q2 (SGD). In short, our GD convergence analysis can be directly extended to SGD case, and the convergence rate remains the same, thanks to the perceptron structure.

To consider the stochastic scenario, let’s suppose the same assumption as Wu et al. (2024, Assumption 2). The parameter is updated by $\\mathbf{w}\_{t+1}=\\mathbf{w}\_t - \\eta\\nabla L\_t(\\mathbf{w}\_t)$ with $L\_t(\\mathbf{w}) = \\ell(\\langle y_t\\mathbf{x}\_t, \\mathbf{w}\\rangle)$ ($\\ell$: Fenchel–Young loss), where a single data $(\\mathbf{x}\_t,y\_t)$ is sampled i.i.d. based on the following assumptions:

• $\\|\\mathbf{x}\\| \\leq 1$ almost surely
• there exist a margin $\\gamma > 0$ and a unit vector $\\mathbf{w}\_\*$ such that $\\langle y\\mathbf{x},\\mathbf{w}\_\*\\rangle \\geq \\gamma$ almost surely

The main idea of our proof is Eq. (4). The upper bound of $\\langle\\mathbf{w}\_t,\\mathbf{w}\_\*\\rangle$ can be shown by the split optimization technique (Eq. (5)), which can be extended to the stochastic scenario as shown in Wu et al. (2024, Lemmas 16 and 17). The lower bound of $\\langle\\mathbf{w}\_t,\\mathbf{w}\_\*\\rangle$ at l.214 also holds (almost surely) straightforwardly. Hence, our proof is almost directly extendable to the stochastic scenario as long as we suppose the above assumptions.

This point seems to be interesting in contrast to Wu et al. (2024) because their convergence proof based on the modified descent lemma holds only for the deterministic case, but our perceptron-based proof remains valid in the stochastic case.

Q3 (other natural loss functions). The general idea of our convergence proof lies in Eq. (4), for which we need to estimate the constants $C\_L$ and $C\_U$. For other loss functions beyond Fenchel–Young losses, $C\_U$ can be estimated without many challenges via Eq. (5), while estimating $C\_L$ needs a bit more technicality. This requires a lower bound on the loss derivative $g$ (l.578–579), but we are not sure for now whether a similar polynomial bound like $g(\\epsilon) \\gtrsim \\epsilon^{\\alpha}$ can be obtained for broader loss functions.

We appreciate the reviewer for taking the time to provide feedback.

W (practicality of FY loss). Although the logistic or hinge losses are widely prevailing in practice, there is room to improve the practical performance by changing loss functions. Notably, Roulet et al. (2025) reported that the Tsallis loss occasionally outperforms the logistic loss even with the simplest ImageNet classification. Our study would be relevant to its mechanism since one of the biggest differences between the logistic and Tsallis losses is separation margin.

Roulet et al. (2025) “Loss Functions and Operators Generated by f-Divergences”

Q1 (dependence on n). In theory, the dependency of the rate on $n$ is due to the worst-case analysis at l.572–575: for example, $\\tfrac1n\\sum\_{j\\in[n]} g(\\langle\\mathbf{w}\_k,\\mathbf{z}\_j\\rangle) \\geq \\tfrac1ng(\\langle\\mathbf{w}\_k,\\mathbf{z}\_i\\rangle)$ for some worst data point $i$. The $\\tfrac1n$ factor eventually leads to the $n$-dependency. This means there always exists a bad data point $i$ with a negatively large prediction margin $\\langle\\mathbf{w}\_k,\\mathbf{z}\_i\\rangle$ before achieving $\\epsilon$-optimal loss.

Such a worst-case is unlikely because most data points tend to cluster in similar directions, and we conjecture that the $n$-dependency can be improved with an extra assumption. Actually, the scenario of duplicated samples suggested by the reviewer falls in this situation.

In practice, Tyurin (2025, Section 6) eliminates the $n$-dependency by adding a multiplicative adaptive factor to stepsize. A similar approach could work for Fenchel–Young losses.

Tyurin (2025) “From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes”

Q2 (tightness). In short, we recognize our analysis is not tight enough.

• Shannon case: Since the corresponding logistic loss has the self-bounding property, GD experiences the phase transition, shown by Wu et al. (2024). The doubled convergence speed by the doubled stepsize should be explained by the convergence rate after the phase transition, not by our Theorem 5, because Theorem 5 characterizes the convergence rate only before the phase transition (discussed implicitly at l.314–316; we will clarify more).
• Tsallis case: Since the corresponding loss function has separation margin (for Tsallis-1.5 and -2.0), GD does not experience the phase transition. When $q=2.0$, Theorem 5 gives $\epsilon=O(1/T^2)$. Actually, the trajectory in Figure 1 is faster than this rate, and close to the exponential rate. We conjecture that an extra assumption on the dataset is necessary to obtain the near-exponential rate just because of the similar reason to Q1.

Q3 (downside of large stepsize).

• For a loss function with separation margin: We do not see downsides of arbitrarily large stepsize so far. To make it sure, Theorem 5 characterizes the convergence rate in EoS phase only. If we look at Tsallis-1.5 and -2.0 in Figure 1, the convergence is actually faster with larger stepsize, and they stay on EoS. For example, Tsallis-2.0 with $\\eta=2^1$ apparently decreases with increasing $t$, but the loss value keeps oscillating locally.
• For a self-bounding loss function: As the reviewer noted, EoS phase continues longer with larger stepsize. This is detrimental to achieving the accelerated convergence rate obtained by Wu et al. (2024).

Q4 (slower convergence than $O(1/\\epsilon)$). The typical GD convergence rate $O(1/\\epsilon)$ for smooth convex losses is valid only for small enough stepsize $\\eta\\le2/\\beta$. The stepsize used in Figure 1 is larger than this threshold, which prevents from achieving $O(1/\\epsilon)$. Note that we plotted Tsallis only in Figure 1.

We would like to thank the reviewer for finding our result and proof techniques interesting. On the limitations, while extending to the multi-class case may not be straightforward, we guess it’s elementary to extend the linear model to deep homogeneous networks as done in several papers such as Tsilivis et al. (2025) because deep homogeneous networks can be analyzed similarly to linear models.

Tsilivis et al. (2025) “Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks”