A Novel Unified Parametric Assumption for Nonconvex Optimization
Artem Riabinin, Ahmed Khaled, Peter Richtárik · 2025
Read A Novel Unified Parametric Assumption for Nonconvex Optimization by Artem Riabinin, Ahmed Khaled, Peter Richtárik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12329.txt.
Introduction
Training neural networks is a nonconvex problem, where standard theory promises far less than practice delivers. Artem Riabinin, Ahmed Khaled, and Peter Richtárik propose one flexible assumption to close that gap. The assumption has knobs that can be tuned. At some settings it matches known well-behaved function families. At others it covers wider classes that still allow fast training. From it they prove one convergence result for gradient methods.
The proof covers both exact and noisy gradient settings. Tests check that the assumption can hold along real training paths. A single frame that explains many cases could guide how new optimizers are built. It also helps predict when training will be easy or slow.
Catalog record
| CREATOR | Artem Riabinin, Ahmed Khaled, Peter Richtárik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12329
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Novel Unified Parametric Assumption for Nonconvex Optimization Artem Riabinin, Ahmed Khaled, Peter Richtárik Abstract Nonconvex optimization is central to modern machine learning, but the general framework of nonconvex optimization yields weak convergence guarantees that are too pessimistic compared to practice. On the other hand, while convexity enables efficient optimization, it is of limited applicability to many practical problems. To bridge this gap and better understand the practical success of optimization algorithms in nonconvex settings, we introduce a novel unified parametric assumption. Our assumption is general enough to encompass a broad class of nonconvex functions while also being specific enough to enable the derivation of a unified convergence theorem for gradient-based methods. Notably, by tuning the parameters of our assumption, we demonstrate its versatility in recovering several existing function classes as special cases and in identifying functions amenable to efficient optimization. We derive our convergence theorem for both deterministic and stochastic optimization, and conduct experiments to verify that our assumption can hold practically over optimization trajectories. 1 Introduction There is a large disconnect between the theory and practice of nonconvex optimization with first-order methods. The theory for nonconvex optimization allows us only to guarantee convergence to a stationary point, or at most, a higher-order stationary point ( Carmon et al., 2017a ; Carmon et al., 2017b ) . In practice, neural scaling laws show smooth decreases in the loss function value as the number of training steps increases ( Kaplan et al., 2020 ) . In contrast, convex optimization theory typically allows us to derive tight guarantees on the function value ( Nesterov, 2018 ) , but is too restrictive to apply to nonconvex models directly. This discrepancy has motivated researchers to develop intermediate theoretical frameworks that allow us to obtain stronger convergence guarantees without losing too much applicability. These developments include star convexity ( Nesterov & Polyak, 2006 ) , quasi-convexity ( Hardt et al., 2016 ; Bu & Mesbahi, 2020 ) , the Polyak-Łojasiewicz (PL) condition ( Polyak, 1963 ; Liu et al., 2022 ) , Aiming ( Liu et al., 2023 ) , and the {\alpha} - {\beta} conditions ( Islamov et al., 2024 ) . Problem statement. We are primarily concerned with the minimization problem \min_{x\in\mathbb{R}^{d}}f(x), where f(x):\mathbb{R}^{d}\to\mathbb{R} is a differentiable objective function. We focus on variants of gradient descent of the form x^{k+1}=x^{k}-\gamma^{k}\nabla f\left(x^{k}\right), where \gamma^{k}>0 is a stepsize, and \nabla f(x^{k}) represents the gradient of the function f at the current point x^{k} . Our analysis also extends to stochastic gradient descent. A novel unified assumption. We build on this line of work by introducing a new assumption that allows us to obtain convergence guarantees for nonconvex optimization. Our unified framework is broadly applicable– it subsumes prior assumptions on nonconvex optimization and allows for unified analysis of convex and nonconvex objectives. The main idea of our framework is that even in complex nonconvex landscapes, effective optimization algorithms rely on the gradient possessing a degree of directional alignment towards the set of solutions. To formalize this, we first make the assumption that a set of solutions exists. Assumption 1.1 . The function f is continuously differentiable and has a nonempty set S\subseteq\mathbb{R}^{d} of global minimizers. Let f^{\star} denote the minimum value of the function f . We now introduce our main assumption, an inequality that relates the gradient at any point x to its projection onto a subset \tilde{S} of optimal solutions, using a progress function P(x;\tilde{S}) to quantify proximity to this set. Assumption 1.2 . There exists constants c_{1}>0 and c_{2}\geq 0 such that for all x\in\mathbb{R}^{d} , \left\langle\nabla f\left(x\right),x-\operatorname{proj}_{\tilde{S}}(x)\right\rangle\geq c_{1}P(x;{\tilde{S}})-c_{2}, where \tilde{S}\subseteq S , S\subseteq\mathbb{R}^{d} is a set of global minimizers of f , \tilde{S}\neq\emptyset , \operatorname{proj}_{\tilde{S}}(x)\in\arg\min_{y\in\tilde{S}}\|x-y\|^{2} , and P(x;\tilde{S}) is a nonnegative function of the argument x\in\mathbb{R}^{d} . Assumption 1.2 has a clear and intuitive interpretation: the progress function controls how “informative” the gradient is in pointing us towards the set of minimizers, while the constants c_{1} and c_{2} control how stringent this information is. Our contributions. We develop a new framework for analyzing gradient descent under Assumption 1.2 . We demonstrate that our framework recovers classical convergence guarantees for convex optimization as a special case, and also subsumes several existing assumptions in nonconvex optimization (such as quasiconvexity and the aiming condition). We provide convergence analysis under this new assumption for gradient descent ( Theorem 2.1 ) and stochastic gradient descent ( Theorem 2.6 ) and demonstrate the flexibility of these theorems in deriving new convergence guarantees. Finally, we provide experimental validation for how applicable our assumption is in half-space learning with the sigmoid, training MLPs on Fashion-MNIST, and training convolutional neural networks on CIFAR-10. 1.1 Brief literature review The challenge of bridging the gap between theory and practice in nonconvex optimization has spurred significant research into developing more refined analytical frameworks. Classical convex optimization theory provides strong convergence guarantees, but its assumptions are often too restrictive for modern machine learning. Conversely, standard nonconvex optimization results guarantee convergence to stationary points and do not reflect the empirical success of first-order methods in deep learning. Convexity can be seen as controlling the lower curvature of a function while smoothness controls the upper curvature. The literature has explored generalizations and alternatives to both. Alternatives to convexity. The Polyak-Łojasiewicz (PL) condition ( Polyak, 1963 ; Liu et al., 2022 ) is a prominent example that relates the function value to the gradient norm, provides a lower bound on the function growth, and ensures linear convergence under certain conditions. Quasi-convexity ( Hardt et al., 2016 ) and star-convexity ( Nesterov & Polyak, 2006 ) represent other relaxations of convexity that have been studied in optimization. More recently, conditions like the Aiming property ( Liu et al., 2023 ) and the {\alpha} - {\beta} conditions ( Islamov et al., 2024 ) have emerged as tools to characterize the loss landscapes of neural networks and analyze the convergence of optimization algorithms in these settings. Alternatives to smoothness. Recent work has explored alternatives to smoothness that may more accurately describe neural network optimization, e.g. generalized smoothness ( Zhang et al., 2020a ; Xie et al., 2024 ) , directional sharpness or smoothness ( Pan & Li, 2022 ; Mishkin et al., 2024 ) , and local smoothness ( Berahas et al., 2023 ) . Assumptions on the stochastic gradients. Another line of work has considered the various properties of the stochastic gradient noise, and its effect on the convergence of gradient-based methods, see e.g. ( Khaled & Richtárik, 2020 ; Faw et al., 2022 ; Zhang et al., 2020b ) . Our work is primarily aimed at relaxing convexity and is therefore orthogonal to these results. 2 Main Theory & Results In this section, we first discuss further Assumption 1.2 and its implications, then present our convergence theory for gradient descent under this assumption, followed by stochastic gradient descent. 2.1 Discussion of Assumption 1.2 To analyze Assumption 1.2 , we start by considering the simpler setting c_{2}=0 . In this case, Assumption 1.2 takes the form \left\langle\nabla f(x),x-\operatorname{proj}_{\tilde{S}}(x)\right\rangle\geq c_{1}P(x;\tilde{S})\geq 0\ \ \text{for all}\ x\in\mathbb{R}^{d}. This means that the negative gradient -\nabla f(x) points toward \tilde{S} in the sense that -\nabla f(x) is nontrivially correlated with the direction \operatorname{proj}_{\tilde{S}}(x)-x .