Optimization of Inf-Convolution Regularized Nonconvex Composite Problems

Emanuel Laude, Tao Wu, Daniel Cremers

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.

Training loss and test error for distributed training with 4 and 8 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.

Comparison of performance metrics for different penalty functions.

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

Abstract

In this work, we consider nonconvex composite problems that involve inf-convolution with a Legendre function, which gives rise to an anisotropic generalization of the proximal mapping and Moreau-envelope. In a convex setting such problems can be solved via alternating minimization of a splitting formulation, where the consensus constraint is penalized with a Legendre function. In contrast, for nonconvex models it is in general unclear that this approach yields stationary points to the infimal convolution problem. To this end we analytically investigate local regularity properties of the Moreau-envelope function under prox-regularity, which allows us to establish the equivalence between stationary points of the splitting model and the original inf-convolution model. We apply our theory to characterize stationary points of the penalty objective, which is minimized by the elastic averaging SGD (EASGD) method for distributed training. Numerically, we demonstrate the practical relevance of the proposed approach on the important task of distributed training of deep neural networks.
BibTeX
@inproceedings{laude2019optimization,
  author = {Emanuel Laude and Tao Wu and Daniel Cremers},
  title = {{Optimization of Inf-Convolution Regularized Nonconvex Composite Problems}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
}
Figure