DADA: Dual Averaging with Distance Adaptation
Authors: Mohammad Moshtaghifar
Anton Rodomanov
Daniil Vankov
Sebastian U Stich
Venue: ICLR 2026 Poster (2026)
Keywords: Adaptive Optimization
Universal Gradient Method
Dual Averaging
Primary area: optimization
TL;DR: Dual Averaging with Distance Adaptation (DADA), a novel parameter-free universal gradient method for solving convex optimization problems.

Abstract: We present a novel parameter-free universal gradient method for solving convex optimization problems. Our algorithm—Dual Averaging with Distance Adaptation (DADA)–is based on the classical scheme of dual averaging and dynamically adjusts its coefficients based on the observed gradients and the distance between its iterates to the starting point, without the need for knowing any problem-specific parameters. DADA is a universal algorithm that simultaneously works for a wide range of problem classes as long as one is able to bound the local growth of the objective around its minimizer. Particular examples of such problem classes are nonsmooth Lipschitz functions, Lipschitz-smooth functions, Hölder-smooth functions, functions with high-order Lipschitz derivative, quasi-self-concordant functions, and (L0, L1)-smooth functions. Furthermore, in contrast to many existing methods, DADA is suitable not only for unconstrained problems, but also constrained ones, possibly with unbounded domain, and it does not require fixing neither the number of iterations nor the accuracy in advance.

Published as conference paper at ICLR 2026
DADA: DUAL AVERAGING WITH DISTANCE ADAPTA- TION
Mohammad Moshtaghifar University of British Columbia mmoshtaq@ cs wbc.
Anton Rodomanov
CISPA Helmholtz Center for Information Security anton. rodemanov@cin spa .de
Daniil Vankov
Sebastian U. Stich
Arizona State University
CISPA Helmholtz Center for Information Security www.cheecipc...e..ccc
dvankov@asu.edu
ABSTRACT
We present novel universal gradient method for solving convex optimization problems. Our algorithm-Dual Averaging with Distance Adaptation (DADA)- is based the classical scheme of dual averaging and dynamically adjusts its coefficients based on observed gradients and the distance between iterates and the starting point, eliminating the need for problem-specin universal algorithm whose convergence rate adapts to the local behavior of the objective around its minimizer, through bounds on its local growth. This leads a single method with explicit, models, including nonsmooth Lipschitz functions, Lipschitz-smooth functions, Hölder-smooth functions, functions with high-order Lipschitz derivative, quasi- self- coffodnncrd functions, and (Lg, L -smoohh functions. Crucially, DADA is applicable to both unconstrained and constrained problems, when the domain is unbounded, without requiring prior knowledge of the number of iterations or desired accuracy.
parameters. DADA is a
guarantees across broad range
INTRODUCTION
Gradient methods are among the most popular and efficient algorithms for solving optimization problems arising in machine learning, as they are highly adaptable and scalable across various set- tings (Bottou et al., 2018). Despite their popularity, these methods face a significant challenge of selecting appropriate hyperparameters, particularly stepsizes, which are critical to the performance of the algorithm. Hyperparameter tuning is one of the standard approaches to address this issue but is time-consuming and resource-intensive process, especially models become larger and more complex. Consequently, the cost of training these models has become significant concern (Sharir
al. 2020 Patterson al. 2021).
Typically, line-search techniques have been used to select stepsizes for optimization methods, and they are provably efficient for certain function classes, such Hölder-smooth problems (Nesterov) 2013). However, in recent years, several so-called parameter-free algorithms have been developed which do utilize line search (Orabona Tommasi 2017: Cutkosky & Orabonal 2018 Carmon
& Hinder 2022; Ivgi et al., 2023 Khaled et al. [023] Mishchenko & Defazio (024). Notably, one strategy involves dynamically adjusting stepsizes based on estimates of the initial distance to the
optimal solution (Carmon & Hinder 2022 [vgi et al. 2023 Khaled et al. 2023). Another approach
leverages lower bounds on the initial distance combined with the Dual Averaging (DA) scheme (De- fazio & Mishchenko 2023 Mishchenko & Defazio 2024). However, these methods primarily focus on nonsmooth Lipschitz or, in some cases, Lipschitz-smann smooth functions. Some of these methods also come with additional limitations, such as requiring bounded domain assumptions (Khaled et al.
2023) or failing to extend to constrained optimization problems (Defazio Mishchenko 2023 Mishchenko & Defazio, 2024

---

Published as conference paper at ICLR 2026
Method
Universal
Constraints
Unbounded domain
No search
Stochastic
DoG (Iygi et 2023
DoWG Khaled atl 2023
Bisection
Camoo & Hinder 2022
Prodigy MMishhhenko & Delazin 2024
X
X
D D-Adaptaton (Dalazio & Mislchenko 2023
X
UGM (Nesterov) 2015
DADA (ADA(Uurs)
Note that UGM different definition of universality. They call their methrd universal hecause works for Holder-smoath functions, which are only a subset of the functions we consider.
Table A comparison of different aduptive algorithus to solve D "Universal" means the ulgorithm achieves problem- dependent convergence rates across convex function classes by exploiting the growth the objective near min- imizer. "C "Constraints" means the algorithm
he applied constrained problems. "Unbounded domain" means the algorithm can he applied to problems with unhounded feasible sets. "Stochastic" indicates that the algorithm is analyzed in the stochastic setting. "No search" means the algorithm does not use an internal search procedure.
To formalize the discussion, we consider the following optimization problem:
min fz)), E
(1)
where Q S Rd is a nonempty closed convex set, and f: R2 UUUUU {+oo} is a proper closed convex function that is subdifferentiable on Q. We assume that Q is a simple set, meaning that is possible to efficiently compute the projection onto Q. We also assume problem I has a solution x² E int dom f. The starting point in our methods is denoted by 20.
Contributions. In this paper, we introduce Dual Averaging with Distance Adaptation (DADA), a novel universal gradient method for solving (I. Building the classical framework of weighted DA (Nesterov |Nesterov[2005b] (0055)) DADA incorporates a dynamically adjusted estimate of Do == || x ||. in- spired by recent techniques from (Ivgi et al. 2023 Carmon & Hinder 2022) and further developed in (Khaled et al., 2023), without requiring prior knowledge of groblem-specifie parameters. Fur- thermore, our approach applies to both unconstrained problems and those with simple constraints, possibly with unbounded domains. This makes DADA a powerful tool across a wide range of appli- cations.
We start, in Section 2 by presenting our method and outline its foundational structure based on the DA scheme (Nesterov) 20055). Our main theoretical result, Theorem establishes convergence guarantees for broad range of function classes.
To demonstrate the versatility and effectiveness DADA, in Section we provide complexity esti- mates across several interesting function classes: nonsmooth Lipschitz functions, Lipschitz-smooth (QSC) functions, functions with Lips-
functions, Hölder-smooth functions, quasi-self-concorte chitz high-order derivative, and (Lu, -mmoohh functions. These results underscore DADA's abil- ity to deliver competitive performance without knowledge of class-specific parameters.
Related work. The development of parameter-free first-order methods has received increasing tention in both optimization and machine learning. A central goal in this line of work is to design algorithms whose performance does not depend on prior knowledge of problem's specific parame- ters, such as smoothness constants, Lipschitz parameters, or distance to the that are rarely known in practice.
quaiiztr--uanntiesss
Classical approaches to removing stepsize tuning include techniques such as Polyak's stepsize rule (Polyak 1987) and doubling schedules (Streeter & McMahan, 2012). While effective certain settings, these strategies either rely on access to the optimal value or introduce additional overhead through repeated restarts. contrast, more recent parameter-free methods aim achieve near- optimal performance without requiring such auxiliary procedures.
A large group of recent parameter-free methods is based on AdaGrad-type conditioning (Duchi al. (011). These methods adaptively accumulate squared gradient norms adjust the effective stepsize. This idea underlies several recent cistance-adaptatti
algorithms, including DoG (Ivgi et al.] 2023), DoWG (Khaled et al. 2023), D-Adaptation (Defazio & Mishchenko 2023). and Prodigy [Mishchenko & Defazio 2024). Although these algorithms achieve parameter- free con- vergence guarantees for nonsmooth Lipschitz Lipschitz-smooth objectives, their theoretical rates
2

---

Published as conference paper at ICLR 2026
do not automatically adapt to broader families of convex functions. We summarize the main prop- erties the algorithms we compare against Table
Beyond AdaGrad-type schemes, coin coin-betting algorithms (Orabona & Pal 2016) provide adaptive guarantees in online and stochastic optimization by treating learning as a sequential investment
game. In different direction, Carmon and Hinder (Carmon & Hinder 2022 propose a bisection- based SGD routine that adapts to the unknown smoothness or distance- distance-to-optimue to-otimm by iteratively solving simpler subproblems. Both coin-betting and bisection approaches orthogonal to ours but share the goal of eliminating learning rate tuning through adaptation mechanisms.
Another universal method worth noting Nesterov's Universal Gradient Method (UGM) (Nesterov 2015), which achieves optimal rates for Hölder-smood functions via adaptive line search. While UGM is often described "universal," its scope limited smoothness-varyinn settings and does not extend to broader function classes such as quasi- maasii-eff-concordant or high-order smooth functions. Moreover, its reliance on internal line search procedures makes it less practical in constrained or composite problems.
Notation. In this text, we work the space Id equipped with the standard inner product (:, and the general Euclidean norm ||ж||| = (Bx, x²)/22 where B is fixed symmetric positive definite matrix. The corresponding dual norm is defined in the standard way ||s||= max -+|- (s. x)
(s. B-1 Thus, for any 8, x R.d, we have the Cauchy-Schward inequality (s,, .> S || |all- The Euclidean ball of radius
O centered at x E Rd is defined as B(r, == {u E Rd
lyy - x|| S r). For a convex function f: I + R {+oo) we denote its effective domain as dom == {x E Rd f(x) < +ooh. The subdifferential of f at point E dom f is denoted by 0f(r), and Vf(x) E 0f(x) denotes subgradient. We use ff(x) rather than g E 0f(x)
throughout the paper to keep the notation lightweight.
2 DADA METHOD
Measuring the quality of solution. Given approximate solution Q problem (I) and an arbitrary subgradient /x(x) E az(x). we measure the suboptimality xr by the distance from x
to the hyperplane {y (Vf(z), y) =0:
e(x) (Vf(z), x²) (2 0).
(2)
[+)()
This objective is meaningful because minimizing v(x) also reduces the corresponding function residual fzx ff. Indeed, there exists the following simple relationship between u(x) and the function residual (Nesterov) 2018 Section 3.2.2) (see also Lemma 3 for the short proof):
f(x) - f I (()(x))
(3)
where
w(t) max f(x) -f B .))
(4)
measures the local growth of f around the solution x². Note that inequality 3 is nontrivial only when B(x", (()), S dom f.
By bounding wt), we can derive convergence-rate estimates that simultaneously apply broad range of problem classes (we discuss several examples in Section 3
The method. Our algorithm is based on the general scheme of DA (Nesterov) 2005b) shown in Algorithm Using standard (sub)gradient method with time-varying coefficients is also possible but requires either short steps by fixing the number of iterations in advance, or paying an extra logarithmic factor in the convergence rate (Nesterov) 2018 Section 3.2.3).
Do and 3g = @(Vk), The classical method Weighted DA (WDA) selects the coefficients a 1=
where Do is a user-defined estimate of Do- The convergence guaranteed for any value of Do but one must pay multiplicative cost of p², where p == max Da De ). if the parameter Do is Do D.

---

Published as conference paper at ICLR 2026
Algorithm 1 General Scheme of DA
Input:
Q, number of iterations T 2 1, coefficients (a=)k=o (Bx)
with nondecreasing 3x
for O,... 1 do
Compute arbitrary 9x (x*x))
#k+1 argmin (Ei= as (9i, 10 xz)) + Me+1 || 2oll²}
Output: of argmin se er 1) f(x)
This cost can be significantly high if Du is not known almost exactly. To address this issue, we propose DADA, which reduces the cost to a logarithmic term, log" offering substantial improvement.
unknown.
Specifically, our approach utilizes the following coefficients:
Tk
04
BA = =cc+++
F == max max Te, F) == 1 Zz
(5)
11
IErCE
where f 0 is a parameter and c certain constant to be specified later. what follows, we assume w.l.o.g. that g& j 0 for all 0 < k < T since otherwise the exact solution has been found, and the method could successfully terminated before making iterations.
As see, the main difference between WDA and DADA, is that the latter dynamically adjusts its estimate Do by exploiting Tt. the distance between Te and the initial point Zo. This idea has been explored in recent works (Carmon & Hinder 2022 lygi et al. 2023). which similarly utilize rs in various ways. Other methods also attempt to estimate this quantity using alternative strategies, based DA and the similar principle of employing increasing sequence of lower bounds for Do Defazio & Mishchenko 2023 Mishchenko & Defazio 2024).
The convergence guarantees for method are provided in the result below: Theorem 1. Consider Algorithm for solving problem
① using the coefficients from with
> 22. Then, for any T 2 1 and 07 = mino v(xk), it holds that
f(x))) - f S w(()),
and
eD
eD
4 <
log
(6)
VT
F
where D := max (T,
2c Do} and D = v2(DDu + D)). Consequently, for given 8 0, it holds
c-v2
that u < 8 whenever T (8)), where
D2 To(8) = 82 log eh
Let us provide a proof sketch for Theorem here and defer the detailed proof to Appendix We begin by applying the standard result for DA (Lemma 5) which holds for any choice of coefficients ag and 3x:
8x D2 <
35 D
a 19.ll-
Σ
1
23,
where D; |1:- x" and v; v(x,) for all i 2 0. Use the specific choices for a and Bg as
defined in we obtain (see Lemma 6):
cvk + D3 cvk+ DJ
VE k--
Σ t=
Fan +
2
Dropping the nonnegative F,o, from the left-hand side, we can show by induction that is uniformly bounded (see Lemma]] 7
Fk S D,
4

