Convergence Analysis of the Subgradient Method Beyond Weak Convexity

The subgradient method and its variants are widely used to solve non-smooth minimization problems in machine learning and frequently achieve strong performance in practice. Nevertheless, from a theoretical viewpoint, non-asymptotic convergence analyses of the subgradient method typically rely on weak convexity, a condition that is often violated in realistic machine learning applications. To bridge this gap, we introduce a class of functions that strictly contains the class of weakly convex functions and establish convergence guarantees for the subgradient method within this broader setting. Building on these theoretical results, we reveal two key insights: (i) a polynomially decaying step size is a robust choice for ensuring convergence; (ii) when the loss function exhibits additional structure, such as local smoothness or sharpness, a polynomially decaying step size can be suboptimal compared to constant or geometrically decaying step sizes. These theoretical findings align with empirical observations from prior work and are further validated by our numerical experiments. Overall, our results expand the theoretical applicability of first-order optimization algorithms to a wider class of non-smooth loss functions, bringing mathematical guarantees closer to practical machine learning scenarios.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-19
DOI
https://doi.org/10.21203/rs.3.rs-11478381/v1
Primary Topic
Stochastic Gradient Optimization Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Convergence Analysis of the Subgradient Method Beyond Weak Convexity

Shunki Arata
Research Square
Stochastic Gradient Optimization Techniques
preprint

Convergence Analysis of the Subgradient Method Beyond Weak Convexity

Shunki Arata
preprint en

Abstract

The subgradient method and its variants are widely used to solve non-smooth minimization problems in machine learning and frequently achieve strong performance in practice. Nevertheless, from a theoretical viewpoint, non-asymptotic convergence analyses of the subgradient method typically rely on weak convexity, a condition that is often violated in realistic machine learning applications. To bridge this gap, we introduce a class of functions that strictly contains the class of weakly convex functions and establish convergence guarantees for the subgradient method within this broader setting. Building on these theoretical results, we reveal two key insights: (i) a polynomially decaying step size is a robust choice for ensuring convergence; (ii) when the loss function exhibits additional structure, such as local smoothness or sharpness, a polynomially decaying step size can be suboptimal compared to constant or geometrically decaying step sizes. These theoretical findings align with empirical observations from prior work and are further validated by our numerical experiments. Overall, our results expand the theoretical applicability of first-order optimization algorithms to a wider class of non-smooth loss functions, bringing mathematical guarantees closer to practical machine learning scenarios.

Research Square
The University of Tokyo (JP)
Stochastic Gradient Optimization Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon