Optimization of Inf-Convolution Regularized Nonconvex Composite Problems

Emanuel Laude, Tao Wu, Daniel Cremers

Introduction

In modern optimization, particularly within deep learning, we frequently encounter "composite" problems aimed at minimizing the sum of multiple functions. A standard technique to handle nonsmooth components is inf-convolution, which "smooths" a target function by blending it with a simpler "potential" function (typically a quadratic). This process generates a Moreau envelope—a regularized version of the original function that is more amenable to optimization.

However, the theoretical foundations for these envelopes largely rely on the assumption of convexity. In practice, deep learning objectives are notoriously nonconvex. When employing "splitting" methods—where variables are decoupled to facilitate parallel or distributed computation—it is not always mathematically certain that a stationary point found in the split model corresponds to a valid solution of the original problem. This paper addresses this gap by establishing theoretical guarantees for splitting methods applied to nonconvex inf-convolution problems.

Theoretical Framework and Methods

The authors extend the standard Moreau envelope framework through several key innovations:

  • Anisotropic Generalization: Moving beyond standard squared-distance (isotropic) penalties, the researchers utilize Legendre functions. This allows for direction-dependent (anisotropic) smoothing, offering greater flexibility in regularization.
  • Prox-Regularity: By leveraging the concept of "prox-regularity," the authors analyze functions that, while globally nonconvex, behave locally like a convex function perturbed by a quadratic.
  • Stationarity Equivalence: A central contribution is the proof of a "gradient formula" for these generalized envelopes. Crucially, the authors demonstrate that under specific conditions, a stationary point of the split formulation is equivalent to a stationary point of the original inf-convolution model.
  • Stochastic Alternating Linearized Minimization: To apply this theory, the authors propose a stochastic algorithm designed for distributed training. This method uses generalized potentials to enforce consensus among multiple workers (e.g., CPUs or GPUs).

Key Insights: Beyond Quadratic Penalties

A significant takeaway is the challenge to the status quo in distributed learning. Standard methods like Elastic Averaging SGD (EASGD) typically rely on quadratic penalties to maintain consensus between local models and a central variable. This research demonstrates that non-quadratic potentials—such as Logarithmic, Tangent, or Cubic shapes—are not only theoretically sound but can be practically superior.

Furthermore, the gradient of the $\phi$-envelope is identified as a robust measure of stationarity. In the complex landscape of deep learning, this provides a mathematically rigorous metric for assessing convergence progress. The distributed approach also exhibits enhanced stability at higher learning rates compared to standard SGD, as it processes more data per iteration, facilitating faster convergence without numerical instability.

Experimental Results

The proposed methods were evaluated using the LeNet-5 architecture on the MNIST dataset. The experiments compared various penalty functions in distributed settings with 4 and 8 workers.

Comparison of training loss and test error across different iterations and worker counts.

As shown in the performance plots, the non-quadratic potentials often lead to faster convergence and better stability than standard momentum SGD (mSGD). Specifically, the Cubic potential emerged as the top performer in terms of generalization.

Final performance metrics for different potential functions (phi).

The quantitative results highlight that the Cubic potential achieved a test error of 0.56%, outperforming the standard quadratic baseline of 0.65%. While Tangent and Log potentials showed competitive training losses, the non-separable variants generally provided superior overall performance compared to their separable counterparts.

Limitations and Future Directions

Despite the performance gains, the use of complex potentials like Log or Tan introduces computational overhead, necessitating line searches to ensure iterates remain within the function's domain. Additionally, while the paper characterizes stationary points, a comprehensive convergence proof for the stochastic version of the algorithm remains an area for future research. Finally, scaling these anisotropic potentials to larger architectures (e.g., Transformers) and more complex datasets (e.g., ImageNet) is a logical next step to validate the broader applicability of this framework.

Summary updated

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