Introduction
In modern machine learning, optimization often involves complex, nonconvex, and non-smooth loss functions. A standard technique to handle these difficulties is the use of "infimal convolutions" to smooth the objective. The most prominent example is the Moreau-envelope, which typically employs a quadratic penalty to regularize the problem. This approach is particularly prevalent in distributed training; for instance, algorithms like Elastic Averaging SGD (EASGD) use quadratic penalties to maintain consensus between multiple workers training on different data partitions.
However, the reliance on quadratic penalties is often a matter of mathematical convenience rather than optimal performance. This paper explores the use of non-quadratic (Legendre) penalties—such as logarithmic or tangent functions—to shape the optimization landscape more effectively. While splitting methods are commonly used to solve these problems, their theoretical guarantees often fail in nonconvex settings. This research bridges that gap by providing a rigorous mathematical foundation for using anisotropic penalties in nonconvex composite problems.
Theoretical Framework: Bridging the Nonconvex Gap
The primary challenge in applying splitting methods to nonconvex problems is ensuring that the stationary points found in the simplified, "split" version of the model correspond to valid stationary points of the original problem. The authors address this by leveraging the concept of prox-regularity.
By establishing the local regularity properties of the anisotropic Moreau-envelope using Legendre functions, the authors derive a generalized gradient formula for the nonconvex setting. This allows them to prove the "translation of stationarity," providing a mathematical guarantee that alternating minimization on nonconvex inf-convolution problems is theoretically sound. Furthermore, because the generalized Moreau-envelope is Lipschitz differentiable at the solution, its gradient norm serves as a robust measure of stationarity during stochastic optimization.
Stochastic Alternating Linearized Minimization
Building on this theory, the authors introduce a Stochastic Alternating Linearized Minimization scheme. This algorithm is specifically designed for distributed empirical risk minimization. While it specializes to the well-known EASGD when a quadratic penalty is used, its generalized formulation allows workers to synchronize using arbitrary Legendre potentials. This flexibility enables the use of anisotropic potentials to either force tighter consensus or allow for better exploration of the parameter space.
Empirical Evaluation
The proposed framework was tested using a LeNet-5 Convolutional Neural Network (CNN) trained on the MNIST dataset. The experiments compared standard quadratic penalties against cubic, tangent, and logarithmic potentials across configurations with 4 and 8 distributed workers.
As shown in the convergence plots, the algorithm demonstrates high stability. Because these EASGD-style variants process significantly more data per iteration than standard Nesterov momentum SGD (mSGD), they remain stable at much higher learning rates (e.g., $\tau = 0.005$ compared to $8 \cdot 10^{-4}$ for mSGD), leading to faster convergence to low objective values.
Key Results
The empirical results highlight the advantages of moving beyond the standard $L_2$ norm for consensus penalties. The non-quadratic potentials consistently matched or outperformed the quadratic baseline in both training loss and generalization error.
Key findings include:
- Superior Generalization: The cubic potential achieved the lowest overall test error of 0.56%, a notable improvement over the quadratic penalty's 0.65%.
- Optimized Training: Tangent and logarithmic potentials achieved lower training losses than the standard quadratic approach, suggesting a more efficient traversal of the loss landscape.
- Robustness: The performance gains were consistent across various hyperparameter scalings, demonstrating the practical utility of anisotropic regularizers.
Conclusion and Future Work
This paper provides both the theoretical justification and empirical evidence for using non-quadratic penalties in nonconvex optimization. By proving that splitting methods remain valid under prox-regularity, the authors open the door for more sophisticated consensus mechanisms in distributed learning.
While the results are promising, some limitations remain. For instance, the cubic penalty technically requires a small quadratic term to strictly satisfy the paper's mathematical assumptions regarding local strong convexity. Additionally, while the authors characterize the stationary points, a full stochastic convergence proof remains a subject for future research. Extending these tests to larger datasets like ImageNet and modern architectures like Transformers will be essential to understanding how these anisotropic penalties scale in practice.
Summary updated