Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization
Authors: Yijin Ren
Haifeng Xu
Qi Deng
Venue: NeurIPS 2025 poster ()
Keywords: Convex optimization
Stochastic optimization
parameter-free optimization
Primary area: optimization
TL;DR: We propose an adaptive, parameter-free accelerated method for local Hölder smooth convex optimization with optimal rates and no need for Lipschitz or target accuracy tuning.

Abstract: This paper introduces new parameter-free first-order methods for convex optimization problems in which the objective function exhibits Hölder smoothness. Inspired by the recently proposed distance-over-gradient (DOG) technique, we propose an accelerated distance-adaptive method which achieves optimal anytime convergence rates for Hölder smooth problems without requiring prior knowledge of smoothness parameters or explicit parameter tuning. Importantly, our parameter-free approach removes the necessity of specifying target accuracy in advance, addressing a significant limitation found in the universal fast gradient methods(Nesterov,2015).
We further present a parameter-free accelerated method that eliminates the need for line-search procedures and extend it to convex stochastic optimization. Preliminary experimental results highlight the effectiveness of our approach in convex nonsmooth problems and its advantages over existing parameter-free or accelerated methods.

Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization
Yijin Ren"
Haifeng Xu"
School of Information Management and Engineering
Shanghai University of Finance and Economics
Qi Deng'
Antai College of Economics and Management Shanghai Jiao Tong University
lanyjrostu. sufe.edu en, xuhalfeng20040stu.. sufe. sufe.edu.co
qdeng248sjtu.
edu. edw.jjt.eeddddeee.
Abstract
This paper introduces new parameter-frre first-order methods for convex optimiza- tion problems in which the objective function exhibits Hölder smoothness. Inspired by the recently proposed gettance-over-raatee accelerated aistpive-adaptive method which achieves optimal anytime convergence rates for Hölder smooth problems without requiring prior knowledge of smoothness parameters or explicit parameter tuning. Importantly, our parameter-fe free approach removes the necessity of specifying target accuracy in advance, addressing signif- icant limitation found in the universal fast gradient methods (Nesterov, 2015). We further present a parameter-free accelerated method that eliminates the need for line-search procedures and extend it to convex stochastic optimization. Preliminary experimental results highlight the effectiveness of our approach convex non- smooth problems and its advantages over existing parameter-free or accelerated methods.
(DOG) technique, we propose
Introduction
In this paper, we consider the following composite function
(xxx) == f(x) + g(x), ZER
min
where f: Rdd_ + R is a continuous convex function, and g: T2d R RR (+00) is simple proper lower semi-continuous (Isc) convex function of which the proximal operator is easy to evaluate. First-order Sooorttmss-Ssubggree
descent and their accelerated variants-ar are the workhorses for solving ( particularly in large-scale machine learning and AI applications. Their empirical success, however, hinges on judiciously chosen stepsizes; manual tuning quickly becomes the dominant practical bottleneck.
In standard analysis, the stepsize policy is often designed based on the smoothness level of the objective function. Specifically, subgradient methods for nonsmooth problems typically employ diminishing stepsizes, whereas gradient descent methods for smooth optimization often utilize
"Equal contribution Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

stepsize inversely proportional to the gradient Lipschitz parameter. In seminal work, Nesterov 27 considered convex Hölder smooth problem where f(z) satisfies the following condition:
[Vf(z) - V f(y)ll. S 1, ull", Vz, y R2
where v E [0, 1] continuously interpolates between the nonsmooth (v = 0) and smooth (v settings. Nesterov introduced accelerated gradient methods capable of universally achieving optimal convergence rates without prior knowledge of the smoothness parameters of the objective. Notably, the universal fast gradient method exhibits convergence rate of
((*²) - -0=)((())
+ 6
A
where Do := ==] - 11 denotes the initial distance to the minimizer. An appealing property of this method is its independence from explicit knowledge of the smoothness level v and the parameter Ly-
Despite these attractive features, recent studies have highlighted significant limitations of the universal gradient methods. One notable issue is that the universal gradient method relies on line search subroutine to adapt to the unknown smoothness level, which makes it challenging to extend to stochastic optimization. More critically, the performance of universal methods is sensitive to the predetermined target accuracy level c. As e must be set in advance, the method does not have an anytime convergence guarantee, which is crucial for practical implementations where iterations can be halted at an arbitrary stage. In addition, as pointed out by Orabona [30], an optimally set should depend on Do. which is unfortunately unknown beforehand. Setting the value of without prior knowledge of the underlying problem structure often results in suboptimal trade-offs between the two error terms 3). This turns out to be critical problem in nonsmooth optimization and online learning [23 3 6 5 40) Although [17] achieves a near-optimal rate in the smooth setting, it does not have a theoretical guarantee for nonsmooth or weakly smooth problems. key strength of their work is providing guarantees for unbounded domains, albeit with suboptimal rate in that setting. investigates parameter-free methods and notes that most existing approaches still require certain problem-specific information, such as the Lipschitz constant and Do- In contrast, our algorithms only require an estimate of lower bound for Do. and this incurs only a minor additional cost. Moreover, [15] further shows that it is impossible to develop truly tuning-free algorithm for smooth or nonsmooth stochastic convex optimization when the domain is unbounded.
In this paper. we demonstrate that near-optimal parameter-free convergence rates can be achieved for convex Hölder smooth optimization, up to logarithmic factors. Specifically, instead of fixing the target e, we set variable target levels that dynamically change based on the optimization trajectory. As mentioned earlier, an optimal level shall depend on the distance to the minimizer and difficult to compute. Motivated by the Distance over Gradients (DOG) style stepsize 3 [4] we approximate
||i00 x= by the maximum distance to the iterates and use this knowledge to choose stepsize in the accelerated gradient method. Leveraging the technique of distance adaptation, we are able to obtain parameter-free and anytime convergence rate of
D1+ i.y log" E
2
Da
where b, is the locally Hölder smoothness constant and is an initial guess for 4D,, without requiring any predefined accuracy level, knowing the smoothness level or the Hölder constant.
In addition, we propose line-search-free accelerated method that achieves optimal convergence rates for both Hölder smooth and stochastic optimization problems. To eliminate the need for line search, we adopt bounded domain assumption, as originally introduced by Rodomanov et al. (34). Different from their approach, which explicitly requires the domain diameter D) to set stepsizes, our method exploits distance adaptation to approximate D. This can be particularly appealing as computing the diameter of a general convex set can be computationally intractable. Moreover, by estimating D through the observed distance from the initial point, our method naturally adopts more adaptive stepsizes in large domains. in the stochastic setting. Since we adopt the bounded domain assumption, the convergence rate remains the same as that in 4 with Do replaced by D. Although we cannot guarantee the potential gap between Do and D, experimental results support our theoretical insights and demonstrate the practical effectiveness of our approach.
(iccoremccharcceee
the convergence rate of this algorithm
2

---

1.1
Related work
The increasing computational cost associated with hyperparameter tuning has driven significant research interest in developing adaptive or parameter-free algorithms. The online learning community has extensively studied parameter- free optimization, particularly focusing on achieving nearly-optimal regret bounds without prior knowledge of domain boundedness or the distance to the minimizer. For example, see [23 24
29 5 40). A recent breakthrough has been made by Carmon and Hinder 3. which moves beyond regret analysis and focuses directly on stochastic optimization. This algorithm appears to be conceptually simpler and motivates a few more practical SGD algorithms, such as Ivgi et al. [14). Defazio and Mishchenko [6], Moshtaghifar et al. [26]. A notable related study to our work is Moshtaghifar et al. [26]. which applied the distance adaptation technique to Nesterov's dual averaging method. They have offered convergence guarantees across various problem classes, including nonsmooth, smooth, (Lo, L )-smooth functions, and many others. However, the convergence rate for the Hölder smooth problem remains suboptimal.
The concept of universal gradient methods adapting to Hölder smoothness was pioneered by Nes- terov 27 Subsequent works extended this approach to nonconvex optimization [Л. stochastic settings 10 and stepsize adjustment 288 has been demonstrated that normalized gradient step- sizes [35 can automatically adapt to Hölder smoothness without requiring line search, shown in Grimmer [1]], Orabona (3I. Recently, Rodomanov et al. [34] proposed a line-search-fre univer- sally optimal method that is robust to stochastic noise in gradient estimations. However, this method requires the domain to be bounded and the diameter to be known. In parallel to universal methods, effective approach for nonsmooth optimization, enabling self- adaptatttn to Hölder smoothness [88]. However, these methods often involve solving complex cut-constrained subproblem and lack straightforward extensions to stochastic settings. The Polyak stepsize method (32) also exhibits self-adaptation to smoothness
bundle-type methods 20 2 have emerged
[13] and Lipschitz
parameters [25). It be seen as special case of the bundle-level method (8) While imposing Nesterov's acceleration technique 7 in the Polyak stepsize can universally achieve the optimal rates for Hölder smooth problems. typically requires knowledge of the optimal value.
Finally, it is important to emphasize that the parameter- free algorithms discussed in this paper differ from adaptive gradient methods [9], which have been substantially studied in the literature [6 33 36). While adaptive gradient methods primarily focus on adjusting to Lipschitz constants or constructing
preconditioner to approximate the Hessian inverse [41 38 21,, parameter-fiee algorithms in our context do not rely on such adaptation mechanisms.
2 Preliminaries
(s.) be the norm associated with inner product (-.-). Its dual norm is defined by ||s||= = max| (s. z)), where s E Rd. For a convex function f dRd + R U [+ we use fx(x) to denote (sub)gradien) of f(-) at the point We use (3(x) {y E Rdd 11y - x1 s 8) to denote the closed ball of radius 8 centered at z. We define I (T_))) when v' and 1 when v= to simplify the expressions.
Let Rdd denote the d-dimensional Euclidean space. Let ||
A convex function f is said to be locally Hölder smooth at with radius r if there exists mapping Mo Rdd x (0,+ + (0, +oo) such that, for any z E Rd, for any x, y E (x) (r > 0), we have
- [Vf+)) & M,(2,r) - vll".
(5)
Nesterov 227 considered the global Hölder smooth functions 2 where the smoothness mapping M2(2,r) r) is reduced to a constant Ly, However, will show that by incorporating both line search and distance adaptation, we can guarantee the boundedness of the iterates. Consequently, the complexity relies on the local Hölder smoothness, which is defined by
M, == 1,(x,,,D0) < +oc.
3

---

3 The accelerated distance-adaptive method
Motivation
Before describing the main algorithm, first shed light the intuition of Nesterov's
universal gradient methods [27]. From the definition of global Hölder smoothness (2). we have the Hölder descent condition:
(wv) S f(x) + (VI(x), x) Ly 1 || yl "
This inequality can be translated into inexact variant of the usual Lipschitz smooth condition:
7(Lw,)) 8)
f(v) S +
|
w11² +
(6)
2
where 6L, = (+) and E (0, 00) is the trade-off parameter. Since the Hölder exponent may be unknown a priori, Nesterov proposed to use pre-specify 5 = e, where is the target accuracy, and then perform line search over (Lv, d) to satisfy the inexact Lipschitz smoothness condition (6).
The primary challenge with this approach is selecting an optimal value for d. This parameter controls fundamental trade-off: a smaller improves the approximation accuracy using a smooth surrogate, but it increases the effective smoothness constant yLL, 6). However, choosing the optimal å necessitates the knowledge of the distance to the minimizer, and cannot be done easily when the domain is unconstrained. Moreover, even if the domain is bounded with D maXe.yEdomg || y/ < xo, this
value can poorly overestimate || 1 ==
To address the limitation in the existing universal fast gradient method, we present the accelerated
ietance-adaptive method (AGDA) in Algorithm [ Our algorithm can be viewed as a variant of the accelerated regularized dual averaging method [37 27 39 which involves the triplets {a*, v y²) The main difference from the prior work is the new stepsize and line search procedure to adapt to the distance to the minimizer.
Specifically, leveraging the distance adaptation technique 26 of values:
14, we approximate Do by sequence
F = max rk): where rı = | b*1 ||,
0,
and then set the averaging sequence dg based on the distance estimation:
a++1 Ax+1 - Ak: where Ak+1 == (
k = 0, 1,
(8)
To deal with the unknown Hölder smooth parameter, we invoke line search procedure to find the appropriate value of Bx+1, which satisfies
f(y ) S f(x (Vf(x" )), g k
Bc+1
1 x 112 11 Thes 2
(9)
6477.A++
where 7 measures the inexactness in Lipschitz smooth approximation and тæ is introduced by Nesterov's 's momentum (Т)- = in the non-accelerated method). As mentioned earlier, me is set to fixed 8 in the universal (fast) gradient method. Different from the earlier approach, we simply take S 3. which dynamically adjusts during the optimization process.
Th
804+1
Line search We describe how to find suitable 86+1 that satisfies the descent property 9.. Note that in this inequality + is dependent on 8k+1, we can describe the searching process of 3 by formulating it as finding root of continuous function. To formalize the idea, we define the auxiliary function (e() as follows:
(3) = - f(y k+ (8))+(())= + f(z + (V ),3 ++ kl1)
B
( - 22 372 -
(10)
+ 64TgAN+1
16A+t1
where (
(8)
Tx)x is the trial point, and **+1
argming E ai ((((V((='),)) + g(x)) + - 20122 Our line search consists two stages, each involving iterative procedure. We assume the first stage and the second stage can be ter-
minated in i/,thh and i th iterations, respectively. In the first stage, we find the smallest value i (1,2,...,) such that 4 (2)-13)) is nonnegative and set if = Consequently, we will have two situations:

---

Algorithm Accelerated Gradient Method with Distance Adaption (AGDA)
Input: x² and F;
1: Initialize An 0, 1- Fn - and 3o be small constant, like 10-3
2: Set initial solution: e0 = y/ x0
3: for k 0, 1,..,. K 1 do
4: Set rı and Fis according to
5: Update 0x+1 and 1 by
and 7
Au41
6: Set a = Tx -
Jy
7:
Apply the line search to find Be+1 such that (1x+4)) 0:
8: Compute g++1 = argmin, S 1 ul + Dit1 ( x²) s(1)))
9: Set gh+1 Tru + (1 7
10: end for
Output:
=K arg ( (v .t.......... *) (1)
1. 1/ 1, i.e., (36)) 2 O, then we set o = and complete the line search;
2. 1 > 1, then we perform binary search to find an approximate root of (+)) = 0 in the interval 12% -2 Bk. - The search stops when the interval width no more than foo We set Bk+1 as the right endpoint of the final interval. tolerance level of 1 2F
Bx..
We now establish the correctness and computational efficiency of the line search procedure. Proposition 1. Suppose f()) is locally Hölder smooth (5) in k at least one of the following two conditions holds:
In Algorithm 7 for any
1. l (Bx)) 0;
2. there exists 3h+1 > Bk such that 44 (8 O, and for all Bh+1. we have (B( O.
Consequently, we have B Ok 20 Moreover, the total number of iterations required by the line search in Algorithm is Lk (1, + (K log K).
Remark 1. Proposition implies that our method requires an additional O K) function eval- uations compared to other algorithms (27). However, it is worth emphasizing that our line search procedure only requires access to function values, whereas the line search in the universal fast gradient method involves both gradient and function value evaluations.
Next, provide two lemmas obtain an important upper bound on the convergence rate and the guarantee of the boundedness of the optimization trajectory.
Lemma 1. In Algorithm] 7 suppose i S 4Do. ifr 1,.,,..,k, k, the line searches successful and we have I, (Be41) Z then we have the following convergence property:
((r ((1)) Bk+1 (D3 D2+1)
3K+172+1
(11)
2A
8A
Lemma 2. In Algorithm 1 suppose that for all i 1.... k the iterates x² yf and v² lie within the set B&Dg ). Then, the line search in the k-th iteration terminates in a finite number of steps, and wh1 1 y x+1 k+1 remain within Bxn,(x))
One key insight of the distance adaptation is that the inequality (1]) implies the boundedness of rk- To avoid the first step of Algorithm from searching too far and breaking the boundedness of rk- we should adopt conservative distance estimation such that < 4Do. The smaller is, the more likely it is that F < 4Dn holds. Therefore, by repeatedly applying these two lemmas, we derive an important upper bound on the convergence rate and establish the boundedness guarantee of the optimization trajectory throughout all iterations.
Theorem 1. Suppose f(-) locally Hölder smooth
5 BsD, (z*). For any k > 0, it holds that
(Db D2)
Berk
(1y²) (xx")xx)))
+
(12)
2A₁
8A
Furthermore, i 4Do, then it holds that 1|
2011 < 4Do and l|u xx S. 3.o. for all k 2 0.
5

---

Since both zf and y are convex combination of u², we immediately have that all the generated points {x', yy 120 are in Ban, (z*).
Next, we further refine the upper bound in 11). Since D/ - -D - 2D Th S Fr and rkk S 4Do. the upper bound in Theorem can be relaxed to
-
{x(x)
2Ap
remains to control the growth of P Ax follows.
To this end, we invoke a useful logarithmic bound 14 as
Lemma 3. Let (d,) be a positive nondecreasing sequence. Then for any K Z 1,
dk
dx
dp
log
edx do
min ISRSK
(13)
d2
K
Zi=0
To apply the above result, we simply take d2 = Vrk- shows there is always some K where
is bounded by O log (Fr/(FFFF))
the error A
Next, we bring all the pieces together. As pointed out earlier, the line search ensures that 8841 is order up O 3-30 = Together with the bound over distance-adaptive term fx. arrive at our final convergence rate in the following theorem.
Ag
Theorem 2. Suppose all the assumptions of Theorem Thold. Then, Algorithmm 7 exhibits conver- gence rate that
My
(4D))
1/k
log e Do
"1y - ((aa)
(14)
K 143
1/2
where k* arg min
Eisd 2/77-
OSick
Remark The term (Day in the inequality approaches as k increases and bounded by small constant under the mild condition k 2 (log Do/F)). If is sufficiently large, this condition is much weaker than the polynomial dependency on Do typically required for nontrivial rate in gradient descent.
Remark 3. According to 14 to achieve e-optimality gap, our method aftains near-optimal 2140)
complexity bound of (Do from line search and distance adaptation, such as Ollo 2) and (log? Do
1+3r - ) where the Ô notation hides logarithmic factors arising
Remark Theorems 7 BandBrequic require the initial guess to lie within a reasonably large neighborhood. specifically F < 4Do This condition is key assumption underlying distance distance-adaptive methods [14). For theoretical purposes, we provide an automatic initialization strategy for in certain special cases (see Appendix). Empirically, observe that the performance of the algorithm is largely insensitive to the specific choice of f.
Stochastic optimization
In this section, focus stochastic optimization of Hölder smooth functions, wherein problem 1. f()) exhibits the expectation form:
f(x) = Be (x,
where & is random sample following from specific distribution. Due the difficulty in exactly computing the gradient (x), it is challenging to perform line search. To bypass this issue, we present line-search-free and accelerated iistance-adaptive method in Algorithm 2 of removing linesearch, we require an additional boundedness assumption.
At the cost
Assumption (Boundedness of domain). The set dom g is bounded, namely, D sup supp..Eddom |
Ull < +oo. We denote M, Mx"x,, D) for simplicity.

---

Let us use Vf(2, E) to represent stochastic gradient, we further assume the stochastic gradient has bounded variance: o² == suP=ER= EE || (xx,
((())] too. For the sake of notation,
denote (*++) v fa L SE and (i("") v fy + present the stochastic gradient in the
k-th iteration, where E and Ex are two i.idd samples.
Algorithm 2 AGDA Line Search Free Modification (AGDA LSFM)
Input: x4, F:
1: Initialize An 3n 0,
2: Set initial solution: v0 800 = 5 = =x
3: for 0, 1,.,,...
K 1 do
4: Solve x*
arg min, Σ == ail (x()))) + (Vf(x"), 2 +')++((())) + 2 1/11 ==??
5: Set dk = ||200 - 1=11:
6:
Update Fx and Ak+1 by 15 and (
7:
Set axtax+1 Ac+1 - AA: Tk Act1
8:
Set FF th + (1 =x)g²
Compute xk+1 = arg miny (ax ([ f( x + [(v)l + 11 y1133:
9:
10:
Set k+1 = -rt ++ + (1 Jzy=
11:
Set 7/
B6-183
3 -
80x-1
12: Solve (16) to obtain the solution B
end for
Algorithm is equipped with the following rules:
Fk max ( dxt, k > 0,
(15)
where de =1a* x=11.
In stochastic settings, traditional line search methods cannot be used as they introduce bias. Therefore, it is necessary to develop an approach that does not rely on line search. Rather than performing line search find the descent direction, Rodomanov al. (34] proposes nonlinear balance equation. The
core idea is to bound the error term f(y*+1) f(**+1) (Vf(=*+)) y z He +1y
112 by constructing balance equation incorporating D. We demonstrate that the term used to bound the error is effectively equivalent to line search, allowing us to use Fv to approximate D, which implies that D is not essential. Subsequently, we will explain how to formulate the balance equation.
As we mentioned in Section 3 line search strategy aims to find 3x41 such that l, (8x+1) = 0. The difficulty is that ++1 depends on 8k+1 and thus solving 4 (8x+1) = cannot be achieved by a closed-form solution. The motivation for applying the balance equation is to decouple the updating rule of g from the 3841. Once t has been updated, (+x+1) = will degenerate to the following balance equation
Bk+1
B6 p (Vf(( - Ff(xa ),ttt -x 241)
8k41 Il k+1 1 x+1 111 (16) 64 As+1
2A
where |++ ma .). We use ( rlt1) to replace the - ((()t( + f(x++1
since we cannot obtain the function value.
Since we decouple *+1 from B8+1, equation it has a unique closed-form solution given by
16 has a simple form that is easy to solve. Moreover,
3x A64T (V v.( ), y x 3all - 1
BK+1
(17)
327272 b+1 11+1112
We leave the details about conducting the closed-fome solution in the appendix.
We next conduct the convergence analysis of Algorithm 2 In order to use the unbiasedness of the inexact oracle, we adopt the balance equation update the BE+1- Moreover, we use Fa is natural underestimation of 7) and Lemma 3 ensures that the cost of underestimation can be reduced to Oloo 2). We leave the proof in the appendix.
7

---

Theorem 3. Suppose Assumption holds. Algorithm 2
exhibits a convergence rate that
My
oD
Blb(y") - o
(18)
K
-
14:3
v k
where arg ming &... (
5 Experiments
We evaluate the performance of our proposed method on a diverse set of convex optimization problems. The goal is to assess its efficiency and robustness across different application scenarios. Additional implementation details and extended results (more different problems and large scale experiments) are provided in the appendix.
5.1
Deterministic setting
10a
10
109
10a
www.
(X0)
10
10
10
000
5000
10000 15000 20000 25000 30000 Steps
200
400
600
800
1000
200
400
600
800
1000
Steps
Steps
Figure 1: Performance of the compared algorithms. Left: softmax problem. Middle: Matrix game problem of size (n, m) = (896, 128). Right: Matrix game size (n, m)) = (448, 64).
Softmax The first problem is optimizing the softmax function:
(a;, x²) bi
min #ERd
plog
exp
(19)
f4
where E Rdd b, E R and μ is given positive factor. This function can be viewed as a smooth approximation of the maximization function.
To facilitate a clear comparison, we design a simple baseline problem for evaluation. Specifically, we first generate i.i.d. vectors (ā:} and b, whose components are uniformly distributed in the interval
[-,, Using these vectors, we define an initial softmax objective f(x) as in (19). We then shift the data by redefining a, = ā - f0a)). where O₂ is the d-dimensional zero vector, and set f() according (19), using the a; and the original b,. With this construction, 022 becomes the global minimizer of f(x).
We employ various methods for comparison, specifically considering DOG [1]. DADA 26). and the universal fast gradient method (FGM) [27] as benchmarks. For DOG, we set r, = 0.01. Both configured with F 0.01, while for FGM, we set n 1000, d 2000 and μ 0.005 as the parameters of the problem. The results of our method illustrated in the left part of Figure [ As expected from complexity analysis, FGM, being an accelerated method, outperforms the aon-accelerated baselines DOG and DADA. Notably, our proposed algorithm achieves the fastest convergence among all tested methods, which empirically confirms the advantage of our adaptive stepsize selection.
DADA and AGDA
0.01. We set
Matrix game The second problem we experimented with is the matrix game problem [27]. We denote A as the standard simplex with dimension d > 0. Specifically, consider payoff matrix E n where two agents engage in a game by adopting mixed strategies x E A,, and E A.. respectively to play game without knowledge of each other's 's strategy. The gain of the first agent is

---

given by (I, Ay), which corresponds to the loss of the second agent. The Nash equilibrium of this game can be found by solving the saddle-poin (min-max) problem:
min max Ay).
(20)
ZE BEAm
This problem be posed minimization problem: ui. (Vpd(a,)) pp(()) va(v)) = 0, where 1p (z)= maxigism (2, Aez) and (=)))= minigign (ei, Ay).
We generate the payoff matrix A such that each entry is independently and uniformly distributed within the interval [-1, 1]. This problem is nonsmooth with Hölder smoothness parameter v = making it a suitable test case for evaluating the robustness of optimization algorithms under minimal smoothness assumptions. We evaluate all methods on two problem sizes: (n, m) = (896, 128) and (n, m) (448, 64). The performance of our method, along with the baselines, is shown in the right panels of Figure [I The results demonstrate that our algorithm remains highly effective even in challenging nonsmooth settings, outperformig the alternatives in both cases.
5.2
Stochastic setting
Function value gap
10
ASDA with
Function value 080
106
AGDAL5PM
8000
Accuacy22
Accumae2
10a
10
Adkm C001
Adam 3.002
104
Steps
103
USFON 0.10
USE 0.01
10a
10
10
10-1
10-
100
200
300
500
2000
4000
6000
5000
10000
Epochs
Epochs
Figure Performance of the compared algorithms. Left: robustness test on diabetes dataset. Right:
Long-run test on Boston housing dataset. Right: robustness test on the softmax problem
Least-squares For the stochastic setting, we first consider the following problem:
f(z) #ER
min
1l Az
b12 s.t. || Sr.
(21)
We set the constraint radius 10 and conduct experiments using real-world datasets from LIBSVM For the first test, we use the diabetes dataset to examine robustness. For both USFGM and our AGDA-LSFM algorithm, we vary the initialization hyperparameter D for USFGM and F for AGDA- LSFM- to evaluate sensitivity to stepsize-relater inputs. As shown in the left panel of Figure 2 USFGM 34 and Adam exhibit unstable performance when hyperparameters are poorly tuned, while our algorithm maintains strong and consistent convergence across wide range of settings.
To further validate algorithm efficiency in practical regime, we repeat the experiment the Boston housing dataset, tuning all methods with their best-performing hyperparameters. The middle panel of Figure 2 shows that our method achieves competitive long-term performance while preserving its robustness advantage. These results illustrate that our approach is not only stable but also effective in real-world stochastic optimization tasks.
5.3 Robustness
We conduct additional experiments to assess the robustness of our method with respect to the choice of the parameter which reflects estimate of the initial distance the optimal solution, Do- Our goal is to show that the performance of our algorithm remains stable across wide range of F values, thereby reducing the sensitivity to inaccurate user-specified estimates.
To this end, we revisit the softmax minimization problem and vary F logarithmically from 10-4 4 to 10 For each setting, fix the target function value tolerance record the number of iterations required to reach the specified accuracy. The results, shown in the
(0.2, 0.4. 0.6. 0.8, 1) and
stttps://www.cr csie. ntu. edu. ttw/c//i/liisepeeeeeetee

---

third panel of Figure 2 reveal that our method is highly robust: the number of iterations remains nearly constant across several orders of magnitude of r. This suggests that our approach can tolerate significant misspecification of Do without compromising convergence efficiency. In practice, users may either provide a rough estimate of the initial distance or simply default to a moderate value such as = 10-3, which performs consistently well across our tests.
5,4 Non-convex neural network
To evaluate performance non-convex optimization, we trained a ResNet18 model on the CIFAR- 10 dataset. We compared the proposed AGDA algorithm against two established optimizers: AdamW and DoG. For AdamW, W. we set the learning rate to 10-3 The DoG algorithm was configured with 10-3, which is consistent with the primary hyperparameter used in the AGDA implementation. The comparative results are presented below.
Training Loss
Validation Loss
Accuracy
0.175
6031
Accuracy
0.125
0.075
10
20
40
10
20
10
20
30
40
Epoch
Epoch
Epoch
Figure 3: Performance of the compared algorithms in network training. Left: Training Loss. Right:
Validation Loss. Right: Accuracy.
The results clearly show that AGDA-LSFM maintains performance on par with the AdamW baseline and achieves superior results compared to DoG. Crucially, these findings establish the competitiveness of our method against SOTA parameter- free approaches, suggesting its practical robustness extends beyond the theoretical assumptions (e.g., boundedness and convexity) that underpin its derivation, even within deep learning's 's highly non-convex landscape.
Conclusion
This paper introduces novel parameter-free free first-order method for solving composite convex op- timization problems without requiring prior knowledge of the initial distance to the optimum (Dp) or the Hölder smoothness parameters. Our method achieves near-optimal complexity bound for locally Hölder smooth functions in an anytime fashion, making it broadly applicable and practical. In the stochastic setting, further develop line-search-free accelerated method that eliminates diameter D during stepsize selection. This enhances
the need for estimating the problem-depente both theoretical generality and practical usability. Preliminary experiments demonstrate that algorithms are competitive and often outperform existing universal methods for Hölder smooth optimization, particularly in terms of robustness and adaptivity. An important direction for future research is to improve the dependence on the diameter Do in the convergence complexity, and to further relax the boundedness assumptions typically required in the stochastic setting.
7 Acknowledgements
This research was supported in part by the National Natural Science Foundation of China [Grants 12571325, 72394364/72394366 and the Natural Science Foundation of Shanghai [Grant 247R14 14731421300).
10

---

References
[1] Amit Attia and Tomer Koren. How free is parameter-free stochastic optimization? arXiv preprint S43i::2402.03/22 2024.
[2] Aharon Ben-Tal and Arkadi Nemirovski. Non-euclidean restricted memory level method for large-scale convex optimization. Mathematical Programming, 102:407-456, 2005.
[3] Yair Carmon and Oliver Hinder. Making sgd parameter-free. In Conference Learning Theory, pages 2369. PMLR, 2022.
[4] Gong Chen and Marc Teboulle. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal Optimization, 3(3):538-543, 1993.
[5] Ashok Cutkosky and Kwabena Boahen, Online learning without prior information. In Confer- ence on learning theory, pages 643-677. PMLR, 2017.
[6] Aaron Defazio and Konstantin Mishchenko.
Learning-rate-fiee learning by d-adaptation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learming, volume 202 of Proceedings of Machine Learning Research, pages 7449-7479, PMLR, 23-29 Jul 2023.
[7] Qi Deng, Guanghui Lan, and Zhenwei Lin. Uniformly optimal and parameter-free first-order methods for convex and function-constraaine optimization. arXiv preprint arXiv:2412.06319, 2024.
[8] Nikhil Devanathan and Stephen Boyd. Polyak minorant method for convex optimization. Journal of Optimization Theory and Applications, pages 1-20, 2024.
[9] John C Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011.
[10] Alexander Vladimirovich Gasnikov and Yu E Nesterov. Universal method for stochastic composite optimization problems. Computational Mathematics and Mathematical Physics, 58: 48 64, 2018.
[11] Saced Ghadimi, Guanghui Lan, and Hongchao Zhang. Generalized uniformly optimal methods for nonlinear programming. Journal of Scientific Computing,
2019.
[12] Benjamin Grimmer. Convergence rates for deterministic and stochastic subgradient methods without lipschitz continuity. SIAM Journal on Optimization, 29(2):1350-1365, 2019. ISSN 1052-6234.
[13] Elad Hazan and Sham Kakade, Revisiting the polyak step size. arXiv preprint 13X.v:100..00313. 2019.
[14] Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pages 14465-14499, PMLR, 2023.
[15] Ahmed Khaled and Chi Jin. arXiv:2402.07799. 2024.
Tuning-free stochastic optimization.
arXiv preprint
[16] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[17] Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic optimization. In The Thirty Seventh Annual Conference on Learning Theory, pages 3257-3324. PMLR, 2024.
[18) Guanghui Lan. Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Mathematical Programming, 149(1-2):1-45, 2015.

---

[19] Guanghui Lan, Zhaosong Lu, and Renato DC Monteiro. Primal-dum first-order methods with complett for cone programming. Mathematical Programming, 126(1):1-29, 2011.
[20] C. Lemaréchal, A. S. Nemirovski, and Nesterov. New variants of bundle methods. Mathematical Programming,
1995.
[21] Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprint arXiv:2305.14342. 2023.
[22] Zijian Liu and Zhengyuan Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises: probbabiyyy bound, in-expectation rate and initial distance adaptation. arXiv preprint arXiv: 1227. 2023.
[23] Brendan Mcmahan and Matthew Streeter. No-regret algorithms for unconstrained online convex optimization. Advances in neural information processing systems, 25, 2012.
[24] H. Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In Conference on Learning Theory, pages 1020-1039. PMLR, 2014.
[25] Aaron Mishkin, Ahmed Khaled, Yuanhao Wang, Aaron Defazio, and Robert Gower. Directional smoothness and gradient methods: Convergence and adaptivity, Advances in Neural Information Processing Systems, 37:148 17:14410-148A. 10-14848, 2024.
[26] Mohammad Moshtaghifar, Anton Rodomanov, Daniil Vankov, and Sebastian Stich. Dada: Dual averaging with distance adaptation. arXiv preprint arXiv:2501.10258, 2025.
[27] Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, (52(1):381-40) 2015.
[28] Konstantinos A Oikonomidis, Emanuel Laude, Puya Latafat, Andreas Themelis, and Panagiotis Patrinos. Adaptive proximal gradient methods are universal without approximation. arXiv preprint arXiv:2402.00221,202
[29] Francesco Orabona. Simultaneous model selection and optimization through parameter-free stochastic learning. Advances in Neural Information Processing Systems, 27, 2014.
[30] Francesco Orabona. Is nesterov's universal algorithm really universal?, November 2023. Blog post, Sarameter-Free Learning and Optimization Algorithms.
[31] Francesco Orabona. Normalized gradients for all. arXiv preprint arXiv:2308.0562)) 2023.
[32] Boris T Polyak. Introduction to optimization. 1987.
[33] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
[34] Anton Rodomanov, Ali Kavis, Yongtao Wu, Kimon Antonakopoulos, and Volkan Cevher. Uni- versal gradient methods for stochastic convex optimization. arXiv preprint arXiv:2402.03221. 2024.
[35] Naum Zuselevich Shor. Minimization methods for non-differentiable functions, volume 3. Springer Science Business Media, 2012.
[36] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26, 2012.
[37] Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal on Optimization, 2(3), 2008
[38] Nikhil Vyas, Depen Morwani, Rosie Zhao, Mujin Kwun, Itai Shapira, David Brandfonbrener, Lucas Janson, and Sham M. Kakade. SOAP: Improving and stabilizing shampoo using adam. In Proceedings of the 13th International Conference Learning Representations (ICLR), 2025. 2025.
12

---

[39] Lin Xiao. Dual averaging method for regularized stochastic learning and online optimization. Advances Neural Information Processing Systems, 22, 2009.
[40] Jiujia Zhang and Ashok Cutkosky. Parameter-free regret high probability with heavy tails. Advances in Neural Information Processing Systems, 35:8000- 8012, 2022.
[41] Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Diederik P Kingma, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. Adam-mini: Use fewer learning rates to gain more. arXiv preprint arXiv:2406.1679 2024.
13

---

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:
We state the complete contributions in Section
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 contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long 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]
Justification:
We discuss the limitations of our work in Appendix A.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 (e.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 on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant 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]
14

---

We give all assumptions needed in Section 2 complete proofs in Appendix.
Justification:
3 and
We leave all the
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced 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 to provide short proof sketch 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental 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)?
Question:
Answer: [Yes]
Justification: Our experimental reproduction scripts will been placed the supplementary material.
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 a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case 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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Our experiments use publicly available datasets or randomly generated data based on specific methodologies. We are committed to making our code completely open source.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//abps.cc/public/uuiiee
ssisssssicyyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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) recommended, but including URLs to data and code permirted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details can be found in the paper and supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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, as 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: Our experimental results do not report standard deviation correlation results in the deterministic case. We focus the convergence rate of algorithm in the stochastic case and do not report them too.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

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 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 be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments were conducted on personal computers, utilizing CPUs for computations, with 16GB of RAM.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate 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 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics Ethics/https:
Answer: [Yes]
Justification:
The code in submission is fully compliant with the NeurIPS code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or 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]
Justification: This paper focuses theoretical problem without any societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or 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), faimess considerations (e.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 tied to particular applications, let alone deployments. However, if there is direct path to 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 a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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 in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There are no such risks in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or 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 challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators original owners of assets properly credited, and the license and terms of use are explicitly mentioned and respected in the paper.
Guidelines:
The answer NA means that the paper does
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, 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 a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide complete document of our code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve such research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then 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 at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: 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 the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve such research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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
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 is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper does not involve any LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy pottts://neurre /ttpearrps.ccccmofeeeeeeee/////p cc//oonferences/22255/LL. for what should or should be described.
20

---

Appendix
Limitations
22
Auxiliary lemmas
22
B. J Proof of Lemma
22
B.2 Proot of auxiliary Lemmas
22
Missing details in Section
23
C.1 Proof of important lemmas
24
Convergence analysis of AGDA
25
Proof of Proposition Proposition
31
Proof of Theorem
32
Proof of Theorem
33
D Missing details in Section
34
D.I Proof of Theorem
38
Two approaches for automatic initialization of parameters in Algorithm
43
E,1 Automatic initialization of 30
43
Automatic initialization of
44
More experiment details
45
Line-search bisection method
46
Structure of the Appendix In Section A we discuss the limitations of our algorithms. Section B presents the proofs of the lemmas for completeness. In Sections and D we provide detailed proofs of the main results discussed in Sections 3 and 4 In Section E, we introduce two methods for automatically setting the hyperparameters. Finally, Section ofters additional experiments to demonstrate the advantage of the proposed algorithms.
21

---

A Limitations
Algorithm I [significatlly reduces the multiplicative overhead of choosing sufficiently small pa- rameter F from a polynomial to a logarithmic factor, and lowers the average number of gradient evaluations one per corpatin four per iteration the Universal Fast Gradient Method (FGM) 27 However, this improvement comes at the cost of increased computational burden during the line search procedure. Specifically, to accurately adapt to the local Hölder smoothness, our method requires more precise selection of the parameter 3g. leading to a total of O log k) line search operations after iterations, whereas, in contrast, FGM only requires (kk)
B Auxiliary lemmas
B.1 Proof of Lemma 3
This result was first established in Ivgi et al. [14, Lemma 3] and Liu and Zhou [22 Lemma 30J. We give proof for completeness.
Proof. Let R₁
and Rot = 0, then for any l: 2 0 Ei
Re k+1 = Tx + Th
Tk
Rx
Tk Tk+1
R3
Tk+1
Then
R
R
R
R,y
Rg
Ti+1
T+41
ri+1
1=0
i=0
i=0
k-1
k-1
R
R
Rg. 1
+ k
Σ
ri
Ti+1
ri+1
where arg minosiss Rg. then follows that
1 k =
1
Rs- 1
ritt
1 k - ((t
t (olg(()))
k )
A
1 - log( m))
log(e Zk
[k)
rg
k(00))
h
B.2
Proof of auxiliary Lemmas
The following three-point Lemma is a well-known result. See also Chen and Teboulle 4 Lemma
3.2] and Lan et al. [19 Lemma 6). We give proof for the sake of completeness.
Lemma 4.
For any proper lsc convex function & : Rd + R U [+oo), any 2 E dom & and 3 > 0.
Let z4 = arg mingedom (0(x) + l1 =1|2). Then, we have
3 x(x)
2 -12 2 112 + 11 x112. Vo E Rd
2
z11 > 0(2+)
(22)
22

---

Proof.
2 2
x²12 +
112
1|=
x||
||
(z+, x)
|
2
2
2 ||=11 (2, z4)
+
2
|| + (2,
|
2- x z+)-
In view of the first-order optimal condition at 24, we have
(Vo(z+) + B(z 2), - 20)
Combining the two inequalities above, we have
2 || z²12 + 3 1| 2+1²
1|2 x11 = B(Z 2+, I - 2+)
2
2
S (Vo(2+) (1((z+);=2) ), =z4)
S ((x) +((+);
where the last inequality uses the convexity of o(.).
Lemma 5, For any u 2 O, k 2 O, there exits a positive constant Cu such that:
(k + 1)th - k. cu(k + 1)--1
(23)
where eu only depends on u.
Proof. When & = 0, we have (1)a 0" = 1" = 10-1 1. Now consider k >> 0. We distinguish
between two cases.
Case 1: If u 2 1, we have
p+1
(A+ + 1)a t² u
xu uu 2 uk=
and hence
b w-1
1 4-1
k+1
2
Therefore,
(k: + 1)th k2 2 )m) ju- (k + 1)"-1
Case 2: 0 <<1 1,
pk+1
(k + 1)a b2th 11
x 2- w--1dr dx 2 u(k: + 1)u-1
Therefore, we can set C, u( ja-
C Missing details in Section
In this section, provide detailed convergence analysis of Algorithm we define the following notations.
For the sake of simplicity,
k+1
O Σ aff(=*) + (VV())))) 2t) +(x)]
3x+ 1 x 22|2
B 1 BarP
8ap+1
Using this definition, it follows that Φ0(x)) 20 112 x1|
23

---

C.1 Proof of important lemmas
To begin our analysis, we first prove the key bound 66) used in universal gradient methods. The bound 66) ensures that these methods can be accelerated by line search without prior knowledge about y/ and Ly,
The following result is from [27] Lemma 2). We give proof for completeness.
Lemma 6. Let 5M (M -
8) (1 {) M where [0, 1] and 5 > 0. Here, 1. Suppose that for any J., BaDg we have
sei
[V5(x) V s My | yl1".
(24)
Then, for any x. y BaDo (x*) we have
f(y) f(z) + (Vf(z), 2) + (Mu, 8)
8 2
1/0 y11 +
(25)
Proof. Note that the condition 24 immediately implies
f(v S (()) + (VI(.), - x) + | w/ 2+v
from basic convex analysis.
For any a, b R2 and p. q 2 1, 1 1 1, applying Young's inequality we obtain
a b
2 ab.
(26)
q
We choose p IFo 1 = T-ui
2
a --
and b = L
F and have
Mr
(1 + v)? u)+
+
(1-1)
I-v Mr
1t1 6
2 +1
v
1-
I&c
2
2
v Mr
(1+ v)t
1 1- 1 My
+ (1+1)0
2 1
2
1+ V 8
2M,
(2 1 - v 1
8
1
T&V M
+
M,
1+
2
1 y
12
8
1+
2 7 M 8)
+
2
My
2
+ y
We set / = || y|l and obtain 25 directly.
To demonstrate the primary convergence results in Section 3 we first establish some useful lemmas regarding the well-definedness of line search and the boundedness of the iterates.
Lemma 7. Let g Rdd + RU } be proper Isc convex function.. For given vector E RR and
point z E 1Rd, define the function 2h) for any h > 0 as: 2(h) == arg min
( (c, + g(x)
hl[z 21 22 Then, the function ||= 2(h)] is monotonically decreasing and converges to
as h +
Proof. First, we prove |مر0 - 2(h)]] is monotonically decreasing in h. For any h1, h2 such that h2 hy O, in view of the optimality of z z(h1) and 2(h2), we have
(c,2(hr) + g(((())) + h1ll=" 2111)112 < (c, =(h2)) + g(=(h2)) h - x(h2)112 (27)
and
2c))() + g(=(hi)) + h2ll20 2(b1i)1 2 (c,2 ((2(122) + - =(h2)112 (28)
24

---

Combining (28 and (27) and noticing that h2 h1 > 0, we have
(h2 h1)l( =((21))²² 2 (h2 h1)ll>" - 2
which implies
|| - =(h1))l 2 ||=0 =(h2)]l-
Next, we prove - 4.00 ||x00 - z(hi]l - by contradiction. If there exists 8 > 0, for any
h E R2, || z(h)ll 2 6, then we have
(c, (1)) + g(=(h)) + h| =(h)]] 2 (c,, (b)) +(((())) + h82.
Let us consider h > ho 0. Uusing the optimality of =(ho), obtain
(a, (h)) + g(=(((()))))))))))))))) + ho |20 - =hh]] 2 (c, (ho)) + g(z(ho)) + hollz =1h
Note that monotonicity proved above implics ||I0 z(h)]l = ||2 - 2(ho)]l. together with the above inequality, we have
(c, 2h)) + (((())) 2 (c, =hoo)) + ((=())))-
Moreover, using the optimality at =h) and the lower boundedness ||000 =(hi]] 2 5, we have
(c,z") + g(x") 2 (c)) + (h)) + hll=
z(h)]] (c, xc,)) g(=(ho)) + ho2. (29)
Since can be arbitrarily large, this result is impossible unless O.
C.2 Convergence analysis of AGDA
Outline The analysis of AGDA is slightly more involved than the standard complexity analysis for smooth problems,
must simultaneously prove the boundedness of the iterates and establish the convergence rate. Our proof strategy is centered on an inductive argument. To proceed, we outline the structure of the analysis. Lemma [ and Lemma 2 develop crucial results regarding one-step iteration, including the success of the line search, convergence error, and the boundedness of the well-defined. This serves the foundational building block for our inductive analysis. Lemma X establishes growth bounds on 3x.- Building on this, Proposition addresses the complexity of the line search step. By employing mathematical induction, we conclude in Theorem [ the boundedness property of all iterates and establish key convergence properties of yx+ FinalTy, utilizing the technique of distance-adaptive stepsizes, we derive the overall convergence rate of AGDA in Theorem -
iterates, assuming that all previous steps
Next, we establish important property about the convergence of the algorithm.
Proof of Lemma I
Proof. Since 14 (36+1) 2 0, we have
1e(++1) f( (3k+1) + (1- -1))a*) + f(xt+1) + (Vf(z+t1), Tru (
+(1 -1--Tal - + BA+1 174u++118 + (1 - Th)y* - 111 +
3F2 3
2 0,
647 An+1
16A
(30)
i...
((1ht)) S s(att2) + (VS(x h+z x bt2) + Bx+1
b+1 x 112 +
Th:
64 Act1
2
Because ++ T + (1 = ghth TrU (1 )² and mi
Bh11r -,,2 it holds
80x
(1 5(1 Tw) (T) + (V/(x)+)), y² - x x(1l)) 1)= + Tx [ (1x + (V w xk11))
+ Be+t Ti 11 u1p BETITE - Bark-1
16A4+1
<(1 Tx)S(1²)) TT (V v - x+1))
Bx+1 || - ,²112+ BRTII7 BaTk-1
+ 64
16A
25

---

Multiplying both sides by A we have
AR+1f S SAn((y)) + aat1 + (Vi(x ),,,,1),,, oktl1 )l(11))
Bkt1 110 12112 1 - -B
+ 64
16
Note that
||u w/112 S (110/11 - x011 + 111t - x²11)² 1 (2 max mmxx(lluftt - 1011, 1111 - x011))² S 47
It follows that
A (1) SA + ak+1 (f (xt) + (V (x
), 1,00-11 1 -xtt11)
+ Br | - 2112 + 3x+1 - 3R
47 k+l + BRTIFR Bark
64
64
16
< < + ak+ (s(x + (VS(xttt))
1) x/- xxt11)
+ BK | - -112 3x+1 - BK k + BK+IFE k BKr
(31)
2
16
16
< f + aax+1 (f
+ (V]((=t)))
), -xit11)
+ Bk 11 k+1 1 1112 +
BK+17h+4
k+1
B
B8+172 - -BuFR-.
16
16
where the last inequality uses FR41 Fk. On the other hand, since g()) convex, we have
g (1- + nig(tht)).
(32)
Combining
31 and 32 we obtain
A An (v") ) + af+1 + (V
o - xbtl) + g((
Bk || - 0112 Bkt1
B + Bk+117 - Ba7
16
16
For B |lott1 - 12, we use Lemma then
2
A )AA(((**) + aat2
+ (Vi(a*t)), o - x111) + (((
+ 3k 11 112
(f((x') + (VS(x'), ot - x²)) + =((ttt)))
2
Bk 1100 1²1
Σ (f(((z') + (Vf(z"), vt - -2') + g(00))
2
1=1
8 - BaPe Bx+177 - -B072-1
16
16
A+1
<Aw0())) + Σ (f(((=)) + (V)(z'), wtz x²) + +((
Bx+1 1 1
x
k
3x
Σ (c([(a))+ (V)(x), vt - -x") + +g(("))
1120 -b²1
2
8 1 -
BR+1T - -BaF2
(33)
We shorten the inequality (3) by using the definition of ox(-):
oc((²* + BK+1 P24 - Burk
8x417h - F
A S Au (v²) + (
16
16
26

---

Applying the upper inequality recursively, it holds
6 B - -Be7?
B4417
-3,
AKt1V(1-11) S0k+1(0 - 2o(0")) +
Σ
Σ
16
==0
i=0
Bk+1
80 22
Bk+1 22
30 2
<
22
+
16
A+1
16 00
16
k
16
3k+1
8K41 22
50x+1(o
+
16
22
k+1
+
16 k+1
Bk+1
sØx+1(b
+
8
2
R+1-
where do (vo) = 0 and 3o 0.
Since wd-1 = arg min Φx+1(2), (z), we use Lemma 4 again and obtain that:
Bk+1 k+1
Akt1V(y Sok+1 1 +
k+1
ox(f(x)) ff((')), 8t -x))+ + Bx+1
Be+1
||000 - 12
rk+t
2
8
1+1
a;(f(x)) (Vf(x'),, - x²) -)xx)) + Bk+1
Bx+1
1: x=11
| - x12
2
2
1=1
8k+1
pktt
8
9k+1
3k++ 11
x x=1 + Bx+1 2
S <a+11((0"))
+
1000 -
-xx11 x²12
2
2
Finally, we use Do and D4+1 replace 1|0.0 - x111 and || - x1 and have
11 s (x+1)(x")+ + Bk+1 D3
Bx+1 Dē + Bx-1 p
2
2
8
((r - (l*x)² s Ba(DD - -D Ba7k+1
2Ax+1 8Aat1
Note that the convergence result above is conditioned on the success of the line search, which further requires the boundedness of the iterates. We prove these important properties in the following lemma.
Proof of Lemma
Proof. For clarity, we divide the proof into the following parts.
Part 1: Finite termination of the line search.
Given the value of a: y² ARt1, Th FRs Pk- and Br. la ((3) is by
1x(3) = A+1 (3) +11 -->))"">) (1*+1) + (V (t))))),))))))))(()( +l (B)
+(1 - - xtt1 + 647 A 11 ((8) ) + (1 Tx ) 22 2 37% Ber
(34)
16A
where , (B+1 == arg min k+1 a: ( ), x) + .(x)) + - |2 - x 112 ,,, R.
We analyze the function (B) and 4 (B) first. .+ + E dom g well-defined and unique since {(x)) + L | x I1 3 E R2 is strong convex and has unique optimal
Et (VV(((()) solution. We claim that g(x) restricted dom g is continuous since is convex and lsc. The convexity guarantees g(r) is continuous at the interior point of dom g. and lower semicontinuity guarantees
27

---

that it maintains the continuity on the remaining points of domg. g. Thus (B) is continuous. Since 4 (3) is the composition of continuous functions, is also continuous.
Next, we discuss the behavior of (3) when B + +00. Recall that we assume xt, of, y fa,,("))) we shall first prove that the line search for y must be finitely terminated. Specifically, applying Lemma with Σtz (xr*) and & have that for sufficiently large value B when 3 2 B, ||00 (x+1((1) (B) < 2Do. which further implies || - - -B)1l S 3Dn-
Let us consider B 2 k++ 5 > O, where
= max (3. SAR+10 + BATk- pk4
32T AR+ A 8).
rk
we must have u E BBD, Since (B) is a convex combination of x*+1(3) and y², we have y (B3) E Bano (x*). Similarly, we have gkt1 E Bang((")) Cemma6/implcc
+ 2) + (Mu, f()*+(()) f( (VI(x).v
5 |x y11 + Vx, E BaDo (35)
2
Moreover, due to the definition of @ we have
7MM, 6)
B
Brg BKT
and
2
64T C Ak+1
16A
Combining the above two results, we conclude that (3) 2 That is, l4 (B() remains nonnegative when /3 exceeds certain threshold, and hence the search will terminate in finitely many steps.
Furthermore, would like point out that 2 is another threshold. For any B 2 k+ have (B) O. The reason is that the following inequalities hold:
5) 2
B
23
5 3 BOTE-1
2872 BAFR-1
and
G4T
64T
2
16A
16A
The second stage of the line search procedure also ends in finite steps as it employs simple bisection method.
Part 2: Boundedness of the (A: + 1)-th iterates.
First, we immediately have +++ The (1 -1-Twh --)r)*** E B3Do (x*) ) by the assumption. Next, prove *+1 px++1 BaDG (x)) Part 1 implies (((++1) 2 0 0, 0,1,..., k). Applying Lemma 1 we have
(DB - -D2-1 BK+I
((yht)) (xxx)=
(36)
2AR+1
8A
We shall consider two cases.
Case 1: Fk+1 = Fk. then rk+1 S Fs S 4Do;
Case 2: Fk+1 = Tk-1- Due to the non-negativity of the optimality gap and 36). we have
Bx+1 [D] - D2+1l
2A
8A
By dividing both sides by
8L+1 24
we obtain
D2 + r
0 D3
which implies:
2 Di
Tk+1
D S $1
<
Do +
4
2
28

---

By the triangle inequality, we have:
rk+1 S Du Dx+1 S Do + Do + Mk+1
r++ S 4.D.
By repeatedly using the D& S Do + fz 2. we have:
Pk 2
D& S Do +
-
Do + 2Do - 3Do
That is, || - x²1 & 3Dg and thus u++ E BAD (x*). Thus, we have y E BBDD (x*) as well since y ++1 +1 the convex combination of g++1 and y².
The following lemma develops an upper bound of 8k.
Lemma 8. Suppose f(.) is locally Hölder smooth in BaDo (a))(*") and Bo S &2I,, In Algorithm for any k O, given cx41 > O, if at least one of the following two propositions holds:
1. 4x 2 O, in which case we set 3k-1 Bki
2. there exists a root B141 where la (8k+1) = and the line search returns value satisfying
B841 S Bk+1 + +
Then, we have
Bx s L.M
(37)
k-
Proof. First, we estimate the growth of ax+1. We have
(A - At) (A At) S 2 2
at+1 A As
which gives
2 S 4FxA4+1.
Next, for 8 that satisfies (1(+ 0, applying Lemma
we have
(B BBDo
(38)
where (B3) is defined in the main text of the paper.
4((8+11) = implics that
f(u (81+1)) = + ). 8+ (8x+1) -
+ (Vf(a*+l)
81+1 11
B B 12 - F
(39)
(of++((8241) (B241) 111
GATăAR1
16A4-1
Applying Lemma 6 we have
f(y k (8t+2)) = f (3xhtl) + (Vf(x++1),
1,,+++((++))))) - x
11 ( (M 0)
8
(40)
+111
2
We take 5 = 82-108-11 - then combine
39 and
40
we have
SAR+1
Bit
22 BarZ
Sy
Mr.
(41)
32T2 A
8A
We prove this lemma by induction. By the assumption on Sg. holds for Next, we assume valid for some k.
29

---

Case 1: The line search is satisfied by the previous step size (3k+1 = Bk). The inductive hypothesis is trivially satisfied for k: + 1:
k+1
= Bx 5
Bu
Σ
3-3
1=1
where the final inequality holds because Fi is non-decreasing.
Case 2: The line search requires a new step size (3x+1 > 3x).
Case 2.a: Bk+1 I 9h+1 + ck41 and v = 1.
Bh+1 327 2 A k+1
8Ak+1 j', = M,
S(
8741"7 k-1
Bk+1
= 22 Mu
Bk+1 52¹ Ly + e S 2" L,
Case 2.b: Bx+1 S 3h+1 + c and v * 1. First we analyze B7+11 Since 3k+1 is the maximal zero
point of [x()), applying Lemma we have
B8+1 S (MM, P2+1 B
32 Ar+1
8A++1
i.e.
Bi+t
1 1- v
8A
8A++1
1-p
<
M <
M
32T Ast1
1
Be Bark
(3k+1
Bx)
can be rewritten in the following form:
BE (B Bc) 2 21 I
40 2u
(k+ (k+1) Me..
As B++1 increases with 3x+1 2 Be. the left-hand side also increases. Thus, by identifying value where the left-hand side is at most equal to the right-hand side, we can determine an upper bound for 3k+1-
Let cu (T My. For ok + 1) 3-30
+ Ete c.. we have
k
k
(coF((k +1) 3 3u
(CoF + 11
3 3v
Σ c - Bx) ト
i=1
k
2(cog((+11) +1) 3-d
3-30
Σ c
Cu
k
i=1
(42)
2ko + 11 2,
(cT 1) 3يه
Cork
k
3-
7
20ok(1k + 1) 3ي
(c,
1
20 1/
14v 14
2 26
(k +
3-
((k
30

---

Since 3-30
E [0, 21, and min
(2)-1
2
1
3-3r
3-30
Applying lemma
5
15u5
it holds that
2
2u
((k:
3 - 3v
k
vi
((k:
4
(43)
3 3v
1
2 Mr
14
1-
((k: + 1) - H (k + 1)
4
22
10440
My
14
2u
Kk
2uc 140
(k 1)2 1-r
This inequality implies that 51+1
2 I M,
3= E of and Bxt1 S Sh+1 + do11 S
2 2TT. - Σ
k+1
i=1
Moreover, since we set de
we can obtain an upper bound of 3g as follows
2
3K+1 2
k+1
MM + 8o - L, 3
B0
27 2
C.3 Proof of Proposition Proposition
Proof. In the proof of Lemma 2 we have proved that the first stage of the line search terminates in finite number of steps, and thus l (2% 3x) 2 O. Moreover, we also proved that 4 (+))) is continuous. Next, we show that at least one of the two propositions mentioned Proposition
correct.
When & 1, we have (2 1-24-19 Bx) 4. (Bx) 2 Thus, the first proposition holds in this case.
When i/ L, we have 12 - 0 and
Since (x(-) continuous, based on the intermediate value theorem, there exists at least one root the interval [2% -2 - Moreover, previously discussed in Lemma 2 there exists threshold 2: such that for any 2 28TH (x() > O. Now, since (8) has at least one root and the set of roots has an upper bound, there exists maximal root B of the continuous function 4 (.), and therefore the second proposition holds.
remains to estimate the upper bound of the amount of searching. Without loss of generality, the Algorithm This is common assumption in the previous work, for example, see (27). and it is reasonable since the upper bound of the searched value increases polynomially in The initial value of the searched value is not very sensitive. Thus all the conditions of Lemma 8 are satisfied, we apply it to obtain that 3 < O(k ))
assume that Pn < 27 L,,,
The first stage in the line search in the k-th iteration starts from 9% to most 23 So the length of the interval is at most 2/3+11 - 3x and this stage in line search procedure requires at most
1 S 1 + log( log((28.4) times in the k-th iteration. We sum them up and obtain that up to the k-th iteration, the total amount of line search operations in the first stage is at most
BEt1 s O(k + log Bo
Σ 1 (1+ 20g + log(
The second step in line search process in the k-th iteration start from 25 8x to at most 2 Bk- Hence, the interval length is at most 2* 8g - 2 2 1 I 3 and this step of process requires at most i - & < + log( ( times in the k-thh iteration. We sum them up and obtain that up to the k-th iteration, the total amount of line search operations in the first part is at most
&
&
3
k
Σ
Sisk
log = k + log
II 1 - log
II 1=1
c
S O log k),
j=1
where we apply Lemma
g to estimate Bx-
To summarize, the total amount of line search operations is O 1ogloog k).
31

---

C.4 Proof of Theorem 1
Proof. We first prove the first part of this theorem. We apply Lemmal I and
2 to prove by induction.
First, I v0 = yd E BaD, (x"). Next, we assume it holds for some k 2 U.
Since 2² vh.g" E (aD,((")) we have (B(++))) 2 Lemma 2 Thus, applying Lemma I it holds that
and x wht1 gh- E BaDa(2") by
(lyht1) - B 100-
BR+ITR+1
(44)
2Ax+1
8AA-1
Therefore, for any ko O, we have
Ba(Di - D2)
"(y") (xx')²
(45)
2Ag
8AA
Then, we prove the second part of this Theorem. The proof is similar to that of Lemma 2 For completeness, we give proof directly using the conclusion obtained in the first part and induction.
Since we assume Σ 4D,, then To F 4Du. Next, we assume it holds for certain & 2 then x++ = Taex + (1 Tkyy" lies in BaD,(T")
Case 1: Fk+1 Fk. then r4+1
Fx S 4Do;
Case 2: Tk+1 = 1--1- Applying the conclusion obtained in the first part, we have
Bk+1 (Dz
-D SK+1
0 S 4/ v(xx)
(46)
2AA+1
8A
Then holds that
0 D3 -D r
Di41 S D3 + 7k+1
22 D3
Tk+1
Dx+1 $ /
S Do +
4
2
By the triangle inequality, we have:
rk+1 $ Do Dx+1 S Do + Do + Tk+1
rk+1 I 4Dg.
Repeat using the D₁ S Do + Fg. 2
we have:
De S Do + Th < Do + 2Do S 3D.
2
That is, || x²1 3Do and thus k+1 E BaDs (x*). goth BBDD (x*) well since ++1 is convex combination of k+1 and y²t
=0 In conclusion, prove that for any N. 11u0- -1o--101 S 4Dg and || - x*11 3D.
The boundedness property is essential for us to remove the standard global Hölder smoothness assumption on the whole domain. Instead, we can safely use the local Hölder smoothness assumption as all the iterates remain in the ball (x),
Finally, the preparatory work for Theorem 2 is now complete. Proposition Jessures the practical implementability of the algorithm, while the first part of Lemma [ and Theorem | provides the tool needed to analyze the convergence rate. Furthermore, Theorem Lemma and Lemma ensure that the convergence rate achieves the best-known rate.
32

---

C.5 Proof of Theorem 2
Proof. Using the triangle inequality, it holds that
D3 2 Dn rkl
D 2 D O + +
(47)
2 2 D D
In view of Theorem
we have
3e Di
D
BATk 8A
23r
BATE 8A
B.DuFk
BAT
"11²) - vb(x)) S
<
S
(48)
2Ap
2Ap
An
8AA
where 47
Applying Theorem
I we can match the right hand side of inequality
(48):
3k DoFk
48k
DOFK
3,8 Dork
<((²) (xxx)
(49)
8Akk
2A
Denote kz = arg min OSigk
Applying Lemma gives
El= f?
fu f x
log El (f)
(4Do do log 4Do
(50)
k
2k
Without loss of generality, assume that 8o < 2 I.M,M in Algorithm similar to the justification provided in the proof of Proposition
This assumption is
Thus, for k*, combining the inequality (50) and Lemma 8 it holds that
min (yy) xxx") < (x²"
yc gv"
3/ DOFR-
2AH-
3k Do
k
k-
===0
F.
(1De)
log 4Da
2
2-
k
2
(51)
$2
2k
4Do
4Do Mo
k- k
3,30
<3841
log"
e
F
122
4D
4Dg
M, MD
<3841>
log
f
4Do log
4Dg
MyD
<3841>
where use the fact (k*) 2 < k 3-30
It remains to use that (2* mingye ( w " (yy) by definition. Since ( < 2 when
k log( 4Do ) log 2, the convergence rate of Algorithm is
MyD
log
Do
1
0
(52)
h
14:30
2
33

---

Remark 5. In the proof of Theorem 2 we show that the convergence rate of Algorithm 7 has
i0 T )" where n 2 2, E 2,. By doing multiplicative factor I.- In fact, we can set Ak+1 = = this, we can achieve result similar to that of Theorem If choose 2 3. then the multiplicative factor To will be replaced by another constant, which does not depend on as Iy is generated by Lemma 5
D Missing details in Section
In this section, we provide the detailed proof of the results in Section rate of Algorithm For the stochastic case, we use the notation - to present the other random variables except & The proofs are similar the deterministic case, however, we do not need to prove the boundedness since we have assumed it under Assumption |
4 and conduct the convergence
Lemma 9 and
a 10 are provided to analyze the balance equation estimate of (k--
Lemma 9. Va 2 0, 3 > 0, v E [0, 1), we have
or ++ Br - + v
) (a (a /B )r 20. O.
(53)
2 2
This auxiliary result has been used in [44] Lemma E.3]. We give proof for completeness.
Proof. is easy see that ar 3r increases first and then decreases later as 2
inereases.
achieves maximum on [0, +o0) iff its gradient equals to zero, i. r = (1-v)a r
28
Thus, for 2 0, ar - Sa(( v)a ) - -3(( (1 v)a r )2
2,3
23
(1
v)a
(1 -vja
1 -
<a(
28
23
-
V
Li a T-V
1 1- V
2 a 1-
2
B T
2
3 --
+
1
T
2
2
1--v
Lemma 10. For nonnegative sequences fashie and {% hen, the sequence {hilieN satisfies that
(1
v)ak+1
h&+1
h4 1
M1+11
(54)
h++1
with hgg = Then for 2 1, we have
hy
%-
(55)
This auxiliary result has been used in [[44] Lemma E.9]. We give proof for completeness.
Proof. We prove it by induction.
Since hg 0 < 0, we assume it is valid for some k 2 0, then
(1 v)o++1
h441
S h4
1441
S
1-
7
im
k+
as)
1=1
i=1
34

---

Define (x) == (1-vlar+1
It is easy to verify that (1) is increasing in Hence, it
x1--
suffices to show
k
k+1
k+1
k+1
S
1
+
n
1=1
1=1
1=1
which means
1++11
1++1
k-
R+1
k++
7/ S
(4)
1
2 (1 - 2 v))++11
az)²-²
o:)
+
7(
(56)
1=1
1=1
i=1
i=1
Rearranging (56) gives us
k+1
k+1
k+1
(1 v)
71
0
1-v
i=1
i=1
1=1
==
which is implied by
k+1
k
k+1
- --avaa S
03)
1-
1-V)
a
(57)
1=1
F=1
1=1
The inequality (77
is valid since
k+1
k+1
v
ail
a
1=1
(=1
1=1
k+1
k+1
k+1
k+1
2((
0g 1-V + (1 w){
Σ
a;)
-
a
) >
as)
im1
iml
k+1
k+1
=((1 D)
a:)
a 1)
ai)
=(1 v)a++1,
where the first inequality is due to the first order condition of the concave function (4)--y v E [0, 1].
Next, we provide the upper bound of the expectation of (k--
Lemma 11. Suppose the Assumption 7 holds and f(-) is locally Hölder smooth in Bang (x*). In
Algorithm 2 it holds that
E B[Ad]
S 2" M, 2" + 22
(58)
Proof. We denote (a
f( (++++)]|+- )|, Ab+1 and [f( - +[( A/-
The expectation of (Ag) and 22 satisfies
[E [[)))) 2] ||| f(x (11 - v |||3] o
(59)
B ( E[[ (( F5 < 5²²
From the balance equation, we have
TkT
=[V5((**1 F5(2)t1), ),y 6+1 2. -xth) 1k+1
11
k+l - 11
2
647 Ak+1
<[Vff(**1> -Vf(att) ) 6+1 - + (V f(a
x+
&f(x *+1 y. - x111)
BK+1
+(vf(r**)) Vf(1" (1) 1. M-1 2011
1+++11 -I xh+ 11
647 As+1
3x-1 11 ++
</Moll - + (A/t) + 4
BATTAA11
35

---

Note that I+ is monotonically increasing function. The first inequality uses the convexity of f-) and the second inequality applies the locally Hölder smoothness and Cauchy- inequality.
Case 1: ==
Bu+177 BKF <((M,
Bk+1
)1
24 + (A - A A - 11++
2Av+1
G4T An+1
Bk+1
BK+1Th - Bark-1 S2AR+1((M,
)11 1-1 k 11 + (A + 11+1)ll1 kt2 x x I1+
6 Ac+1
BK+1
BK+IFI - BB-k-11 -2AR+1(M..
)118
k+1
x 1 +
111+
2
3k+1
BK+ITR - BBRT 52(k + [),
)11 ++1 x + 1| + F + ++11)l ht1 x I|+
Bx+1 - Bx 2(k + 1)²
Bk+1 }1ly x+1 112 + /+ + 1 -x
(M,
Fk
2
where we use Au+1 S (k + F) and D FR+1 2 Fk.
We prove that
k 2 10 (() + (AX))) + +2"
(60)
Since = < 2 D2 we prove it by induction. Define k- max (i]3: S 2 > 0, so
wk S k- satisfies the inequality 60 We assume it is valid for certain &: 2 k", then
1
3x+1
3R+1
Ak+1 B&
[2(k: + 1)2(
Illy
2412 12 2(k 1) + 14 +
Fk
D
28
3k++1
2-k + +1)²
1
k+1
112 + 1)) + A ( x x+1 11+
29
29
A x+112
2(k + 1)2 1)2 2
$ 7/
2(k + 1)²
+ Fk
28k+1
23x+1
11 + 1
-2 (k: + 1)2
BK41
Then
(8 (88 Be+1 (Bx41 B&) < 29 (1))))AA
(A + 22+1)
Be+1 52 (1) + 1x+1)² +
Be+1 (k (1) + 1x 2 22
Be41 10 1)? 1 Σ
2'02(AA + A77 22'
k+1
Be+1 < Σ
2 2A! + A37 M?DD?
i=1
where we use 52 < Σ k
200 A? + 28 M2D by induction. Applying the inequality a² + 6² 2
i=1
(a + b)2 where a, b > obtain
BR+1 220
Σ
2 + + + M.
1=1
36

---

We take the expectation of 3x:
J:
B|Bb] SB2$
?(A - ) M,,
<2$
<2$
V2i² + 2 M.D
k + 2n M,,
where we use the Jensen's 's inequality that b] S (B[X]) and estimate Ei= 12 n3 roughly.
Case 2: # 1 Applying Lemma 9 for three times with 11 x 1|, a Mr, $ Bet1 D : = 11ght1 x ||, a' 1 8 2567 ; :r +ly xb+1 11, a" 1
128T
3"
Bx+1
it holds that
256r Au+1
Tkll
1 + 1
M
1 1287 AR+1
H2 I-
+ (A
2 k+1 +
1
Ax1))² 12 2507? Axt1
2
2
2
Bk++1
Bx+1
+ 1 1 1- M
vr 128T 2
K. A
11 1-0
+ (A + ) 118 AM+1
2
31-1
Bk+1
where the last equality is obviously nonnegative.
Similar to the proof of Lemma g we have
ax+1 S 4F AR+11
which implies 7% AR+1 S 4Fk. Consequently,
1 V Mr
(1- 11) Fk Lhu
+ (A + 11+112 2
2
2
Bk+1
BR+1
-M (1 - -1)22 Fk
(4 + + 2020F 1
BK+IP2- BBrk SAa+1
--v
3r41
Be+1
- (1 - -v)2
1-P + (1+1)) (A + A )2 2220
BKTITE - -Bark S(k + MM
Bk+1
Ba+t
Bk+1 Bx S(k + 1)² M - (1 (1-v)
(1-))2² 1)22
14
2u + (k + 1) + 12+) )2
210
BE+1
k
3R41
where we use Ax+1 - (k + 2 and Fk 2 Fk-1- It then follows that
BK+1 - Bb) 2(k + 1)²M, - ((1 v)23)
+ 22 + 1)² k
B kk+
8 8 B2 52(k + +)) - ((1 - 2)28)
1+v
T-p
2 + 1)²
B 2v
b
k+i
We apply Lemma 10 with hy = 83 ak = x (28)
1-
k2 MD 1-v
(1 - v)
1ー k-1
2n
and 7h =
2 (k + 1) it holds that
32 <
2 x (2 + M (1 - v) デ
1-
+
21,2
1=1
<22 1
211-v 211
Σ
<(2 ),,,(1 - 20 12 3v
211
12 AAA
1=1
37

---

Here we estimate Σ i=1 8² < kea roughly. Applying the inequality a²+ I =(a+b)²
where a, b 2 0.
we obtain
3n (2 T+
MM(1- " +2
Finally, we take the expectation of [3::
k
E [2 D'''k""
+2
1 AA7) }
<(2 94TH
2 )M +2
AB
5(2 ( +2
P)
<2 (1 +2#
where we use Jensen's inequality again.
In conclusion, we have [[ S 2 2100" M, DO سيية
+ 2
We are now ready to derive the convergence rate of Algorithm 2
D.1 Proof of Theorem 3
Proof:
In view of the balance equation 166 and the fact [xr]+ 2 it holds that
O<(V (<( +1)) ~55 (o00)1)),) 1), whtl) +
3x+1
11 k+1
112 + The
64T Ax+1
2
(V h+1 1 <(ff( ++1 ). y h+1 xhtl) + Bx+1
1 1+ - x2 +
-24t-2
Th-llk
64TR-Am...
2
(VS(*+t)) E( 1,, y²* - x4111
The first order condition of convex function f(-) implies f(yht1) f(aht11 S (V I thus
f( (f(aht)) + (Vf(x 1tt - btl) + 64 A
B641
1ly 12 +
TkTlk 2
+ +[VS(***') (((
), n+ xtt1).
8e 16 -B8 82-1 804
Because x+1 = Trank + (1 - Tx) gp+l = Thttt1 + (1 - Tx)y** and m7s-
holds that
f(y S(1 TT) + (V)(x ) 1² - x(t1/) + Th (f( + ), x11111)
Ak+11 2211a - 112 + Bx+1 - Bxpz 72
Be+1
16A
+ (Vf() - 1013--((60 t(1) yx+z x ,t2
k+1) <(1 (1) + (f( + (+ ), ghtt1 - ,(411
Br
|| || - 113 + Bk+l 3h +
+
64A
16Ar+1
8 x k+1 + 3k+1 3x 11 x012
+ (1 (1--m)) (T)
vf(x*+1),
64Ax+1
+ (V - &s(( ) xt1
38

---

Since ax+1 (e=1(( (, + 1111aht - u211 S ax+1 (++1(V((att)), ( + -
- 1
we have
f(g - (w)(()) T. (f( + (Vf(xkt))) yetl - 21t11)
+ Bx 1 8* 12+ Bk+1 Bx pz
64A
16A4+1
+ (1 (V)(((( ()( ) 1 + BA+1 - BK || - 11
61Ak-1
+ (Vf(**) f ght!! x 2ttl
11 - +x) + (x( (11 + (V (x))) yhtt - x2(11)
Be 110 - ,²112= + Bk+1 Bx pk
64Ax+1
16A++1
(1-Tx) (V (1l1--f(le v)(x*+1),,) ), - 1 + Bk+1 - BR 2
16A k++
[V &5( gh k.1
Here, the last inequality is due || - S (d++1 + rh)² S 4r
We match the error terms by A sides by As+1. we have
Beti BR 22
Bi-r 8d++1 k+1 Multiplying both
16A++1
16Ac+1
k+1
Ast1f(y SAnf(y") + aa + (5 1, xx )1111)
3k
l1ottl 8 3k+1 Bx
+
64
8Ak-1 k+1
+ Au (V - ([(ext+)) --t--x11 x1t11
+ Ax+1 (V - k+l x² x111).
On the other hand, it holds that
g 5 (1) + Teg(ott1).
(61)
Combining 31) and 61 we obtain
A AA + ax41 (Vf(xtt)), x+1 -btt + g((
3A S/ 1100 | - u& 2 + Bk+1 - 3x _
8A k++
+ - ), - - x+1)
Aut1 Ef(y s+1 - x+
39

---

For 8 1llttt1 12, we use Lemma 4 then
2
A SAn + (f + (Vf(a o - xhtl + g((ht1))
a(f(x') + (Vf(z)), uttt - x²) + g(( + Br 1| - 12t
2
Σ (x('((²)) + (VI(x'), v - 2²) + +((10))
3x 11200 12
2
1-1
3 3k 2 + Ac( - ( ), - -1tt1)
8AR+1
(VS - - At - -
+
SAa((1)) Σ ai((((')) + (VS(x'), e - x²) + ((( + Bu+1 1x=00 112
Σ aa((((+)) + - Sh 11100 - 111112
- +
BK+1 Bk rkt1 + Ax An( - vf(o*t1), ). 21t1)
8A++1
+ A 11) - ( nh - =(t1)..
(62)
We can simplify (33) by using the definition of (x(-)):
A SAvD())) ) + 1 - (o")
+ Bk+1 32 p2
8A++1 k+1 + An ( -VS
((( 1, ), -
-ttt)
(63)
+ A (V &(( ),
nhz - ,ltt).
Applying the upper inequality recursively, it holds that
Aub(1²)) Spa(o*) - -o0(
Bi+1 - Bip + P - -
1=0
+ A+t1 (V/(
411
(1 -
(1(
3x 2
Bo न
A-1
<pn(1* +
+ Σ A - (s(ctt2),)) - xtt2)
k
8
8
+1)
x(t)
Som(o") + 3k
k-1
+
Σ
- -
8
1=0
+ A ( (, -,(t2),
where do (v0) = and 30- 0.
40

---

Since vt = arg min (x),,, we apply Lemma 4 again and obtain that:
A (T)( + BK
P/
Σ
1-
A - V - x²-1)
+
8
1=0
+ + + )((') - -
3K |1000 111
Be r/
ot - x²) + +(((t))
8
A( - - -/((())))) As+1 (V { stth x(t1)
1=
(V(6),=)))
+ Bk 2
||u0 -/11 - x011²
Bk
2 - 2011
1=1
2
Σ A, - ()(x*t1),,)))))))))))))))))))(
), - x1t11
8
- +6(1 101 x1t2
$
(ff(x') + (VI(x'), x" - x²) + +z(x"))
+ 3k
|1000 -211000 - ==111
Bk
l1 x01
2
2
3n 2
Σ
ai+1 (Vf(tt))))) 11 vf(xtt)) ),0² xx")
8
+ A (V - 45 +11 11 g+
)
<Aab(=)) + 3h 11000 x²12 0112_
3r
BR p
11ttt x² +
2
2
8
a++1 (Vf(xt)) vf(x (1 ),0² - =x">
1=0
A { yt x111).
We use Do and Dr to replace 1|=0 - =I11 and 1|u* x²1 Since D8 D3 2Dork 2DDrx. we have
A SAnD(*)) +
Dg D3
BL D +
3x
2
8
k-
+ Σ
a++1
( - vf(z ,, -2")
r²
0=0
+ A - -1
4t -
11
which implies
Bx D2)
Bark
k-1
(1r²) - -(=))=)))))) <
+
Σ
a:4 (Vf(ott1) - (f(x(t1),) - x²)
2Ap
8A
+ A (Vfl(tt))
- ",,
(64)
93rDFR
k-1
Σ (Ht1" -vf(++t)
1² - x²)
SA
+ Art1
(Vi()+t))) El(r((1), -2
41

---

We take the expectations of both sides and obtain
9
Dřr-
[[b((**] - [[b((=)]
<
E
a.41 (Vf("\)))) - vf((""1),, --)]
8AA
1=0
E k-1
A
-
Since E BlVf(=tt))
Vf((x*) ) = 0 and v², x², fi+1 are independent, we have
E
a1+1 (V((xt)) vf(x'')), x5))
=E-et
E
Regn
Σ
( V x²1)
S4t1
For the same reason, have
E
Σ A
(V
- |(+1
E
Egy
(V (f(()t)) ). yttz - r1t1)
0.
Thus
3 Dřa
El(() (xx))
A
We will apply Lemma 11 and 3 to obtain the final complexity. Note that k*
arg min 0sick
Σ
Applying Lemma 3 we obtain that:
F log el
4Da d log 4Do
(65)
k
2k
2i=o
Thus, for k.*, combining the inequality 65) and Lemma
it holds that
E
}]
xx(x))
8x-
D
E
Ak
E
8g D
8
A -1
1=0
(40 x log
2
(66)
<
E[(2
My +u k
3-34
+ 2 Do)
p.
]
8
2k
4D
4D Mr 1 2 k: Do
3-3"
$ 36(
log
e
F
h2
1D
4D
M.D++
Do
36(
log
Vi
where the facts (Bi Jin is nondecreasing and the random variable B is independent of both and D.
Finally, it remains to use 2 xh by definition.
42

---

The following lemma is used to show that the balance equation admits closed-form solution.
Lemma 12. Let 3,I,d 2 and r O. Then the equation
(5+ = -3-
(67)
has unique solution given by
3+ = 3 + [1 Sd]+
(68)
+ d
This auxiliary result has been used in [[4]] Lemma E.1]. We give proof for completeness.
Proof. First, the equation has unique solution since the left-hand side increases from zero infinity monotonically with respect to 84 while the right-hand side decreases from a nonnegative number to zero monotonically with respect to B+.
We show that the + in (68) is the very solution of 67
When - 3d < 0, 8+ = B. LHS = (3+ - B)r = 0 and RHS = -1-3++ = -1- [B]+ S 0,
which implies RHS S = 0. Therefore, LHS RHS and B4 is the solution.
When / - [d 0, 3_ = 8+ -td
L- then LHS (3+ B)r (8 + 11 3)r r 8d
r
and RHS = || 3+d]- = - - = I -3d]++ = r Bd). Therefore.
LHS = RHS and B4 is the solution as well.
E
Two approaches for automatic initialization of parameters in Algorithm 1
E.1
Automatic initialization of 3o
In the proof of Proposition I and Theorem 2 we assume that Bo < 22' This is reasonable since the upper bound of 5% increases polynomial in k, it still holds for enough large k. Previous works often ignore the choice of legal Sg. Nevertheless, we provide a simple method for choosing an admissible Sg.
Algorithm 3 30 Initialization Method
Input: æ0, F, any other point x' E Rdd that satisfies || - -
|| S Fand [('')
a²) >>> 0;
Output: 3 2 L,
I: Set min
- -Vf(=), -
and M = 2
|| -z' - 3//
2: Let ß = F max (ovax(8v220 8v 2M, 128M min Vct:
Proposition 2. Suppose f(+) is locally Hölder smooth and f(-) is not linear function in dom g. i is small enough such that F S. 4Do, then Algorithm can
can generate a 8o that satisfies
Bu < 2222,,, I,,"
(69)
and this method can be implemented in one operation.
Proof. Since
M = 2 5(0') - f(x0) (VI(x")),> - x²)
C
p
> 0,
||000 - 2'112
we have
M
f(x') - f(x²) (V)((²)) -x')
x'
(70)
2
The equation
x E BAD (x*), so that we have 700 is tight and x0,x''
M < (M,, cF - 1
(71)
1+ cF2
43

---

cdrmin((128M) 128MM) sc²² F(128M) " -228(
1 1 M
(72)
Thus
C2 m2 128M] & 2 L.,r
(73)
So initialize 30 mmmmmm(118811 128M).
E.2 Automatic initialization of
As mentioned in the context, Algorithm 1 requires input F guess of 4Do that satisfies F I 4Dp Setting small enough F to meet F S 4Do will incur multiplicative cost of (ADo) in the convergence rate for other algorithms without distance adaptation. contrast, we reduce the multiplicative cost to log"( (4Pa). Moreover, we provide a simple method for obtaining an admissible F S 4Do in some special cases.
Proposition can handle the cases where we can choose xº and make sure f(.) + g-)) is weakly smooth on one of its neighborhoods. Then we can modify the problem by setting f2( f(x) g(x) and g' (a) to get legal
Algorithm 4 F Initialization Method
Input: x² and an initial guess r for 4Do
Output: f S 4Do
1: Initialize i 4-11
2: repeat
3:
++itl
4:
d, d++2 2
5:
Run Algorithm
1 with parameter by one iteration and collect the point ni and the coefficient
B1,1
6: Denote T1,i ||u] 211l
7: until of is interior point in dom g and F1, 2 d;
8: Set F = d,
Proposition 3. For any x E domg. g, g(x) = 0, if there exists ó > 0, S S Bs(x²) C dom g, and let vs be the maximal Hölder exponent of [(-) S with finite local Hölder continuous constant Mus < +00, vs 0, then Algorithm 4 can generate 4Do, and this method can be implemented in finite number of iterations.
Proof. Without loss of generality, we assume å < 3Dg since if 5 3Do we can always take smaller 8' < 3Dg that still satisfies the condition.
Note that Theorem I implies that if F1,6 T1,6 then S f1, S 4Do, and this conclusion is independent of the value of 31. So we only need to prove that this method completes in a finite number of operations. Note that x = Tor + 101-Tol Toly" = Tox +11 70)x = x does not depend on the value of To. The condition of this method ensures that there exists an interior point in the direction of fxxx"..
Applying Lemma 7 it holds that
|00 - 2011 2 !ll! - =1
where we define
min (d.(Vf(x²) (xx))xz=) ) =x') B0|1 - 2012
o = arg
zEdom g
2
(74)
arg min (Vf(z"), =0) + Bolla 1 - x 2012
zédomg
2d,
44

---

Applying Lemma again with h;
80. we have ||l - =01| + 0 as i + too. Therefore, there
2d."
exists large enough 1" such that vi 2 1" satisfies that
2 11l 2
2 10 ==||.
(75)
Case 1: If this method requires at most i operations. Then we prove it directly.
Case 2: If this method requires more than operations.
Inequality 75 show that i E (xxx²) C domg, g. which means if is an interior point. Then, applying the first-order optimality condition to the interior point v!. we have:
d fvf(x)) + (1,(( - =x0==
of x = di Vf(x²)
(76)
B1,
We can adapt the method 3 to obtain legal 30 to produce 31 S cody which guaranteed by Lemma 8 where = 2 T,M,,
Vf(29)|
Vf(+>)|
11 =1|o} - 2011 = d.
2 di
dl-v
(77)
$1
C2
Thus f1,1 d: d. d/-"
2 d, when 2r di S
& and this method requires
Cv [1V Gr
cv
most
log
log loops.
More experiment details
In this section, we provide more details about the experiments.
Softmax problem We first reexamine the softmax problem with more parameter settings. Specifi- cally, we set μ E {0.1, 0.01, 0.001). In all the results, we find that our AGDA consistently performs better than the other compared methods.
10a
10
10
10a
10
10a
109
10
10
10
10
10
10
5000 10090
15000 20000 25000 30000 Steps
5000 10000
15000 20000 25000 30000
5000
10000 15000 20000 25000 30000 Steps
Steps
Figure 4: Performance of the compared algorithms the softmax problem. From left right: 4 0.1, μ = 0.01 and μ = 0.001.
DOG
USP
PX0 [x"3
Cornt
Stape
Ste56
Steps
Figure 5: Performance of the compared algorithms on the I. norm problem. Left: p = with diabetes. Middle: p 1.5 with boston. Right: p = 2 with boston.
45

---

Lp norm problem We consider the following problem as an illustrative example, where the smoothness property can be directly adjusted by modifying parameter p E []:
min #ER
(() |r
blpp-
(78)
where A _nxd b In are taken from real-world datasets LIBSVM. It is important note that the smoothness of this problem can be controlled by changing the parameter as p increases, the degree of smoothness decreases.
We use the same comparison methods as in the softmax problem. adhering to the same parameter settings. In this problem, our algorithm significantly outperforms the other methods, especially when p is small. This suggests that our algorithm is more adaptive in nonsmooth settings and highlights its greater stability.
Large scale problem Subsequently, we present the efficacy of our method when applied to large- scale instances. Our main focus is performance comparison with the UGM algorithm.
F1 Line-search bisection method
Here we provide the pseudocode of Line-search bisection method for clarification.
Algorithm 5 Two-Stage Line Search
Input: 8g. function (-); tolerance d
8n 262
Output: 8k+1
2: while (2 < 0 do
3:
1+i+1
4: end while
Stage 1 complete
5: 1/2 +
6: if 1 then
Case 1: 4 (Bx) 2 0
7:
1. +0
8:
8k+1 +- 8k
9:
else
D Case 2: Need binary search
10:
a - 2% -B3
11:
b + 2% 1 Bk
12:
while
c do
13:
m + (a + /
14:
if l (m) 0 then
15:
a + m
16:
else
17:
b b+n m
end if
19:
end while
B +- b
21:
end if
46


Reviews:
[{"review_id": "rcXfxxTXCG", "reviewer": "Reviewer_MdZu", "summary": "This paper introduces new parameter-free optimization algorithms.\nThe paper then analyzes the convergence rate for the objective function, which is convex and exhibits Hölder smoothness.", "questions": "# Questions\n1. Lemma 7 shows that $x^i,y^i,v^i$ remain inside the ball around $x^*$. Can't Theorem 1 be proven directly from Lemma 7 instead of being proven using Proposition 2?\n\n# Suggestions\n1. In my opinion, the paper should explain more clearly why the algorithm only needs that the objective function is locally Hölder smooth. This is related to question 1.\n2. In Theorem 2, instead of using $z^K$, which is an arg-min, it would probably be better to define $k^\\*$ as in Theorem 3 and use $y^{k^\\*}$.\n3. Missing citation of [1], which introduced a parameter-free algorithm that achieves near-optimal results for both the nonsmooth and smooth cases.\n4. There are some typos in the paper:\n    1. In equation (4), you forgot to write the Hölder smoothness constant.\n    2. In line 184, you accidentally wrote $f$ inside the bound.\n    3.  In Algorithm 2, line 2, you wrote $z$ instead of $v$.\n    4. In Algorithm 2, line 4, you accidentally wrote $\\nabla$ instead of $\\tilde{\\nabla}$.\n    5. In equation (17), you wrote $z^{k^\\*}$ instead of $y^{k^\\*}$.\n\n[1] Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic\noptimization. In Conference on Learning Theory (COLT), 2024.", "limitations": "yes, except what I mentioned in weakness 1.1.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n1. The paper introduces the AGDA algorithm and analyzes the convergence rate bound of this algorithm for the deterministic case. The resulting convergence rate bound is near optimal.\n2. To avoid the problems that the line search in the AGDA algorithm causes for the stochastic case, the paper introduces the AGDA LSFM algorithm, which does not contain a line search. The paper then analyzes the convergence rate bound of this algorithm for the stochastic case and achieves an in-expectation bound. In the case that the domain is bounded, has a diameter $D$, and that $\\\\| x_0-x^* \\\\|=\\Theta(D)$, then the in-expectation bound is near optimal.\n\n# Weaknesses\n1. The convergence rate bounds require that the number of steps $K$ will be $K\\ge\\Omega(\\text{log}(D/\\bar{r}))$.\n    1. In this regard, the paper only mentions this constraint in the proofs that are written in the appendix. The paper should mention this clearly in the theorems themself.\n2. As mentioned in the paper, the AGDA algorithm contains a line search and thus is inappropriate for the stochastic case.\n3. The AGDA LSFM algorithm requires a bounded domain with diameter $D$. The convergence rate bound is dependent on $D$ instead of $\\\\| x_0-x^* \\\\|$, and thus can be very large in the case that $\\\\| x_0-x^* \\\\|\\neq\\Theta(D)$.", "was_revised": true, "final_justification": "The weaknesses that I mentioned still hold after the author's rebuttal; however, in my opinion, none of the weaknesses were major.\nA slight exception is Weakness 1, where the author said they will clarify the theorem; however, the theorem still requires that $K\\ge \\Omega(\\text{log}(D/\\bar{r}))$ in order to be optimal.", "rebuttal": "## Weakness \n**1)The convergence rates of the algorithms hold under the condition that $k \\geq \\Omega(\\log(D_0/\\bar{r}))$. 2) This condition is in appendix and should be mentioned clearly in the theorems.**\n\n**Ans**: We thank the reviewer for the careful reading and agree completely.  Our original proof used the condition $k \\geq \\Omega(\\log(D_0/\\bar{r}))$ to ensure the term $(\\frac{4D_0}{\\bar{r}})^{\\frac{1}{k}}$ in (51) is almost a constant, which simplified the final expression of the rate. While this is a mild condition, its role should be transparent.\n\nTo address this, we have revised the manuscript to make the result more precise. We now state the more general bound directly in Theorem 2, which removes the hidden assumption. The updated rate is:\n\\begin{equation}\n\\mathcal{O}\\left(\\frac{\\widehat{M}_{\\nu}D_0^{1+\\nu}(\\frac{4D_0}{\\bar{r}})^{\\frac{1}{k}}\\log^2 e\\frac{D_0}{\\bar{r}}}{k^{\\frac{1+3\\nu}{2}}}\\right),\n\\end{equation}\n\nWe have added a remark immediately following the theorem. This remark explains that the term $(\\frac{4D_0}{\\bar{r}})^{\\frac{1}{k}}$ approaches 1 as k increases and is bounded by a small constant under the mild condition $k \\geq \\Omega(\\log(D_0/\\bar{r}))$. If $\\bar{r}$ is sufficiently large,  this condition is much weaker than the polynomial dependency on $D_0$ typically required for nontrivial rate in gradient descent. We thank the reviewer for helping us improve the theorem's clarity and precision.\n\n**AGDA contains a line search and thus is inappropriate for the stochastic case.**\n\n**ANS**: Certainly, line search is inappropriate for the stochastic case without stronger assumptions on the stochasticity of the gradients. To address this, we developed AGDA-LSFM, which extends AGDA to the stochastic setting. However, this extension requires the additional assumption that the domain is bounded.\n\n**In the stochastic case, the convergence rate depends on $D$ instead of $\\|\\|x_0-x^\\*\\|\\|$, and thus can be very large when $\\|\\|x_0-x^\\*\\|\\|\\neq \\Theta(D)$.**\n\n**ANS**: Yes, it is a limitation of AGDA-LSFM. We have some ideas about removing the assumption of bounded domain and we think it is a future work. However, you can check our proof of AGDA-LSFM and find out the main error term is $\\frac{\\beta_k (D_0^2 - D_k^2)}{2A_k} + \\frac{\\beta_k \\bar{r}_k^2}{8A_k}$ and the right term can be bounded using $D_0$ but not $D$. So thisthe bound can be partially relaxed comparing to USFGM which dosen't have this property.\n\n## Question\n**Can't Theorem 1 be proven directly from Lemma 7 instead of being proven using Proposition 2?**\n\n**Ans:** We thank the reviewer for this excellent suggestion. The reviewer is correct that Theorem 1 can be proven directly from Lemma 7 using an inductive argument.\n\nThe core of our analysis is contained in Lemmas 6 and 7. These lemmas establish the crucial results for a single iteration of our algorithm (AGDA), including the success of the line search, the one-step convergence error, and the boundedness of the next iterate, given that all previous iterates are well-defined. These findings provide the essential components for the main inductive proof in Theorem 1.\n\nTo improve the paper's clarity and logical flow, we decided to remove Proposition 2 and integrate its content in Theorem 1. We now prove Theorem 1 directly from the foundational lemmas. Recognizing the importance of those lemmas, we will state Lemmas 6 and 7 in the main body of the paper. Moreover, in the revision, we will give an outline to the structure of our proof and clarify the connections between the key lemmas and theorems. \n\n\n\n\n**Why the algorithm only needs the objective function to be locally Hölder smooth?**\n\n**ANS:** This is a great question that gets to the heart of our paper's technical contribution. For local Hölder smooth function, smooth parameter will depend on the variables, and hence it would be potentially be unbounded if we can not guarantee boundedness of the iterates $\\{x^k,y^k,v^k\\}$.\nTherefore, our proof must achieve two intertwined goals simultaneously:\n- Prove Boundedness: Show that all iterates generated by the algorithm remain within the domain where the function is well-behaved.\n- Establish Convergence: Prove the algorithm's convergence rate.\n\nThis dual objective makes the analysis more complex than standard proofs for globally smooth functions, which only need to focus on the second goal. Our inductive proof is designed specifically to handle this challenge. We understand this point could have been clearer. As promised in our previous response, we will better illustrate this key technical intuition and the structure of our proof. Thank you for helping us improve the paper's clarity.\n\n\n\n**In Theorem 2, instead of using $z^K$, it would probably be better to define $k^\\*$ as in Theorem 3 and use  $y^{k^\\*}$.**\n\n**ANS:** We thank the reviewer for this constructive suggestion. We agree that using the same notation for the output iterate in both theorems improves the consistency and readability of our results. In the revised manuscript, we have updated Theorem 2 and state the bound in terms of $\\psi(y^{k^\\*})-\\psi(x^\\*)\\in\\mathcal{O}\\left(\\frac{\\widehat{M}\\_{\\nu}D_0^{1+\\nu}\\log^2 e\\frac{D_0}{\\bar{r}}}{K^{\\frac{1+3\\nu}{2}}}\\right)$, where $k^\\*=\\mathop{\\arg\\min}\\_{0\\le i\\le k}\\frac{\\bar{r}\\_k^{{1}/{2}}}{\\sum_{i=0}^{k-1}\\bar{r}_i^{1/2}}$.\n\n**Missing citation of [1], which introduced a parameter-free algorithm that achieves near-optimal results for both the nonsmooth and smooth cases.**\n\n**ANS:** We will cite and discuss [1] in our revision—thank you for the suggestion.  Our paper focuses on achieving near-optimal accelerated rates across the full spectrum of Hölder smooth functions.  Although U-DOG achieves a near-optimal rate in the smooth setting, it does not have a theoretical guarantee for nonsmooth or weakly smooth problems. A key strength of their work is providing guarantees for unbounded domains, albeit with a suboptimal rate in that setting. We plan to continue our research in this direction in future work.\n\n**There are some typos in the paper.**\n\n**ANS**: Thank you! We have fixed these typos in the revision.\n\n\n[1] Itai Kreissler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic optimization. In Conference on Learning Theory (COLT), 2024."}, {"review_id": "xMU7wQ7PV7", "reviewer": "Reviewer_4xjD", "summary": "This paper propose a novel parameter-free first-order method (called AGDA) for solving Hölder smooth composite convex optimization problems. It is proven that AGDA achieves a near-optimal convergence rate, up to logarithmic factors, without the need to specify the target accuracy in advance. Additionally, the paper eliminates the necessity of line-search procedures in AGDA and introduces AGDA-LSFM. Under bounded domain assumption, a convergence result for AGDA-LSFM is established. Preliminary experiments demonstrate the effectiveness of both AGDA and AGDA-LSFM.", "questions": "Q1. Why introduce the general Bregman distance at the beginning of Section 2 but not use it later?\n\nQ2. Why is $\\eta_k$ chosen in the special form, differing from the earlier approach? What is the underlying insight?\n\nQ3. What is the price of the automatic initialization strategy for $\\bar{r}$ discussed in Remark 3 and Appendix?\n\nQ4. In Fig. 1 (Middle and Right), why does FGM with $\\epsilon=1$ perform better than FGM with $\\epsilon=0.01$?\n\nQ5. Why are standard statistical results not reported for the experiment in the stochastic setting?\n\nTypos:\n\n- Line 16: if $g$ is real-valued, then its domain is the whole space.\n  \n- Eq. (8): $k$ should start from $0$.\n  \n- Should $\\bar{r}$ be introduced after Eq. (4)?\n  \n- In Algorithm 1, should $z^0$ be $v^0$?\n  \n- Line 8 in Algorithm 1 and Line 147: There are two different sums in the definition of $v^{k+1}$ ? By the way, $v_{k+1}$ should be $v^{k+1}$.\n  \n- Proposition 2: It seems that $D_k$ has no definition.\n  \n- Remark 2: A reference is missing for the lower bound.\n  \n- Line 4 of Algorithm 2: $\\nabla f$ should be a stochastic gradient.\n  \n- What is $f$ for the matrix game?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1）The proposed AGDA is novel, combining Nesterov’s dual averaging technique with a distance-adaptive approach.\n\n2）AGDA is shown to achieve a near-optimal convergence rate for solving Hölder-smooth composite convex optimization problems without requiring prior knowledge of smoothness parameters or explicit parameter tuning.\n\n3）The effectiveness of AGDA and AGDA-LSFM is validated through numerical experiments.\n\n**Weaknesses:**\n\n1）The line search procedure used in AGDA introduces additional computational overhead per iteration, which may reduce the algorithm’s overall efficiency.\n\n2）In Line 56, the paper claims, ``In addition, we propose a line-search-free accelerated method that achieves optimal convergence rates ... \" but it lacks clarity following Theorem 3.\n\n3）The paper does not sufficiently discuss the proposed methods in comparison to the restarted variant of SGD, such as the recent results in Attia, A. and Koren, T. (How Free is Parameter-Free Stochastic Optimization?) and Khaled, A. and Jin, C. (Tuning-Free Stochastic Optimization).\n\n4）Although the numerical results are interesting, the paper lacks further experimental results on large-scale model training, which would provide valuable insights.", "was_revised": true, "final_justification": "The rebuttal addressed all of my concerns thoroughly.", "rebuttal": "## Weakness\n**1The line search procedure introduces additional computational overhead per iteration, which may reduce the algorithm’s overall efficiency.**\n\n**Ans**: Yes, the reason why AGDA only achieves a nearly optimal convergence rate with respect to $K$ is the increasing cost of line search compared to FGM. Up to the $K$-th iteration, AGDA requires about $\\mathcal{O}(K\\log K)$ calls of oracle, while FGM only need about $\\mathcal{O}(K)$ calls. We think this issue could be addressed in future work.\n\n\n**2 In Line 56, what the paper claimed lacks clarity following Theorem 3.**\n\n**Ans**: Thank you for pointing this out. Theorem 3 establishes the optimal convergence rate with respect to $K$ for Hölder-smooth and stochastic problems. However, in our analysis, the bound on $D_0$ is relaxed to $D$, which may become large if $D_0$ is not on the same order as $D$. We will clarify this point in the next revision.\n\n**3 The paper does not sufficiently discuss the proposed methods in comparison to the restarted variant of SGD, such as the recent results in [1] and [2].**\n\n**Ans**:  Thank you for pointing out this omission. We acknowledge that our paper does not sufficiently compare our proposed methods with restarted variants of SGD, as discussed in [1] and [2]. \n[1] investigates parameter-free methods and notes that most existing approaches still require certain problem-specific information, such as the Lipschitz constant and $D_0$. In contrast, our algorithms only require an estimate of a lower bound for $D_0$, and this incurs only a minor additional cost. [2] further shows that it is impossible to develop a truly tuning-free algorithm for smooth or nonsmooth stochastic convex optimization when the domain is unbounded. We will include a more thorough discussion of these works in the literature review section of the next revision.\n\n\n**4 The paper lacks further experimental results on large-scale model training, which would provide valuable insights.**\n**Ans**: See our response to 7VzW.\n\n## Question\n\n**1 Why introduce the general Bregman distance at the beginning of Section 2 but not use it later?**\n\n**Ans**: We apologize for the confusion. We will remove the introduction of the general Bregman distance in the next revision.\n\n\n**2 What is the underlying insight of choosing $\\eta_k$ in the special form, differing from the earlier approach?**\n\n**Ans**: FGM, as proposed by Nesterov, achieves a convergence rate of $\\mathcal{O}(D_0^\\nu M_\\nu / k^{\\frac{1+3\\nu}{2}} + \\delta/2)$, where $\\delta$ is set as the target accuracy $\\epsilon$. Under this setting, FGM cannot guarantee convergence to the optimal solution as $k$ approaches infinity. Our key insight is that by adaptively setting $\\delta$ to $\\mathcal{O}(D_0^\\nu M_\\nu / k^{\\frac{1+3\\nu}{2}})$, it is possible to balance the two terms in the convergence rate expression.\n\n\n**3 What is the price of the automatic initialization strategy for $\\bar{r}$ discussed in Remark 3 and Appendix?**\n\n**Ans**: The automatic initialization strategy for $\\bar{r}$ provide a legal $\\bar{r}$ satisfied $\\bar{r}\\leq4D_0$ in some special cases. At the end of the detailed proof of this strategy, we claim that we need implement the first step of AGDA at most $-\\frac{1}{\\nu}\\log\\left(\\frac{\\|\\nabla f(x^0)\\|}{c_\\nu }\\right)/\\log2$ times. Moreover, the first step of AGDA will call at most a constant number of oracle. \n\n**4 In Fig. 1 (Middle and Right), why does FGM with $\\epsilon = 1$ perform better than FGM with $\\epsilon = 0.01$?**\n\n**Ans**: $\\epsilon = 0.01$ corresponds to a large Lipschitz smooth constant for FGM. Consequently, FGM struggles to make progress despite its acceleration. This is precisely the issue our proposed method, AGDA, is designed to overcome. By adaptively tuning $\\delta$, AGDA maintains a well-conditioned trajectory, enjoying the benefits of a small effective error tolerance without suffering from the associated ill-conditioning. This experiment effectively demonstrates the practical advantage of our adaptive mechanism over the fixed-parameter approach of the universal FGM.\n\n**5 Why are standard statistical results not reported for the experiment in the stochastic setting?**\n\n**Ans**: We apologize for not reporting the standard statistical results. We provide some statistical results below and will include them in the next revision.\n\nAGDA-LSFM:\n\n|Epoch|Mean|Std|Var|95%-CI|\n|---|---|---|---|---|\n| 100   | 4.5176e+03 | 1.3818e+02| 1.9093e+04  | (4.4187e+03, 4.6164e+03)  |\n| 200   | 3.1232e+03 | 1.6090e+02| 2.5889e+04  | (3.0081e+03, 3.2383e+03)  |\n| 300   | 2.1278e+03 | 1.8061e+02| 3.2620e+04  | (1.9986e+03, 2.2570e+03)  |\n| 400   | 1.3908e+03 | 5.9527e+01| 3.5435e+03  | (1.3482e+03, 1.4334e+03)  |\n| 500   | 9.6490e+02 | 1.0554e+02| 1.1139e+04  | (8.8940e+02, 1.0404e+03)  |\n| 600   | 6.0236e+02 | 1.5445e+01| 2.3854e+02  | (5.9131e+02, 6.1341e+02)  |\n| 700      | 3.9653e+02 | 2.7015e+01| 7.2980e+02  | (3.7721e+02, 4.1586e+02)  |\n\nAdam:\n\n|Epoch|Mean|Std|Var|95%-CI|\n|---|---|---|---|---|\n| 100   | 6.0804e+03 | 6.1950e+01| 3.8378e+03  | (6.0361e+03, 6.1247e+03)  |\n| 200   | 4.2011e+03 | 7.8974e+01| 6.2370e+03  | (4.1446e+03, 4.2576e+03)  |\n| 300   | 3.1595e+03 | 4.8552e+01| 2.3573e+03  | (3.1247e+03, 3.1942e+03)  |\n| 400   | 2.5412e+03 | 1.8405e+02| 3.3874e+04  | (2.4096e+03, 2.6729e+03)  |\n| 500   | 1.9329e+03 | 1.2730e+02| 1.6206e+04  | (1.8418e+03, 2.0240e+03)  |\n| 600   | 1.4822e+03 | 4.7201e+01| 2.2279e+03  | (1.4484e+03, 1.5160e+03)  |\n| 700   | 1.1632e+03 | 9.7067e+01| 9.4220e+03  | (1.0938e+03, 1.2326e+03)  |\n\nUSFGM:\n\n|Epoch|Mean|Std|Var|95%-CI|\n|---|---|---|---|---|\n| 100   | 1.1473e+04 | 7.6193e+02| 5.8054e+05  | (1.0928e+04, 1.2018e+04)  |\n| 200   | 1.0233e+04 | 3.0175e+02| 9.1050e+04  | (1.0017e+04, 1.0449e+04)  |\n| 300   | 9.3534e+03 | 1.8890e+02| 3.5684e+04  | (9.2182e+03, 9.4885e+03)  |\n| 400   | 8.7421e+03 | 1.6653e+02| 2.7732e+04  | (8.6229e+03, 8.8612e+03)  |\n| 500   | 8.2098e+03 | 1.6352e+02| 2.6739e+04  | (8.0928e+03, 8.3267e+03)  |\n| 600   | 7.7925e+03 | 1.5409e+02| 2.3745e+04  | (7.6823e+03, 7.9027e+03)  |\n| 700   | 7.4379e+03 | 1.5542e+02| 2.4156e+04  | (7.3267e+03, 7.5490e+03)  |\n\nAs shown in the table, our method demonstrates faster convergence and greater stability.\n\n\n**There are some typos in the paper.\nTypos:**\n1) Line 16: If $g$ is real-valued, then its domain is the whole space.\n2) Eq.(8): $k$ should start from 0.\n3) Should $\\bar{r}$ be introduced after Eq. (4)?\n4) In Algorithm 1, should $z^0$ be $v^0$?\n5) Line 8 in Algorithm 1 and Line 147: There are two different sums in the definition of $v^{k+1}$? By the way, $v_{k+1}$ should be $v^{k+1}$.\n6) Proposition 2: It seems that $D_k$ has no definition.\n7) Remark 2: A reference is missing for the lower bound.\n8) Line 4 of Algorithm~2: $\\nabla f$ should be a stochastic gradient.\n9) What is $f$ for the matrix game?**\n\n**Ans**: \n1) Yes.\n2) Yes.\n3) Yes, we will do it.\n4) Yes.\n5) The definition of $v^{k+1}$ in Algorithm 1 is correct and yes, $v_{k+1}$ should be $v^{k+1}$.\n6) Yes, $D_k:=\\|v^k-x^*\\|$. We will add the defination before Proposition 2.\n7) We will add the reference in Remark 2.\n8) Yes, the notation should be $\\tilde{\\nabla} f$ instead of $\\nabla f$.\n9) For the matrix game, we consider $\\min_{x \\in \\Delta_n} \\max_{y \\in \\Delta_m}\\langle x, A y \\rangle = \\min_{x \\in \\Delta_n}  \\psi_p(x) = \\max_{y \\in \\Delta_m}  \\psi_d(y),$ where $\\psi_p(x)\\stackrel{\\text{def}}{=} \\max_{1 \\leq j \\leq m} \\langle x, A e_j \\rangle $ and $ \\psi_d(y) \\stackrel{\\text{def}}{=} \\max_{1 \\leq j \\leq m} \\langle x, A e_j \\rangle$\n\nThen, this problem can be posed as a minimization problem:\n$$\n\\min_{x \\in \\Delta_n, y \\in \\Delta_m} \\{ \\psi_{pd}(x,y) = \\psi_p(x) - \\psi_d(y) \\}.\n$$\n\nAnd the optimal value of this problem is zero.\n\nWe appreciate your feedback and have fixed these typos.\n\n[1] Attia A, Koren T. How free is parameter-free stochastic optimization?[J]. arXiv preprint arXiv:2402.03126, 2024.\n[2] Khaled A, Jin C. Tuning-free stochastic optimization[J]. arXiv preprint arXiv:2402.07793, 2024.\n[3] Dahl G E, Schneider F, Nado Z, et al. Benchmarking neural network training algorithms[J]. arXiv preprint arXiv:2306.07179, 2023."}, {"review_id": "QD6XnP9uDL", "reviewer": "Reviewer_7P9W", "summary": "The paper presents an accelerated gradient method for Hölder-smooth functions that does not require any difficult input parameters, such as the Hölder smoothness constant or the distance to a solution. The algorithm has an almost optimal (up to log factors) any-time convergence rate. The stochastic version of the algorithm relies on the assumption of a bounded domain instead of a line search.\n\nThe paper is well written, with clear explanations of how the proof works. However, I did not check the proofs in the appendix.", "questions": "### Minor questions/typos\n\n- This paper https://arxiv.org/abs/2402.06271 may be relevant.\n\n- l.16: \"where\" is missing\n\n- l.104: Why do we introduce the Bregman distance at all?\n\n- l.166: I think error bounds in optimization community have a bit different meaning. To me that condition looks as the \"Hölder\" descent lemma.\n\n- l. 143: \"that\" is missing\n\n- l. 159 \"smooth smoothness\"\n\n- l. 254: \"t\" is missing", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "My main concern is that I don't know which practical functions this method is applicable to. It seems that the authors don't know either. Softmax and least-squares are smooth problems. Matrix games can be solved using primal-dual methods in time complexity of $O(1/T)$ instead of $O(1/\\sqrt T)$.\n\n### Experiments.\n\n- **Softmax.** Did authors mean that we first fix $x=0$ and used it to define $a_i$? Otherwise, the function $f$ will become quite non-convex and I don't see why 0 will be its solution.\n\n- **Matrix game.** I find it a bit suspicious.  For the matrix game problem we can estimate easily\nall constants we want. Also acceleration is this case ceases to exist. Even good\nsubgradient algorithm should work equally well on this problem. So to me it\nlooks as either intentional not-optimal implementation of other algorithms or\nsome cherry-picking. Or then there must some clear reasons of such start\ncontrast in the performance.", "was_revised": true, "final_justification": "I will keep my score as it is (which is rather positive), as I still find the paper's motivation a bit too narrow for my taste. However, this is, of course, quite subjective.", "rebuttal": "## Weakness\n**My main concern is that I don't know which practical functions this method is applicable to.**\n\n**ANS:** The primary strength of our algorithm lies in its ability to automatically adapt to the effective smoothness of a problem, which is valuable in scenarios where the optimal smoothness parameters for an optimizer are unknown or difficult to determine.\nThis is particularly relevant in several practical settings: 1) Black-Box Optimization where the function's analytical form is hidden; 2) ill-Conditioned Smooth Problems, which may be theoretically smooth, but can behave like a non-smooth function from an optimization perspective; 3) locally Smooth Problems (e.g. piece-wise smooth function): A globally non-smooth function may possess some local smooth structure that our algorithm can exploit to accelerate convergence.\n\nOur experiment with the softmax function provides a concrete example. As shown in Figure 1 (left), when the problem is made ill-conditioned ($\\mu=0.0005$), our adaptive algorithm significantly outperforms specialized methods, including standard non-smooth (DOG), non-accelerated smooth (DADA), and even accelerated smooth (FGM) algorithms. This result highlights our method's ability to find a more effective optimization path by adapting to the problem's structure.\n\n\n**Did authors mean that we first fix $x = 0$ and used it to define $a_i$? Otherwise, the function $f$ will become quite non-convex and I don't see why 0 will be its solution.**\n\n**ANS:** Yes, the correct way to define $a_{i}$ is $a_{i} = \\hat{a}_{i} - \\nabla \\hat{f}(0)$. There is indeed a typo in the paper regarding this definition. Thank you for pointing it out; we have fixed this issue.\n\n**Matrix games can be solved using primal-dual methods in $O(1/T)$ instead of $O(1/\\sqrt{T})$. Result looks a bit suspicious. Subgradient method should work equally well**\n\n**ANS:** \nThe reviewer is correct that specialized primal-dual methods can solve matrix games with a faster rate of $O(1/T)$. Our goal with this experiment was not to claim state-of-the-art performance for this specific problem class, but rather to demonstrate the generality and robustness of our parameter-free framework on a standard non-smooth problem, a testbed also used in [1].\n\nRegarding the comparison to the subgradient method, our algorithm's superior performance stems from its ability to discover and exploit the problem's \"hidden smoothness.\" While the matrix game problem is non-smooth in the worst case, our adaptive method (AGDA) identifies a much smaller local smoothness constant. This allows it to take more effective steps and converge faster. A standard subgradient method cannot adapt to this structure and thus performs more poorly. This finding is consistent with the results in [1], where Nesterov also reported that a subgradient-based method (dual averaging) was outperformed by his FGM on this same problem. The table below provides direct evidence for this mechanism, showing that the effective Lipschitz parameter computed by AGDA is orders of magnitude smaller than that found by the FGM. \n\n| Steps      | 200        | 400        | 600        | 800        | 1000       | 1200       | 1400       | 1600       |\n|:---------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|\n| **FGM**   | 14459.5507 | 43499.1062 | 211329.6208| 236944.2313| 262557.3429| 288169.2348| 620206.7242| 656420.8525|\n| **AGDA**  | 35.8016    | 216.1367   | 474.8734   | 798.8322   | 1213.5683  | 1668.9429  | 1913.2760  | 1837.6467  |\n\n(Table: The computed Lipschitz parameters in FGM and AGDA. The results of FGM are nearly the same as those reported by Nesterov's paper.)\n\n\n\n\n## Minor questions\n\n**This paper [2] may be relevants** \n\n**ANS**: Thank you for bringing [2] to our attention. First, this paper considers the same setting as ours and proposes a novel step size adaptation algorithm. The main difference between our method and this paper is that we use acceleration, which allows us to handle the general case, and we also provide an analysis for the stochastic setting. We will cite [2] in the next revision.\n\n**Why do we introduce the Bregman distance at all?**\n\n**Ans**: We apologize for the confusion. We will remove the introduction of the general Bregman distance in the next revision.\n\n**There are some typos in the paper.**\n\n**ANS:** Thank you! We have fixed these typos.\n\n[1] Nesterov Y. Universal gradient methods for convex optimization problems[J]. Mathematical Programming, 2015, 152(1): 381-404.\n\n[2] Oikonomidis K A, Laude E, Latafat P, et al. Adaptive proximal gradient methods are universal without approximation[J]. arXiv preprint arXiv:2402.06271, 2024."}, {"review_id": "ySD2XfA8Yp", "reviewer": "Reviewer_7VzW", "summary": "The authors introduce a parameter-free optimization algorithm for convex and Hölder smooth objectives, applicable in both deterministic and stochastic settings. The proposed algorithm removes the need for prior knowledge of key problem parameters such as the distance to the optimal solution or Lipschitz constants. It dynamically adapts its step size to achieve near-optimal convergence rates. Numerical experiments demonstrate robustness to misspecification of initial distance estimates and consistent performance across a wide range of scales.", "questions": "How would the algorithm perform if the boundedness assumption (Assumption 1) were relaxed or violated? Could adaptive domain expansion strategies maintain convergence guarantees in unbounded settings?\n\nCan you provide explicit comparisons of computational cost per iteration between your method and DOG/DADAPT? \n\nAbout the logarithmic factors in your convergence rates: are these fundamental to the distance adaptation approach, or artifacts of the current analysis that could potentially be tightened?\n\nFor the stochastic case, how does your balance equation approach compare empirically with variance-reduced methods or adaptive step-size rules like AdaGrad/Adam on unbounded problems?", "limitations": "The bounded domain assumption for stochastic optimization significantly restricts applicability. Many practical machine learning problems (neural network training, sparse regression) naturally involve unbounded feasible sets.\n\nWhile claiming to be \"parameter-free,\" the method still requires choosing initial distance estimate $\\bar{r}$, and performance depends on this choice being reasonable ($\\bar{r}\\leq 4D_0$). The line search adds computational overhead per iteration.\n\nThe convergence bounds include logarithmic terms whose necessity is not clearly established. Compared to optimal rates, this represents a potentially improvable gap.\n\nEvaluation focuses on convex problems with moderate dimensions. Modern machine learning applications involving high-dimensional, nonconvex, unbounded problems are not addressed. The claimed robustness would be more convincing with large-scale evaluations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Quality\nThe theoretical framework is rigorous and builds upon well-established results in convex optimization. The key innovation lies in combining acceleration with distance adaptation to achieve strong guarntees without specifying the target accuracy in advance. \n\nThe extension to stochastic optimization via the balance equation (15) circumvents the line search requirement while maintaining theoretical guarantees, though at the cost of requiring bounded domains.\n\nEmpirical evaluation demonstrates practical utility and robustness, especially regarding sensitivity to initialization. However, the experimental scope could be broader in terms of problem scales and domains.\n\n2. Clarity \nThe paper is well-structured and accessible to readers with background in optimization theory. The motivation behind replacing fixed $\\varepsilon$ with the dynamic $\\eta_k$ is clearly explained and theoretically justified.\n\n3.  Significance\nRemoving dependence on unknown problem parameters while maintaining acceleration is an interesting and useful contribution, in particularly in anytime settings, where classical stopping criteria are not easily applied. The stochastic extension fills an important gap.\n\n4. Originality\n\nThe authors propose a novel approach to parameter-free optimization by combining acceleration with dynamic distance adaptation. The key insight of using variable target levels instead of a fixed one is new and theoretically sound.\n\nIt extends previous work on parameter-free methods (e.g. DOG) in a non-trivial way by incorporating acceleration and Hölder smoothness. The line search procedure and balance equation for stochastic settings represent meaningful technical contributions.\n\n\nWeaknesses\n\n1. Quality \nThe assumption of a bounded domain (Assumption 1) in the stochastic case significantly limits applicability. Many machine learning problems are naturally posed on unbounded domains (e.g., unconstrained neural network training). The authors acknowledge this but don't provide clear guidance on relaxation strategies.\n\nThe convergence bounds contain logarithmic terms that, while claimed to be \"near-optimal,\" lack clear evidence that tighter analysis is impossible. The dependence on initial distance estimation introduces a practical parameter despite \"parameter-free\" claims.\n\nThe local Hölder smoothness assumption, while more general than global smoothness, still requires the optimization trajectory to remain in the required domain, which may not hold if $\\bar{r}$ is poorly chosen initially.\n\n2. Clarity\nThe notation becomes dense in places (e.g., the interplay between βₖ, r̄ₖ, and Aₖ in Algorithm 1), potentially hindering implementation. The line search termination criteria could be specified more precisely.\n\nThe relationship between Algorithms 1 and 2 could be better explained—particularly how the balance equation replaces line search and the computational trade-offs involved.\n\n3. Significance\nWhile theoretically sound, the practical advantages over existing adaptive methods (Adam, AdaGrad variants) in machine learning contexts remain unclear (in what practical scenarios does algorithmic complexity justify the theoretical improvements over simpler adaptive methods?)\n\nThe bounded domain requirement for stochastic optimization limits immediate applicability to modern deep learning.\n\nThe experimental evaluation, while demonstrating robustness, focuses on relatively small-scale convex problems. Large-scale nonconvex evaluations would strengthen the significance claims.\n\n4. Originality\nThe technical contributions, while solid, represent incremental advances over DOG/DADAPT rather than fundamental breakthroughs. The core distance adaptation idea predates this work, and the main novelty is in the specific combination with acceleration.", "was_revised": true, "final_justification": "The authors addressed all the questions that I posed in my review, and I maintain my positive score.", "rebuttal": "Thank you for your insightful comments. Since several questions overlap, we've combined them below to provide a clear and organized response.\n\n## Weakness\n**Concern about the boundedness assumption in the stochastic case. How does algorithm perform without it? Can you use relax it?**\n\n**A** We agree that the boundedness assumption is a limitation for the stochastic case. We appreciate the opportunity to clarify our reasoning and discuss potential extensions. Our primary goal is to design a fully parameter-free algorithm. For stochastic optimization on an unbounded domain, this ambitious goal is provably impossible. As recently shown by Khaled and Jin [1], any parameter-free method will fail with constant probability for some simple convex problems in this setting, as the iterates' error can diverge. The bounded domain assumption is therefore a necessary precondition for the specific theoretical guarantees we aim to provide. While theoretical result seems unpromising, we did some preliminary experiments without the bounded domain assumption.\n\n**Relaxing boundedness** That being said, we believe this assumption can be relaxed if one is willing to move away from a strictly parameter-free design. A promising direction, inspired by [2], involves using a carefully controlled dynamic step size to ensure the iterates remain bounded with high probability. However, this approach would likely add a logarithmic factor (e.g., $O(\\log(T))$) to the convergence rate and hence is suboptimal. Moreover, the proof would require a substantially different analysis based on concentration arguments, which we leave for future work.\n\n**The convergence bounds contain logarithmic terms lack clear evidence that tighter analysis is impossible.**\n\n**A** Thank you for your valuable comment. Compare with the optimally tuned SGD, the convergence rates of AGDA contain a log term $\\log(\\frac{D_0}{\\bar{r}})$. In the distance adapation, this term is generated by the AM-GM inequality, and it is tight in our method.\nTo our knowledge, it is unclear at present whether such a logarithmic term is tight or not. We acknowledge this as an interesting open question and will consider investigating it in our future work.\n\n**The dependence on initial distance estimation introduces a practical parameter despite “parameter-free” claims; Trajector may not in the domain if $\\bar{r}$ is poorly chosen initially**\n\n**A** The reviewer is correct that our algorithm requires an initial distance estimate $\\bar{r}$. In this line of research, the term \"parameter-free\" or \"tuning-free\" does not mean an absence of all user inputs. Rather, it refers to algorithms that achieve near-optimal convergence rates (often within logarithmic factors of the best possible rate) with almost no knowledge of problem-dependent constants. The need for an initial, and potentially very loose, estimate for the distance is consistent with the established definition of \"parameter-free\" used across the recent literature [1, 2, 3]. In practice, our experiments (Fig. 1) demonstrate that the algorithm's performance is quite robust to the choice of this initial estimate.\nFrom a theoretical standpoint, we discuss in the appendix how a suitable $\\bar{r}$ can be determined in a preprocessing step, ensuring this parameter is not a barrier to using the method.\n\n**The local Hölder smoothness requires the trajectory to remain in the required domain, which may not hold if $\\bar{r}$ is poorly chosen initially.**\n\n**ANS:** This is a good question. If $\\bar{r} > 4D_0$, our analysis shows that the algorithm doesn't fail, but its performance degrades gracefully. Specifically, if $\\bar{r}$ is chosen much larger than $D_0$, we can modify the analysis to show that the sequence $\\{x^k, y^k, v^k\\}\\_{k=0,1,\\ldots,K}$ remain within an enlarged ball $\\mathcal{B}_{D_0+\\bar{r}/2}(x^*)$, hence we can still ensure the local Hölder smoothness. \n\nThe consequence of a poorly chosen $\\bar{r}$ is that the rate is $\\mathcal{O}\\left(\\left(\\frac{\\bar{r}}{D_0}\\right)^{\\nu}\\frac{D_0^{1+\\nu}}{K^{\\frac{1+3\\nu}{2}}}\\right),$ as opposed to $\\mathcal{O}\\left(\\log^2\\left(e\\frac{D_0}{\\bar{r}}\\right)\\frac{D_0^{1+\\nu}}{K^{\\frac{1+3\\nu}{2}}}\\right).$ Thus, while a good initial estimate is needed for optimal performance, the algorithm remains robust and convergent even with a poor one. We will add a remark to the paper to clarify this important trade-off.\n\n**Clarity: The notation is dense, potentially hindering implementation; The line search termination criteria could be specified more precisely.**\n\n**ANS:** Thank you for your feedback. We acknowledge that the notation such as for $\\beta_k$, $\\bar{r}_k$, and $A_k$.  In the next revision, we will clarify the relationships between these parameters and provide additional explanations.\n\nThank you for pointing this out. For the function $l_k(\\beta)$, we first locate an interval containing the root by repeatedly doubling the search range. We then perform a binary search within this interval until its length is less than a given tolerance. We will include pseudocode in the Appendix to specify the termination criteria more precisely.\n\n**The relationship between AGDA and its LSFM could be clarified by explaining how the balance equation replaces line search, particularly with regard to the computational trade-offs involved.**\n\n**ANS:** Thank you for your suggestion. The line search uses the current smoothness information to update the parameters at each iteration, whereas the balance equation only relies on information from previous iterates. As a result, the balance equation may not accurately estimate the smoothness at the current point. To mitigate the risk of significant inaccuracies, it is necessary to assume that the domain is bounded.\n\n**Large-scale nonconvex evaluations would strengthen the significance claims. Advantage over existing adaptive methods (AdamW, AdaGrad) unclear**\n\n**ANS** Our paper's primary focus is on establishing a rigorous theoretical foundation for a new class of distance-adaptive, parameter-free optimizers. The current experiments are therefore designed to validate these theoretical contributions in controlled settings. We agree that applying these ideas to large-scale non-convex problems is a crucial next step. However, this often requires significant, non-trivial engineering and problem-specific adjustments (e.g., layer-wise DOG learning rate [2]), which represents a substantial project beyond the scope of this theoretical work.\n\nRegarding the comparison with methods like Adam, we believe our work addresses a **complementary, rather than competing**, challenge. Adaptive methods like Adam excel at learning an effective preconditioning metric, while we focus on learning a robust step size schedule adapt to function's unknown smoothness. The success of Adam follow-up work like Muon, Shampoo suggests, that for many deep learning tasks, choosing the right metric is currently more impactful than adapting the step size alone. We hypothesize that the most powerful approach would likely involve integrating both ideas. It would be interesting to integrate our theoretically-grounded adaptive step size schedule with the powerful metric adaptation of methods like Adam.\n\n**The core idea represents no fundamental breakthroughs, and the main novelty is in the specific combination with acceleration.**\n\n**ANS** We thank the reviewer for acknowledging our work's technical solidity. While our approach builds upon the important foundations of distance adaptation and Nesterov's acceleration, we respectfully argue that their synthesis is a significant and non-trivial step, as a naive combination fails.\n\nOur core contribution lies in the new analytical techniques we developed to make this combination successful. Specifically, our analysis introduces a delicate inductive argument to handle acceleration under the practical assumption of only local Hölder smoothness—which requires simultaneously proving iterate boundedness—and eliminates the domain diameter D as a parameter in the stochastic setting. We believe these technical advances are a key contribution and will revise our introduction to better highlight them.\n\n## Questions:\n\n**Are there specific comparisons of computational cost per iteration between AGDA and DOG/DADAPT?**\n\n**ANS:** The main computational cost of the algorithm comes from computing gradients. Therefore, we evaluate the computational cost by measuring the average number of gradient oracle calls per iteration, as shown in the table below:\n\n| |AGDA|FGM|\n|---|---|---|\n|matrix game|3.06|4.18|\n|softmax|2.7941|3.0024|\n\n\n**For the stochastic case, how does your balance equation approach compare empirically with variance-reduced methods or adaptive step-size rules on unbounded problems?**\n\n**ANS:** In the experiments presented above, we compare AGDA with AdamW. Due to time constraints, we have not yet included comparisons with other adaptive step-size methods or variance-reduced algorithms on large-scale models. We plan to conduct more comprehensive empirical comparisons with a wider range of adaptive and variance-reduced methods on unbounded problems in the future.\n\n**The line search adds computational overhead per iteration.**\n\n**ANS:** Yes, the reason why AGDA only achieves a nearly optimal convergence rate with respect to $K$ is the increasing cost of line search compared to FGM. Up to the $K$-th iteration, AGDA requires about $\\mathcal{O}(K\\log K)$ calls of oracle, while FGM only need about $\\mathcal{O}(K)$ calls. We think this issue could be addressed in future work.\n\n[1] Khaled A, Jin C. Tuning-free stochastic optimization. arXiv:2402.07793, 2024.\n[2] Ivgi, M., Hinder, O. and Carmon, Y., 2023. DoG is SGD’s best friend: A parameter-free dynamic step size schedule. In ICML\n[3] Attia, A. and Koren, T., 2024. How free is parameter-free stochastic optimization?. arXiv:2402.03126\n[4] Bernstein, J. and Newhouse, L., 2024. Old optimizer, new norm: An anthology. arXiv:2409.20325."}]

Author rebuttal:

Meta-review: The paper studies the problem of minimizing a convex function that is Holder smooth, both in the deterministic and stochastic settings. The main contributions of the paper are parameter-free algorithms that attain nearly-optimal convergence guarantees under some assumptions such as bounded diameter in the stochastic setting. In contrast, prior work requires knowledge of problem parameters such as the smoothness. The paper evaluates the empirical performance of the proposed algorithms on small scale instances.

The reviewers generally appreciated the theoretical contribution and were positive about the paper. The reviewers raised several concerns, including significant limitations of the experimental evaluation, the overhead introduced by the approach, the bounded domain assumption for the stochastic algorithm, and the extent of the technical novelty. The author response provided additional experiments with larger-scale datasets. Following the discussion, the reviewers remained positive about the paper and there was consensus that the paper meets the threshold for acceptance.
Decision: Accept (poster)