A proximal average for prox-bounded functions

Jiawei Chen, Xianfu Wang, Chayne PlanidenarXiv 2019 · DOI · arXiv

Abstract

In this work, we construct a proximal average for two prox-bounded functions, which recovers the classical proximal average for two convex functions. The new proximal average transforms continuously in epi-topology from one proximal hull to the other. When one of the functions is differentiable, the new proximal average is differentiable. We give characterizations for Lipschitz and single-valued proximal mappings and we show that the convex combination of convexified proximal mappings is always a proximal mapping. Subdifferentiability and behaviors of infimal values and minimizers are also studied.

Introduction

In the field of optimization and variational analysis, the ability to "average" two functions while preserving their structural properties—such as the location of their minimizers—is a critical capability. While a standard arithmetic average, $(f+g)/2$, is straightforward to compute, it often fails to maintain the geometric and variational characteristics of the original functions. To address this, the concept of the proximal average was introduced for convex functions. This operator averages functions in a way that corresponds to the weighted average of their proximal mappings, which are the fundamental steps in proximal gradient algorithms.

However, modern optimization challenges frequently involve nonconvex functions. Until now, a robust framework for applying proximal averages to nonconvex functions was missing. This paper bridges that gap by extending the proximal average to the class of prox-bounded functions, providing a construction that maintains differentiability and predictable minimization behavior even in the absence of convexity.

The Challenge of Nonconvexity

The primary difficulty in extending proximal averages to nonconvex functions lies in the "wild" behavior of their proximal mappings. Nonconvex functions can possess multiple local minimizers and discontinuous proximal mappings, making a simple blend difficult to define without losing the "nice" properties that make the proximal average useful in the convex case.

The authors overcome this by utilizing the Moreau envelope and proximal hulls. A function $f$ is considered prox-bounded if it is bounded below by a quadratic function, ensuring that its Moreau envelope—a smoothed approximation—is well-defined.

Methodology: Construction via Moreau Envelopes

The core contribution of this work is a new construction of the proximal average $\phi_\mu^\alpha$ for two functions $f$ and $g$. The construction relies on the Moreau envelope $e_\mu$, defined as:

$$e_\mu f(x) = \inf_y \left\{ f(y) + \frac{1}{2\mu} \|y - x\|^2 \right\}$$

The proposed proximal average is defined as:

$$\phi_\mu^\alpha = -e_\mu(-\alpha e_\mu f - (1-\alpha)e_\mu g)$$

In this framework, the functions are first smoothed via the Moreau envelope, then a weighted arithmetic average of these smoothed versions is taken, and finally, the result is "unsmoothed" to return to the original functional space. This approach is significant because it only requires the functions to be prox-bounded, a much broader class than convex functions.

Key Insights and Theoretical Results

The paper establishes several critical properties of this new proximal average:

  • Differentiability and Smoothing: A striking result is that if at least one of the input functions is differentiable, the resulting proximal average is also differentiable. This positions the proximal average as a powerful smoothing operator for nonconvex optimization.
  • Backward Compatibility: The construction is "backward compatible" with classical theory. If $f$ and $g$ are convex, the formula perfectly recovers the standard proximal average.
  • Epi-continuity: The authors prove that the average is epi-continuous. This ensures that as the weighting parameter $\alpha$ varies from 0 to 1, the function (and its set of minimizers) transforms continuously from one proximal hull to the other.
  • Proximal Mapping Link: The research demonstrates that the proximal mapping of the average is exactly the weighted average of the convexified proximal mappings of the original functions.

Analysis of Minimizers and Special Cases

The paper provides a detailed analysis of how minimizers behave under this transformation. Under specific conditions, the set of minimizers of the proximal average stays within the "average" of the minimizers of the input functions.

Furthermore, the authors provide explicit closed-form solutions for the proximal average of quadratic functions. This is highly relevant for researchers utilizing Hessian approximations or second-order methods, where quadratic models are prevalent. The study also offers new characterizations for when proximal mappings are Lipschitz continuous or single-valued in a nonconvex setting.

Limitations and Open Questions

While the theoretical framework is robust, the authors identify certain limitations. The "nice" behavior of the proximal average often depends on the proximal mapping being convex-valued. In cases of extreme nonconvexity, the relationship between the average of proximal mappings and the proximal mapping of the average may break down.

Additionally, from a practical standpoint, calculating Moreau envelopes for high-dimensional, complex functions remains computationally demanding. Finally, the paper leaves open a significant theoretical question: whether a convex combination of proximal mappings of any nonconvex function is always a proximal mapping. This remains a challenging open problem in the field of variational analysis.

Conclusion

By extending the proximal average to prox-bounded functions, this work provides a new set of tools for blending and smoothing nonconvex functions. The preservation of differentiability and the continuous transformation of minimizers make this construction a valuable addition to the theory of optimization and its applications in machine learning and data science.

Summary updated

Abstract

In this work, we construct a proximal average for two prox-bounded functions, which recovers the classical proximal average for two convex functions. The new proximal average transforms continuously in epi-topology from one proximal hull to the other. When one of the functions is differentiable, the new proximal average is differentiable. We give characterizations for Lipschitz and single-valued proximal mappings and we show that the convex combination of convexified proximal mappings is always a proximal mapping. Subdifferentiability and behaviors of infimal values and minimizers are also studied.
BibTeX
@misc{chen2019proximal,
  author = {Jiawei Chen and Xianfu Wang and Chayne Planiden},
  title = {{A proximal average for prox-bounded functions}},
  year = {2019},
  eprint = {1909.06221},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.06221},
}
Figure