Skip to content
Open access

Fast Initial Convergence Under (L₀,L₁) - Smoothness: Gradient and Coordinate Methods

2026 · IEEE Access · Vol 14, pp. 161146-161158 · 0 citations · 22 references

TL;DR

The first convergence guarantees under coordinate-wise coordination guarantees under coordinate-wise smoothness for random coordinate descent and its order-oracle counterpart are developed.

Abstract

We study gradient descent (GD) and its variants for convex objectives satisfying <inline-formula> <tex-math notation="LaTeX">$(L_{0},L_{1})$ </tex-math></inline-formula>-smoothness. Our analysis reveals a fast initial regime that is hidden by worst-case sublinear bounds: while <inline-formula> <tex-math notation="LaTeX">$\|\nabla f(x^{k})\|\geq L_{0}/L_{1}$ </tex-math></inline-formula>, the objective residual decreases geometrically, and after the trajectory crosses this threshold the method retains the standard <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1/N)$ </tex-math></inline-formula> guarantee. We establish this trajectory-level behavior for <inline-formula> <tex-math notation="LaTeX">$(L_{0},L_{1})$ </tex-math></inline-formula>-GD, whose step adapts to the gradient norm, and for clipped GD with an arbitrary clipping threshold; we also characterize the corresponding geometric regime of normalized GD. We then develop, to the best of our knowledge, the first convergence guarantees under coordinate-wise <inline-formula> <tex-math notation="LaTeX">$(L_{0},L_{1})$ </tex-math></inline-formula>-smoothness for random coordinate descent and its order-oracle counterpart, which uses only <inline-formula> <tex-math notation="LaTeX">$\mathrm {sign}(f(y)-f(x))$ </tex-math></inline-formula>; for the latter, we also quantify the comparison complexity of the one-dimensional search. Strong convexity yields three explicit contraction factors across the trajectory. Numerical examples verify the predicted transition and illustrate the advantage of adapting the step to generalized smoothness.

Read PDF

Similar papers

Open access 2026

RelSea: A Reliable L-Curve Search Region to Improve Regularization Parameter Selection

The selection of regularization parameters (<inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>) using the L-curve method is a well-established strategy for addressing ill-posed inverse problems. Several techniques have been developed to identify an appropriate <inline-formula> <tex-math...

Dorisney González-Caboverde, Gustavo Daniel Martín-del-Campo-Becerra, D. Torres-Román et al. · 0 citations
Open access Nov 2026

Minimax-Optimal Estimation of High-Order Missing Masses, and the Rare-Type Match Problem

Consider <inline-formula> <tex-math notation="LaTeX">$n\geq 1$ </tex-math></inline-formula> random samples <inline-formula> <tex-math notation="LaTeX">$\mathbf {X}_{n}=(X_{1},\ldots,X_{n})$ </tex-math></inline-formula> from an unknown distribution <inline-formula> <tex-math notation="LaTeX">$P=\sum _{j\geq 1}p_{j}\delt...

S. Favaro, Zacharie Naulet · 0 citations
Open access Dec 2024

Sparse PCA: Phase Transitions in the Critical Regime

This work studies sparse principal component analysis (PCA) in high dimensions. Given <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> independent <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula>-dimensional Gaussian samples with covariance <inline-formula> <tex-m...

Michal Feldman, Theodor Misiakiewicz, Elad Romanov · 0 citations
#machine learning Preprint Oct 2026

Last-Iterate Convergence Rate of Normalized Gradient Descent under H\"older Smoothness

Normalized gradient descent is a widely studied adaptive optimization method. Most existing analyses focus on the best iterate or a weighted average of the iterates, whereas practical implementations typically return the last iterate. In this paper, we study the last-iterate convergence of normalized gradient descent f...

Yuki Takezawa, Eduard A. Gorbunov · 0 citations
Open access

On Abstract Convexity with Respect to a Certain Quadratic Coupling Function: Subsets

<jats:p> We investigate abstract convexity generated by the coupling function <jats:inline-formula> <jats:alternatives> <jats:tex-math notation="LaTeX">\varphi(x,A)=|A[x]^2|,\quad x\in \mathbb{R}^n,\ A\in \mathcal{L}^2_{sym}(\mathbb{R...

J. Maksymiuk · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.