🤖 machine learning

Generalized Convexity and Smoothness via Conjugate Duality: Optimization Theory for Deep Neural Networks

This paper establishes a unified optimization framework for deep neural networks by generalizing convexity and smoothness via Legendre functions and convex conjugation, introducing new optimizers with proven convergence rates and theoretical bounds that align with empirical training dynamics across diverse architectures and configurations.

Original authors: Binchuan Qi

Published 2026-08-11

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Binchuan Qi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Optimization Mystery

Imagine you are trying to find the lowest point in a vast, foggy mountain range. This is what computers do when they "learn" from data; they are essentially trying to find the perfect set of settings (parameters) that makes their predictions as accurate as possible. In the world of mathematics, this is called optimization. For decades, the rules of the game were strict: to guarantee you'd find the bottom, the landscape had to be a simple, smooth bowl (convex) with no jagged cliffs (smooth). If the terrain was bumpy, twisted, or full of sharp edges, the old math said, "Good luck, you might get stuck on a random hill."

Yet, in the real world of Artificial Intelligence, something strange happens. Engineers build massive, incredibly complex neural networks that look like tangled spaghetti mountains—full of sharp corners, deep valleys, and weird bumps. These networks are definitely not smooth bowls. They are messy, non-convex, and often non-smooth. According to the old rules, these systems should fail or get stuck forever. But they don't. They work amazingly well, finding the bottom of the mountain with surprising speed using a method called Stochastic Gradient Descent (SGD). This paper sets out to solve the mystery: Why does this messy, rule-breaking method work so perfectly on such a messy, rule-breaking problem?

The New Map: A Unified Language for Chaos

The author of this paper, Binchuan Qi, propose a new way to look at these messy mountains. Instead of trying to force the jagged terrain into a smooth bowl, they invent a new kind of map that can describe both smooth hills and jagged cliffs using the same language. They call this Generalized Convexity and Smoothness.

To understand their trick, imagine the old math used a ruler made of rigid steel (a quadratic formula) to measure how steep a hill was. If the hill didn't fit the ruler, the math broke. Qi suggests replacing that rigid steel ruler with a flexible, stretchy energy function. Think of it like a piece of elastic fabric that can stretch to fit any shape, whether it's a gentle slope or a sharp spike. By using a mathematical tool called "convex conjugation" (which is like looking at a mountain from the opposite side of a mirror), they show that the "steepness" (smoothness) and the "curvature" (convexity) are actually two sides of the same coin. They prove that even if a neural network's loss function looks like a chaotic mess, it still follows hidden, orderly rules that can be described by this new elastic framework.

The Magic of "Step Size One" (Under the Right Conditions)

One of the most surprising findings in the paper is about how these computers take their steps down the mountain. In the old days, engineers had to carefully tune a "learning rate"—a dial that decided how big each step should be. If the step was too big, they'd overshoot the bottom; too small, and they'd never get there. It was like trying to walk down a steep, icy slope without slipping.

However, the author proves that if you view the problem through their new "H(Ψ)-smooth" lens and use their specific "Generalized Gradient Descent" algorithm, the optimal step size is exactly 1. This is a crucial distinction: for classical gradient descent on standard problems, you still need to tune the learning rate carefully. But for this new Generalized Gradient Descent, which is specifically designed to match the flexible energy functions of the framework, the math guarantees that a step size of 1 is perfect. It's as if they discovered a universal law of physics where, if you use the right kind of elastic map and the right generalized algorithm, you just need to take one giant, confident stride at a time, and the math guarantees you'll move closer to the bottom. They call this "Generalized Gradient Descent." It turns out that the messy, non-smooth problems that confused the old math are actually perfectly solvable with this simple, fixed step size, provided you view them through their new lens and use their specific update rule.

The Two-Part Secret: Energy and Architecture

The paper goes deeper, explaining why deep neural networks (DNNs) are so good at learning. They break the training process down into two distinct jobs that happen simultaneously:

