Logo image
Back
Dual Averaging With Non-Strongly-Convex Prox-Functions: New Analysis and Algorithm
Preprint   Open access

Dual Averaging With Non-Strongly-Convex Prox-Functions: New Analysis and Algorithm

Renbo Zhao
ArXiV.org
Cornell University
04/04/2025
DOI: 10.48550/arxiv.2504.03613
url
https://doi.org/10.48550/arxiv.2504.03613View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We present new analysis and algorithm of the dual-averaging-type (DA-type) methods for solving the composite convex optimization problem minx∈Rnf(Ax)+h(x), where f is a convex and globally Lipschitz function, A is a linear operator, and h is a ``simple'' and convex function that is used as the prox-function in the DA-type methods. We open new avenues of analyzing and developing DA-type methods, by going beyond the canonical setting where the prox-function h is assumed to be strongly convex (on its domain). To that end, we identify two new sets of assumptions on h (and f) and show that they hold broadly for many important classes of non-strongly-convex functions. Under the first set of assumptions, we show that the original DA method still has a O(1/k) primal-dual convergence rate. Moreover, we analyze the affine invariance of this method and its convergence rate. Under the second set of assumptions, we develop a new DA-type method with dual monotonicity, and show that it has a O(1/k) primal-dual convergence rate. Finally, we consider the case where f is only convex and Lipschitz on C:=A(domh), and construct its globally convex and Lipschitz extension based on the Pasch-Hausdorff envelope. Furthermore, we characterize the sub-differential and Fenchel conjugate of this extension using the convex analytic objects associated with f and C.
Mathematics - Optimization and Control

Details

Metrics

5 Record Views
Logo image