Abstract
Despite the vast empirical success of neural networks, theoretical understanding of the training procedures remains limited, especially in providing performance guarantees of testing performance due to the non-convex nature of the optimization problem. The current paper investigates an alternative approach of neural network training by reducing to another problem with convex structure — to solve a monotone variational inequality (MVI) — inspired by a recent work of (Juditsky & Nemirovsky, 2019). The solution to MVI can be found by computationally efficient procedures, and importantly, this leads to performance guarantee of $\ell_2$ and $\ell_{\infty}$ bounds on model recovery and prediction accuracy under the theoretical setting of training a single-layer linear neural network. In addition, we study the use of MVI for training multi-layer neural networks and propose a practical algorithm called stochastic variational inequality (SVI), and demonstrate its applicability in training fully-connected neural networks and graph neural networks (GNN). We demonstrate the competitive or better performance of SVI compared to widely-used stochastic gradient descent methods on both synthetic and real network data prediction tasks regarding various performance metrics, especially in the improved efficiency in the early stage of training.
Introduction
Standard neural network training typically relies on minimizing a loss function, such as Mean Squared Error or Cross-Entropy, using Stochastic Gradient Descent (SGD). However, the highly non-linear nature of deep neural networks results in a non-convex optimization landscape characterized by numerous local minima and plateaus. While empirical techniques have made SGD effective in practice, there remains a significant lack of theoretical guarantees for global convergence.
This research addresses these challenges by reformulating non-convex parameter estimation as a monotone Variational Inequality (VI). Building on the work of Juditsky and Nemirovski (2019) regarding Generalized Linear Models (GLMs), the authors propose the Stochastic Variational Inequality (SVI) algorithm to bring convex-like efficiency and theoretical rigor to deep learning training.
Methodology: Stochastic Variational Inequality (SVI)
The core innovation of this work is the transition from following loss gradients to following a "monotone operator" (a vector field). In standard backpropagation, weight updates are scaled by the derivative of the activation function (e.g., ReLU or Sigmoid). This often leads to the "dead neuron" problem where inactive neurons cease to update because their gradient is zero.
SVI introduces a backward unrolling scheme that effectively skips the derivative of the activation function during the weight update. While a standard SGD update is proportional to the product of the loss gradient, the activation derivative, and the input, the SVI update omits the activation derivative. This simplification allows for the construction of a monotone operator, transforming the training of single-layer networks or the final layer of deep networks into a convex problem with a unique solution and a provable convergence rate of $O(1/T)$.
Experimental Results
The authors evaluated SVI against SGD across synthetic data, Graph Neural Networks (GNNs), and classic computer vision benchmarks.
Performance and Convergence
- Aggressive Early Learning: By ignoring the activation state of neurons during updates, SVI facilitates more significant weight adjustments in the early stages of training. This results in much faster initial convergence compared to SGD.
- GNN Tasks: In solar radiation and traffic flow anomaly detection, SVI achieved lower classification errors and higher $F_1$ scores significantly faster than SGD. On the large-scale
ogbn-arxivdataset, SVI reached ~40% accuracy within 100 epochs, a benchmark SGD struggled to approach in the same timeframe. - Parameter Recovery: Synthetic tests demonstrated that SVI consistently outperforms SGD in recovering true underlying model parameters, particularly in non-convex scenarios.
Hybrid Training Strategies
Experiments on the MNIST dataset revealed that a hybrid approach—starting with SVI for the first 10% of training followed by SGD fine-tuning—yielded higher accuracy and lower loss than SGD alone. SVI effectively moves the model into a "good neighborhood" of the parameter space quickly, allowing SGD to perform precise local optimization.
Discussion and Conclusion
While the theoretical foundations for SVI are robust for single-layer and final-layer training, its application to multi-layer architectures currently relies on a heuristic approach. Although empirical results are promising, global monotonicity is not strictly guaranteed for the entire deep stack. Furthermore, the strongest theoretical guarantees require activation functions with strictly positive derivatives, though the authors provide analysis for cases like ReLU.
In conclusion, SVI offers a mathematically grounded alternative to SGD that excels in early-stage training efficiency and provides unique guarantees for fine-tuning tasks. Future work will explore its scalability to Large Language Models (LLMs) and broader applications in regression and edge classification.
Summary updated