Incremental Weak Subgradient Methods for Non-Smooth Non-Convex Optimization Problems

Non-smooth, non-convex optimization problems frequently arise in modern machine learning applications, yet solving them efficiently remains a challenge. This paper addresses the minimization of functions of the form f(x)=∑i=1mfi(x) where each component is Lipschitz continuous but potentially non-smooth and non-convex. We extend the incremental subgradient method by incorporating weak subgradients, resulting in a framework better suited for non-convex objectives. We provide a comprehensive convergence analysis for three step size strategies: constant, diminishing, and a novel dynamic approach. Our theoretical results show that all variants converge to a neighborhood of the optimal solution, with the size of this neighborhood governed by the weak subgradient parameters. Numerical experiments on classification tasks with non-convex regularization, evaluated on the Breast Cancer Wisconsin dataset, demonstrate the effectiveness of the proposed approach. In particular, the dynamic step size method achieves superior practical performance, outperforming both classical and diminishing step size variants in terms of accuracy and convergence speed. These results position the incremental weak subgradient framework as a promising tool for scalable and efficient optimization in machine learning settings involving non-convex objectives.