Mathematical optimization theory is built on a beautiful, idealized foundation: convexity. In a convex world, optimization is highly predictable. If you calculate a local gradient and take a step downward, you are guaranteed to move closer to the single, global optimum. This geometric simplicity allows theorists to prove strict convergence rates, establish tight generalization bounds, and guarantee the stability of distributed systems.
However, modern deep learning does not live in a convex world. Deep neural networks operate in high-dimensional, highly non-convex loss landscapes filled with saddle points, rugged valleys, and discontinuities. This mismatch creates the convexity assumption gap: a profound disconnect between the elegant mathematical proofs used to justify optimization algorithms and the empirical reality of how those algorithms perform on neural networks.
As noted by Aaron Defazio et al. in their work on A Momentumized, Adaptive, Dual Averaged Gradient Method, a massive gulf separates the empirical success of deep learning optimizers from their formal theoretical guarantees. When the core assumption of convexity is violated, the mathematical scaffolding underlying our algorithms often collapses, leaving practitioners to rely on heuristics that lack rigorous foundations.
Where the Theory Breaks Down
The convexity assumption gap manifests across nearly every subfield of machine learning, distorting our understanding of distributed training, adversarial games, and model generalization.
Distributed and Federated Learning
In federated learning, multiple client devices train local models on their respective datasets and periodically synchronize their parameters with a central server. To prove that these systems will converge efficiently without consuming excessive network bandwidth, theorists frequently assume that the local objective functions are smooth and strongly convex, as highlighted by Rohit Parasnis et al. in Connectivity-Aware Semi-Decentralized Federated Learning over Time-Varying D2D Networks.
When these algorithms are deployed on non-convex neural networks, the theoretical guarantees fail to hold. A primary culprit is "client drift"—a phenomenon where heterogeneous local data pulls client models in wildly different directions. In a convex landscape, client drift can be bounded and corrected mathematically. However, as Anton Rodomanov et al. demonstrate in Federated Optimization with Doubly Regularized Drift Correction, drift correction techniques that show immense theoretical promise under convex assumptions often fail to yield significant performance gains when confronted with the high-dimensional, non-smooth landscapes of deep learning.
Minimax Optimization and Adversarial Games
Training Generative Adversarial Networks (GANs) or optimizing for adversarial robustness requires solving minimax (min-max) optimization problems, where a generator and a discriminator (or a model and an attacker) play a zero-sum game. Traditional proofs of stability and convergence to a Nash equilibrium rely heavily on the assumption that the loss surfaces are convex-concave.
Neural network loss surfaces violate this assumption entirely. Abhay Kumar Yadav et al. point out in Stabilizing Adversarial Nets with Prediction Methods that because deep learning objectives are inherently non-convex, empirical strategies designed to stabilize GAN training often lack a rigorous theoretical foundation. The chaotic dynamics observed in practice—such as mode collapse or endless oscillations—are direct consequences of navigating a non-convex-concave landscape using tools designed for a simpler mathematical world.
The Practical Consequences of the Gap
Why does this theoretical gap matter if neural networks clearly still train successfully in practice? The danger lies in unpredictability, a lack of safety guarantees, and a failure to verify critical model properties.
Catastrophic Failures in Constrained Optimization
When machine learning models are deployed in safety-critical systems, such as power grids or autonomous vehicles, they must satisfy strict operational constraints. Frameworks designed to enforce these boundaries, such as FSNet (Hoang T. Nguyen et al. in FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees), often rely on mathematical relaxations like the Polyak–Łojasiewicz (PL) condition or L-smoothness to prove convergence. If the underlying real-world functions violate these idealized conditions, a dangerous gap opens between the proven safety bounds and empirical execution, potentially leading to catastrophic constraint violations.
The Illusion of Data Deletion
The convexity assumption gap also compromises emerging capabilities like machine unlearning, where a model must entirely "forget" a specific subset of its training data to comply with privacy regulations. Theoretical frameworks that establish performance and privacy bounds for data removal typically rely on strongly convex loss functions to ensure that the model's parameters return to a verifiable state (Martin Van Waerebeke et al. in When to Forget? Complexity Trade-offs in Machine Unlearning). In a non-convex landscape, it is exceptionally difficult to mathematically guarantee that a data point's influence has been permanently purged, rather than merely obscured within a complex pocket of the parameter space.
Navigating the Non-Convex Landscape
To bridge the convexity assumption gap, researchers are forced to either relax their theoretical assumptions or design algorithms that inherently accommodate non-convexity.
One common approach is to substitute global convexity with weaker, localized conditions. However, even these approximations can fall short when optimization paths traverse highly non-quadratic regions. Another strategy involves adapting empirical heuristics to mimic convex stability. For example, Jed Mills et al. propose dynamically decaying the number of local SGD steps over time in Faster Federated Learning With Decaying Number of Local SGD Steps. By doing more local work early and less work later, the algorithm counteracts the chaotic divergence that occurs when optimizing non-convex client objectives, recovering some of the stability promised by convex theory.
Ultimately, acknowledging the convexity assumption gap forces the machine learning community to move past mathematically convenient assumptions. By identifying exactly where these assumptions fail, researchers can begin developing a new theoretical paradigm—one explicitly engineered for the rugged, high-dimensional terrain of modern deep learning.
Key Foundational Work
Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure (2017) — contributed 1 concept elements to this direction.
Asynchronous Distributed Semi-Stochastic Gradient Optimization (2016) — contributed 1 concept elements to this direction.
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017) — contributed 1 concept elements to this direction.