---

Published as conference paper at ICLR 2026
where D is the constant from Theorem I This bound is crucial to analysis, as need to eliminate fk-1 from the right-hand side of 7 Achieving this requires selecting the coefficients precisely defined in (5). which is the primary difference compared to the standard DA method (Nettrrov 2005b). Next, using the inequality D/ - Di S 2rk Dp. we get
h-1 Frv S
Vk Y Th
< (Do + =
After establishing this, the rest of the proof follows straightforwardly by dividing both sides by ΣE= F and applying the following inequality (valid for any nondecreasing sequence Fk. see Lemma 2
log 8o
Fg
ISKST
===
Fb
T
This gives us
+
eD f
log
VT
which is almost except for the extra factor of (z)+ This extra factor, however, is rather weak as it can be upper bounded by constant (say,
exp(1)) whenever T 2 log 4. The case of T < log D is not interesting since then ( holds trivially because, for any k 2 0, in view of (2) and Lemma 7 we have Uk I D& S D. According to Theorem [ our method converges for any e > v2. that minimizes this bound is c 2/2. more detailed discussion of this choice is provided in Appendix C
obtain the smallest complexity bound (up logarithmic factors), the value
3 UNIVERSALITY OF DADA: EXAMPLES OF APPLICATIONS
Let us demonstrate that method is universal in the sense that it simultancously works for mul- tiple problem classes without the need for choosing different parameters for each of these function classes. For simplicity, assume that V fx=")
(this happens, in particular, when our prob- lem ( is unconstrained) and measure the e-accuracy in terms of the function residual. This as- sumption made only keep the discussion clean and readable, and it also reflects an important practical setting (unconstrained problems, or constrained problems with x² in the interior of Q)- The general constrained case, where V fz(") + O, covered Appendix D there, for some func- tion classes (e.g.. Lipschitz-mmooth), the complexity bounds include an additional f/ /ll3/c2 term that may affect the rate. We also assume, for simplicity, that the objective function satisfies all necessary inequalities on the entire space, but all our results still hold if they are satisfied only locally at x² (see Appendix D). To simplify the notation, we also denote log = 1 + log t and Do == max ; || - x= []]]], where is the parameter of our method.
Nonsmooth Lipschitz functions.
This function class is defined by the inequality
[x(x) - [v)] S Lol|ar - vll
for all v, y E Rdd For this problem class, DADA requires at most (see Corollary 10
o L _2 log? F
Do
oracle calls to reach r-accuracy, which matches the standard complexity of (sub)gradient meth- ods (Nesterov) 2005b 2018), up to an extra logarithmic factor. Note that a polylogarithmic factor in Do appears in the complexity bounds of all distance addattattit methods (Defazio Mishchenko
2023 Ivgi et al. 2023 Khaled et al. 2023 Mishchenko & Defazio 2024).
5

---

Published as conference paper at ICLR 2026
Lipschitz-smooth functions.
Another important class of functions those with Lipschitz gradi-
ent:
[Vf(2) V & L1|| yll
for all 2, y E Rd. In this case, the complexity of our method is (see Corollary 13
o ( (
log Du
This coincides with the standard complexity of the (nonaccclerated) gradient method on Lipschitz- smooth functions (Nesterov 2018, Section 3) up to an extra logarithmic factor.
Note that the complexity of DADA is slightly worse than that of the classical gradient method with line search (Nesterov 2015 which achieves complexity bound of O [ + logl L [), where P
the initial guess for L1. The difference is that the logarithmic factor in the latter estimate appears in an additive way instead of multiplicative.
Hölder-smooth functions. The previous two examples are subclasses the more general class of Hölder-smooth functions. It is defined by the following inequality:
[V)()) [ S H2llæ vll"
for all f,y E RRd, where E [0, 1] and H, 2 0. Therefore, for = O, we get functions with bounded variation of subgradients (which contains all Lipschitz functions) and for 1 we get Lipschitz-smooth functions.
The complexity of DADA this problem class is (see Corollary 16
o
(
H
Do D log
This is similar to the =a 14 D3 + log
Hu
complexity of the universal (nonaccelerated)
gradient method with line search (GM-LS) (Nesterov 2015). where İ is the parameter of the method. Again, the complexity of GM-LS slightly better since the logarithmic factor addi- tive (and not multiplicative). However, GM-LS is not guaranteed to work (well) on other problem classes such as those we consider next.
Functions with Lipschitz high-order derivative. This class is generalization of the Lipschitz- smooth class. Functions in this class are times differentiable, and have the property that their pth derivative (p 2) is Lipschitz, i... for all x, y E Rd, we have
[<')(>> V sw))ll < Lp
where the ||-|| norm in the left-hand side is the usual operator norm of symmetric p-linear operator: ||A||| = max |||l= [|]][]]]] For example, the pth power the Euclidean norm is an example of function in this class (see (Rodomanov & Nesterov 2019)). The complexity of DADA this problem class is (see Corollary 19
o
[V''((>")
Lp pple
D log? Do 7
max 2
+
Although line-search gradient methods might be better for Hölder-smooth problems, to our knowl- edge, they are not known to attain comparable bounds on this function class.
Quasi-self-concordaan (QSC) functions (Bach 2010). A function is called QSC with parame- ter M > it is three times continuously differentiable and the following inequality holds for any Tr, U. Rd.
f2) u, < M(V f(x),, u) [|ll-
(8)

---

Published as conference paper at ICLR 2026
For example, the exponential, logistic, and softmax functions QSC; for details and other examples, see (Doikov) 2023). When applied to a QSC function, our method has the following complexity (Corollary 2:3:
( [V
Do log F
In terms of comparisons, second-order methods, such as those explored in (Doikov 2023). are more powerful for minimizing QSC functions, as they leverage additional curvature information. Their complexity bound, in terms of queries to the second-order oracle, is O(M Do log Fo + log Dow clu
)
where Fu = f(x)) - -f" Do is diameter of the initial sublevel set, and 9o | (V((x))
(see (Doikov] 2023 Corollary 3.4)). However, each iteration of these methods is significantly more expensive.
To our knowledge, the QSC class has not been previously studied in the context of first-order meth- ods. The only other first-order methods for which one can prove similar bounds are the nonadaptive variants of our scheme, namely the normalized gradient method (NGM) from (Nesterov 2018 Sec- tion 5) and the recent improvement of this algorithm for constrained problems (Nesterov 2024
(Lo. - smooth functions. As introduced in (Zhang et al. 2020 function f is said to be (Lo, - smooth if for all Rd. have
I [(x) S Lo (1|V/(>>|
The complexity of DADA on this class is (see Corollary 26
([1AD8 LoDi e
log? Do
Up the extra logarithmic factor, this matches the complexity of NGM from (Vankov al. 2024). with the distinction that their approach is less robust to the initial guess of Do. Specifically, the penalty for underestimating
D latter method is multiplicative factor of p² while in our method this factor is logarithmic: log
EXPERIMENTS
To evaluate the efficiency of our proposed method, DADA, conduct series of experiments convex optimization problems. Our goal is to demonstrate the effectiveness DADA in achieving competitive performance across various function classes without any hyperparameter tuning.
We compare DADA against state-of-the-an distance- addattttionn algorithms, namely, DoG (lygi et al., 2023) and Prodigy (Mishchenko & Defazio 2024), using their official implementations without any modifications. We also consider the Universal Gradient Method (UGM) from (Nesterov) 2015) and the classical Weighted Dual Averaging (WDA) method (Nesterov) (005b). For UGM, choose the initial value of the sene-h parameter Lo = 1 and set the target accuracy to = 10 For WDA, we use the coefficients a₃ = D. and 3x Vk, where Do | x="
TT
For each method, we plot the best function value among all the test points generated by the algorithm against the number of first-order oracle calls. We set the starting point to 2o = (1,..., 1) and select the initial guess for the distance to the solution comparison between DADA and DoG (Ivgi et al. 2023), as DoG employs a similar initialization strategy. In all experiments, we fix 5 10 Additionally, conduct separate experiment to evaluate the sensitivity of DADA to the choice 5.
8(1 [2ol)). This choice ensures fair
We have several experiments different problem classes. However, due space constraints, present only a single representative experiment in this section. The remaining experiments can be found in Appendix

---

Published as conference paper at ICLR 2026
p 2.0.d10000
pm 10000
p K.D.d- 10080
10"
DvB
10-0
10-t
20066
20/60
10:3000
40002
100/60
70000
10030)
Namber of oradi sule
Mumber ces
Number of colb
Figure 1: Comparison different methods on the worst-case function.
Worst-case function. As an example of function with Lipschitz high-order derivative, sider the following worst-case problem from (Doikov et al. 2024):
d-1
min aERo
{ f(x)
=
(0)
x 20 + [p(0pp.
where p 2 2, and (1) is the ith element of x. The optimal point in this problem is is 0.
As illustrated Fig. [ nearly methods exhibit similar performance when p 2, except for Prodigy whose convergence becomes slow after few initial iterations. While Prodigy eventually reaches similar accuracy to the best methods, it is much slower at the beginning the process. As p increases, method converges significantly faster than DoG. We suspect that this improvement arises because our method adapts to the high-order smoothness of the function, whereas DoG's convergence rate remains unchanged and does not take advantage of this property.
In contrast, both DADA and UGM demonstrate stable and consistent performance across different values of p, with DADA performing slightly better than UGM.
5 DISCUSSION
Comparison with recent distance-adaptation methods. Let us briefly compare our method
with several recently proposed parameter-free algorithms, namely, DoG (Ivgi al.
2023 DoWG (Khaled et al. 2023), D-Adaptation (Defazio Mishchenko 2023) and
Prodigy Mishchenko & Defazio 2024).
To begin, we clarify the key differences between our method and other existing gradient methods using the distance- addattttionn technique. One immediate difference is that
DA instead of the classical (sub)gradient method employed by DoG. We could also instantiate our approach us- ing the standard subgradient method instead of DA. However, doing would either require fixing the number of iterations in advance or would worsen the overall complexity by an additional poly- logarithmic factor in the target accuracy. However, the most significant difference lies in how the sequence of gradients is handled. In contrast to existing distance-adaptation methods, which follow the AdaGrad (Duchi al., 2011) principle of accumulating squared gradient norms, our method simply normalizes O& by its own norm. This modification makes our method universal, ensuring that the distance from x² to the supporting byperplane-cooverrges to zero, which is not known to be the case for DoG, even for deterministic problems.
Both DoG and DoWG employ a similar approach to estimate D, = ||0 - x"|| and achieve compa- rable convergence rates for Lipschitz-smooti and nonsmooth functions. Similarly our approach, DoWG considers only the deterministic case, but with an additional assumption of the bounded fea- sible set. They have different definition of universality, considering only Lipschitz-smooth and nonsmooth settings.
Furthermore, to the best of knowledge, these D-Adaptation and Prodigy have not been tended to constrained optimization. Nonetheless, their methods yield notable results in experiments, demonstrating strong empirical performance.
8

---

Published as conference paper at ICLR 2026
It is important to emphasize that the advantage of our method over DoG does not lie in guaran- teeing convergence. Indeed, (Ivgi et al. 2023 Theorem 1) shows that DoG asymptotically con- verges minimizer for any convex function, with complexity of Ō ((-L))) where LR max.e Rt) [ for R 3Do and denotes the target accuracy in the function value. However, this complexity bound has critical drawback-it remains inversely proportional c² across all function classes, which is not the case for our method. For illustration, consider the setting where ʃ has an L2-Lipschitz Hessian. Further, assume for simplicity that the problem unconstrained and that || )| is zero (or negligibly small). In this case, the above complex-
0 - ). which is substantially worse than Ō 2 for DADA (see Corollary 19). Thus. in comparison to DoG, our method provides significantly stronger effi- ciency guarantees and exhibits automatic acceleration under favorable conditions for considerably broader family of function classes.
ity bound for DoG becomes
Conclusion. We proposed DADA, a new adaptive and universal optimization method that ex- tends the classical Dual Averaging algorithm with novel distance adaptation mechanism. Our method achieves competitive rates across a wide class convex problems including Lipschitz, Lipschitz-smoott, Hölder-smooth, quasi-self-concorddat (QSC), and (To, L1 smmothh functions- without requiring parameter tuning or knowledge of smoothness constants. In contrast to recent approaches such DoG, DoWG, D-Adaptation, and Prodigy, DADA seamlessly accommodates both constrained and unconstrained settings, and does so without requiring restarts or line searches.
DADA provides a unified and adaptive framework for convex optimization with convergence guar- antees under minimal assumptions. Future work includes extending DADA to stochastic and non- convex optimization, and evaluating its empirical performance in large-scale learning tasks.
Here, we use the that functions with Lipschitz Hessian, La =0 (LiR+ 4 42))). where 1;
2 f(*")]l-

---

Published as conference paper at ICLR 2026
REFERENCES
Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384 4414, 2010. doi: 10. F0.S21400-EJJS511. URL http:://dpo............ http:////oi..rr//0..o 022111..111441 0 -2210029--J5555
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale ma- chine learning. SIAM Review, 60(2):223311, 2018. URL https://aci.org:
16M1080173
Yair Carmon and Oliver Hinder. Making SGD parameter-free In Proceedings Fifth Confer- ence on Learning Theory, volume 178, pp. 2360-2389, 2022. URL htt.kttst/s//cceee.....
mlr. pww.s/rsssvvvv v1 18 carmon22a html
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-fre online learning in Banach spaces. In Anmual Conference Computational Learning Theory, 2018. URL https:
//api. semant icscholar wwwprrrrgg//eee Crg/
Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by D-adaptation. In Pro-
ceedings of the 40th International Conference Machine Lecumingg volume 202, pp. 7449-7479, html
2023. URL https: http::://prrceeeiss........ www.::/wweee.ao...............m. ott.:/accc...a...oo....e///////a
Nikita Doikov. Minimizing quasi-seeff-concordaal functions by gradient regularization of Newton method, 2023. UBL/ttpps://axxc...orr////
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized Newton method. SIAM Journal on Optimization,, 34(1):27-56, 2024. doi: 10. 10.1137//2M15194444 URL
https://dde wttp:o...13//22.....5..
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2121-2159, 2011. URL
http:// jml wttgpapprraae...oo /vi 2/ duchi1la .html
Maor Ivgi, Oliver Hinder, and Yair Carmon. DoG is SGD's best friend: A parameter-free dynamic step size schedule. In Proceedings of the 40th International Conference on Machine Learning, pp. 14465-14499, 2023. BtLhhtts::/ arxiv. org/ ppf/2302.222/ 12022
Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. DoWG unleashed: An ef- ficient universal parameter-free gradient descent method. In Advances in Neu- ral Information Processing Systems, volume 36, pp. 6748-6769, 2023. URL
Zijian Liu and Zhengyuan Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises. ArXiv, abs/2303.12277 2023. URL https::/apl..sematticcchooo org/
CorpusID:2576633
Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter- free learner. In Proceedings of the 41st International Conference on Machine Learning, vol-
ume 235, pp. 35779-35804 2024. URL https:: ftttss://proeeednggs.oo mlr ptess/v235/
m1 shchhnenk224a..o .html
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103: 127-152, 2005a.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Program- ming, 120:221-259, 2005b. URL pettps://aph. http://w.e..oooeee.eeo.ooo.oooor 14935076
Yurii Nesterov. Universal gradient methods for convex optimization problems. Mathemati-
cal Programming, 152:381-404, 2015. URL httpss//app...mmmttccccoooo org/
CorpusID:1806277
Yurii Nesterov. Lectures Convex Optinization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.
URL https::/app www.steetttttttooeet org/
CorpusTD: 12:15350776
10

---

Published as conference paper at ICLR 2026
Yurii Nesterov. Primal subgradient methods with predefined step sizes. Journal of Optimization Theory and Applications, 2024. doi: 10.10077440957--22440444444 URL httphtts::////m /arxiv..
org/abs/ 230..233.... 14742
Francesco Orabona and Dániel Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems (NeurIPS), 29, 2016.
Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through
coin betting. In Neural Information Processing Systems, 2017. URL https://api.
David Patterson, Joseph Gonzalez, Quoc Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training, 2021.
URL httpttss///axi...oto/ org/ 2004. 10350
Boris T. Polyak. Introduction Optimization. Optimization Software, Inc, 1987.
Anton Rodomanov and Yurii Nesterov. Smoothness parameter of power of Euclidean norm. Jour- nal of Optimization Theory and Applications, 185:303-326, 2019. URL https:://// //api. semant i oospsscsooooo.oooooooooooraaaaaa 19:3966803
Anton Rodomanov, Xiaowen Jiang. and Sebastian U. Stich. Universality of AdaGrad stepsizes
for stochastic optimization: Inexact oracle, acceleration and variance reduction. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// openreview wet.ee.weeeeeeeeee www.:eetttoooooe htt//forummmii wtt.ee/.eeeooooomiimm--/m/ ddrnnnddddiinn AV
Or Sharir, Barak Peleg, and Yoav Shoham. The cost of training NLP models: concise overview, 2020. UtLpttps: http/xixivvo.oo/// abs 2004. 08900
Matthew Streeter and H Brendan McMahan. No-regret algorithms for unconstrained online convex optimization. In Conference on Learning Theory (COLT), pp. 1-11, 2012.
Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U. Stich. Op- timizing (4, -mooohh functions by gradient methods, 2024. URL http:://axxss...orr
2bs/2410.. 10800
Jingzhao Zhang, Tianxing Hc, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelcrates training: A theoretical justification for adaptivity. In International Conference on Learning Rep- resentations, 2020. htLpstts:: http///pppe//eeeeeee/e net fett/forrummldBBJJgppoo/

---

Published as conference paper at ICLR 2026
A AUXILIARY RESULTS
The following result has been established in prior works such as (Liu & Zhou 2023 We include the proof here for the reader's convenience.
Lemma 30).
Lemma 2. Let (d be positive nondecreasing sequence. Then for any T 2 1,
+ log edz do
d
do
di
T
Proof. Let A4 = + 2z E1-11 de for each 2 0 (so that Ao = 0). Then, for each 2 0, we have
dx41A4+1 Ax = de.
which implies that
A& + (1- dk
Akt1
AІ Akt1
As.
dx+1
dx+1
dx-1
Summing up these identities for all 0 S k < T - 1, get
ST
Σ ==
dk Ar
+
T-1
Σ
1
d&
) As A
A7 + -Sr),
dx+1
dx+1
k=0
where A7 maxosksT A ga Aş and have used the fact that (d:) is nonde-
creasing. Hence,
ST
A
+ T ST
Applying now the AM-GM inequality and denoting .r = (de)) (E (0. 1)), we can further estimate Sr Tyr, giving us
TTT
A
2
+ T(1 yr)
Thus,
dn
1
(1 (1+ -r))
min 15kST
< 7
-i=0 di
A
T
Estimating further 7(1 7T) < - -Tlog log 77 the claim.
1 and substituting the definition of yr, we get
The following lemma is classical result from Nesterov 2018 Lemma 3.2.1).
Lemma 3. Let x. dom if be such that f is subdifferentiable on x. Then, we have fxx f < w(v())), where w(.) and v(-) are defined as in (2 and (with fx) being an arbitrary subgra- dient from (f()).
Proof. Let E denote the orthogonal projection of x ty: (Vf(x), v) 0}:
onto the supporting hyperplane
B Vf(z)
== + v(z)
Then, (VI()), x) 0. and || - v(x). Therefore,
f(x) < f(z) + / x) f(²),
and hence,
-()) < x11)) w(v())).
12

---

Published as conference paper at ICLR 2026
Lemma 4. Consider the nonnegative sequence (de) that satisfies, for each ks 0.
dk+1 max d2. R + yd
where 0 y < 1 and R 2 are certain constants. Then, for any k 2 0, we have
dR S max {1-,
R.
Proof. We use induction to prove that de S D for a certain constant D to be determined later. To ensure that this relation holds for it O, we need to choose 2 dg- Let us now suppose that our relation has already been proved for some k 2 0 and let us prove it for the next index & + 1. Using the induction hypothesis and the given inequality, we obtain
dx+1 S maxx R + yd & max(D, R +++700 DD}.
To prove that the right-hand side is S D, we need to ensure that R + +D < D, which means that need choose D - R. Combining this requirement with that from the base of induction,
we see that we can choose D = max - R, do
B PROOF OF THEOREM
Lemma 5, In Algorithm 7 for any S k T, it holds that
0, x²) + 8k 10 - 1²12
3x
1
02
Σ
1
x²11
x²
1 1=0
199
2
2
2,3
1=0
where Bo is an arbitrary coefficient in (0, 81).
Proof. For any 0 S k S T, define the function (1x(()) as follows:
k-1
Σ as x x.) + 3x
(x)
2 || xoll?
so that vo(x)) = Ae || zoll (with 30 as defined in the statement). Note that the is fe-strongly 2 convex function and ny. is its minimizer. Hence, for any x E Q and 0 s k < T, we have
3x || 1x112
vx(z) 2 v + 2
(10)
where = ()x))) Consequently,
Bk+1 3k
oht th+t (IK+I) 1) = (xx++)) + an (gles Tz41 1 xx) +
| - xol1
3R || - .xa12 + ak (gk, Tk+1 -ra) + 3k+1 Bx
2 1/ +
|
xoo1
8g ||x+11 - xx + a (gk, #k+1 - xA) 2 v/t
ag
2 n +
| 11.
2
2
Telescoping these inequalities and using the fact that vi = 0, we obtain
28, 11
1=0
Combining this inequality with the definition of tha and 10 thus obtain
akgi x- xz)) + Bk | x²112 vx(x")
B
> wh
||
x 112
2
2
1
a
BR
l1g.11.
11
+
||
x x²1
2,3
2
1=0
Rearranging, we get the claim.
13

---

Published as conference paper at ICLR 2026
Lemma 6. Consider Algorithm using the coefficients defined in (5) holds for all I k S T:
Then, the following inequality
cvk+1
COk+
V
Feus +
D
D
1-
2
2
1=0
where Dj: =1 x"] and 02 == v(zz).
Proof. Applying Lemma and the definition of vi we obtain
0.cillos11=+ + 8x
8c D
2
D
2
28
1=0
==0
Substituting our choice of the coefficients given by we get
cvk+1
cvk+1
CV k +
Vk
F.m 2
D
D
D2 +
k-11
where we have used the fact that Fą is nondecreasing and
Di=o VFF
2
Lemma 7. Consider Algorithm 1 using the coefficients defined Then, we have the following inequalities for all 0 & k T:
5 and assume that /2.
V2 c
Fk S D,
D& S Do D.
2c where D = max c-v2
Do} and D3 == =|æ x²|l.
Proof. Both bounds are clearly valid for k 0, so it suffices to consider only the case when 1 < T.
Applying Lemma 6 dropping the nonnegative Frys from the left-hand side and rearranging, obtain
2v
2 k-r
D < D3 +
R- D8
2Vk +
Consequently,
V2
D3 ~ Do + T4-1-
(II)
Therefore,
Pą || xool < D2 + Do 2Do + V2 Tk-1-
Hence,
V2
FA = max(Fx-1,72)) I max Fk Fk-1, 2Du +
F2-1j
Since 2 was allowed to be arbitrary, we can apply Lemma to conclude that
2
2c
)=
Fk < max F,
Do = max F, c V2 Do = D.
This proves the first part of the claim.
Substituting the already proved bound on FĄ into III. we obtain the claimed upper bound on Dg-
We now ready prove the main result.
14

---

Published as conference paper at ICLR 2026
Proof of Theorem | Let T 2 be arbitrary. According to Lemma 3 and the fact that w(+) is nonde-
creasing, we can write
f(x7) f min [f(x)) f*]
min w(ex) w(++), 0S
ogks7
where == v(ra) and tp = minlo This proves the first part of the claim.
Let us now estimate the rate of convergence of oy.. To that end, let an arbitrary S S T. In view of Lemma we have
k-1
cvk (D. D2) + Vk - --
Σ
2
where D3 = || x²1 Note that
D D = 11000 - x 11 || x x²11 (1 - x'1 - |0 - x [][ - x + 1| - x²1)
s 2 xo 20 x² 2r Do-
Therefore, we can continue as follows:
Σ F.m S cvi + Do +
k-1
Vk - (cDo
- ( + 1
vik-i)v++ c
0
S + - DV
k+1 2
Tk:
where the second inequality is due to the fact that Fs = max(fR-11 1, Jk the final inequality is due Lemma 7 and the constants D and D are as defined in the statement. Hence,
Frus
Fk
k+1
=
min Osick
0i S
D
Fz
2
Letting now k argmin ISkST
and using Lemma
we obtain
2i-0
D k++1
PT
eTT
D
D
eD log 7
bi S 1t
log
where we have used the fact that k² + T
S
27 (since
S k- S T) and that FT S D
(see Lemma 7) This proves 6 in the case when 2 log (2)) exp( + log 5e.
D since then we can further bound
On the other hand, by the definition of uy and Lemma 7 we always have the following trivial inequality for any 0 < k < T-T1 -
Uk (V(()) x²) Dr Do D
V2
DSD.
[[((x)]
cD log eD This means that (6) is also satisfied in the case when T < log since then / D log D DVT 2 D (we still consider T 2 1). The proof of (6) is finished.
2
VT
The final part of the claim readily follows from 6
C How TO CHOOSE THE CONSTANT
According Theorem our method converges for any V2. However, the choice of can influence the constant factor in the complexity of DADA. Hence, our goal here is to find the optimal constant that minimizes T. (6). To determine this c, let be sufficiently small, so that
2c Do
2c
D = max F. c
v2 Do-
/2
15

---

Published as conference paper at ICLR 2026
Then, disregarding the logarithmic factors, due their minimal impact on the complexity of our method, we can determine the optimal constant c that minimizes
D= v2 ve + : - v2(eet c- v2 Do.
This is the value
c= 2v2.
(12)
For this optimal choice of we get 1) = [F. 4Do} and D 4Do + D, so the complexity of our method given by Theorem iis
To(o) = eAD D)2
eD F
log 8²
D CONVERGENCE OF DADA ON VARIOUS PROBLEM CLASSES
In this section, we analyze the complexity of DADA across different problem classes. To achieve this, first establish bounds on the growth function:
w(t)
max zEB(2*
f(z) - f",
and determine the threshold such that (1)) for a given c. Subsequently, we combine these results with the complexity bound (()) derived in Theorem enabling us to estimate the oracle complexity of DADA for finding an e-solution in terms the lunction residual.
D.1 NONSMOOTH LIPSCHITZ FUNCTIONS
Assumption 8. The function f problem ①1) is locally Lipschitz x". Specifically, for any x B(x", P)) the following inequality holds:
[(x) - 1r Tollx - x²11.
(13)
where Lo,P p > 0 are fixed constants.
Lemma 9. Let f be locally Lo -ipschttht x* (Assumption 8y. whenever E 5(c), where
Then, w(t) S for any given
8(c) min {
Lo .j.
Proof. According to 13). for any t < p. we have
w(t) Lot.
Making the right-hand side < c, we get the claim.
Combining Theorem I annd Lemma
we get the following complexity result.
Corollary 10. Consider problem
T under Assumption g Let Algorithm ! Twith coefficients 5 be
applied for solving this problem. Then, f(x))- - f" S for any given whenever 2 T(e), where
LE (e2
e
T(c) max
dd D log
and the constants D and D as defined in Theorem
16

---

Published as conference paper at ICLR 2026
D.2 LIPSCHITZ- FUNCTIONS
Assumption 11. The function f in problem ① is locally Lipschitz-smooth at x". Specifically, for any B(x D), the following inequality holds:
I1 || x=1 + (V(((=",,==='))
(14)
where Li, 0 fixed constants.
Lemma 12. Assume that f is locally Lipschitz-smooth at x² with constant L1 (Assumption
Then, (t) S for any given e > 0 whenever t S 6(c), where
8(e) = min {v Li (122 |1
Proof. According (1). for any B(x", P), have
f(x) - S V5 ||||| x"1l
+ 2/ || x²1
La
2
Hence, for any 0stsp.
w(t) - h (V((")))
To make the right-hand side S suffices to ensure that each of the two terms is S
I 1 s 2'
[V
2
Solving this system of inequalities, get the claim.
Combining Theorem I and Lemma
12 get the following complexity result. ① under Assumption 77 Let Algorithm
Corollary 13. Consider problem
| with coefficients (5) be
applied solving this problem. Then, f(xT)) f S ffrrr any given whenever 2 T(c), where
T(e) max {4
V[V 2
eD F
e D2
log"
p3
and the constants D and D defined in Theorem
D.3 HÖLDER-SMOOTH FUNCTIONS
Assumption 14. The function I in problem ① is locally Hölder-smooth at x². Specifically, for any x B(x", the following inequality holds:
He x= 1211222
f(z) S (Vf(") r")
(15)
I
where v E [0, 1] and H.: > O are fixed constants.
Lemma 15. Let f be locally (v, Hy)--Höller-smooth at x" (Assumption given e whenever t S 5(c), where
14).
Then, w(t) S e for any
(1 + v)e
T
8(c) = min
PS.
2H,
Proof. According to 15 for any
B(x", .p). we have
- f f < f(( - x11l + Hy
|| x=1 221
17

---

Published as conference paper at ICLR 2026
Hence, for any 0 0 P.
H2 g 1+v
w S [V
To make the right-hand side of the last inequality I c, it suffices to ensure that each of the two terms is S ;:
c 2 VV )|
H t1 S
E
1+V
2
Solving this system of incqualities, we get the claim.
Combining Theorem Tand Lemma
15 we get the following complexity result.
Corollary 16. Consider problem ①I under Assumption [4] Let Algorithm S coefficients (5) be applied for solving this problem. Then, [(xrr) 8" S for any given whenever 2 (t), where
[
2H,
F4
4|V 2²
eD
T(c) max
o² D2 log 7
(1+
p2
and the constants D and D are as defined in Theorem
D.4 FUNCTIONS WITH LIPSCHITZ HIGH-ORDER DERIVATIVE
Assumption 17. The function J in problem ① is such that its pth derivative is locally Lipscccti at x² Specifically, f is times differentiable on B(x", ,p) and, for any E B(x", p), the following inequality holds:
| f(x((>)
& Lp x=1
where Lps P 0 are fixed constants.
The Assumption 17 immediately implies the following global upper bound on the function value:
(()) D x"1'
1p+ x 11ptt
Lp
(16)
Lemma 18. Assume that J has locally Lipsccit pth derivative at xt (Assumption 17 Then, ((1) 6 for any given e > whenever S 5(c), where
ie ()+1)][Vi fxx)))
pple
8(c) min
min 25iSp
Lp
"0 (1++))V((>>))
Proof. According (16), for any B(x", p). have
Lp (p 1)!
f(x) - ft < V [1)) 21 V''((2))) -='x="))l==="11
| x" 21|1tt1
Therefore, for any < < p. we have
Lp
w(t) < [V I|l.
[1') +
(p+ l)I
To make the right-hand side S c, suffices to ensure that each of the following inequalities holds:
Lp
[VS( ||.1 D+I' [ 1+1'
pp+1
D+I == 2......9 ..
(p+1)1
Solving this system of incqualities, we get the claim.
Combining Theorem
1 and Lemma 18
get the following complexity result.
18

---

Published as conference paper at ICLR 2026
Corollary 19. Consider problem 11 under Assumption 17 Let Algorithm Wwit coefficients (5) be applied for solving this problem. Then. f(xr) - S fforr any given whenever 2 T(e), where
(p + [+11
T(c) = max
max 25+5p
ile
Lp
(p+ (++1)1V
eD log
D
p!c
F
and the constants D and D are as defined in Theorem
D.5 QUASI- SELF-CONCORDANT FUNCTIONS
Assumption 20. The function J in problem ① is Saaii-eef--Concrdaare (QSC) in a neighborhood x² Specifically, it is three times differentiable in neighborhood of x² and for any x E B(xx,, and arbitrary directions u, v E Rd, the following inequality holds:
{<)()) u, v) S ( [(x),, u) [|]l,
where M 0 and 0 are fixed constants.
The following lemma provides an important global upper bound on the function value for QSC functions.
Lemma 21. (Doikov 2023 Lemma 2.7) Let f be QSC with the parameter M. Then, for any I, E dom f. the following inequality holds:
f(y) $ f(x) + (Vf(z), x) + (V2 - 2).y x))((Mll xI)),
where pp() c'--1
Lemma 22. Assume that f is a locally QSC function at x* with constant M (Assumption 20 Then, w() S for any given e > 0 whenever S ö(E), where
1 M V 2(E - (c-])]([(((x11]] 2|[ o)
8(e)
min
Proof. According Lemma 21 for any x E B(x", p). we have
f(x) f* s (Vf(x"), xx) + (V2 f(x (xx x²) x²) {M([| x²1))
< |V ||= + | f(x 11 p(M - =1))).
x0
Therefore, for any S $ p. we get
(t) [V (()))))]+++ || [(=")
(17)
where we have used the fact that pp-) is an increasing function.
Note that, for any into 17). we obtain
M we can estimate s(MM) S y(1)
Substituting this bound
(t)) < Vf(x")]l+++ + (e 2) / 2 fx=))
To make the right-hand side suffices to ensure that each of the two terms is S 5:
[f 2. (e - 2)=
Solving this system of inequalities, we get the claim.
Combining Theorem I Land Lemma 22 get the following complexity result. [ under Assumption 20 Let Algorithm 7 with coefficients 5 be
Corollary 23. Consider problem
applied for solving this problem. Then, f [(x)) J < ffr any given whenever T 2 ((e), where
T(e) max Mr 2(e 2(e-2) 2(e-2)[V3 4 4 12
eD
2 2 log
and the constants D and D as defined in Theorem
19

---

Published as conference paper at ICLR 2026
D.6 (Lu, L1) -1)-SHOOTH FUNCTIONS
Let us now consider the case when Q = R and is (Lo, Li) -smothh Zhang et al. 2020 meaning that for any x E IRd
[V & Lo + L=]])(>))..
where Lo, L, 2 0 are fixed constants.
Lemma 24. Vankov et al. 2024 Lemma 2.2) Let f be (Lo, -smoohhh Then, for any x, y E IRd, it holds that
((0) s (x) (VI()),y x) Lo + L LI
E(Tilly-
1
where E(() = -1-
Lemma 25. Assume that f is (Lu, L1) -mmothh function. Then, w(t) S for any given
whenever t E 8(c), where
2x
8(e) = min
Li
3(Lo + Li [ill)((++)l)))
Proof. According to Lemma
24 for any x E Rd, have
< x Lo L
V
Il.
f(x) f f
[(L2||> x²
Li Lo + L1 ff(xx)) )l.
S ||=1Ix =211+
E(L1 || x²|))
Therefore, for any 2 0, we get
w - [V Lo + I [[|VS((*)Il
E(Lnt),
(18)
L
where the second inequality uses the fact that ((x) is an increasing function. Note that, for any 0 < < J. we can estimate
1,tt
3
E(L.t) S
I LiP.
2(1 41)
4
Substituting this bound into 18 we obtain:
3(Lo + (1{)))
(t) < V [V((x*)) 1lat+
4
To make the right-hand side of the last inequality I c, it suffices to ensure that each of the two terms is I 5:
3(Tg + T [V
[lf(=")),ts 2'
Solving this system of inequalities, we get the claim.
Combining Theorem I and Lemma
we get the following complexity result.
Corollary 26. Consider problem
under the assumption that f is an (Lo, L1 L1)-smooth function. functtion.
Let Algorithm 7 with coefficients 55) be applied for solving this problem. Then, f(z f e for
any given > O whenever T > (e). where
T 3(Lo + L1 V 4 4[(f(())
eD
T(e) = max
2 è 2
log
2c
and the constants D and D as defined in Theorem
20

---

Published as conference paper at ICLR 2026
n- 1000, 10000 2000--0000000 pm
2000, 2 9.01
21 1000, 2000, 0.005
Fist
321
337
33-1
200.0
50000
326032
506600
330302
20000
<2660
sr6ce
102.00
nurrer of orecesolt scall
Number of sel
Nambar of oforide
Figure 2: Comparison of different methods on the Softmax function.
n- 2020, 2020,
2000, 2020,
1000, 2000, -0000,0000000000
DoC
D-C
DoC
p7
10'
hrodgr
101
10"
101
30
107
107
491
107
000
40303
150030
03303
130003
03030
00303
Figure 3: The ratio for the Softmax function with different optimal points x².
Pt
E ADDITIONAL EXPERIMENTS
Softmax function.
Our first test problem is
(a;, x)
bi
min FER"
f(x) = log
Σ exp
(19)
S ni, and / >> This function can be viewed as smooth approximation of maxigign .²) b.] (Nstteoov 2005a).
where a; E R2, and b,
To generate the data for our problem, we proceed as follows. First, we generate i.i.d. vectors à with components uniformly distributed in the interval [-1, for = 1,..., and similarly for the scalar values by- Using this data, we form the preliminary version of function, f. We then compute a, a (0) and use the obtained (a,, b;) define our function f. This way of generating the data ensures that x² = 0 is solution of our problem.
The results are shown in Fig. where fix n 10 and 2n, and consider different values of {0.1, 0.01, 0.005]. As we can see, most methods exhibit similar performance for = 0.1 ex- cept for Prodigy which stops converging after a few initial iterations. This issue, along with decline in performance for UGM, persists y decreases, whereas DADA, DoG, and WDA remain largely unaffected. Notably, DoG performs very similarly to DADA, which we hypothesize is primarily due to the similarity in estimating Do.
Additionally, Fig. illustrates the ratio between Do and f, showing the estimation error Prodigy, DoG, and DADA throughout the optimization process. For Prodigy, we use Do to generate the plot. The figure demonstrates that DADA and DoG exhibit similar behavior in estimating Dn, despite em- ploying different update methods Dual Averaging and Gradient Descent, respectively. However, Prodigy appears encounter challenges in estimating Do its estimation stabilizes at a relatively large value.
danax
Hölder-smooth function.
Let us consider the following polyhedron feasibility problem:
min #ER
f(x)
(a, -b.4%
(20)
21

---

Published as conference paper at ICLR 2026
4 1.0, 10000.0- 1200
0- 1,56 10000, 1000
4 2.8.n 10000, d
Ded
19
Protip
30
10-3
10'7
10"l
10t1
16m
10-12
12
2000
2,393
5032
1060
2000
5230
1000
4.00
Number Numberatoreco oforede ca
Namber otorads
Numbar orack
Figure 4: Comparison of different methods on the polyhedron feasibility problem.
p
p
107
107
Pr23 DADA
Prodayy
DANA
0400
10
10a
300
25
47
37-
18
107
300
101
20000
80303
40005
SE000
193532
20000
03331
A0333
40200
139333
20000
03333
40303
190000
Namber oracd
Namber oww.cccccccooom
Figure 5: The ratio D for the worst-case function with different optimal points x". F,
where a, b, E Rd q E [1. and [r]+ max(0, T). This problem can be interpreted as finding point x" E Rd lying inside the polyhedron P {ar (a,, x) b,, I...., n). Such a point exists if and only if 0.
Observe that problem (0 Hölder-smoote with parameter v = q - 1. Therefore, by varying E []. we can check the robustness of different methods to the smoothness level of the objective function.
The data for our problem is generated randomly, following the procedure in (Rodomanov et al. 2024]. First, we sample x² uniformly from the sphere radius 0.95R centered at the origin. Next, generate i..dd vectors with components uniformly distributed in [-1, 1]. To ensure that x0), < O, we invert the sign a, if necessary. We then sample positive reals 8; uniformly from [0, 0.11mmll where Cmin (a,,(,;;"") O, and set b, (a,, x0) st. By construction, x² is a solution to the problem with f 0.
10 d 10 R 1 and consider different values of E 1., 2}. As shown in Fig. 4 as q increases and approaches 2, the performance of DoG significantly declines. However, DADA, Prodigy, and UGM demonstrate similar performance regardless of the choice of q.
We select
Worst-case function. In addition to the experiments presented in Section we evaluate the es- timation error of Do for Prodigy, DoG, and DADA throughout the optimization process, as shown in Fig. 5 The figure illustrates that while Prodigy's estimate of Dp. shows some improvement over time, remains noticeably inaccurate. Moreover, for DoG, the estimate deteriorates as p increases, a behavior that is not observed with DADA, whose estimate remains stable across different values of p.
Comparison of different initial estimates of the distance. In this experiment, evaluate the sensitivity of DADA to the choice of the initial point Zg. We consider the same Softmax function as in (19) with 10 d 2n, and (0.5, 0.1,0.013,
The results are shown in Fig. where we consider 8 E [10-1...., 10-63. As we can see, the choice of 8 does not affect the performance of DADA, which consistently achieves similar performance across all tested values.
22

---

Published as a conference paper at ICLR 2026
0.1
1-0000
30
Gam 24
307
10
Warber staaii
Figure 6: Comparison of different initial estimates of the distance on the Softmax function with different values of μ.
23


Reviews:
[{"review_id": "Sy1FxmKLU5", "reviewer": "Reviewer_7W2a", "summary": "This paper proposes DADA, a parameter-free version of dual averaging (DA). The main idea of parameter-free methods is to adaptively tune the step sizes based on the observed distance of iterates from the starting point to reduce the cost incurred by the (estimated) initialization scale (denoted by $\\rho$ in the paper). Applying this to DA, we can adjust the parameters based on a running estimate of an adaptively estimated lower bound of $D_t$, and the authors show that this yields convergence guarantees having a smaller $\\log^2 \\rho$ dependence while maintaining rates with respect to other factors. The paper also shows theoretical results under applications to a wide variety of function classes (nonsmooth Lipschitz, Lipschitz-smooth, Hölder-smooth, functions with Lipschitz higher-order derivatives, quasi-self-concordant, and $(L_0, L_1)$-smooth). The rates usually match previously known methods up to logarithmic factors while maintaining the benefits of distance adaptation.", "questions": "- Are the guarantees for applications should be essentially thought of as considering unconstrained problems? The problem and the main theorem claims to focus an objective with a constrained form, but we have to assume that projections are be easy to compute in order to seamlessly translate iteration complexity into the actual computational costs, and for the applications we also need assumptions like $\\nabla f(x^{\\star}) = 0$ to do the theories, both of which makes me feel like it’s a slight overclaim to advocate DADA as an algorithm with clear theoretical guarantees for constrained problems. Can the authors provide what can we say about DADA on constrained cases, or are there experimental results on constrained problems that can show consistency of the analyses?\n    - The updates of dual averaging type algorithms have some structural similarities to FTRL updates of the form [1, 3]\n    $$ x_{t+1} = \\operatorname{argmin}\\_{x \\in \\mathcal{X}} \\left\\\\{ \\sum_{i=0}^{k-1} \\langle g_i, x_i \\rangle + \\frac{1}{2 \\eta_k} \\\\| x - \\textcolor{red}{x_0} \\\\|^2  \\right\\\\} $$\n    or Frank-Wolfe updates of the form [2, 3]\n    $$ \\begin{align*}\n    d_k &= \\sum_{i=0}^{k-1} g_i + \\frac{1}{2 \\eta_k} (x - \\textcolor{red}{x_0}) \\\\\\\\\n    v_k &= \\operatorname{argmin}\\_{v \\in \\mathcal{X}} \\\\langle d_k, v \\\\rangle \\\\\\\\\n    x_{k+1} &= (1 - \\sigma_k) x_k + \\sigma_k v_k\n    \\end{align*} $$\n    which are both good ways to solve *constrained* optimization problems (FW being *projection free*). In particular, [3] considers updates (with the ${\\textcolor{red}{x_0}}$'s) that look exactly as above but uses $\\eta_k \\equiv \\eta$ and $\\sigma_k \\equiv \\sigma$ for technical reasons (in order to use automated proof generation via PEP).\n    - I am not very familiar with the proposed (classical) dual-averaging algorithms in the paper; could there be a possibility that using distance adaptation and appropriately scaled regularizers (ex. try to match the $\\alpha_k$ and $\\beta_k$ of dual averaging and DADA) somehow yield regret/FW-gap upper bounds with better dependence on initialization scale, or this doesn't make any sense because of the $\\alpha_k$ and $\\beta_k$'s or for some other reason? (This is a light question, I only expect a simple high-level answer on the authors' take on this.)\n- Have the authors tried experiments on the stochastic setting as well? Up to my knowledge, methods like D-adaptation also work quite well under stochastic settings, despite the theoretical statements holding only for deterministic oracles, and I expect something similar for DADA as well.\n\n[1] Hazan, E. and Kale, S. 2012. Projection-free online learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning (ICML'12).\n\n[2] Orabona, F. (2019). A Modern Introduction to online learning. ArXiv, abs/1912.13213.\n\n[3] Weibel, J., Gaillard, P., Koolen, W. M., and Taylor, A. Optimized projection-free algorithms for online learning: construction and worst-case analysis. 2025. ⟨hal-05097004⟩", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It seems like a good idea to use an adaptive, increasing estimate of $D$’s, with a similar spirit (but different in detail) as in methods like D-adaptation, to reduce the cost incurred by estimated initialization scale to a logarithmic term. This allows the algorithm to gain similar benefits in (almost) all the broader classes of convex problems that classical dual averaging can deal with.\n- The theoretical statements, proof sketches, applications to examples, and comparison with previous work are all clear. There also are empirical results that align with the theory proposed in the paper.", "weaknesses": "- I am currently giving a rating of 2 because **the format of the submission (exceeding 9 pages) falls into desk rejection criteria.** (*I will update my score if the paper somehow avoids desk rejection.*)\n- See Questions for other details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ilHxdJyhCG", "reviewer": "Reviewer_xex2", "summary": "The paper studies gradient methods that can adapt to the distance between the initial solution and the optimal solution. Previous works have developed such algorithms for various settings, both deterministic and stochastic with different assumptions on the gradients. This work shows a single algorithm that works simultaneously for several classes of functions including Lipschitz functions, Lipschitz-smooth functions, Holder-smooth functions, functions with higher order Lipschitz derivative, quasi-self-concordant functions, and (L0, L1) smooth functions. The algorithm is based on the dual averaging method combined with a recent technique for adapting to the distance to the optimal solution, previously applied to gradient descent algorithms.", "questions": "Could you please comment on the barrier for obtaining a method with acceleration?\n\nThe previous work Orabona. https://arxiv.org/pdf/2308.05621 seems to suggest that one can combine normalized gradient descent with different algorithms in a similar fashion. The previous \"universal\" result by Khaled et al. used gradient descent whereas this paper uses DA. Is there a fundamental reason for this or do you see your technique being applicable to gradent descent as well?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The new method works simultaneously for many classes of functions, for both constrained and unconstrained problems. The proof is done via a unified approach and the bounds for each function class is a relatively simple corollary of the main proof.", "weaknesses": "The new method does not work for the stochastic case whereas some previous works include the stochastic case.\n\nThere is already a previous method that is universal for several classes of functions listed but that work did not consider others like Lipschitz higher order derivative.\n\nIn theory, one can use classical methods like the doubling trick to adapt to the distance and can combine even with tools like acceleration. Thus, the main benefit here is that one does not need to restart.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RLU7tWQeLh", "reviewer": "Reviewer_UHdw", "summary": "This paper introduces a novel universal gradient method for solving convex optimization problems, termed Dual Averaging with Distance Adaptation (DADA). The algorithm is based on the classical dual averaging scheme and dynamically adjusts its coefficients based on observed gradients and the distance between iterates and the starting point. This adaptation eliminates the need for problem-specific parameters, making the method broadly applicable. The authors provide theoretical convergence guarantees and demonstrate the practical effectiveness of DADA through experiments.", "questions": "Please see above.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proposed DADA algorithm offers a parameter-free approach to convex optimization, enhancing its applicability across various problems.\n\n*  The paper provides rigorous theoretical convergence guarantees for the proposed method.\n\n* Empirical results demonstrate the practical effectiveness of DADA in solving convex optimization problems.", "weaknesses": "* I am a bit concerned about the assumption that $x^* \\in \\mathrm{int}(dom(f))$ for constrained problems. For example, in a linearly constrained problem where the constraint set $\\mathcal{Q}$ is a polyhedron, the optimal solution will often lie on the boundary. It seems that the current work may not fully handle constrained settings, and the results may primarily hold for unconstrained problems (please correct me if I am wrong). I suggest clarifying this or considering an unconstrained version of problem (1).\n\n* I suggest using $g$ rather than $\\nabla f(x)$ to denote a subgradient. The notation $\\nabla f$ is typically reserved for the gradient of differentiable functions, and using it for subgradients may cause confusion.\n\n* As discussed in the conclusion, it would be interesting to explore whether the proposed methods can be extended to nonconvex and stochastic settings.\n\n* Are the proposed algorithms universal for convex functions satisfying the KL property? Some discussion or analysis would be helpful.\n\n* In Figure 4, could the authors explain why WDA and DADA exhibit sudden decreases after a large number of oracle calls, whereas other methods show smoother decreases? Additionally, in Figure 4, DADA’s performance is not as good as UGM or Prodigy; could the authors provide insight into this behavior?\n\n* Could the authors clarify what convergence rate the proposed algorithm achieves for strongly convex functions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)