A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in $p$-norm geometry

Introduction

In this paper, we consider the unconstrained convex optimization problem

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a continuously differentiable convex function. We assume that problem (1) has at least one optimal solution. Since the seminal work on accelerated gradient methods [27], the development of fast first-order methods has remained a central focus in the study of smooth convex optimization. In practice, the performance of first-order methods is influenced by many factors, including the acceleration mechanism, the parameter selection, and the underlying geometry. The goal of this paper is to develop an accelerated first-order method in $p$-norm geometry that adapts its parameters to the optimization trajectory and achieves a unified convergence bound for all $p\in[2,\infty]$.

In recent years, there has been fruitful research on first-order methods for smooth convex optimization [1, 28, 29]. In particular, many recent efforts have focused on parameter selection in first-order methods, which is often guided by estimates of the Lipschitz constant of the objective gradient. Instead of fixing the parameters based on a global Lipschitz constant, adapting them to local curvature typically leads to much faster practical progress. In this direction, there has recently been growing interest in first-order methods that adapt their parameters based on local curvature without requiring costly line searches. The use of local curvature to select stepsizes has a long history, as exemplified by the well-known Barzilai-Borwein (BB) stepsize [2]. However, directly applying the BB stepsize without line searches does not generally yield convergence guarantees for smooth convex problems. Recently, several studies have proposed novel stepsize schemes for line-search-free gradient methods and established provable convergence guarantees for solving problem (1); see, e.g., [17, 24, 36]. In addition, notable adaptive accelerated gradient methods, including AC-FGM [18] and AdaNAG [33], achieve optimal convergence rates for smooth convex optimization without requiring line searches.

Beyond parameter selection, the choice of geometry is another important aspect of first-order method design. For many constrained problems, replacing the Euclidean squared distance with a suitable Bregman divergence in first-order method design allows the resulting updates to reflect the intrinsic geometry of the feasible region. Well-known examples include the Kullback-Leibler divergence on the probability simplex [4] and the Itakura-Saito divergence on the positive orthant [3]. These examples can be unified under the general mirror descent framework [4, 26], whose update takes the form:

where $\gamma_k > 0$, $X$ denotes the feasible region, and $D_h(x,y) := h(x)-h(y)-\langle\nabla h(y),x-y\rangle$ is the Bregman divergence generated by $h$. When $h(x)=\lVert x\rVert_2^2/2$, the update reduces to projected gradient descent. More generally, suitable choices of $h$ allow mirror descent to exploit non-Euclidean geometry. Under the relative smoothness condition

for some $L>0$, convergence bounds of mirror descent methods can be established in terms of $D_h$, where $\Omega$ is a suitable convex set containing the iterates and relevant comparison points [4, 20]. Mirror descent and relative smoothness extend gradient descent and Lipschitz smoothness in the Euclidean norm, respectively, to non-Euclidean settings. Nonetheless, extending accelerated gradient methods to non-Euclidean mirror descent is nontrivial. There have been many recent studies on acceleration in mirror descent, including both specific accelerated variants [12, 16, 25] and lower bounds on achievable convergence rates [11]. In addition, adaptive mirror descent methods have also been developed [30].

Another line of research explores first-order methods that directly exploit norm geometry to shape search directions. In particular, replacing the squared Euclidean distance with the squared distance induced by a general norm yields the dual preconditioned gradient update [15]:

where $\gamma_k>0$, $\lVert\cdot\rVert$ and $\lVert\cdot\rVert_*$ denote a general norm and its dual, respectively, and $J_*(g)\in\partial(\lVert\cdot\rVert_*^2/2)(g)$ for all $g\in\mathbb{R}^n$. For convex problems, this preconditioned method achieves an $\mathcal{O}(T^{-1})$ convergence rate in the objective gap under a Lipschitz gradient condition defined using the general norm and its dual, together with a level-boundedness assumption [15], where $T$ denotes the number of iterations. This bound is analogous to that of classical gradient descent. Moreover, this preconditioned gradient descent has also been analyzed under a dual relative smoothness condition [23]. This condition serves as a dual counterpart to the primal relative smoothness condition used to analyze mirror descent [20]. In addition, accelerated variants of preconditioned gradient descent in general norm geometries have been developed in [6, 8]. In particular, when the primal and dual norms are the $p$- and $q$-norms, respectively, with $1/p+1/q=1$ and $2\le p<\infty$, these methods achieve an $\mathcal{O}(T^{-(1+2/p)})$ convergence rate in the objective gap, matching the lower bounds up to logarithmic factors [7]. From a technical standpoint, these methods rely on the uniform convexity of the proximal regularizer to control linearization errors in their accelerated updates [6, 8]. For the case $p>2$, the resulting $p$th-power proximal terms interact with the quadratic terms arising from Lipschitz smoothness, making parameter selection and the convergence analysis more involved than in the case $p = 2$ (see Remark 1). It is also noteworthy that $p$-norm geometry has attracted significant recent interest in the design of deep learning optimizers, particularly in the endpoint case $p = \infty$, which leads to sign-based update directions; see, e.g., [5, 10, 13, 22, 31]. These theoretical advances and growing practical interest motivate the following natural question:

