On Decomposing the Proximal Map

Yaoliang YuNeurIPS 2013 · OpenReview

Introduction

The proximal map is a foundational operation in gradient-type algorithms, which have become the standard for solving large-scale, high-dimensional optimization problems. For simple functions, this proximal map is available in a fast, closed form. However, for more complicated functions—particularly those formed by combining multiple regularizers—computing the proximal map can become highly nontrivial.

This paper initiates a systematic investigation into "prox-decomposition": identifying exactly when the proximal map of a sum of functions decomposes into the sequential composition of the proximal maps of the individual summands (i.e., $P_{f+g} = P_f \circ P_g$). By uncovering the roles of scaling and cone invariance, this work unifies scattered results in the literature and effortlessly derives several new decompositions.

The Challenge of Complex Regularizers

In modern machine learning, regularizers are frequently used to bake prior knowledge into models, such as using the $\ell_1$ norm to induce sparsity. To capture multiple structural priors simultaneously—for instance, both sparsity and smoothness—practitioners often optimize the sum of different regularizers.

The workhorse for solving these composite problems is the proximal gradient method. While the proximal map for a single simple function is typically cheap to compute, the proximal map for a sum of functions is notoriously difficult. It often requires an expensive inner loop of iterative optimization. The fundamental question this paper addresses is: When can we bypass this expensive iterative approach and simply apply the proximal maps of the individual functions one after the other?

Theoretical Framework and Methods

The author approaches this problem through the lens of convex analysis and subdifferentials, yielding several key technical contributions:

  1. A General Sufficient Condition: The paper derives a core theorem establishing that if the subdifferential of $g$ at the point $P_f(x)$ contains the subdifferential of $g$ at $x$, then the exact decomposition $P_{f+g} = P_f \circ P_g$ holds.
  2. Invariance Analysis: The study explores how different types of "invariance" satisfy this sufficient condition:
  3. Scaling Invariance: If $g$ is a positive homogeneous function (such as a norm), the decomposition holds if and only if $f$ is a radial function (a function depending only on the magnitude of the input).
  4. Cone Invariance: The author generalizes the scaling concept to polyhedral gauge functions, where the subdifferential remains constant over specific cones.
  5. Constructive Proofs: Utilizing these conditions, the paper verifies existing empirical tricks and rigorously derives new closed-form solutions for structured sparsity.

(Note: As a purely theoretical contribution to mathematical optimization, this paper relies on mathematical proofs rather than empirical datasets.)

Key Insights

  • The Radial Connection: A surprising theoretical insight is the discovery that for scaling-invariant functions, the condition for prox-decomposition is mathematically identical to the condition required for the validity of the Representer Theorem in kernel methods. This reveals a deep, previously unnoticed link between optimization theory and learning theory.
  • One-Step Convergence: Most operator splitting methods (like Douglas-Rachford) are inherently iterative. This paper identifies the exact "Goldilocks" conditions under which these iterative procedures converge in exactly one step, yielding an exact closed-form solution for a complex sub-problem.
  • Unification of "Folklore": Several specific decomposition results previously existed in the literature as isolated cases (e.g., tree-structured groups). This paper provides a unifying theory that explains why those specific cases work, offering a systematic method for researchers to discover new ones.

Main Results

  • New Closed-Form Solutions: The paper identifies novel prox-decompositions for complex regularizers like the Ky-Fan k-norm and octagonal norms (often used for feature grouping). Previously, these were assumed to require complex algorithmic handling.
  • Tree-Structured Regularization: The author provides a simplified, elegant proof explaining why tree-structured $\ell_2$ norms decompose, demonstrating it as a natural consequence of the properties of Hilbertian norms.
  • Computational Efficiency: By mathematically proving these decompositions, the author enables "lazy updates" in gradient algorithms. Instead of computing a complex joint proximal map at every iteration, algorithms can apply simple, sequential operations without sacrificing mathematical exactness.

Limitations and Future Directions

  • Convexity Requirement: The current theoretical framework is built entirely on the foundation of closed, convex, proper functions. While this covers the vast majority of standard regularizers, it does not currently account for non-convex regularizers (such as SCAD or MCP) that are increasingly popular in deep learning.
  • Open Challenges: The author explicitly notes the ambition to generalize these results to non-convex functions in future work. Furthermore, while the paper provides a powerful sufficient condition, establishing a complete characterization (both necessary and sufficient conditions) for the most general "cone invariance" cases remains an open challenge in mathematical optimization.

Summary updated

Abstract

The proximal map is the key step in gradient-type algorithms, which have become prevalent in large-scale high-dimensional problems. For simple functions this proximal map is available in closed-form while for more complicated functions it can become highly nontrivial. Motivated by the need of combining regularizers to simultaneously induce different types of structures, this paper initiates a systematic investigation of when the proximal map of a sum of functions decomposes into the composition of the proximal maps of the individual summands. We not only unify a few known results scattered in the literature but also discover several new decompositions obtained almost effortlessly from our theory.
BibTeX
@inproceedings{yu2013decomposing,
  author = {Yaoliang Yu},
  title = {{On Decomposing the Proximal Map}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=B1-jVOZuZH},
}
Figure