Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses
Authors: Han Bao
Shinsaku Sakaue
Yuki Takezawa
Venue: NeurIPS 2025 spotlight ()
Keywords: gradient descent
loss function
implicit bias
Primary area: optimization

Abstract: The gradient descent (GD) has been one of the most common optimizer in machine learning. In particular, the loss landscape of a neural network is typically sharpened during the initial phase of training, making the training dynamics hover on the edge of stability. This is beyond our standard understanding of GD convergence in the stable regime where arbitrarily chosen stepsize is sufficiently smaller than the edge of stability. Recently, Wu et al. (COLT2024) have showed that GD converges with arbitrary stepsize under linearly separable logistic regression. Although their analysis hinges on the self-bounding property of the logistic loss, which seems to be a cornerstone to establish a modified descent lemma, our pilot study shows that other loss functions without the self-bounding property can make GD converge with arbitrary stepsize. To further understand what property of a loss function matters in GD, we aim to show arbitrary-stepsize GD convergence for a general loss function based on the framework of \emph{Fenchel--Young losses}. We essentially leverage the classical perceptron argument to derive the convergence rate for achieving $\epsilon$-optimal loss, which is possible for a majority of Fenchel--Young losses. Among typical loss functions, the Tsallis entropy achieves the GD convergence rate $T=\Omega(\epsilon^{-1/2})$, and the R{\'e}nyi entropy achieves the far better rate $T=\Omega(\epsilon^{-1/3})$. We argue that these better rate is possible because of \emph{separation margin} of loss functions, instead of the self-bounding property.

Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses
Han Bao"
Shinsaku Sakaue"
The Institute of Statistical Mathematics bao. han@ aemiss.... ac. ip
CyberAgent
shinsaku
Yuki Takezawa Kyoto University and OIST
takezawa@ml.. ist kyoto-u.o............ a.a.oo ip
Abstract
The gradient descent (GD) has been one of the most common optimizer in machine learning. In particular, the loss landscape of neural network is typically sharpened during the initial phase of training, making the training dynamics hover on the edge of stability. This is beyond our standard understanding of GD convergence in the stable regime where stepsize is chosen sufficiently smaller. Recently, Wu et al. [63] have shown that GD converges with much larger stepsize under linearly separable logistic regression. Although their analysis hinges the self- ooffdoouniig property of the logistic loss, which seems to be a cornerstone to establish modified descent lemma, our pilot study shows that other loss functions without the self- bounding property can make GD attain arbitrarily small loss with large stepsize. To further understand what property of loss function matters in GD, aim show large-stepsize Fenchel-Yourg losses.
GD convergence for general loss function based on the framework We essentially leverage the classical perceptron argument to derive the iteration complexity for achieving e-optimal loss, which is possible for a majority of renchel-Young losses. This convergence result highlights that the self-bounding property may not be necessary for GD to attain arbitrarily small loss. Moreover, when a loss function entails separation margin, notion relevant the margin in support vector machines, GD often yields faster convergence than typical GD rate T [2 1) for convex smooth objectives. Specifically, GD with the Tsallis entropy attains e-optimal loss with the rate T Q(= 1/2). and the Rényi entropy achieves the far better rate T = (133).
Introduction
Gradient-based optimizers prevalent in the modern machine learning community with deep learning thanks to its scalability and plasticity. Among many variants, GD remains to be a standard choice. GD with constant stepsize is written follows:
Wi+1
7/ Lww,),
for = 0, -
(GD)
where E Rd is the optimization variables, L(-) is the loss function, and O is stepsize fixed across all steps. The descent lemma 44 Section 1.2.3] is a key to GD convergence: for 3-smooth objective L, the stepsize choice 77 2/3 ensures that L( (w)) monotonically decreases. Nonetheless, little optimization theory has been known beyond the threshold r7 > 2/3: though modern neural networks exhibit much smaller smoothness values than practically used stepsize values [66] 57).
"This work was primarily conducted during the period when HB was affiliated with Kyoto University, and SS with the University of Tokyo and RIKEN AIP.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tsallis (g = 0.5)
logistic
L(we)
27
n= 2
L(We))
24
n=
2-1
n= 2
2-
n=
7=
n= 2
2
2-1
n=
200
2
2
tsallis (g- - 1.5)
tsallis (q 2.0)
24
24
L(w)
n=20
L(W))
n=20
2-14
n=
2.4
7-21
n-
0 0-2
2
2
7-22
2-4
2
2"
Figure 1: Pilot studies of GD with the same toy datasct as 63 The dataset consists of four points, X1
[1.0.2] , 1/1 = 1, X2 = 1-2, 0.2" 1/2 = 1, X, = [-1, 0.2] v/s = -1, x, = [2, -0.2] and y/ = -1 GD is run with initialization wo [0, 0] Note that the logistic loss corresponds to the Tsallis 1-loss. The Tsallis 2- and g-loss are also known as the modified Huber loss 67 and q-entmax loss 455 respectively.
Moreover, recent studies have reported that GD trajectories of neural networks tend to inflate the sharpness of the loss landscape and hover the edge of stability (EoS) before convergence [34 18 2
Among several recent developments in the theory of large-stepsize GD (which we will review in Section I.I. Wu et al. [63] investigated the large-stepsize behavior of GD by using the binary logistic regression with a linearly separable data, minimal synthetic setting. They showed that GD initially oscillates with non- monotonic loss values (the EoS phase), which terminates in finite time (phase transition), and then the loss value decreases monotonically (the stable phase). Beyond the logistic loss, these results have been extended to loss functions with the self-bounding property: for differentiable loss function &: IR + IR and its absolute derivative g(-) == (+),, E satisfies
(()) s ( x) + Cøg(z)(z =2) V2, x with |a z| 1. for some C3 > 0. (1)
The self- self-bounding property generalizes the polynomially-taie
loss B1 30). and refines the standard smoothness property by allowing the smoothness modulus locally adaptive to the derivative, such that Czg(x). Thus, large r) can be cancelled out with the vanishingly small loss gradient after the Lemma 29], and GD follows the descent direction.
phase transition 663
In this paper, we study GD with large stepsize under wide range of loss functions to identify key factor to induce the convergent behavior. This is motivated by our pilot study shown in Figure [ where we found that GD with large stepsize such as 17 2 remains to converge under the Tsallis q-loss (detailed in Section 4. even if the stepsize has gone beyond the classical stable regime. It is noteworthy therein that the Tsallis g-loss with q does not enjoy the self- self-hounding property. How much does the self-bounding property play a vital role in large-stepsize GD convergence? We specifically consider Penchel-Young losses (1]] class of convex loss functions generated by potential function é, as template of loss functions. Fenchel-Young losses have been used in applications such as structured prediction [ differentiable programming [10) and model
selection (7), while being used as theoretical tool for online learning [51] 52). We identify that
Fenchel- Young losses with separation margin (formally introduced in Section 2 relevant notion
to the margin in support vector machines, can often benefit from better GD convergence rates. We say a loss function has separation margin if the loss value vanishes with a sufficiently large positive prediction margin. Specifically, our main result is informally stated as follows.
Theorem 1 (Informal version of Theorem 5 Consider a binary classification dataset that is linearly separable. We run (D) with arbitrary constant stepsize 1) 0 and initialization wo 0 under
2

---

Sunchel-Youngg loss generated by twice continuously differentiable and convex potential & with separation margin. For ε >> O, after at most T steps of GD), where
d'(H)
1 6(u) u (
T= T and a == - -immsup sup
n40
we have L(Wr) S
As defined in Section 2 loss function with separation margin vanishes for sufficiently large prediction margin, which is a natural indicator of correct classification used in support vector machines. The order of the convergence rate T = Ot ") differs across various potential Φ. With specific choice, the rate can be ((==1/3) (with & being the Tsallis 2-entropy) and T 1/3) (with é being the Rényi 2-entropy, also known as the collision entropy (14). Remarkably, these convergence rates are better than the classical GD convergence rate T ()==') under the stable regime, and even better than the convergence rate of the logistic loss after undergoing the EoS and phase transition [ Both the Tsallis and Rényi entropies above lack the eeff-bounding property but have separation margin. Therefore, we advocate the importance of separation margin for better GD convergence rates. We compare different Fenchel- losses in Section and contrast our convergence result with the EoS and implicit bias in Section
We present Theorem T formally in Section 3 Our proof leverages the classical perceptron argu- ment [44] without relying on the descent lemma at all. Intuitively speaking, we track the growth of the parameter alignment (W,, w.) with the optimal separator w.. When a loss entails separation margin. (We, W.) cannot grow arbitrarily large (as we simulate in Figure 2 later) while each step
of (GD) improves a lower bound on (Wr, w.), leading to the convergence. Section 3.1 describes
this proof overview in detail. This is different from the proof of Wu et al. [63] whose core is the
modified decent lemma (recapped in Lemma in the appendix) based on the self-bounding property.
Although the perceptron argument is partially used therein [63]. the average loss is finally controlled
by the modified descent lemma, and thus the proof is only applicable to the self-bounding losses.
1.1 Related work
Gradient descent with large stepsize has attracted attention recently. Specifically, non-monotonic behaviors of loss functions [65] and the sharpness adaptivity to loss landscapes [34 [8] have been observed empirically. It was argued that the sharpness tends to initially increases until the classical stable regime breaks down, and hovers on this boundary, termed the edge of stability [8]. This observation mainly sparks two questions: why the loss landscape hovers on the EoS, and why converging. Answering either question must go beyond the classical optimization theory under the stable regime.
On why hovering on the BoS, let us make brief review, though it is not a central focus of this paper: Ahn et al. [2] is a seminal work to empirically investigate the homogeneity of loss functions contributes maintain the EoS. Later, it was showed that normalized GD (represented by scale- invariant losses) adaptively leads their intrinsic stepsize toward sharpness reduction (36). The sharpness fluctuation is often attributed to the non-negligible third-order Taylor remainder of the loss landscape 337 20
We rather focus on why GD attains arbitrarily small loss with much larger stepsize. In this line, previous studies show convergence based on specific models such as multi-scale loss function [2]. quadratic functions (5). matrix factorization (59 171, scalar multiplicative model [68 33
sparse coding model 31 and linear logistic regression (62 Among them, we advocate the logistic
regression setup proposed by Wu et al. (22 because it is relevant implicit bias of GD
[54] 29) 46
and moreover, Wu et al. (33 corroborates the benefit of large stepsize in GD convergence rate.
Our work is provoked by Wu et al. (63). questioning what structure in loss function leads GD to arbitrarily small loss. Indeed, we observe in Figure [ that loss functions without the self-bounding property (L) can make GD attain arbitrarily small loss, though the self-bounding property seems essential to calm the EoS down to the stable phase [63] as well as to establish the max-margin directional convergence 229 46). similar question to ours is raised by Tyurin [58), who argues that the stable convergence of steesste logistic regression might be an artifact due to the functional
'Throughout this paper, we consider @11) with respect to the error tolerance e when we say arbitrary stepsize unless otherwise noted.
3

---

form of the logistic mass-eventuully Tyurin [38] argued that large-stepsize logistic regression behaves like the classical perceptron. To this end, we show in Theorem that urbitrary-stepsize GD can converge under a wide range of losses even without the self- self-bounding property (T), and moreover, occasionally yielding a better rate than the classical stable convergence rate. We discuss it more in Section 5 Note that one work attempts to extend the separable logistic regression setup to the non-separable one [41]; yet, we still do not have satisfactory results beyond the one-dimensional case. Due to its intricateness, we follow the separable case.
Lastly, our work benefits the study of regret bounds of surrogate losses 9 regret bound connect a surrogate loss to downstream task loss, while the optimization error of the surrogate loss is usually ignored. Our GD convergence analysis can be integrated to surrogate regret bounds when discussing downstream task performance.
23
A surrogate
1.2 Notation
Let l2 be the set of nonnegative reals. Let [n] == {1, (I,...,my ,n. for E N. Let 1 be the all-ones vector and e, E Rdd be the i-th standard basis vector, i.e., all zeros except for the i-th entry being one. For _ R4, (S) denotes its (relative) interior, and Is: R + {0, oo its indicator function, which takes zero if μ E S and oc otherwise. For f2: IRd + R U (oo), dom( = {ur E Rd 2(z) < oo) denotes its effective domain and 22" (0) = sup {(O. μم) - 2(()) μ E } } its convex conjugate. Let A = F E RS (1) = } be the probability simplex. We introduce (I)) as the set of k-th continuously differentiable functions on the interval I _ R.
Let V: Rd + I (xx) be a strictly convex function differentiable throughout int v) + 2. We say V of Legendre-type if lim [|VV
oo whenever X1; X2, a sequence in int(dom V) converging to a boundary point of (ntm v) (see [49] Section 26)).
2 Preliminary on Fenchel-Young losses
Fenchel- Young losses have been introduced by Blondel al. | as a general class of surrogate losses for structured prediction, which are classification calibrated [00] This can be seen as a Bregman divergence comparing primal and dual points (25 Despite that the logistic and hinge losses are widely prevailing in practice, we can improve the performance of some prediction tasks by changing specific Fenchel- Young losses, as reported by Roulet al. (50]. We choose Fenchel-Yoour losses because a vast majority of convex, Lipschitz. and cnasification-caliire
losses are included in this class otherwise, GD convergence is hardly obtained beyond the edge of stability. Moreover, the separation margin property, one of the key features of Fenchel- Young losses, controls GD behaviors significantly.
Definition 2. Let Ω2 B.K + R R (oo) be a potential function. The Fenchel-Young loss ln: dom( x dom + R20 generated by Q is defined as
(0; 11) = (0) + 2(μz) (0. p.)
In multiclass classification, (0; μ) measures the proximity between score O and a target label
u = e; (for a class E [K]) By definition, (p(; μJ) is convex for any μ E dom( Moreover, (n( (1) = 0 holds if and only if μ 00 (0) due to the equality condition of the Fenchel- Young inequality.
We follow [1] Section 4.4] to consider binary (K = 2) loss functions. The following set of assumptions is imposed on a potential function Q. The asymmetric generalization is possible, but we choose to keep the analysis simpler so that we can focus more on the essence of GD convergence.
Assumption 1. For potential function Z assume dom(12) S A and that Ω satisfies the zero- entropy condition (((z)) = 0 for μ E (eiheetKi convexity 9[(1 a) + aqr) S (1 at) + as((p) for a + yt' and E (0, 1): symmetry 2(1) (2(P)) for any K x K permutation P.
Let us restrict ourselves to K = 2 (binary classification) and write (())= = 0(p,1 1- =) If we
choose 0 = [s, -s]T E ? as a score vector, the Fenchel-Young loss can be written as
(-s) if = 1, (s)
( (0;e))
if 2.

---

and dom((") = R. Hence, the Fenchel- Young loss is simplified as (-y-ys) if we relabel two classes and 2 with y 1 and y -1. respectively. Thus, we suppose the form of symmetric marsin-based loss function {(=) == o (-z). Therein, Fenchel-Young loss & extends proper canonical composite loss 47 over the entire prediction space 2 R. as discussed in 77]
Separation margin. For specific potential functions, Fenchel- Young losses entail separation margin [TT Section 5], which is generalized notion of classical margin in support vector machines.
Definition 3. For loss E: R - Rzo. we say l has the separation margin property if there exists m > such that any prediction 2 2 m. incurs {(=) = 0. The smallest m. is the separation margin of E.
0 indicates the prediction = E R not only correctly classifies a given point but also has safe margin mn away from the classification boundary 2 = O. It is shown that the existence of the separation margin property can be tested through the subgradient Oe [T]] Proposition 6].
Hence, ((=)
Proposition 4 (LI.). A Fenchel-Young loss (z)) (-=) satisfying Assumption has separation margin if and only if @0()) + Ø for any μ E [0, 1). When & E C² ((0, 1)) has separation margin m,
lim o' (14). #10
m
For a differentiable o, the nonempty-suben snnempty-subgradeen condition requires that the derivative d'(u) does not explode at the boundary points of the domain μ dom(o) {0. 1). In this case, is not of Legendre-type [49]. As we will see later, the convergence behavior of GD hinges on the separation margin property of loss function. More detailed analysis of the separation margin property for binary classification can he found in (7). In Section E we show that a loss satisfying the self- self-hounding inequality (I) does have separation margin (but not the other way around).
Examples. With the Shannon negentropy d(u) = l μ + (1 - p)) In(1 - 14), we recover the logistic loss (-== = In(1 + exp(-=)). With the negative of the Gini index ((11) 11² 14,
can generate the modified Huber loss (-2) max f0, 2} /4 2 -1 and 0² (-2) -
otherwise [67]. which is the binarized sparsemax loss (39]. If we choose Φ(μ) = max {u. /1].
we recover the hinge loss o² (-z) = max {0, 1 - =]. We discuss more examples Section
3 Convergence of large stepsize GD under Fenchel-Young losses
We consistently assume that the dataset is bounded and linearly separable. Assumption 2. Assume the training data (x,, W))ti satisfies
for every E [n]. ||x||| S 1 and ys E (+1};
there is 7 > and a unit vector w. such that (w.;zi) 2 7 for every i E [n], where z; == y:x;
Instead of logistic regression, we choose Youchel-Young loss {(2) (=(-=) associated with binary potential function á and minimize the following risk by (GD) with fixed stepsize n) > to
leam linear classifier w
L(w)= = 71
Σ
((W,yxxi) =
Σ n2 ZE(m]
e((w, zi)).
(2)
xE|n]
We impose the following assumptions our loss function.
Assumption 3. Consider a loss É: R + Rzo-
A. Fenchel-Youre loss. Assume that E(2) is Fenchel-Yourr loss (-22 generated by potential
: IR + R U {0o} such that & C² ((0, ()) satisfies Assumption 7 is strictly convex, and
8"
> on the interval (0, 1).
Regularity. Assume that p(A) = minSeR Xe(2) + 2² (for X 2 1) is well-defiedd
"To generalize the linear model, one straighttorward way is to focus on deep homogeneous networks (56). We stay on the linear model for now because the straightforward extension to deep homogeneous networks may not significantly change the problem structure.
5

---

C. Lipschitz continuity. For g(-) = (-), assume g(-) S for some Cg > 0.
We will later see that p characterizes the growth rate of the parameter norm ||we|l during GD (5) This notion is inherited from [63]. Now, we are ready to state our main result, the GD rate to attain arbitrarily small loss for linearly separable data under Fenchel-Youne Young losses. Remarkably, we show convergence without the self-bounding property of loss function, unlike [63].
Theorem 5 (Main result). Suppose Assumption 2 and consider (GD) with stepsize v > 0 and wo 0 under Fenchel-Yourd Young loss satisfying Assumption For any E (0, 1),
d'(H)
[
$(1)) (d(
A and CΦ = Li - o())aa'
a = sup ME(O,2] p
(3)
where Cs > 0 depends on & and e solely and æ = min (E), 13. af Co E (0, 20) and
for (0, T> AVD(721(T)
Cg e
Cog2
1
holds, then we have min L L(w:) S.
This convergence guarantee even applies to non-smooth Fenchel-Young losses as long as Assump- tionB]is satisfied note that & must be strongly convex to ensure the smoothness of the associated Fenchel-Young loss [II] Proposition 2.4]. As seen later in Section 4 and Cs neither diverge nor degenerate for arbitrarily small under many examples of Φ. When has separation margin, Lemma in Section|A]pme provvdee a finite upper bound p. yielding the following simpler form.
we additionally assume that i has separation margin m 0. For any (0, if (a, C.) defined in satisfies a, Co E (0, 20) and
Corollary 6. Under the same setup with Theorem S
for E (0,E),
T> n
4m
+ C. E-a
holds, then we have minrelry L(wi) E.
loss function without separation margin does not have finite p. which typically yields slower convergence as we see in Section 4 Therefore, (GD) operated on many common Fenchel-Young
losses converges under the separability, regardless of the choice of 77. Note that the classical GD convergence analysis under convex smooth functions provides T ((=-1)) As see later in Section some loss functions entail better rates with a < 1, summarized in Table
3.1 Proof outline
The proof of Theorem essentially relies the perceptron convergence analysis [44] and the asymptotical order evaluation of rate functions (6) We sketch the proof in this section to highlight the structure of the GD convergence in setup and complete the proof in Section B
When we show the convergence of perceptron, we leverage an inequality of the following type:
Cut Wt, w.)
[wll S (t) for 2
(6)
where CL > 0 is non-degenerate constant independent of t. The inequality holds only while perceptron misclassifies some examples. Thus, perceptron correctly classifies all examples after at most T iterations such that CLT > CT))). Such T exists as long as Ct()) sublinear in T.
When comes to our setup, an inequality (+) is obtained by recursively expanding the update GG
(We, w.) 2 (w,-1, w.) + 29 g(( w, ,- b,,,)) 2
g( 2..)) = (wG()
'This expansion relies on (w., 2,- 2 namely, the linear separability in Assumption 2
To lift the
linear separability assumption, may require introduce additional distributional assumptions here.

---

where 2 is a misclassified example by wi. Perceptron enjoys an inequality of -type immediately (i.e.,
because it optimizes the loss function per (2) = max f- 0). which yields g(z)
1 if
misclassified). When considering a Tenchel-Young loss satisfying Assumption 3 we do not have non-degenerate lower bound for g(z) because we can make g(2) arbitrarily close to zero. Instead,
we lower-bound g(2) by (non-degenerate) error tolerance 1 0, g(2) 2 ε1, before we attain the
e-optimal loss. Lemma 11 and (a part of) Lemma 13 in Section B are relevant to (+). Note that the
perceptron argument is used in [63 but in different way: they control L(wx) through the upper
bound on G (W&) (see Lemma 25 This is applicable only seff-bounding losses.
To obtain an inequality of (+) by following the standard perceptron analysis,
we directly expand the update (GD) |/ W 7 (w, recursively, and upper-bound it by noting that Eper has separation margin, leading (t) O(VE), Though this is possible for Fenchel- Young loss with separation margin, we can improve this bound by borrowing the split optimization technique, introduced by [63]. Eventually, can upper- pouer-bound |wr/l as follows:
||wll 5 4Vp()2mt) + CnC
(5)
In particular, we have p(A) ((1 when a loss has separation margin (see Lemma 9 and therein Cu(t) = (1). This is where separation margin plays a crucial role. We recap the split optimization technique in Lemma 10 based on which Lemma 19 in Section Dishows this inequality of (ty-e
The remaining piece is to assess the order of the convergence rate. After solving the inequality +) with f = T being the stopping time, we have T as a function of the error tolerance e, T f(e).
where f is a nondecreasing rate function depending on é. To characterize the asymptotic order at vanishing e, we attempt to evaluate in the form (() = go for an order parameter og >> O, which can be estimated by
E ( 240 [(s)
ao: the limit exists.
Thus, the order parameter ong is solely determined by the functional form of potential function c. This technique has been initially developed in functional analysis estimate moduli of Banach and Orlicz spaces [53 27 13), and recently introduced in convex analysis to approximate convex function by power functions (28) and estimate moduli of convexity 66 g The general statement of the order evaluation is given in Lemma 12 and instantiated for GD convergence in Lemma 1 in Section B
4 Examples of loss functions
Now, we instantiate Theorem 5 for several examples of Penchel-Young losses to discuss the con- vergence rate. Instead of specifying a loss function {(z) = (=(=),, we directly specify its potential function & subsequently. For each Φ, we compute (a, C₂) in (3) to investigate the convergence rate given by Theorem 5) by taking & (and thus jı) vanishingly small. In addition, we can compute separa- tion margin m by Proposition if exists; otherwise, we need to compute for loss (see Lemma 27). Table | Summarizee different loss functions and their GD convergence rates. All the detailed calcula- tions are deferred to Section where we have additional example of o (pseudo-spherice) entropy) with non-converging a.
Shannon entropy. Consider the binary Shannon (neg)entropy (()) μ p p + (1- 14) In(1 μt) The generated Sanchel-Youngg loss is the logistic loss É(2) = In + exp( -2 2) which enjoys the self- bounding property and hence does not have separation margin (see Section E The loss parameters are a and Cp 1. Moreover, we know C2 = 1 and p(A) < 1+ In (A) (63). Plugging this back
to Theorem 5] we have the e-optimal risk at most after
4 4v2(1og (7"") 1)
ns-
T 2
iterations,
"
In 2
722
where logarithmic factors in e are ignored. This indicates the rate T T (( recovering the standard GD convergence rate under the stable regime but with arbitrary stepsize 7). In Section 5 we compare this rate with (63] in more detail.
7

---

Table 1: Comparison of Fenchel-Young losses generated by different potential function Here, and
= oc indicate lack of separation margin and smoothness, respectively. Since we not have closed-form 3 for the Rényi entropy with q E (1. 2). we merely show its lower bound. The convergence rates ignore the dependency on {m, 7,7,, and hold for arbitrary stepsize 1) regardless of n 2/B.
Potential
Parameter
Sep. mgn. m
Smoothness
Order
Conv. rate for i(E=!)
Shannon
0
1/4
Semi-circle
0C
1/4
9((T
(0, 1)
00
29-3
Q( ((0=2/9)
Tsallis
(1,2]
q
q
0((=11/9)
(0)
q
1/2
02(-1113)
(0, 1)
(
1/4g
2((-2119)
Rényi
(1)
2 1/4g)
(0c-1/1)
q
8
1/3
12(c 1/3)
Semi-cirele entropy. Consider ((x) = -2 11(1 14). The generated Fenchel-Young loss (we call the semi-circle loss) {(2) (-2+ /22 + 4)/2 enjoys the self self-bounding property and does not have separation margin since (4) + -00 as μ1 + 0 (see Section The semi-circle loss is exp(- - z), which has the semi-circle entropy as the Bayes risk [. The loss parameters are a = and C. = Moreover, we have C₁ = 1 and p(A) S 52/(2 In A). Plugging this back to Theorem 5 we have the e-optimal risk at most after
relevant to the exponential/boosting loss (exp(=)
40n
2n - iterations, 7
T
for lacking separation margin
where the first term (2E=1) is an extra price due to the lack of separation margin of the semi-circle loss. For arbitrary stepsize т), the convergence rate is T = (( and stepsize 7) large as " ())=2) improves the rate be T (((-2) by cancelling the extra term
This convergence rate the semi-circle loss is even worse than the GD convergence rate for general convex smooth functions, 7 ()) This is because the perceptron argument is merely sufficient for GD convergence. Nonetheless, the perceptron argument more informatively states that we have (We, w.) //ll 2 5" after minimizing the risk at the s-optimal level-by combining the inequalities )) (in Eq. (4)). This indicates that the loss function with larger a yields slower parameter alignment toward w..
Tsallis entropy. For g with + 1, consider the Tsallis (neg)ennropy
12 + 41)
q
generalizing the Shannon entropy for non-extensive systems 55 It recovers the Shannon entropy at
the limit q 1. The generated Fenchel- Young loss known the q-entmax loss 45 the case depending on parameter
We divide
When 0 < < (a,Ca) Cb) (1/g, 1), and o² does not have separation margin.
When 1 < q 2: (a, Co) = (1/q, 1). and o² has separation margin m = = - 1).
When 2 < q: (a, C.) = (1/2, 2/ and @* has separation margin m = q/(g 1).
For all cases, and Co stay in (0, oc). The convergence rate is T = (2(22//4) for q E (0. 1) (by Corollary 28): T = ( for g (1,2); T 1/221 for 2 < This suggests that we have better convergence rate over the Shannon case when q 1 and the best rate is 112).

---

Rényi entropy. For (0, 2 \ {1}, consider the Rényi q- (neg)ennyyy
<(n) q
In fa + 1 - 1u)9]
generalizing the Shannon entropy (with the limit q - 1) while preserving additivity for independent
events [48]. The Rényi entropy extended beyond > 2 becomes nonconvex, which we do not consider. The Rényi 2-entropy is referred to as the collision entropy [14].
We divide the case depending on parameter q:
When 0 < < C²) (1/g, 1), and o* does not have separation margin.
When < C2) = (1/q, 1), and o² has separation margin m = =//44 - 1).
When q = 2: (a, Cb) = (1/3, / 3/8) and o* has separation margin m = 2.
For all cases, a and C2 stay in (0, xc). The convergence rate is 7 = 22(=2/09) for & E (0, 1) (by Corollary 28 T 20 1/0 for 4 E (1, T = -2(== 1/3) for 2. Surprisingly, we have "leap" of the order from E 1/4 to e-----1 1/3 as t 2. and the convergence rate (0(=-1/8) is far better than the Shannon and Tsallis cases. When q = 2, Corollary implies that we have the s-optimal risk at most after
T> 8/83
8 + q2
n
c 1// iterations.
17
5 Discussion and open problems
Comparison with Wu et al. 163]. The large-stepsize logistic regression has been shown to ex- hibit the following phase transition (63] the GD sequence initially stays in the EoS phase such that the risk L(w,) fluctuates initially with its average 1-1 Σx L(wx) controlled. Once we experi- ence L(w)) S min (1/n, ((0)/n), which is possible within O(n) steps most, GD leaves the EoS and the loss converges in the rate L(W.)) = (())()))). The stepsize 7j trades off the phase transition time for the stable convergence rate. If we know the maximum number of steps T in advance, the choice 1) (TT) balances them, achieving the acceleration to L(w,) 0(1/T9) We detail them in Section D This is arguably interesting to demonstrate how GD benefits from large stepsize.
Nevertheless, we would like to highlight two caveats. First, must undergo L(w:) S 8(0)/n before exiting the EoS phase. This means that our linear model has already classified all points correctly during the EoS phase since any single point z; incurs loss at most E( E((W,, z:)) I {(O) = (w,, 2,) 2 (cf. Lemma 22 in Section D GD keeps improving the logistic loss after the stable phase just because the logistic loss does not enjoy separation margin and never touches strict zero We refer interested readers to the relevant discussion in Tyurin (58), who argues that the faster convergence in the stable phase is attributed to the choice of the logistic loss.
Second, the FoS termination condition T. T.(w,) S 1/n suggests that the risk must be once ((/TT)- optimal (with the optimally balancing choice 17 ((T)) before benefitting from the super-fast rate O(/TT². Yet, GD under some loss functions including the Tsallis q-loss (q > 1) and the Rényi q-loss (q > 1) achieves better risk with the same GD steps. If our goal is simply to classify all training points, these alternative losses might do better jobs in terms of optimization solely.
Self-bounding property and implicit bias. Having said that, the phase transition may play an important role in implicit bias. It was shown under the linearly separable case that logistic regression optimized with GD enlarges the norm ||w,]l toward the max-margin direction in rate ((In(t)) [54] [6). Thus, we may argue that w, gradually comes to classify all data points correctly during the EoS phase and evolves toward the max- max-mnrgin direction in the stable phase.
We reported how ||w:|| evolves under the pilot setup in Figure 2 with different loss functions. As seen, the logistic and Tsallis 0.5 losses inflate ||wz]| endlessly, which do not have separation margin. In
*Cai et al. [66 extends Wu et al. 62 for two-layer near homogeneous NNs, where it is not explicit that the model correctly classifies all points after the EoS phase. Taking a closer look, we can see that their Lemma A.7 leverages the well-controlled risk, which is alternative expression "L(ws) ) & {(0)/re" under their setup.

---

tsallss
logistic
tralls
2=
n=
2
2
n=
27
2
14.
Figure 2: Under the same setup Figure 1
we show
||wr|| along the number of steps with different losses.
stark contrast, the Tsallis 2-loss prevents ||wel from growing endlessly just because of its separation margin- recall the norm upper bounds of the norm |[wlll in (IT) and the growth rate p in Lemma 9 This raises two open questions: (1) Do we have similar implicit bias aligning toward the max- margmn direction under loss function with separation margin? (2) What are benefits and caveats of endless growing of //wll? The latter is particularly relevant to the overconfidence issue due excessively large Wr [6]] and worse generalization due to prohibitively large within-class variance [26]. Wu
al. [64 argues that excessively large || |/wll leads an inconsistent estimator.
The study on implicit bias for loss functions with the self-bounding property has been very scarce. To knowledge, 335 crafted the complete hinge loss, which behaves like the hinge loss before GD converges to the zero risk yet incurs an extra penalty to artificially align the parameter toward the max-margin direction. Together with the benefits and caveats of the max-margin implicit bias, believe this is an interesting open topic.
Dependency on n. Our main result (Theorem 5 provides the rate depending on the factor n. This extra factor with respect to arises due to the worst-case analysis such that we have least one "bad" direction z; before the convergence, corresponding to the inequality (9) in the proof of Theorem 5 (see Section B This worst-case scenario supposes that all data points are nearly equidistant, which is unlikely since most data points tend to cluster in similar directions. We conjecture that this n-dependency not essential with additional mild data assumptions.
The stochastic case. Our result can be extended for the stochastic gradient descent (SGD). Consider the scenario where we sample one fresh data point at each ł and update the linear parameter with the loss function computed on this sample. Under the similar setup to Theorem 5 the population risk is e-optimal with high probability after T 1?(E (a++))))) The formal statement and proof are shown in Section C While this rate apparently looks significantly slower than the GD rate T (?)=") the extra iterations -2 is necessary for collecting sufficient samples to estimate the population risk. By noting that the GD/SGD updates consume n/one samples, the GD/SGD rates are comparable in terms of the number of consumed samples.
Finite-time convergence. Last but not least, we may potentially have another benefit of loss functions with separation margin. Take look at Figure I again. Loss functions without separation margin, such as the Tsallis 1.5- and 2-losses, converge to exact zero within finite time when sufficiently large stepsize is used. Such finite-time convergence under the linearly separable case can be shown without significant challenges if we use perceptron, or even the hinge loss, while becoming highly non-trivial in the case of wrice-differentiable loss functions. This is because the perceptron argument requires a non-degenerate lower bound on (w,, w.) (see (4). which is not straightforward therein the loss gradient We conjecture that an additional data assumption is necessary because the loss gradient could be adversarially vanishing against GD convergence, and leave this future work.
be arbitrarily small positive (due to the twice differentiability of the loss).
Acknowledgments
HB is supported by JST PRESTO (Grant No. JPMIPR24K6). SS was supported by JST ERATO (Grant No. 19M)ER YT is supported by JSPS KAKENHI (Grant No. 23KJ1336).
10

---

References
[1] Shivani Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses. Journal of Machine Learning Research, 15())115531167, 2014.
[2] Kwangjun Ahn, Jingzhao Zhang, and Suvrit Sra. Understanding the unstable convergence of gradient descent. In Proceedings of the 39th International Conference Machine Learning, pages 247-257, 2022.
[3] Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang. Learning threshold neurons via edge of stability, Advances in Neural Information Processing Systems, 36:19540-19569, 2023.
[4] Shun-ichi Amari. Information Geometry and Its Applications, volume 194. Springer, 2016.
[5] Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In Proceedings of the 39th International Conference on Machine Learning, pages 948-1024, 2022.
[6] Han Bao. Proper losses, moduli of convexity, and surrogate regret bounds. In Proceedings of the 36th Conference on Learning Theory, pages 525-547, 2023.
[7] Han Bao and Masashi Sugiyama. Fenchel-Youne losses with skewed entropies for class- posterior probability estimation. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 1648-1656, 2021.
[8] Han Bao and Asuka Takatsu. Proper losses regret at least 1/2-order. arXiv preprint arXiv:2407.10417, 2024.
[9] Peter I.. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156 2006.
[10] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Dean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Advances in Neural Information Processing Systems. 33:9508-999 19999999999.. 2020.
[11] Mathieu Blondel, André F. T. Martins, and Vlad Niculae, Learning with Fenchel-Young losses. Journal of Machine Learning Research, 21(35):1-69) 2020.
[12] Dick E. Boekee and Jan C. A. van der Lubbe. The R-norm information measure. Information and Control, 45(2): (((())133-1555 155, 1980.
[13] Jonathan Borwein, Antonio Guirao, Petr Hájek, and Jon Vanderwerff. Uniformly convex functions on Banach spaces. In Proceedings of the American Mathematical Society, volume 137, pages 1081-1091, 2009.
[14] Gustavo M. Bosyk, Mariela A. Portesi, and Ángel L. Plastino. Collision entropy and optimal uncertainty. Physical Review A-Atomic, Molecular, and Optical Physics, 85(1):012 2012.
[15] Andreas Buja, Werner Stuetzle, and Yi Shen. Loss functions for binary class probability estimation and classification: Structure and applications. Technical Report, 2005.
[16] Yuhang Cai, Jingfeng Wu, Song Mei. Michael Lindsey, and Peter L. Bartlett. Large stepsize gradient descent for homooooggenuus two-layer networks: Margin improvement and fast optimization. Advances in Neural Information Processing Systems, 37:71306-71351, 2024.
[17] Lei Chen and Joan Bruna. Beyond the edge stability via two-step gradient updates. In Proceedings of the 40th International Conference Machine Learning, pages 1330-4391 2023.
[18] Jeremy Cohen, Simran Kaur, Yuanzhi Li, J. Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In Proceedings of the 9th International Conference on Learning Representations, 102

---

[19] Jean-Pierre Crouzeix. A relationship between the second derivatives of a convex function and of its conjugate. Mathematical Programming. 13(1):364-36) 1977.
[20] Alex Damian, Eshaan Nichani, and Jason D. Lee. Self-stabilization: The implicit bias of gradient descent at the edge of stability. In Proceedings of the 1 11th International Conference on Learning Representations, 2023.
[21] John M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathematics, 14(4):641-664 1966.
[22] David A. Freedman. On tail probabilities for martingales. the Anmals of Probability, 3(1): 100-118, 1975.
[23] Rafael Frongillo and Bo Waggoner. Surrogate regret bounds for polyhedral losses. Advances in Neural Information Processing Systems, 34:21569 111155901118,, 2021.
[24] Tilmann Gneiting and Adrian E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-3777 -78, 2007.
[25] Geoffrey Gordon. Regret bounds for prediction problems. In Proceedings of the 12th Annual Conference Computational Learning Theory, pages 29-40, 1999.
[26] Mingcheng Hou and Issei Sato. A closer look at prototype classifier for few-shot image classification. Advances in Neural Information Processing Systems, 35:25767-25778, 2022.
[27] Henryk Hudzik. Lower and upper estimations of the modulus of convexity in some Orlicz spaces. Archiv der Mathematik, 57(1):80-87) 87, 1991.
[28] Kazuhiro Ishige, Paolo Salani, and Asuka Takatsu. Hierarchy of deformations in concavity. Information Geomerry, pages 1-19, 2022.
[29] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data, In Proceedings of the 32nd Conference on Learning Theory, pages 1772-1798, 2019.
[30] Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, pages 772-804, 804, 2021.
[31] Ziwei Ji, Miroslav Dudik, Robert E. Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Proceedings ot the 33rd Conference on Learning Theoory pages 2109-21333 2020.
[32] Lingkai Kong and Molei Tao. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective function. Advances in Neural Information Processing Systems, 33: 2625 2638, 2020.
[33] Itai Kreisler, Mor Shpigel Nacson, Daniel Soudry, and Yair Carmon. Gradient descent mono- tonically decreases the sharpness of gradient flow solutions in scalar networks and beyond. In Proceedings of the 40th International Conference on Machine Learning, pages 17684-17744, 2023.
[34] Aitor Lewkowyez, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: The catapult mechanism. arXiv preprint MxXiv2003300218., 2020.
[35] Justin N. Lizama. Completion of hinge loss has an implicit bias. Master's thesis, University of Illinois at trbana-Champaign. 2020.
[36] Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of normalization layers: Sharpness reduction. Advances in Neural Information Processing Systems, 35:34689-34708, 2022.
[37] Chao Ma, Daniel Kunin, Lei Wu, and Lexing Ying. Beyond the quadratic approximation: The multiscale structure of neural network loss landscapes. Journal of Machine Learning, 1(3): 247-267, 2022.
12

---

[38] Anqi Mao, Mehryar Mohri, and Yutao Zhong. Cross Cross-entropy loss functions: Theoretical analysis and applications. In Proceedings of the 40th International Conference on Machine Learning. pages 23803-23828, 2023.
[39] André F. T. Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification, In Proceedings of the 33rd International Conference on Machine Learning, pages 1614-1623, 2016.
[40] Peter McCullagh and John A. Nelder. Generalized Linear Models, volume 37. CRC Press, 1989.
[41] Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao, and Christopher Sa. Gradient de- scent on logistic regression with non-separable data and large step sizes. arXiv preprint arXiv:2406.0555 035033, 2024.
[42] Yurii Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018
[43] Vlad Niculae, André F. T. Martins, Mathieu Blondel, and Claire Cardie. SparseMAP: Differ- entiable sparse structured inference. In Proceedings of the 35th International Conference on Machine Learning, pages 3799-3808. 2018.
[44] Albert B. J. Novikoff. On convergence proofs for perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata, pages 615-620, 1962.
[45] Ben Peters, Vlad Niculae, and André T. Martins. Sparse sequence-to-sen to-uueeecc models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1504-155 1519, 2019.
[46] Hrithik Ravi, Clayton Scott, Daniel Soudry, and Yutong Wang. The implicit bias of gradient descent separable multiclass data. Advanced in Neural Information Processing Systems, 37: 8 81324-81359, 2024.
[47] Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research, 11:2387-2422, 2010.
[48] Alfréd Rényi. On measures of information and entropy. In Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability, volume 1, 1961.
[49] R. Tyrrell Rockafellar. Convex Analysis, volume 28. Princeton University Press, 1970.
[50] Vincent Roulet, Tianlin Liu, Nino Vieillard, Michael Eli Sander, and Mathieu Blondel. Loss functions and operators generated by f-divergences. In Proceedings of the 42nd International Conference Machine Learning, pages 52110-52138, 2025.
[51] Shinsaku Sakaue, Han Bao, Taira Tsuchiya, and Taihei Oki. Online structured prediction with Fenchel-Youne Young losses and improved surrogate regret for online multiclass classification with logistic loss. Proceedings of the 37th Conference on Learning Theory, pages 2024.
[52] Shinsaku Sakaue, Han Bao, and Taira Tsuchiya. Revisiting online learning approach inverse linear optimization: A Fenchel-Young loss perspective and gap-dependent regret analysis. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, pages 46-54, 2025.
[53] Igor Borisovich Simonenko. Interpolation and extrapolation linear operators in Orlicz spaces. Matematicheskii Sbornik, 105(4):536-553, 1964.
[54] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasckar, and Nathan Srebro. The implicit bias gradient descent on separable data. Journal of Machine Learning Research, 19 (70):1-57, 2018.
[55] Constantino Tsallis. Possible generalization of Boltzmann-Gibbe statistics. Journal of Statistical Physics, 52:479 487, 1988.
13

---

[56] Nikolaos Tsilivis, Gal Vardi, and Julia Kempe. Flavors of margin: Implicit bias of steepest descent in homogeneous neural networks. In Proceedings of the 13th International Conference on Learning Representations, 2025.
[57] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using PAC-Bayesie Bayesian analysis. In Proceedings of th 37th International Conference on Machine Learning, pages 9636-9647, 2020.
[58] Alexander Tyurin. From logistic regression to the perceptron algorithm: Exploring gradient descent with large step sizes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 20946, 2025.
[59] Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames homogeneity: Convergence and balancing effect. In Proceedings of the 10th International Conference on Learning Representationss 2022.
[60] Yutong Wang and Clayton Scott. Unified binary and multiclass margin- -aaged classification. Journal of Machine Learning Research, 25(143):1-51, 2024.
[61] Hongxin Wei, Renchunzi Xie, Hao Cheng, Lei Feng, Bo An, and Yixuan Li. Mitigating neural network overconfidence with logit normalization. In Proceedings of the 39th International Conference Machine Learning, pages 23631 123644, 2022.
[62] Jingfeng Wu, Vladimir Braverman, and Jason D. Lee. Implicit bias of gradient descent for logistic regression at the edge of stability. Advances in Neural Information Processing Systems, 36.74229-74256, 2023.
[63] Jingfeng Wu, Peter Bartlett, Matus Telgarsky, and Bin Yu. Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. In Proceedings of the 37th Conference on Learning Theory, pages 5019-5073, 2024.
[64] Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, and Bin Yu. Benefits of early stopping in gradient descent for overparameterized logistic regression. In Proceedings of the 42nd International Conference on Machine Learning, pages 67081-67110. 100 2025.
[65] Chen Xing. Devansh Arpit, Christos Tsirigotis, and Yoshua Bengio. A walk with SGD. arXiv preprint 000111000777700 2018
[66] Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W. Mahoney, Hessian- analysis of large batch training and robustness to adversaries. Advances in Neural Information Processing Systems, 31:4949-4499 2018
[67] Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the 2 International Conference on Machine Learning, page 116. 2004.
[68] Xingyu Zhu, Zixuan Wang, Xiang Wang, Mo Zhou, and Rong Ge. Understanding edge-of- stability training dynamics with a minimalist example. In Proceedings of the I 11th International Conference on Learning Representations, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In Section I we summarized our main result informally in Theorem
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contri- butions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The implicit bias structure for large-stepsize GD is nuanced. We carefully discussed this in Section
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to
provide closed captions for online lectures because fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't tcknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our main set of assumptions are stated Assumption 3 The complete proof
corresponding to main result is in Section B and the proof sketch is in Section 3.]
15

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numhered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experimental details are described in the caption of Figure [ despite that it synthetic simulation. Since the problem is convex by construction, the reproduction is straightforward.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken
make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g.. a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [No]
Justification: Our synthetic experiments reported in Figure are not challenging to reproduce because the dataset and model are extremely small and the problem is convex.
16

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines bbttps://nips.. http/iips..ooo cc/
public/guise gttp//uiiee///eee Sodeee//oooSSemiiiccc ssionPolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https coooooiiiccy for more details.
7 cinisscc/ppll holllccguui /eddeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See the caption of Figure
Guidelines:
The answer NA means the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We do not report the statistical significance for the synthetic simulation in Figure 1 because there no randomness. All of the initialization, algorithm, and datasets are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI. if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
17

---

If eтror bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [No]
Justification: Since the synthetic experiments in Figure I are extremely small-scale, do not need huge amount of computational resources to reproduce them. The experiments can be finished within minute with a consumer laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics https::/t//... /twur//eerrri wtt.ccc/pbblcccceeeec.ee cwt.ihiccssiiieee ines?
Answer: [Yes]
Justification:
This paper studies theoretical aspects of optimization, which hardly face such a challenge.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethies.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper studies theoretical aspects of optimization, which hardly face such challenge.
Justification:
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
18

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
This paper studies theoretical aspects of optimization, which hardly face such challenge.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
All datasets used in the simulation in Figure are synthetic.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, [paperswi] t code. com/ curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
has
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
All datasets used in the simulation in Figure are synthetic.
Guidelines:
19

---

The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/mooel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: All datasets used in the simulation in Figure I are synthetic.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants. whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve any human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We did not use L.M in any aspects when conducting this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components. Please refer to our L.MM policy (https neuri fct//ooneerenncs/222555 for what should should not be described.
20

---

A
Technical lemmas
We introduce the gradient potential for a loss function in consideration as follows:
" G(w)
πt g((w, z;)).
(6)
Lemma 7, Consider a loss satisfying Assumption 3B
Then, we have
(VP(s)) -
p(A)
X
Proof. See 63 Lemma 20).
Lemma 8. Consider a Fenchel-Young loss E(2) (-2) satisfying Assumption 3A Then, E and
are nonincreasing. Moreover, & is strictly decreasing on (-00, (-0,,m)( m) R) if f has separation margin m 0; otherwise, & is strictly decreasing on IR
Proof. We have by Danskin's 's theorem 21 (6*)² = (6)) and then
(2) - = (d') (d)) 00
Edom(d){[oo1)
which implies that nonincreasing. Since is convex and nonincreasing we have that g(-) [e((-) = (-) is nonincreasing.
For the latter part, if nonincreasing l has separation margin, {(2) 0 if and only if 2 m. Then, we have é = on the interval [m, oo) C IR and >> 0 on the interval (-oc, m) C R. On the latter interval, must be strictly decreasing because of its convexity. We can prove similarly for lacking separation margin.
Lemma 9. Consider loss satisfying Assumption 3B Suppose that i has separation margin m > Then, we have p()) I m² for any X 2 1.
Proof. When l has separation margin m (see Definition 3 we have
Xe(2) + = for 2 2 m.
By the definition of we have
P(A)= min Al(z) + 3 min 2 m².
22m
Lemma 10 (Split optimization
663
Suppose Assumption 2 and consider convex and nonincreasing
loss é satisfying Assumption 3C and let u1 + U2 such that
C w.
u1 Sw.,
11
27
For every t 1, we have
Iw.
1112
1 I-1
1
(e
+ Σ
L(wk) s ((78)
2tt
2nt
2n
Proof. For Is < t, we have
|| u 12 |W u||2 2n (VI(w:). 1- wx)
|w u||2 + 21 ((Ww)), i - wx) + (2 (VL(W)), + + V[W=)()))
21

---

For the second term, we have
n
(VL(wA), u1 -wk)
El ((wk: 2i)) (Zi, un - wk)
i=1
n
(((wk: 2z) (1))((2..2))) - (Wi. zi))
11
[e(uu,, 2()) <WW,, 2,)i
(E: convex)
(()0) I(wx).
(a: nonincreasing)
For the third term, we have
(WW) u2) + m| [[ww]l]
2
1
( ((Wk: 2,)) (23, u2) +
e' (((Wk, 2i)
1=1
i=1
2
1
<
(' ((wk, m1)) (Z,, u2) +
Σ
l' ((wk, 2;))
(|2/|l S 1)
11
i=1
2 u2ll
<
E' ((Wk: zi)) (zi, w.) + n. G(wr)
(Assumption 3C and G(Wa)) 2
7
< 2-27 [2r]|u2|/G(wa) + - G(wx)
(Assumption 2 and G(wx) 2 0)
= 0,
where the last equality is by the choice of u2 and G(w) is defined in (
By combining them altogether, we have for k < t, || u/1 < l| u|| 21 [l(70) L(wx)].
Telescoping the sum from to / and rearranging, we get
Wr ull
((wx) < {(70) + |Wo ul 2 2np
2zyl.
which completes the proof.
B Proof of Theorem
Lemma 11. Suppose Assumption and consider (G)) with any stepsize n > 0 under Fenchel-
Young loss & that satisfies Assumption 3A For 2 assume G(wx) 2 Gmin > 0 for all k E [0,1-1].
where G(w) is defined in 66.. Then, we have
G (w,, w.) (Wo. w.).
Proof. By the perceptron argument we have
(WE+1, w.) = (Wk, w.) (V (We), w.)
= =(wk, w.)
7
(((Ww: 24) 124, W.
n
= (WK, w.) + n
7
g( ((Wes 2.)) (w., 2.)
(use g(-) = (-( by Lemma
(Wk, w.) Gwws)
(note g(.) 2 0 and Assumption 2
(wx, w.) + Gmim.
Telescoping the have the desired inequality.
22

---

Lemma 12 (Order evaluation), Let I C22 be an open interval containing zero as the left end. For f: Rzo + Ezo U {oo} that is nondecreasing and differentiable on I and satisfies f(0) 0. let
x (x) f(x)
sup 2c(0.2g)
for some Zu E I.
(8)
Then, for any E zo). have
where C= f(1o)
f(x) 2 Cx",
x0
Proof. By the definition of a, we have
a (x) f(x)
for all æ (0.
Then, for any (0,20), we have
To
ds
f((s) ds In f(2o) f(8)
In
[(x)
By reorganizing this inequality, we can prove the original argument.
Lemma 13. Consider Senchel-Young, loss f(z) = o² (-2) satisfying Assumption 3A
Then, for
arbitrary 0 < and a defined in (3. we have
(E) Csca for (0,E), where Cs (())
Proof. Choose any Eo O. For E E (0, Eo), we can invert get (-) because é is strictly decreasing on l ((0, 1)) (by Lemma 8) and hence invertible. Note that
(Eo), m) if é has separation margin 0.
2 E (e- (Eo), otherwise,
because (-) is nonincreasing. We write this range as I, then = (=) E I for E (0, Let verify g(z) (z) is differentiable at E I first. By the definition of Fenchel-Young losses, we have
((2) 0-=)= = sup [x: ((=)) (6') (6)) (00') zE(0.1)
for I, where we used the first-order optimality - = of the convex conjugate at the last identity. Since á is twice continuously differentiable and o" > on the interval (0, 1) by Assumption 3A we can apply the inverse function theorem to have
('(00)
(() (())= 8" (")())1((=))
z
((00) - (00)-1(-2)
for 2 I. Since is twice continuously differentiable, once again to get (z) for E I, and hence is differentiable on
apply the inverse function theorem
In addition, is continuously differentiable with non-degenerate derivative at I because é is strictly decreasing on I. From these observations, we can see that (-)- = f(-) nondecreasing on I and differentiable on I (because it is the composition of two nondecreasing and differentiable functions and {-)). Now we can apply Lemma 12 to this f. Let us compute the exponent as defined in (8). By the differentiability and non-degenerate derivative of on I, we can apply the inverse function theorem on & to have
ef)(
g( (() (((-((E))
(inverse function theorem)
f(E)
((e-1(E))
(())
(E {(2))
(z)
23

---

(z))
(o() (())
[e(=))²
( (=)
(E== -2)
[()))
[(u)]
(a)
(4 = (0))
122
('()) [1 ((1)
(
1 (Hr)
where at (A) we introduce a as the dual of by the mirror map o' such that
2 = ('))) and === (6") (2),
which implies (²( = pdl (p) - ((n) together with the definition of the convex conjugate, and
[p)( [[)) =
with Danskin's 's theorem
21 and the inverse function theorem. Note that this identity is often referred
as Crouzeix's 's identity 19 Here, have
[2 -mm - and μ (0.g(e- if has separation margin m 0, [ E (-00, (co) and 1a E g0, otherwise,
by noting that g(2) (2) (6")(-2) is nonincreasing. With this primal- dual relationship, we have
(3) = pž (1)) and (x"())) (=))
by the definition of the convex conjugate and Crouzeix's identity. Now ready to apply Lemma 12] which yields
(E) Cas" for (0,
where
((²))
Φ(u)
Cs == g(E (z)
0: = sup
ga and = (e)).
mE(0,e] (p)
Since the choice of Eo was arbitrary and Im(g) Im(()")) dom(d') S [0, 1]. we can choose such ē E (0, 1).
1]. if we have L(wa) E, there exists E [n] such that (((w,, 2:)) > Then, we have for this specific E [n].
Proof of Theorem 5 For a fixed & E -
(Wk: zi) < 5- (E) g((We, 2;)) 2 (c))
(l is strictly decreasing when L > 0 by Lemma S
(g is nonincreasing by Lemma g
This implies that
1 Σ o((wk 2,)) (1)) - gg(( 2x)) n JE(n
1 - (e- (s))
G(wx) =
(9)
holds while L(Wx) ) is e-suboptimal, that is, L(Wa) >
Next, fix wo = 0 and consider the case where L( L(W+)& > E holds for all E [T 1]. By Lemma g
Lemma 19 By Lemmas 11 and 19
take Gunin g (E)) (noting and
have
mg (e- (E)) T
(Wr, w.) (Wu, w.)
(Lemma
(WT, w.)
(with the choice of wo 0) (the Schwarz inequality with ||w,|| 1)
I|wrll
AVP(721))) + n/C
(Lemma 19
7
24

---

By reorganizing and applying Lemma
13 we leverage the primal-dual relationship to have
T1 4
1 + Cs "
T
+ Cg
71
?2
(t-1(s))
72
where Co is defined in Lemma 13 Therefore, L(Ws) is e-suboptimal after at most
n
4A/p(72nt)
+ +G 8-a
(= T()))
Co
7
iterations. That is, if > T(s), the gradient lower bound (9) must be violated some E [7]. and for this i, we achieve L(w.) S.
Finally, verify that Cs defined in Lemma 13 matches 3 By introducing & as the dual of μ such that
$ (')) and f == (d))
have
8 E= (n))
(g is invertible when g()) 1)
= (2)
( = (z)) = g(-)) implies -(()) = -2)
= (z)( (p),
where the invertibility of g can be verified through the differentiability of g as Lemma 13 (by
relying upon o" > 0 in Assumption 3A). and the last identity follows by the definition of the convex
conjugate. Plugging this into Cp deñned Lemma 13 we see that matches Co in (3) Thus, we have proven all statements.
L
C Extension to the stochastic gradient descent
We discuss the extension of Theorem 5 to the stochastic setup. We consider the constant-stepsize online stochastic gradient descent (SGD) follows:
W++1 == W. (w,)). where L,(w) = (((w,(((WW)) y(x,), t 0,
(SGD)
for a loss function é: R + Rzo- Here, (Xe, Ve Ve)2 are independently and identically distributed according to the following assumption.
Assumption 4. Assume the training data (x4,81)ez are independent copies of (x, y) following distribution such that
||x|| S 1, and yı E {+1}, almost surely;
2. there is 7 > and a unit vector w. such that (w,; 21) Y for Ze == yt almost surely.
Proposition 14. Suppose Assumption 4 and consider (SGD) with stepsize rj > and wo 0 under Fenchel-Yourd loss l satisfying Assumption 3 and additionally having separation margin m > 0. For arbitrary 5, E (0, 1), define (a,, Co) as in Eq. f.r which we assume a, Co (0, 20). In addition, for arbitrary
E), define
Mn == e -- ?
4m + v/gg)
32M² 4.7 In(1/8) 8M ln(1/))
and 1. :==mmm maxx
62
Then, if we run SSD with T iterations such that
2a
(m
N. where N
Cg E-a
Cor
then we have min (w,((w:)] < with probability at least (1 8)..
Before proving Proposition 14 several auxiliary lemmas are presented. Since the proof of Propo-
sition [4closel follows Theorem 5 the following Lemmas 15 and T6 are almost identical to the deterministic versions (Lemmas and 19 respectively), and hence omit the proofs.
25

---

with any stepsize 0 under Fenchel- Young loss that satisfies Assumption 3A Moreover, assume that there exists [0,
Lemma 15, Suppose Assumption 4 and consider (SGD)
such that we have non-trivial lower bound g Ww. Rx)) Jmin O. Then, we have
Mimin
(We, W.)
(Wo, w.).
Lemma 16. Suppose Assumption 4 and consider
SGD
with any stepsize nj > 0 under convex and For every 2 1, we have
nondecreasing loss satisfying Assumptions 3B and 3C
4 pl + CCC
Iwwll
The following concentration result is an additional argument that we need in the stochastic case.
loss that satisfies Assumptions 3A and 30 Let Zo.....Zu. 7t-1 be the independent copies of data z. yx following Assumption We introduce the filtration (Ft) where Fk is a a-algeera defined on Z1....; 7h.
Lemma 17. Consider (SGD) with any stepsize nj under a Fenchel-Yours
and let H = E((Wx) Zk)) ) be a random variable, where Wk an meessuaalee random variable. We write St = Ex=o H& for random variable standing for the accumulated loss, and let S: = -t/tt. Moreover, we introduce the following assumptions:
(Bounded mean) 14: B[H+|/Fs11) M for h O,...,t t 1.
(Bounded variance) Var (R-)) o² for K O,...,t
Then, for any E > 0 and 8 (0, 1). if we have
E S
32a In1//) 8M (MIn(115)
and 1 max
(10)
8
then we have S, s/2 with probability at least 6.
Proof. First, we apply type of the martingale inequality, Freedman's 's inequality [22 Theorem 1.6]. Since B[H, ug -x is the mean-zero martingale difference with the bounded variance o².
Freedman's inequality is applicable. Then, we have
u
Pr < E[S]] - u} S exp
2(Mu + to
Equivalently, we have the following inequality with probability at least
8:
S > E[S.] v 12 (1/8) + 24o2 In(1/)) - M ln(1/8
[[S v 2to (1/5)) - 2M ln(6)))
Dividing by we have
3
S
20 ln/5))
2M (n(10)))
>
E
4
2'
where we used the conditions
I00 at the second inequality. Thus, the desired inequality is shown.
Now ready prove Proposition 14 Overall, the proof consists of the perceptron argument and the concentration property.
Proof of Proposition The first step is establish the concentration property. To apply Lemma we confirm the bounded moment conditions. For the mean E = B[(((wE, [x)
17
where F i is the r-algebra defined on { [21)/=1 k-1
we have
E[ Z4)) & E(e( w & Fx-1)
(E is nonincreasing and | < 1)
4m + n/C
(Lemmas 9 and 15
Ma
26

---

For the variance Far(H&|FR-a we similarly have
(F-1)
B[H
- l 4m + n
M
Note that these moment bounds hold uniformly for any By plugging M Mny and 0² M into Lemma 17 if we have
fo+
32M In(1/8)
8M In(1/8)
E ([La(Wa) >E and t 2 max
7:7
(11)
g2
then we have
1o+t-1 (ww)
L
with probability at least 1 - 8.
to
2
Let us use this concentration argument. Split the interval [0, into length-t sub-intervals (for t satisfying (IT)) such that
[0, = 00, f t 2t
[2t 3
U (NN 1)t Nt - L Tj. (12)
T
TT
Consider the scenario where EL (w:)] holds for all k E [0, and focus arbitrary sub-interval I, Since we have to Σxez, [[[+(wA)) > E, the concentration argument implies that
gs EKEI, La (w(w)) ) > e/2 with probability at least 1 - 5. This further indicates the high-probability
1
existence of kı I₁ such that La, (Wx,)= > e/2. In this case, have g( (W (n,)) (e/22
for this specific kı E Ir which can be seen in the same manner as the proof of Theorem 5 Since this
concentration argument does not depend on the sub-interval choice I, there exists set of indices
{ki [K) such that each of ((WA, 2x)) 2 ((=2)) holds with probability at least
Next, we invoke the perceptron argument. Omin (((-)(E/2)), have
By combining Lemmas 15 and 16 with the choice
mg (e ( N (WT, w.) < |WT|| S PVP(7²n11) + n < 4m + n
with probability at least (1 8) where we additionally used Lemma 9 at the last inequality. By applying Lemma [3 at the left-mos, side, we have
mm (
4m + n/C
N
7
which implies
2n
4m
C. g-a )
N <
(=)).
Co7
Therefore, N > ((s) (or N()) -t), with probability at least (1 ([-6)- 8, we have ([L)( S E for some & [0,
Finally, we need verify that Cs defined in Lemma 13 matches but we skip it because it can be confirmed in the same manner in the proof of Theorem 5
C.1 Comparison between GD and SGD
Whereas the iteration complexity for GD given by Corollary i T ?(e=a), the iteration complex- ity for SGD given by Proposition 14 is T (e (()+))) Hence, the SGD rate is significantly slower than the GD case. This deterioration is because can observe non-trivial lower bound g( zz))
27

---

after every t" bounds, and hence the total iteration number amounts to Nt 00== While this apparently looks a big bottleneck, note that the GD rate is T Z ne if we explicitly write the n-dependency. Since (SGD) consumes only one fresh sample at every update (while (GD consumes n samples), the extra complexity N 92(= 2) appearing the SGD case compensates for this gap of sample sizes. The GD/SGD rates are comparable in this sense.
?) steps. As in the GD case, we need N = - such non-trivial lower
D Phase transition of large-stepsize GD
We recap Wu al. 63
who shows the existence of the phase transition from the EoS stable
phases.
Assumption 5. Consider a loss l E Ct (TR) that is convex, nonincreusing, and E(+00) = O.
A. Self-bounding property. For some C3 > 0, g() Col(.) and
((2) ((x) l' (z) 2)) C3g(2)(2 2)² for and x such that x2| 1. Exponential tail. There is a constant C. > such that {(z) S Ceg(2) for 2
Theorem 18 (663). Consider (GD) with stepsize vj > and initialization wo = O under a loss satisfying Assumptions 3B and 3C and 5A Let T be the maximum number of steps. Then, have
the following:
The EoS phase. For every 1 >> O, we have
66 p6 + n,,
Σ L(Wn) S
872211
The stable phase. If < T is such that
E(0)
L(w.) S min
(13)
403''
then GD is in the stable phase, that is, ([(w)))T decreases monotonically, and moreover,
I(w.) < p(> 2 s))
2 - (s,
Phase transition time. There exists a constant C₁ > that only depends on Cg, Cs. and E(O) such that the following holds. Let
+/ (C1(1) + n))
C1 (41++ny)) m)m] where +(A)
X
17
P(A)
T S T, 13 holds for some S T. Moreover, if additionally satisfies Assumption 5B and there exists C2 > 0 that depends C., Cg. C3. E(O), and such that improved as follows:
C2 max nn.
722
The proof consists of Lemma 19 (the EoS phase), Lemma 23 (the stable phase), and Lemmas 24 and 25 (phase transition time). respectively. Most of the results in this section have already been provided in Wu et al. (63] We restate the statements and proofs here to make the paper self coff-contained, and moreover, simplify the statements from the NTK setup the linear-mode case to highlight the essential structures.
Lemma 19 (EoS phase). Suppose Assumption and consider convex and nonincreasing loss E
satisfying Assumptions 3B and 3C For every 2 1. we have
L(wR) < [6 p()p((2)) T)C
8
and
w < 4yp((2mmt + n
28

---

Proof. By invoking Lemma 10 with the choice of 0
vp((21tt)
we have
Wr u||?
1 Σ
1
[(wx) S ((+0)
0 +
21yl
1
2xpl
27
p()2ntt
1
+
0 +
(Lemma 7
2
2np
27
which implies that
|| w. S I/w - u/l + ||u||
21()
0 7T0
nCg 2
??
24
Pmt
'/O'g
+2
0
(Va+bs Va Vb)
27
4v p())
+ nn
7
and
p()2m1) I(wx) -
0+ + '/Cg] 2
Σ
+
t k=
2nt
27
(())
(2 ( + r)(')
81
(2(1 + /2) v p()21))) + n)C
(a² + 12 s (a+ for a, b 2 0)
p() + t1g'
2nt
Thus, the proof is completed.
Lemma 20. Suppose Assumption 2 and consider a convex and nonincreasing loss & satisfying
Assumptions 3B and 3C
Then, we have
G(ww) S pV + Cg t t T.
72
k=
where G(w) is defined in 66.
Proof. By the perceptron argument we have
(We+1, w.)
(We, W.) 17 (VL(Ww). w.) = (We, W.)
(((w. zi)) (w.,z.)
2 (Wz, w.)
79
(((w,,
(Assumption 2 and note -())) 2 0)
n ==1 (We, w.) (wW)).)
Telescoping the sum, have
1
Σ G(we)
(Wr, W.) - (Wo, w.)
||wll
4 p(722t)) + n
yt
72t
k=0
where the last inequality is due to the parameter bound in Lemma 19
29

---

Lemma 21 (Modified descent lemma). Consider a loss satisfying 5A such that
Suppose there exists s < T
L(w.)= S 40
then every E [s, T) we have
1. L(wi) - 1/CC))) and G(wi) & 1/(4Cnn) I(w(11) L(we)= - 3n [VL(W) - L(we).
where G(w) is defined in (
Proof. We first show that Claim implies Claim 2. By Assumption 5A we have
[((we+1:2)) z()) _ e((w,, 2.)) + fl (((w,, z.)) (We-1 W,,z,) + C29( (we(( 2,)) (We+1 Wes 2,)
(((w,, 2.)) + El ((ww, 2:)) (We-1 Wr, zz) + Cag((we, 2i)) (wr; [i))] woll? Taking average over E [n.] we get
I(w++1) I(w:) + (VI(ws), W++1 - w.) + CsG((w))lweH) w L(we) /l; C
I(w+) (w;)l - -= V[.:)11
(Claim
311
L(wi) 4
|VL((:))
which verifies Claim 2.
Next, we prove Claim by induction. The base case = s holds by Assumption 5A as follows:
1 7 Σ g(( (We. 2;)) S
a Σ Col((we, = CoL(we) S 4Cgm
G(ws)
(14)
To prove the step case, suppose I(wx)= 1//(433) and G(ww) S 1/(4C for 8,8 1....,t and prove them for &e t 1. Since Claim implies Claim 2, we have
1
L(we+1) S I(w,) ... S L(ws) S 4C3r
Since G(w++1) S C3L(w holds as in 14). we have
1
G(w+41) I CaL(w1+1) S
4C
Thus, the step case shown, and claims are proven.
Lemma 22. Consider nonincreasing and nonnegative loss l. For every such that
L(w) 1 {(0)
n
we have yi (W,x.) 2 0.for [n].
Proof. See 63 Lemma 31].
Lemma 23 (Stable phase). Consider nonincreasing loss é satisfying Assumptions 5A and Suppose there exists s < T such that
3B
{(0)
L(w,) < min
4C'3m
Then, for every [0, -s), we have
L(Ws+s) < 5
30

---

Proof. By the lemma assumption, we can apply Lemma 21 for s onwards. Therefore, we have for k 2
VL( [I(w+tk) [(w [(Wstk).
(15)
Choose comparator centered at Wa.
u = W, + Ow., 0= v((nttt)
For h S t- - 1, we have
| [s+k411 u/|2 || + (VI(W Ws+k) ( V
4
Wa+h - ull2 2n (VL(W u- +
3 (Ws+k)))
(by 15
Following the same derivation of we can bound the second term follows:
(V[(w+4R) u Wotk) e(07 (W,) I(Wa+t)-
The assumption L(w.)= S E(0)/n allows us to apply Lemma 22 so (We, z;) 2 0 and thus E(O> + (w,, z()) S {(0r) = p(7)()))
where l is nonincreasing due to the lemma assumption. Consequently, we can control the second term by
(V W7L(w++)),u Wota) S Sl(v <((Vp(72()) L(Ws+x).
Plugging this back, we get
[W++41 u/2 < W - u1l + 27| (()221() 2n1((V/((?11t) I(w.- + (WW((WoHH)
4
$ W - ull2 2 n(()2tt) (WWkk)))
Telescoping the sum from 0 to t - and rearranging, get
W|tt
11/
t-1
3| w. u
L(w - 3E( 33133((((P))) p()2nt))
+
2ny
2ny
0=0
((72t)
3|| u/1
+
(Lemma
22t
2n7t
Finally, we can show the claims follows:
((w++k) S 3 p(721)t)
3/|w. u// 2
7Pml
2npl
9 (n))
2 7P
< 5 ((2211))
22
By Lemma 21 L(w,) is nonincreasing for / 2 and thus we have
L(W++1) < L(w.+k) < 55 ((22))))
H
77
k=0
31

---

Lemma 24 (Phase transition). Suppose Assumption 2 and consider a convex and nonincreasing loss È that satisfies Assumptions 3B and 3C Define
A
(0A)
A
p(A)
Then, there is C 0 depending on Co. CB. and E(O) such that the following holds. Let
(C(n) + m)) C(n + m))
7 max
IfT T < T, then there exists
[0, r] such that
((0)
L(we) S min
AC33" n
Proof. Applying Lemma with we have
2
Σ T(wa)s
16 (V + Cng
3
p()
v2
87
V2
~/1
4
V72
Choose such that
Japr 2 max { 40 (5 ( (44C3 + }
It is clear that
1
p())
z²
min {(2)
(A)
a decreasing function. Then, we have
p(7211r)
3
3
1
S
V2
7/
V2 V ((F))
v2
18[40 + n/((0)]
2
/A33 + n/((0)
and
V2 C
1
1
4 Vn2
2
/
/4C3n=n/E(0 - n/E(()
These two inequalities together imply that
{(0)
((wk) S 40%m + n/e(0)
min
4C
K=
which implies that there exists s S r for L(w,) satisfies the right-hame side bound.
Lemma 25 (Phase transition time under exponential tail). Suppose Assumption and consider
nonincreasing loss & satisfying Assumptions 3B and 3C and Furthermore, assume 1j 2 Then, there exists C 0 depending on Ce. Cp. Cp, E(O), and n such that the following holds. Let
? max (n, Inn).
If T S T, then there exists E [0,7] such that
((0)
L(w.) S min
40'3" n
32

---

Proof. Under Assumption 5B
we have
((2) S Ceg(z) = Cx)(
for 2 2 0.
which implies
(()) {(z)
- -0 for 2 0.
Integrating both sides, we get
In (n In (()) + [. /- ((())
da & In (()) - C,t2, for 2 2 0,
{(()
which implies
(()) {()) exp(-
for 1220
Using the exponential tail property, we have
p()) min x((2) + 2 S Ae(C,, + C2 S ((0) In2
=EB
Applying Lemma 20
we have
G(w)) v 4V/()22TT) + C/Cg
7/T
K=
4v ((0) + C2 + C2
4/0(0) + 4C. In.In(72 + C
(Va+bs Vo + vb)
4C, In(??T)
4Ce
4 ((0) 1
+
7PT +
7
7²
7
727
Here, we take C' > 0 depending on Ce, Cg. CB, {(O), and additionally such that
22r 2 C max (n,n)
and
min
8 Co f
In C C
(1 + Cg 4C, + 440((0)
This choice possible with sufficiently large C > e because (In C)/C strictly decreasing in C' 2 toward zero. Such C' enables us to have
G(ww)
4C. (In In max (n. n3) CC 4C, + 4v/e())
Caxx {n.
7
4CalIn C + Iun) C, + 4C. + 4/((0)
(n 2 1)
Cmax (n In 4C,(1 +Inn) + C. + +CC, + 4V8(0)
(In C2
C
max [1.2] n}
min
[C..z' : C.
max (1/ m}
1
{(0)
<mnn
4C.C331
Can
33

---

From this we have some S T such that
(0)
G(w,) S min
10n Can
This ensures that for every i E [m].
C.n < g(0)
((0)
(( zi)) S G(w,)
g (w.. 2.)
where the last inequality is due to Assumption
5B
The above implies (w., 2,) 2 0 since g(:) is
nonincreasing. Thus, we can apply Assumption 5B for (Ws: zi) and get
(((w., 2i)) s Ceg((w.,z;))
Taking average over E [n]. have
I(w.) S C.G((w)-
We complete the proof by plugging in the upper bound G(w,).
E Separation margin and self-bounding property
In this section, we discuss the relationship between separation margin and the boundinnn property. First, we show that loss function does not have separation margin if it satisfies the self-bounding property.
Proposition 26. Consider a loss t: R + R that is continuously differentiable and nonincreasing, and satisfies f(zo) > foror some 2o E R. If satisfies Assumption 5A then does not have separation margin.
Proof. Choose any E (0,1/Cg). The convexity of é implies that g(2) = (2)) 2 ((2) {(= +
for any & E R.
E
By the self-bounding property (Assumption
5A we further have
{(2) {(= + E) S g(z)= & Csl(z).
8
Solving this, we have
{(z + 8) 2 (1 -1- CgE)(()...
Thus, {()) > holds, we additionally have f(= + +) > for e E (0, 1/Cg), and we conclude that l cannot have separation margin because > 0 holds on the entire R.
Next, we argue that the converse of Proposition 26 does not hold, that is, even if a loss does not have separation margin, it does not always imply that & satisfies the self-bounding property. A counterexample is Fenchel-Young loss generated by the following potential function:
((u) /"" x (p)dp, where & is the standard normal CDF (xx)
1 1 + erf
2
/
and orf is the error function. The generated Senchel-Youne loss is relevant to the probit model 40 because ø' is nothing else but the probit link function prevailing in generalized linear models. Hence, we call the generated Fenchel-Youn loss the probit Fenchel-Young loss for convenience. We can have concise form of the probit Penchel-Young loss:
((2) o² (-2)
(0) (C))g
$(C)dc
34

---

(Ç0(() + (() --2((-2) + (=22).
The probit Fenchel-Young loss does not have separation margin because ('()) (x) - as j 0 (see Proposition However, does not satisfy the self-bounding property, To this, have
g(2)
(z) ((2)
{(z)
4 (P(-)
-24(-2) + (-(2)
((2)
(8 = -2
+ +
which implies
lim g(z) lim
(3
(L Hopiiaal's rule)
20000 (())
Σー oc ((2) + 20' (()
(3(2)
lim
2
(()
(2)
lim
(L'Hópital's rule)
20y-00 (1(3)
(2)
lim
(2)
20.
Hence, g22) cannot always be bounded from above by {(2), that is, the self-bounding property not satisfied.
F Omitted calculation for examples
Here, we compute for each cb
lim (p)
(())
m40 (m)
(p)(
to estimate the power a of the convergence rate provided in Theorem) 5 by making the error parameter in 3 arbitrarily small. Correspondingly, we compute
/
lim #40
(uo' (μ) (1))aa
estimate the constant Co the convergence rate, verifying that C. neither degenerates nor diverges for arbitrarily small error parameter ह > 0.
Before proceeding with each example, provide rough estimate of for loss functions without separation margin.
Lemma 27. Consider a loss satisfying Assumptions 3A and 3B that does not have separation margin. Then,
p()) S + A.
Proof. First, we rewrite dual form. By introducing the dual variable μ of = by
2 ('()) and == (cb (s),
we have
P(A) min Ae(2) 22
sER
min A (z) + 22
35

---

min A(po'(4) x(14 + (0' [=[
where we use the definition of the convex conjugate (0(2) = μmz - ((4) at the last identity. Now, we write the objective as R(j)::
R(x) Mpddl +(H)) + (0'
Differentiating R, we have
d">0
R' (u,,)) = [Apt 22'((4))0""(
e'(,,) = - -4
the minimizer fl, of R. Plugging this back to R, we have
p(A) R(p.) = R( Mr (-2 2/ -llu)) +
(-
A (2) --
= -d((L)) S - ( X
where the last inequality owes to that a convex potential satisfying Assumption Dis minimized at the uniform distribution μr, 1/2 [1] Proposition 4].
By using Lemma 27 we can simplify the convergence rate of GG given by Theorem S for a loss that does have separation margin. Note that the following convergence rate is not sufficiently tight due to overestimation of by Lemma nevertheless, the provided convergence rate convenient when we do not have an access p analytically.
Corollary 28. Under the same setup with Theorem we additionally assume that & does not have separation margin. If (a, C³) with 3 satisfies a, Co E (0, and
20 16[-0(1/2]m² =-20 20 for E (0,e), T>
C272
C37221
then we have L(WT)= E.
Proof. Combining Theorem 5 and Lemma 27 we have the following convergence rate:
T 4ny -(1/2) VT+ Cyne
COTYT
O27
Defining
4 -b(1/2)=
COT/11) and b = Cyne-a
Cop2
we have the following inequality in T:
T (a² 2b)T + b2>000000 0.
This can be solved for T 1:
a² + 2b
2h
T
+ 1
a + 2h
S1
for which T a² + 2b is sufficient. Thus, we have shown the statement.
Throughout this section, repeatedly L L'Hôpital's rule. When it is used, we notate by (#).
36

---

F1 Shannon entropy
For the Shannon entropy ((4) = Junn + pun
(1 - (1) In(1 - 11), we have
1
('(n) In In(1 14) and ("(n)=
1 1 14"
which imply
lim ('())
((1))
In =
Jeln μr + (1 - (1) In(1 - 1t)
1
lim
(d)(
1 (H)
nJ0 1 I-p
pm 1am---pl | (t)
μ
p. j 1 (2) flm 1
p In p)
lim In
#30
1
-
In r-a
Inn
11)
lim
#40
11
lim
and
1
lim
lim
A40
ud'(1) x(1)
In 11 In(1 u)
In (1 u In(1 11)
lim
1b
Inn[1 14) 2/1-
lim 16.
P30 In 14)
lim(1 1 11)
p40
1.
Finally, we derive the convergence rate for the logistic loss. Plugging a = 1, Co = 1, Cg = 1, and p()) < (A) < (A) to Theorem
5 we have
n 72
(4221((221TT) +1 --1=
4v21n((21)
4v2
ne
+ +1+
In T
71
11
72
Dividing both ends by In T, we have
T
4 (4221(771)) +1 [
1
4/2
ne
T
17
I
72
for which the following is sufficient when T 2:
T
4v21n(72m)
4
ne-1
+1
T
In
2
72
4 4 lo2, ())
1
4
nE
"
1n
"
By ignoring the logarithmic factor, we have
4 4 4V2log,
1
4
ne
>
+
17
In
7
7.2
37

---

F.2
Semi-circle entropy
For the semi-cirele entropy ((H) = -2v - n), we first derive the analytical form of the corresponding Fenchel- loss. We have
('(1) - 2/1 -1
and ('()) 2[u(1 4))8/2
vu(1 - (1)
The dual transform ( given by
(
thanks to the Danskin's theorem 21 Then, we can derive the Fenchel- Young loss by the definition of the convex conjugate:
= (-z)= ( -2 22 +
2
Next, compute the loss parameters and Co respectively follows:
2n-1
lim (1())
((u)
v vu(1-n)
2 M(1 11)
lim #30
#40 pal"
sel (
m(2x-1)
2lu(1=1)) 3/2
Vu(I-H)
1 2(1 11)
lim 2(2 1)(1 11--1)) (4) AJ0
2p 1
2,
and
lim #40
lim
2p-1
+ 2 1(1 1)
V (1(
lim 140
14)
To estimate p(A),
P(A) = min Ae(2) + 22 sER
Ind
VIn² X +
5
+ In?
(a In
2
2X
+ +In² A
In + VIn +4
5
2
where we used
X
21
2
In? A
for
In
In Vn
X4
Finally, we derive the convergence rate for the semi-circle loss. Plugging a = 2, = 1, C. = and p(A) & 52 X) to Theorem 5 we have
n
4
TTT In(
(
+1
1
-2 -
E
2
10
21T In(7PnI")
+
ne -2
7
222
38

---

for which the following is sufficient when T' 2 2:
2v10
2²
ne
T>
+
In(2
72
Subsequently, we follow the same flow as in the proof of Corollary 28
Defining
2v10ne-2
7&11
ne 2 7/
?-1
V
In(2??n)
and b=
we have the following inequality in T:
T (a² + 2b)T + b² > O.
This can be solved for T 2 1:
a² 2
2b
T
1
2
a² + 26
$
for which T> a² + 2b is sufficient, namely,
40n² 2
2n -2
T
4
2121n(2221)
72
sufficient. Thus, the convergence rate is =
F33 Tsallis entropy
For the Tsallis entropy
(()) 19 (1 (1-H)* 11)
q 1
define
6o(p) N² + (1 - 11)9 1,
6 (1)) 1 (1 - 1-1
(2(14) = n2-2
2 (1 - (1-1))- 12-022
When 0 < < 2 + 1),
('(N)
[
(1x)
quoi (1) do((4)
lim
lim
p20 (
(1))
4(q 1) 14o 22(1))
112
1
qudi(()) )o((m)
lim
b(p 1)
140
+ (1-m]
2-g
1
qupb1 (11) @o(H))
lim
1)
140
419
1
gΦl (1) + 4(a 1))(2(()) - goi (w)
lim
91 1)
#40
qua-1
1
11 9--1
(1 11)0-22
lim
140
118-1
(1) lim
(g 1)11-22 + (1 11)0-2
(g - 2)(1 - 11)00-11
#40
(q
11118-2
1 lim
1 P 2-9
3-97
(q 2) i-
q 1A0
( 1
q
39

---

In addition, we have
lim 140 ( - ((1))////
(9 - 1/
lim
lquei (14) 2 (2))
quen (1i) so(())
1//
= (q - 1)
lim P40
100
9/1(1 11)9-1
+ (1- 11)9 - 11
-1/9
(q - 1)
1
lim
14.
119
q(1 11)0-1
0(9
1)/(11 - 11)0-2 9(1 - 11)0-1 -1/4
b 1) 1/0
q
lim 140
9pa
(q - 1)
(q - 1)
lim p30
1
(q 1)
(q 1 + 0) 0//1// 1/0
= 1.
When 2,
lim o'(H)
1 o(w)
#40 pd² (p)
(M)
quii - (o
lim
9(q 1)
140 )b(())
112
qa (1) - sb((())
lim
q(4 1)
1410
122
9(q 1) lim g/40 (1 - -11)8-2/11 - 119 -(1 14)9
112
a-qu6611 - (1 - 11) + (q 1)(1 - 11)8-22)
9p--1 + 9(1 - -1)8-1
lim #30
11
2/1
11922 2
+ (1 1-)
lim
#40
2
1
2'
In addition, we have
quon (1) - (d)_m)(()) }
1/2
lim
(g 1)1/2
lim 140
#40
(1) 2/1))1/22
412
qoi (1) + +(9 - 1)H12(11) (92((1)) 11/2
( (g 1)2/2
lim m20
2/1
a(q 1)
+ (1 -1) -1/2
(g 1)1/2
lim liml
2
a50
9q(9 - 1)
-1/2
(g 1)1/2.
2
2
$V q
40

---

F.4 Rényi entropy
For the Rényi entropy
1
Φ(4)
In lut + (1 -1)9.
9-1
define
6 (1) = 109 + (1 11);
6 (w) = 109 - (1 11)0-1
(2(11) 1892 (1 11)9-2
(2(11) pM-3 (1 11)03
When <q 2 #
('(H)
((x)
lim
#40 (
uD (1)
(N)
g- In ev(u)
= =lim
m40 (g - 1) p) (24
(1))
t1( - p po(a)
(sa
(6(H)
Φ (1) In po(N))
-ii
p.00 (g 1)
(M)(K))
p (H) (a(44)
quoi (N)
(1)
lim v. (0(4)
In (1) u
lim 140
(g 1) lim
((2(()))
q 1ii
1ob (0ff))
(14
- - -1
(g . 9-
9
1
where we
2-9
Φo(H) +1,
pQ2(1)
1
I-
P
1, pdi(H) p²
(1 1--))-- + 0,
1
(1())
2-q
P
1-
and
In co (1)
(8)
86(1)
uΦl (1L
Φ0(H)) u (H) + (1())
(1())
nen (4) + (1)
g
( ()) (1)
(q 1)
+1
q
(g 1
1.
In addition, we have
/ (μ) 1/4)
lim n10
129
1/9
uso uv (1) - (p
41

---

(q 1)
1/9
lim
qudn u30
(1) (1) In (o(H))
(u 1)18
1/9
lim
(Øo(K) + 1)
1g0 quci (n) - (2) In (4)
910-1
1/9
(
(g- 1) lim
140 q (11) + 9(9 1) (1)
q0h (4) In (o(()) 901
121
1/a
(g
1) lim 1io (q 1) - 11 In @o()) |
1/9
(9 1)
(g lim
n:00 (g - 1))2(1) + (q - () 2) (14)
(زر
(g (1)2(11) In do (m))
dol(e)
[1 + m 2- + - 2) mm)
3-01
yoh (w)
[1 + (1 2- "I In so (1))
1) tn(
lim 140
(A)
+1+ (q 2)
0 1. -1/2
1,
where at (A) we used
(1)2
112-901(10 (N)2
11 (00())
= 119 2(1 - 11)9-11 1 + (1 11) 10-22-2221 2
-2(1 - 4/ c + (1 11) 24 11299
(1 (1-1)20-2 2((1 - 1) 118-1
n9-2
(2g - 2)
11) 20 2(q - 1)(1 11) 200- -2 1)(1 - 11)01110 100
(q - 2) 2
2(g- -1) 1)
(1 11) + 4 1 (1 -H))10-2
9-2
(1 - (1-1)22-
14-3
2(g - 1)
(1 - 11)-1 1 + 110-1 1 - (1 - -11)p1822
11
-2
11933
[ H 1-9
2(g 1)
(1-p)
11 + 11² - (11 - 4)l
2 2
0.
When q 2, we leverage
(0()) = 24²² - 2/ + 1, (1))) = 2μ - 1, Φ2(u) = 2, bo(u) = 20 (w), (i()) =2 2
to have
(1))
1 ((1))
lim
a5o (H)
2udr (1)) 2 (14) In (o(a)
-iim aJo
p0(1)-
4422 (M) (1)
2pch (1) - (n) In @o(H)
= -lim
(go + 1)
#.0
442(00(11) - (1)))
(p)) + 2p] - 24h (n) In (1)) - 2 (1)
lim
4(2pl0o(u)- - (4))))))())))))))))))))))))))))) + 20 (1) 462(1101
42

---

2μ 01 (4) In 00(4)
lim
#50 Ap) - Φ1(22² (u01(1))
2 21n Φ0(())
(0)
(1((4)
lim
1i00 4(0o(u) 01(1)3 1v) [ 4u(201 (+)) 401 (1) Φ1 (1) 2pj
1 - In (0()) - (,(4²²
= -lim
a.0 ((( +1 (1)) - 4 (pt) 2p221
(p) 400 (1)) (N) ())))2260)) 2 (11)
(1)
lim
6o(m)
(1)²
P.0 2[2 (u) 401 (11) - 40, (4) - 8u1 4p}
lim (1(
(0)(w) - -01(1)
(0))2
6101 + 2p1]
In addition, defining
2uchi (n) Φ In (o(() Φ
we have
1
(5 = lim
[ndd (p) 6(4))1/3
lim
iippiiss & = lim 15-1/3; will use this below at ($) 140
1400
(pddil))-ooffh In vo(())
1/3
60(1))
2/3/3
4 limn (H)
p40
+ 2/
20u(u)) (u)²
(b1(m) (o())
dolp))
(1)
22/3
-lim M40
4
1((0(11)
Φ1 (1)21
./4 2/ 2nho (w) 201(2)²
(
lim
@o(P)*
140
(vo(u)) 21 (14)2 + 1 (1)) - 4ah (n)) C1/3
21) - Φi (1
lim
140
[do(1) o1 (1)2 - 2ud (1)]51/3
2/2/3
lim
p40
2
p6o(H)(oo(1) - on (1)2) -3 (o
(000))01(11 2 (11
2/2/3
lim p40
2
u(0o(1)) - di (1)²2]
(0(1) (11) 2pco (n)
2 (o(u) (b(11²² (uS 1/8-1
2p
lim
+ lim
k403 3
1
#40 (1(14) Φi (n)2 2 (11) 113
(5)
2
limm(- 140
2/1)
+
1
lim
3
{ 410 2 - 3/c
4
1
2
3
2
S
which implies
g =
352
+
28
By solving this, we have
1/3
3
lim 140
=
lu (1)) - ((()))13
43

---

q=2
q= 10
q= 20
6 2-
2-
0
0
0.0
0.2
0.4
0.6
0.2
0.4
0.6
0.4
0.6
0.2
0.6
/
Figure 3: For the pseudo-spherical entropy, a(u) 10 (1)//o" (1-)(u)//ml) (n)) is shown.
F,5 Pseudo-spherical entropy
Consider the o-pseudd--ppherical entropy (11) [n4 (1 1,)9)2/9 for q >> 1 24 It is also
known as the g-norm (neg)entropy [12. When 2, it recovers the spherical entropy associated with the spherical loss []]. When g oo, approaches (5) max {u, pp] - 1, which the
Bayes risk of the hinge/0-1 losses 15 As seen in Figure the limit a (in (3) does not exist, which
indicates that we cannot guarantee the e-optimal risk for vanishingly small
44


Reviews:
[{"review_id": "8lS1phTr8w", "reviewer": "Reviewer_Fpmo", "summary": "This work sits at the intersection of two major threads in optimization for machine learning:\n\n### **1. Convergence Analyses for Specific Loss Functions**\n\nOne line of work builds on the success of convex optimization theory to develop fine-grained convergence analyses tailored to particular loss functions—such as logistic regression—that arise frequently in machine learning. The goal is to go beyond general smooth convex convergence rates and exploit structural properties (e.g., higher-order smoothness) to obtain faster rates or design better algorithms. A representative example is the [self-concordant analysis of logistic regression by Francis Bach](https://www.di.ens.fr/~fbach/bach_ejs_self_concordance.pdf), along with several follow-up works. These efforts aim to isolate specific regularity assumptions that make certain loss functions easier to optimize than general convex functions. The broader hope is to both explain faster convergence and to inspire new algorithms that leverage loss-specific structure.\n\n### **2. Edge of Stability (EoS)**\n\nA separate thread of work focuses on phenomena observed in deep learning, particularly the so-called *edge-of-stability* (EoS). Empirically, training with a near-optimal step size often leads to dynamics where the model navigates increasingly sharper regions of the loss landscape, eventually stabilizing at a level of sharpness dictated by the step size. Intriguingly, step sizes that work well in practice are often significantly larger than those suggested by classical smoothness-based bounds (e.g., the $1/\\beta$ rule from the descent lemma).\n\nThis raises a natural question: Are the classical step-size constraints overly conservative? And if so, for which functions can we prove convergence with larger—or even arbitrary—step sizes, and what are the resulting rates?\n\n### **Wu et al. and Logistic Regression**\n\nAt the intersection of these two threads lies the work of Wu et al., which revisits logistic regression but does not exclusively use classical descent-based analysis and higher-order smoothness arguments. Instead, they provide a phase-based analysis of gradient descent, identifying two distinct phases: an initial non-monotonic phase where the loss fluctuates but decreases on average, and a second phase of accelerated convergence. This allows them to prove a $1/\\sqrt{\\epsilon}$ convergence rate—faster than the standard $1/\\epsilon$ rate for non-accelerated methods.\n\nInterestingly, this perspective also offers insight into EoS: perhaps the phenomenon is not unique to deep networks, but rather arises from commonly used loss functions, such as logistic loss, which can exhibit EoS-type behavior even in simpler settings. That said, Wu et al. do not discount the role of representation learning and multiple phases in deep models as contributing factors to EoS. Subsequent work has extended their analysis to shallow homogeneous networks.\n\n### **This Paper**\n\nThis paper contributes to both lines of research while offering a fresh perspective on the work of Wu et al. Rather than relying on higher-order smoothness or phase-based arguments, the analysis is inspired by the classical perceptron algorithm. It demonstrates that for a broad class of loss functions—specifically, Fenchel-Young losses derived from suitable potential functions—faster convergence is possible under a \"separation margin\" condition.\n\nFenchel-Young losses are convex and often exhibit desirable properties as surrogate losses, such as better calibration depending on the choice of potential. While the paper does not aim to characterize which potentials are most beneficial from a learning-theoretic perspective, it leverages this class to showcase how convergence rates can improve with a separation margin.\n\nThe paper (along with some previous work) also argues that while the two-phase analysis of Wu et al. offers valuable insight, it is fundamentally tailored to logistic regression. And when the data is separable, the second phase in Wu et al. is less relevant for the downstream classification task. Notably, the paper demonstrates that logistic regression, despite possessing self-bounding gradients, fails to satisfy a separation-margin condition and therefore cannot benefit from the improved convergence guarantees provided by the new analysis. As a result, the perceptron-based analysis can not beat the classical $O(1/\\epsilon)$ rate. This raises the question: Does the accelerated convergence in the later phase of Wu et al.'s analysis \"truly capture\" why EoS is a valuable phase in deep learning tasks? While the paper does not answer this question, it suggests the answer might be no. In particular, the paper highlights that by optimizing losses with a separation margin that enables faster optimization, binary classification on separable data can be performed more efficiently, leaving room for future inquiry into these loss functions. \n\nFinally, the paper supports its theoretical findings with experiments, illustrating faster convergence—and convergence with arbitrary step sizes—for select Fenchel-Young losses that admit a separation margin.", "questions": "I have suggested making certain changes in the weakness above, but these are minor organization changes and won't change my score. They would make the paper more readable though. I have some questions about the results and the extensions:\n1. Does the perceptron based view, extend more easily to the non-separable case? The analysis of Wu et al. seems particularly hard to extend to the case of non-seperable data, and can thus arguably not capture many real world artefacts/noise in the data. If not, can the authors highlight the key difficulty.\n2. Can the perceptron based view, accommodate noise? In general, it would be valuable to address this, as the edge-of-stability phenomenon can also arise with stochastic gradient methods and their variants.\n3. Are there any other natural loss function classes where the authors can extend similar ideas?", "limitations": "While there are no major limitations, it may be helpful to comment on the extent to which the current analysis extends to loss functions without bounded gradients, particularly in cases where the functions exhibit higher-order smoothness. More broadly, the related work section could be strengthened by including discussions of higher-order smoothness assumptions—such as quasi-self-concordance—which are notably absent. Additionally, the paper only studies exact gradient descent.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The Perceptron algorithm and the analysis of its mistake bound are classic theoretical results, often taught early in foundational machine learning courses. Demonstrating that this analysis extends to a much more general setting—namely, to Fenchel-Young losses—has both scientific and pedagogical value. This alone provides sufficient justification for accepting the paper. Furthermore, the paper demonstrates that this perspective can enhance convergence rates for specific losses, both in terms of speed and robustness to step-size choices. Overall, the paper is technically solid and clearly contextualized within the relevant literature.\n\nThat said, the writing is lacking in many places, with frequent grammatical errors and awkward phrasings. The entire related work section is riddled with such issues—too many to list exhaustively. I strongly recommend a careful revision of this section, ideally using a grammar checker or editor. Beyond Section 1.1, the following lines contain grammatical mistakes or awkward constructions: 125–127, 135, 224, 225, 245, 311, 329, 330.\n\nSome key definitions, such as that of the *separation margin*, appear only later in the paper, despite being referenced early in the introduction. This creates confusion for the reader—for instance, it is unclear what it means for a \"loss to entail a separation margin.\" Definitions critical to understanding the main contributions should be presented earlier or clearly foreshadowed.\n\nThe background discussion in Section 2 also feels rushed and lacks sufficient context. If the paper is accepted, the authors should consider using the additional page to expand the preliminaries. Specifically, it would be helpful to clearly address the following: *\"Loss X has desirable properties as a surrogate for downstream task D, and our analysis shows faster optimization for Loss X—therefore, we suggest a better algorithm for the downstream task D.\"* This line of reasoning is currently implied but not clearly articulated. While the authors note in Section 5 that losses with a separation margin are suitable for classification, the connection between surrogate loss properties and optimization guarantees can be made more explicit.\n\nIn fact, the discussion around surrogate loss selection and what the authors refer to as \"regret with respect to a downstream task\" (lines 110–113) is not entirely beyond the scope of the work. For example, logistic regression is a widely used surrogate for classification due to its theoretical guarantees and empirical performance. This justifies the need to study its optimization behavior in more detail, even if it does not admit a separation margin.\n\nI also recommend creating a separate section titled **\"Comparison with [59]\"** and moving the relevant discussion from the current \"Phase Transition\" subsection there. It is essential to clearly explain how the results in this paper relate to those in [59]. Because logistic regression lacks the separation margin property, the perceptron-style analysis in this paper cannot yield better than $1/\\epsilon$ rates, while [59] achieves $1/\\sqrt{\\epsilon}$ via a phase-wise argument. As mentioned in the summary, the current paper suggests that the phase-wise view might offer limited insight for separable classification problems, where the optimization target is achieved early. Section 5 briefly touches on how phase transitions might have auxiliary benefits, but these points are not clearly or explicitly presented. Improving the organization and writing of this section would strengthen the paper.\n\nFinally, it would be valuable to elaborate on how perceptron-style analysis might yield useful insights for optimizing deep networks, and what role the separation margin plays in that broader context. While the paper leaves these as open questions, they are arguably the most compelling directions beyond the optimization theory itself.", "was_revised": true, "final_justification": "I am happy with the author's response. I don't have any major outstanding concerns, and as such recommend accepting the paper.", "rebuttal": "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.\n\n**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.\nWe 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.”\n\n**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.\n\n**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.\n\nTo 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:\n\n+ $\\\\|\\\\mathbf{x}\\\\| \\\\leq 1$ almost surely\n+ 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\n\nThe 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.\n\nThis 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.\n\n**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."}, {"review_id": "gNvkLmbgCc", "reviewer": "Reviewer_i177", "summary": "This paper studies GD convergence under arbitrarily large stepsize. Previous studies have noticed that certain objective functions still converge when optimized by GD, even with excessively large step sizes. Researchers have been trying to understand what properties of functions allow this to happen, and this paper adds to this line of research. While earlier work showed that functions with a self-bounding property can make GD converge with any step size, this paper extends the result by demonstrating that the self-bounding property isn't necessary. Specifically, it proves that GD with any step size converges on Fenchel-Young losses with a separable margin, which may not have the self-bounding property. Moreover, this paper instantiates the Fenchel-Young losses with certain examples, including Shannon entropy, full circle entropy, Tsallis entropy, and Renyi entropy, and provided explicit convergence rates for each loss. Notably, Tsallis q-loss achieves $O(\\epsilon^{-1/2})$ for $q>2$ and Renyi 2-entropy achieves $O(\\epsilon^{-1/3})$, both faster than the standard $O(\\epsilon^{-1})$ rate of GD on unstructured convex and smooth losses.", "questions": "NA", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper contributes to the literature by extending the line of research on GD convergence under arbitrarily large stepsize. Previous studies focused on functions with a self-bounding property, and this paper broadens the family of objective functions by demonstrating that the self-bounding property is not necessary. Instead, it shows that GD converges on Fenchel-Young losses with separable margins, which may not possess the self-bounding property. This extension enhances the understanding of what properties of loss functions allow convergence with large stepsize.\n\nMoreover, it is notable that certain instantiation of Fenchel-Young loss, such as Tsallis q-loss and Renyi q-loss for $q>1$ achieve a faster rate compared to the standard $O(\\epsilon^{-1})$ rate. Such result is also new to the field.\n\nIn addition, I find the proof technique of this paper inspiring. Instead of standard analysis that build on some variants of descent lemma, this paper uses the perceptron method. This technique could inspire further research and exploration.\n\nAs a limitation, the current analysis is restricted to the binary classification problem, where the loss function can be reduced to a Fenchel-Young loss on 1d prediction namely $\\phi^*(-z)$, and a linear model where the prediction can be formulated as $\\langle w, x\\rangle$. Extending to a more complicatedly structured model such as deep neural networks will be an interesting (and definitely very challenging) result.", "was_revised": true, "final_justification": "Sorry for the late response, I wasn't aware of the new requirement of this year. I have read the responses from the authors and the comments from other reviewers. I keep my current score as the recommended score.", "rebuttal": "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.\n\nTsilivis et al. (2025) “Flavors of Margin: Implicit Bias of Steepest Descent in\nHomogeneous Neural Networks”"}, {"review_id": "6ienlpLx6t", "reviewer": "Reviewer_7Hzu", "summary": "This paper investigates gradient descent (GD) with arbitrary stepsizes in the setting of binary classification with linearly separable data, focusing on a broad class of loss functions called Fenchel–Young losses. The work extends prior results that showed convergence for logistic loss under large stepsizes, notably beyond the classical “edge of stability” (EoS) regime where standard convergence guarantees no longer apply.", "questions": "1. **On the dependence on the number of samples $n$ in Theorem 5:**  \nThe theorem’s bound scales with $n^{1+\\alpha}$, but intuitively, shouldn't the convergence rate be independent of $n$? For instance, duplicating each sample (so $n \\to 2n$) does not affect the empirical risk $L(w)$, yet the bound would change. Could the authors clarify this apparent inconsistency?\n\n2. **On the tightness of the bound in Theorem 5:**  \nCan you comment on how tight your convergence bound is, at least empirically? For example, for the **Shannon entropy** (i.e., logistic loss), it seems from Figure 1 that **doubling the stepsize approximately doubles convergence speed**, as expected by your theoretical predictions?  Can other such comments be made?\nAlso, when the stepsize $\\eta$ is very large, the theoretical convergence rate saturates at $\\mathcal{O}(n^2 / (\\gamma^2 \\ln 2 \\cdot t))$. Can you comment on whether this behaviour is observed experimentally?\n\n3. **On arbitrarily large stepsizes:**  \nYour results suggest that using the larger the stepsize, the better the convergence rate. But is there any practical downside (e.g., stability, generalisation) to this claim? How is this compatible whith the EoS perspective where GD is initially in an oscillation phase: shouldn't this oscillation phase be arbitrarily long when taking $\\eta$ to $\\infty$?\n\n4. **On the slow convergence for Rényi entropy with $q < 1$:**  \nFor Rényi entropy with $q = 0.5$, Theorem 5 yields a **slow convergence rate** of $\\Omega(\\varepsilon^{-4})$, which seems to align with what is observed in Figure 1. However, **gradient descent on smooth convex losses** typically achieves $\\mathcal{O}(1/\\varepsilon)$ convergence. What prevents this from holding here? Is the associated loss function **not $L$-smooth**, or is some other property lacking?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\nThis paper is very well written and easy to follow, even for readers who are not familiar with Fenchel–Young losses. The presentation is well structured, with key ideas introduced in a logical and intuitive progression. The theoretical contributions are clearly stated, carefully justified, and supported by concrete examples that help illustrate and clarify the main results. Finally, while the experiments are minimal, they provide clear and effective illustrations that support the theoretical claims.\n\n**Weaknesses**\nThe focus on Fenchel–Young losses, while theoretically appealing, may limit the practical relevance of the work. In practice, most machine learning applications rely on standard losses such as the logistic or hinge loss. The motivation for exploring this broader class—beyond unification or analytical convenience—is not entirely clear.\nThe paper would benefit from a more detailed discussion of practical scenarios in which non-standard Fenchel–Young losses might be preferable. For example, are there settings (e.g., structured prediction, robustness to noise, or implicit regularisation effects) where the improved convergence rates offered by certain losses lead to practical advantages?", "was_revised": true, "final_justification": "The paper is well written and the theoretical contributions are clear and justified, which is why I recommend the acceptance of this paper.", "rebuttal": "We appreciate the reviewer for taking the time to provide feedback.\n\n**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.\n\nRoulet et al. (2025) “Loss Functions and Operators Generated by f-Divergences”\n\n**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.\n\nSuch 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.\n\nIn 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.\n\nTyurin (2025) “From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes”\n\n**Q2 (tightness).** In short, we recognize our analysis is not tight enough.\n\n+ _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).\n+ _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.\n\n**Q3 (downside of large stepsize).** \n\n+ _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.\n+ _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).\n\n**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."}, {"review_id": "g9jTwCHgce", "reviewer": "Reviewer_Trfc", "summary": "This paper investigates gradient descent in the edge of stability (EoS) where step sizes are chosen to be much larger than the classical stable regime $1/\\beta$ for minimization of $\\beta$-smooth functions. The main contribution in this work is in extending the analysis of large step size GD for losses that satisfy the self bound property (e.g., logistic) to Fenchel-Young losses (Bregman divergences). In particular, this work shows that large step sizes achieve accelerated convergence for some loss functions that violate the self bounding property.", "questions": "* Since the authors consider a variant of Bregman divergence, a natural algorithm is to use mirror descent. In particular, GD is sub-optimal in the dimension dependence. Can GD outperform mirror descent in high dimensions using large step sizes?", "limitations": "The authors clearly state a few limitations in Section 5.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n* This work shows that large stepsize GD converges at an accelerated rate for a larger class of loss functions that was known previously.\n\n* The generality of the Fenchel-Young losses is used to compare the rate achieved by large step size GD compared to the rate achieved by classical (small step size) GD. As shown in Table 1, large step sizes accelerate convergence for Tsallis and Renyi entropies, but not for Shannon or Semi-circle losses. \n\n**Weaknesses**\n\n* Confusing wording: Authors use the wording “arbitrary” step size, referring to how it is independent of the error tolerance. This choice of wording makes it hard to follow the paper, since this is used in claims such as “GD converges with arbitrary step size” throughout the paper. This is not true, since GD remains in the EoS phase for O(step size) iterations. \n\n* While the results are interesting, the claim that achieving the accelerated rate is “groundbreaking” seems like an overstatement, given that the EoS phenomenon has been observed in prior works. \n\n* The authors consider full-batch GD and prove convergence of the training error. As discussed in Section 5, all points are therefore classified in the EoS phase. When aiming for perfect training accuracy, it’s unclear whether large step sizes are truly useful.\n\n* It would be more interesting to see if large step sizes achieve accelerated convergence in a population error under the stochastic setting. [Wu et al. 2024] show that this is not the case for the logistic loss or 0-1 loss. Can accelerated convergence in the population error be shown for the Fenchel-Young losses considered in this work? Without any practical benefits to using large step sizes, the motivation for studying this problem is unclear.", "was_revised": true, "final_justification": "I have raised my score from 4 to 5. My recommendation is based on the paper's solid contribution and the authors' constructive engagement. \n\n- The paper's presentation issues were addressed appropriately. My initial concerns about presentation clarity have been effectively addressed. The authors proposed a specific re-phrasing that I agree is much clearer. I believe that by incorporating this, along with the excellent presentation suggestions from Reviewer 1, the final camera-ready version will be significantly improved. \n- Scope: My main concern was its extension to the stochastic setting. The authors addressed this concern, and I am encouraged by their response. However, because the detailed analysis for the stochastic case is not included in the submitted manuscript, it is difficult to fully assess the significance and correctness of this important extension. \n\nGiven the strength of the work and the resolution of my concerns, I am happy to recommend this paper for acceptance.", "rebuttal": "We highly appreciate your critical feedback. We will revise wordings based on your suggestions.\n\n**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”?\n\n**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$.\n\n**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.\n\nTo 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:\n\n+ $\\\\|\\\\mathbf{x}\\\\| \\\\leq 1$ almost surely\n+ 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\n\nThe 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.\n\nThis 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.\n\n**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$."}]

Author rebuttal:

Meta-review: **Summary:** Previous studies have shown that for certain objective functions (e.g. logistic regression), GD with large stepsizes still converges. While earlier work showed that functions with a self-bounding property can make GD converge with any step size, this paper extends the result by demonstrating that the self-bounding property is not necessary. Specifically, it proves that GD with any stepsize converges on Fenchel-Young losses with a separable margin, which may not have the self-bounding property. Moreover, this paper instantiates the Fenchel-Young losses with certain examples, including Shannon entropy, full circle entropy, Tsallis entropy, and Renyi entropy, and provides explicit convergence rates for each loss. 

**Strengths:**
- Going beyond the exponential/logistic losses systematically to consider Fenchel-Young losses is novel and interesting
- Nice proof technique that builds on the perceptron method, and can easily handle stochasticity
- Well-written paper with a clear contribution, and cleanly presented theoretical results. 

**Weaknesses:**
- Lack of examples justifying the importance and use of Fenchel Young losses. 

**Decision and Suggested Changes:** The reviewers unanimously agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the rebuttal/discussion, I tend to agree. Please incorporate the reviewer comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Discussion about the non-separability and extension to SGD (response to Rev. Fpmo, Rev. Trfc)
- Discussion why extending to the multi-class classification setting is non-trivial (Rev. i177)
- Discussion about the dependence on $n$ and the tightness of the bound (Rev. 7Hzu)
- Incorporating the presentation suggestions from Rev. Fpmo
Decision: Accept (spotlight)