Can we design a line-search-free accelerated first-order method for smooth convex optimization that exploits $p$-norm geometry for preconditioning throughout the range $p \in[2,\infty]$?

This paper provides an affirmative answer to this question. Specifically, our proposed method employs an acceleration mechanism that combines optimistic dual averaging [32] in $p$-norm geometry with weighted iterate averaging [14]. To adapt the regularization parameters, we aggregate past linearizations into an affine model and use this model to derive a new parameter selection rule that directly controls a Lyapunov potential. This construction differs fundamentally from the parameter selection rules used by existing line-search-free accelerated gradient methods in the case $p = 2$ [18, 33].

Moreover, our analysis relies on the relaxed dual-potential expansion inequality in Lemma 1, which avoids the need for a uniform convexity inequality for the proximal regularizer. Consequently, our method directly uses the squared $p$-norm as the proximal regularizer for $p > 2$, in contrast to existing accelerated methods that rely on $p$-uniformly convex regularizers [6, 8] (see Remark 1). On the theoretical side, we establish an accelerated convergence rate for the proposed method under a generalized local smoothness condition (see Assumption 1(b)). This condition incorporates gap-dependent curvature into the local smoothness condition and allows us to distinguish the contributions of the constant and gap-dependent curvature terms to the convergence bound. Our main contributions are summarized below.

• We develop an adaptive accelerated optimistic dual averaging ($A^{2}$ODA) method under $p$-norm geometry for solving problem (1). To the best of our knowledge, this is the first line-search-free first-order method that combines adaptive acceleration with squared $p$-norm regularization in a unified framework covering all $p \in[2,\infty]$.

• Under the generalized local smoothness condition (Assumption 1(b)), we establish a unified convergence bound for Algorithm 1 across all $p \in[2,\infty]$ that explicitly separates the contributions of constant and gap-dependent curvature (see Theorem 2). In the special case of local smoothness, this bound recovers a nearly optimal convergence rate (see § 3.4).

The rest of the paper is organized as follows. In § 2, we introduce the notation and preliminary results. In § 3, we present the proposed algorithm and state its convergence guarantees. The proof of our main convergence result is presented in § 4. Additional lemmas and proofs are deferred to the appendix.

Notation and preliminaries

Throughout this paper, we use $\mathbb{R}^{n}$ and $\mathbb{R}_{+}$ to denote the $n$-dimensional Euclidean space and the set of nonnegative real numbers, respectively, and $\langle\cdot,\cdot\rangle$ to denote the standard inner product. We adopt the convention $0^{0}=1$ and $1/\infty=0$. For a positive integer $N$, we define $[N] := \{1,2,\ldots,N\}$. For any $p \in[1,\infty)$ and $z \in\mathbb{R}^{n}$, we define $\|z\|_{p} := \left(\sum_{i=1}^{n}|z_{i}|^{p}\right)^{1/p}$ and $\|z\|_{\infty} := \max_{1\leq i\leq n}|z_{i}|$. For any $A \in\mathbb{R}^{n\times n}$ and any $p,q \in[1,\infty]$, the induced $p$-to-$q$ operator norm is defined by $\|A\|_{p\to q} := \sup_{\|x\|_{p}\leq1}\|Ax\|_{q}$. For any convex function $h:\mathbb{R}^{n}\to\mathbb{R}$, its Fenchel conjugate is defined by $h^{*}(u) := \sup_{x\in\mathbb{R}^{n}}\{\langle x,u\rangle-h(x)\}$ for every $u \in\mathbb{R}^n$. Let $\partial h(x)$ denote the convex subdifferential of $h$ at $x$. The Fenchel-Young equality holds if and only if $u \in\partial h(x)$:

For $x,y \in\mathbb{R}^n$ and $g_y \in\partial h(y)$, define the generalized Bregman divergence by $D_h^{g_y}(x,y) := h(x) - h(y) - \langle g_y,x-y\rangle$. When $h$ is differentiable at $y$, we omit the superscript and denote the Bregman divergence by $D_h(x,y)$. In addition, we use $O(\cdot)$ and $\Theta(\cdot)$ to denote asymptotic upper and two-sided bounds, respectively.

For conjugate exponents $p \in[2,\infty]$ and $q \in[1,2]$ satisfying $1/p + 1/q = 1$, define the primal and dual regularizers by