Reducing "Gradient Energy": The optimizer (the computer's brain) works to lower the "energy" of the slope. Think of this as the computer frantically trying to flatten the hill it's standing on. The paper shows that the standard method, SGD, is incredibly good at this. It naturally pushes the gradient energy down, smoothing out the immediate path.
Controlling the "Jacobian's Shape": This is where the network's design (its architecture) comes in. The author introduces a concept called the induced norm of the Jacobian matrix. In plain English, this measures how much the network's internal gears are "stuck" or "slipping" as they turn. If the gears are too loose or too tight, the network can't learn well.

The paper argues that the magic of deep learning happens because these two things work together. The optimizer (SGD) handles the energy, while the network's design handles the shape.

Why Skip Connections Are Superheroes

To prove their theory, the author looks at specific architectural tricks, like skip connections (used in ResNets). In a very deep network without skip connections, the "gears" tend to get stuck as the signal travels down the layers, causing the network to forget what it was learning (a problem known as vanishing gradients).

The paper shows that skip connections act like a bypass road. They ensure that the "gears" (the singular values of the Jacobian matrix) stay strong and don't decay as the network gets deeper. This keeps the "elastic map" taut and useful, allowing the optimizer to keep reducing the energy effectively, even in networks that are hundreds of layers deep. Without these bypasses, the map would go slack, and the optimizer would get lost.

The Verdict: A New Way to See the World

The author didn't just guess this; they proved it mathematically and then tested it on real-world data. They ran experiments on various datasets (like images of handwritten digits and text sentiment) and different network types (from simple grids to complex Transformers).

The results were striking. They found that the theoretical bounds they derived—based on the gradient energy and the network's shape—matched the actual training behavior almost perfectly. Whether they used different loss functions, different optimizers (like Adam or SGD), or different model sizes, the pattern held true. The paper suggests that the reason deep learning works isn't because the problems are secretly simple; it's because we finally have a mathematical framework that can describe the complexity without breaking.

In short, this paper tells us that deep neural networks aren't breaking the rules of optimization; they are just playing a different game than we thought. By using a flexible, unified view of "energy" and "shape," we can finally explain why these chaotic, non-smooth systems learn so well, and perhaps even design better ones in the future. The mystery of the messy mountain is solved: it's not a mess at all; it's just a landscape we finally learned how to read.

Technical Summary: Generalized Convexity and Smoothness via Conjugate Duality

1. Problem Statement

Deep Neural Network (DNN) training consistently achieves high empirical performance using Stochastic Gradient Descent (SGD) and its variants, despite the objectives being highly non-convex and non-smooth. Classical optimization theory, which relies on assumptions of convexity, differentiability, or Lipschitz smoothness, fails to fully explain this success. Existing attempts to bridge this gap generally fall into two categories:

Structural approaches: Utilizing frameworks like the Neural Tangent Kernel (NTK) or Fenchel–Young losses, which often rely on infinite-width assumptions or restrict the loss family, limiting their applicability to practical, finite-width networks and diverse loss functions.
Generalized assumptions: Extending strong convexity and Lipschitz smoothness (e.g., $(L_0, L_1)$ -smoothness, $\ell$ -smoothness). However, these often still require convexity or differentiability for global convergence guarantees or introduce analytical complexities that hinder practical utility.

The core problem is the lack of a unified optimization framework that can characterize DNN training without relying on restrictive assumptions (infinite width, convexity, differentiability) while providing rigorous convergence guarantees and explaining the interplay between model architecture and optimization dynamics.

2. Methodology

The paper proposes a unified framework based on Legendre functions and convex conjugation to generalize classical convexity and smoothness.

2.1 Generalized Definitions

The author introduces two new concepts defined via energy functions (Legendre functions with radial representation):

$H(\Psi)$ -smoothness: A function $G$ is $H(\Psi)$ -smooth if its first-order Taylor remainder is bounded above by an energy function $\Psi$ : $S_G(\mu, \nu) \leq \Psi(\mu - \nu)$ .
$H(\psi)$ -convexity: A function $G$ is $H(\psi)$ -convex if its first-order Taylor remainder is bounded below by an energy function $\psi$ : $S_G(\mu, \nu) \geq \psi(\mu - \nu)$ .

Here, $\Psi$ and $\psi$ are Legendre functions. Crucially, the constant terms $\Psi(0)$ and $\psi(0)$ allow these definitions to unify smooth/non-smooth and convex/non-convex functions. If $\Psi(0)=0$ , the function is smooth; if $\psi(0)=0$ , it is convex. Non-zero values allow the framework to handle non-smooth and non-convex objectives typical of DNNs.

2.2 Generalized Optimization Algorithms

Building on these definitions, the paper defines:

Generalized Gradient Descent (GD): An update rule $\theta_{k+1} = \theta_k - \alpha (\nabla G(\theta_k))^*_{\Psi^*}$ , where the update direction follows the conjugate dual of the gradient.
Generalized SGD: A stochastic variant using mini-batch gradients and the same conjugate update mechanism.

The framework introduces gradient energy ( $\Psi^*(\nabla G)$ ) as the primary metric for convergence, replacing the standard gradient norm.

2.3 Composite Optimization Framework

The paper reformulates DNN training as a composite optimization problem $G(\theta) = F(h(\theta))$ , where $F$ is the loss and $h$ is the model mapping. The convergence analysis relies on two jointly controlled quantities:

Gradient Energy: Reduced by the optimization algorithm (SGD).
Induced Norm of the Jacobian: Controlled by the model architecture (e.g., skip connections, initialization).

New metrics are introduced to characterize training dynamics:

Gradient Correlation Factor ( $M$ ): Quantifies the coupling between model parameters and the impact of mini-batch updates on unseen data.
Model Capacity Risk ( $R_G$ ): Quantifies the discrepancy between the global optimum of the full dataset and the expected optimum of mini-batches, dependent on model capacity.

3. Key Contributions

Theoretical Foundations

Unified Formalism: The paper establishes that $H(\psi)$ -convexity and $H(\Psi)$ -smoothness provide a single formalism unifying convex/non-convex and smooth/non-smooth objectives. It reveals a natural duality between generalized smoothness and convexity via Legendre conjugation.
Optimal Learning Rate: The author proves that for Generalized GD, the optimal learning rate is exactly 1, eliminating the need for learning rate tuning in the generalized setting. This contrasts with classical GD, where the optimal rate depends on the Lipschitz constant.
Convergence Guarantees: Rigorous convergence rates are derived for both Generalized GD and SGD in terms of gradient energy. The bounds depend on the "tightness" of the energy functions (specifically how close $\Psi(0)$ and $\psi(0)$ are to zero).

Optimization Mechanism for DNNs

Composite Risk Bounds: The paper proves that the empirical risk in DNN training is bounded by the gradient energy and the induced norm (singular values) of the model's Jacobian matrix.
Role of Architecture:
- Random Initialization: Under an approximate gradient independence assumption, increasing model width (parameters) balances the extreme singular values of the Jacobian, tightening risk bounds.
- Skip Connections: Theoretical analysis shows that skip connections prevent the exponential decay of the Jacobian's induced norm with depth, preserving the conditioning of the optimization landscape and maintaining trainability in deep networks.
Model Capacity: The convergence limit of gradient energy is shown to be determined by the Model Capacity Risk and the Gradient Correlation Factor, explaining why simpler models may fail to converge to zero error on complex datasets.

4. Experimental Results

Extensive experiments validate the theoretical bounds and mechanisms across diverse settings:

Learning Rate Verification: Experiments on non-Lipschitz smooth functions confirm that the optimal learning rate for Generalized GD is 1, with performance degrading as the rate deviates from 1.
Risk-Bound Correlation: Across various datasets (MNIST, CIFAR-10/100, TREC, SST-2), architectures (LeNet, ResNet, ViT, TextCNN, MLP), and optimizers (SGD, Adam, RMSprop), the empirical risk consistently tracks the theoretical upper and lower bounds derived from gradient energy and Jacobian singular values. The local Pearson correlation between risk and bounds approaches 1.
Architecture Effects:
- Width: Increasing width stabilizes the extreme singular values of the Jacobian.
- Depth & Skip Connections: Without skip connections, extreme singular values decay exponentially with depth. With skip connections, they grow linearly (or remain stable), confirming the theoretical prediction that skip connections preserve the induced norm.
Robustness: The findings hold regardless of loss function (MSE, CrossEntropy, KL, custom losses), data modality (image, text), and regularization techniques (BatchNorm, Dropout).

5. Significance and Claims

The paper claims to provide a unified optimization-theoretic framework that explains the success of SGD in DNN training without relying on the restrictive assumptions of classical theory (convexity, differentiability, infinite width).

Unification: It bridges the gap between convex and non-convex, smooth and non-smooth optimization, offering a single geometric characterization for deep learning objectives.
Mechanism Explanation: It identifies the specific mechanism of DNN optimization: SGD reduces gradient energy, while architectural choices (initialization, skip connections, over-parameterization) control the Jacobian's induced norm. The interplay of these two factors determines the convergence limit and speed.
Practical Insight: The framework suggests that the "trainability" of deep networks is not merely a result of stochastic noise escaping local minima, but a consequence of maintaining favorable spectral properties (induced norms) of the Jacobian matrix, which allows gradient energy reduction to translate directly into empirical risk reduction.
Generality: The theory applies to a wide range of loss functions and architectures, offering a more general explanation than NTK or specific smoothness extensions.

The author positions this work as a foundational step toward understanding deep learning optimization, moving beyond "black box" empirical success to a rigorous, duality-based theoretical understanding.