Better Approximation and Faster Algorithm Using the Proximal Average

Yaoliang YuNeurIPS 2013 · OpenReview

Overview

This paper introduces a novel approach to solving complex optimization problems in machine learning by approximating "hard" nonsmooth functions with a "proximal average" rather than relying on traditional smoothing techniques. By treating the proximal map as if it were a linear operator, the author develops the Proximal Average Accelerated Proximal Gradient (PA-APG) algorithm. This method achieves strictly better convergence rates than state-of-the-art smoothing methods without adding any computational overhead.

The Challenge of Composite Minimization

In large-scale machine learning, researchers frequently encounter "composite minimization" problems. These typically involve a smooth loss function (such as least squares) combined with a regularizer that is a sum of several nonsmooth functions (like the $L_1$ norm in Lasso).

While efficient tools like the Accelerated Proximal Gradient (APG) algorithm exist, they rely on computing a "proximal map"—a specific optimization sub-step. For simple functions, this map is straightforward to calculate. However, when the regularizer is a sum of nonsmooth functions (e.g., in overlapping group lasso or graph-guided fused lasso), the proximal map of the sum is usually not the sum of the individual proximal maps. This non-linearity makes the problem computationally expensive, often requiring nested iterative loops that severely slow down convergence.

The standard workaround, popularized by Yurii Nesterov, is to "smooth" the nonsmooth parts. While effective, this smoothing introduces its own set of theoretical and practical performance bottlenecks, such as increasing the Lipschitz constant and forcing algorithms to take smaller steps.

The Proximal Average Approach

The author proposes a "naive" but mathematically brilliant shortcut: what if we simply act as if the proximal map of a sum is the sum of the proximal maps?

  1. The Proximal Average: Using a tool from convex analysis called the "proximal average," the paper proves that this naive summation actually corresponds exactly to the proximal map of a specific nonsmooth approximation of the original function.
  2. PA-APG Algorithm: The paper integrates this approximation into the standard Accelerated Proximal Gradient framework. Instead of smoothing the objective, the algorithm operates directly on this proximal average approximation.
  3. Step-size Adjustment: Because there is a mismatch between the Lipschitz constant of the smooth loss and the approximation parameter ($\mu$), the algorithm slightly "tunes down" the step size to ensure stability and convergence.
Comparison of the proximal average approximation and the smoothed Moreau envelope.

The key insight here is that smoothing isn't always the optimal answer. A nonsmooth approximation (the proximal average) can provide a strictly tighter fit to the original function than a smooth one (like the Moreau envelope). By avoiding explicit smoothing, PA-APG bypasses the performance penalties associated with artificially inflated Lipschitz constants.

Experimental Setup

The paper evaluates the algorithm on two structurally complex regularization problems using synthetic data designed to mimic real-world high-dimensional challenges:

  • Overlapping Group Lasso: A problem where variables are grouped, and groups share members. The data was generated with $n=5000$ samples and $d \approx 4500$ variables, featuring 50 overlapping groups.
  • Graph-guided Fused Lasso: A problem where the regularizer encourages sparsity in both the variables and the differences between variables connected by a graph. The setup involved $n=5000$ and $d=1000$, with the graph structure derived from a correlation matrix.

Key Results

The PA-APG algorithm demonstrates both theoretical and practical advantages over existing methods:

  • Theoretical Superiority: The paper proves that PA-APG removes a secondary error term ($M^2/2\epsilon$) typically found in the complexity bounds of smoothing methods, making the algorithm theoretically strictly better.
  • Faster Convergence: In experiments on both Overlapping Group Lasso and Graph-guided Fused Lasso, PA-APG converged significantly faster than the standard Smoothed APG (S-APG) across various accuracy requirements.
  • Zero Overhead: Because computing the sum of proximal maps is already a requirement for smoothing methods, PA-APG achieves this speedup with exactly the same per-iteration computational cost.
Convergence comparison showing PA-APG achieving faster convergence than standard smoothed APG.

Limitations and Future Work

While highly effective, the algorithm does have limitations. It requires a specific choice of the parameter $\mu$ and a corresponding step-size adjustment. If the smooth part of the function has a very large Lipschitz constant, the required step size might become quite small, potentially impacting performance.

Furthermore, the author notes that while this approximation outperforms smoothing, it is not yet definitively clear if the proximal average is the absolute optimal approximation for these types of problems. Future work will likely focus on broadening the application of this framework to other complicated regularizers in fields like computer vision or signal processing, where sums of nonsmooth functions are ubiquitous.

Summary updated

Abstract

It is a common practice to approximate complicated'' functions with more friendly ones. In large-scale machine learning applications, nonsmooth losses/regularizers that entail great computational challenges are usually approximated by smooth functions. We re-examine this powerful methodology and point out a nonsmooth approximation which simply pretends the linearity of the proximal map. The new approximation is justified using a recent convex analysis tool---proximal average, and yields a novel proximal gradient algorithm that is strictly better than the one based on smoothing, without incurring any extra overhead. Numerical experiments conducted on two important applications, overlapping group lasso and graph-guided fused lasso, corroborate the theoretical claims."
BibTeX
@inproceedings{yu2013better,
  author = {Yaoliang Yu},
  title = {{Better Approximation and Faster Algorithm Using the Proximal Average}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=SkZv6dZuWH},
}
Figure