A Simple Adaptive Accelerated Optimistic Dual Averaging Method for Unconstrained Convex Optimization (arXiv 2611.05334)

Forum topic · 小凯 · 2026-11-04

Summary

Researchers Bowen Li, Danqing Zhou, and Chuan He propose A2ODA, an adaptive accelerated optimistic dual averaging method for unconstrained convex optimization, in arXiv paper 2611.05334. The method uses low-cost preconditioning based on p-norm geometry with p in [2, infinity], and is line-search-free, employing a new stepsize selection technique built on an aggregated affine lower model. Its update structure is simple and unified across the p-norm family, with p > 2 requiring no more elaborate updates than the Euclidean case p = 2. Under a generalized local smoothness condition, the authors derive a convergence bound that separates constant-curvature effects from gap-dependent curvature effects, where the latter can yield faster-decaying terms. In the special case of local smoothness, the bound recovers a nearly optimal convergence rate. The work targets efficient preconditioning in large-scale first-order optimization.

Paper Overview

Field: Machine Learning Authors: Bowen Li, Danqing Zhou, Chuan He Published: 2026-11-03 arXiv: 2611.05334

Abstract

Efficient preconditioning plays an important role in large-scale first-order optimization. In this paper, we propose an adaptive accelerated optimistic dual averaging (

\text{A}^2

ODA) method for unconstrained convex optimization that adopts low-cost preconditioning based on

\(p\)

-norm geometry for

p\in[2,\infty]

. The method is line-search-free and employs a new stepsize selection technique based on an aggregated affine lower model. Its update structure is simple and unified across

p\in[2,\infty]

, with the case

\(p>2\)

requiring no more elaborate updates than the Euclidean case

\(p=2\)

. Under a generalized local smoothness condition, we derive a convergence bound that separates the effects of constant and gap-dependent curvature, with the latter potentially yielding faster-decaying terms. In the special case of local smoothness, this bound recovers a nearly optimal convergence rate.

Key Highlights

Proposes $\text{A}^2$ ODA: an adaptive, accelerated, optimistic dual averaging method for unconstrained convex optimization
Low-cost preconditioning via $$p$$ -norm geometry, $p \in [2,\infty]$
Line-search-free, with a new stepsize selection based on an aggregated affine lower model
Unified update structure: $$p > 2$$ needs no more elaborate updates than the Euclidean case ( $$p = 2$$ )
Convergence bound under generalized local smoothness separates constant vs. gap-dependent curvature effects
Recovers a nearly optimal convergence rate under local smoothness

--- *Auto-collected on 2026-11-05 from arXiv:2611.05334*