PaperlayerView exact revision on arXiv

Source-linked AI summary

Proximal Algorithms in Statistics and Machine Learning

Nicholas G. Polson, James G. Scott, Brandon T. Willard

arXiv:1502.03175v3stat.MLcs.LGstat.ME

TL;DR

Statistical learning problems often combine fit terms with non-smooth or non-convex regularization, motivating optimization methods for composite objectives. The paper develops proximal algorithms using closed-form proximal operators and multiple envelope representations, then applies them to regression and fused-lasso problems. It reports extremely fast convergence with second-order information and discusses convergence for accelerated and non-convex algorithms.

  • Problem

    Statistical optimization frequently requires minimizing composite objectives that combine a fit measure with a regularization penalty, including non-smooth and sometimes non-convex terms.

  • Method

    The paper develops proximal algorithms based on closed-form proximal operators, splitting, and Moreau, forward-backward, Douglas-Rachford, and half-quadratic envelope representations.

  • Results

    The methodology is applied to logistic and Poisson regression, fused-lasso penalties, and bridge penalties; second-order information produces extremely fast convergence in a fused-lasso simulation.

  • Takeaways & Limitations

    The envelope perspective provides a framework for constructing and extending proximal algorithms for statistical optimization, including selected non-convex objectives.

  • Takeaways & Limitations

    A variational representation of the Lq-norm does not satisfy the cited convergence conditions within the half-quadratic framework.

Abstract

from arXiv · show

In this paper we develop proximal methods for statistical learning. Proximal point algorithms are useful in statistics and machine learning for obtaining optimization solutions for composite functions. Our approach exploits closed-form solutions of proximal operators and envelope representations based on the Moreau, Forward-Backward, Douglas-Rachford and Half-Quadratic envelopes. Envelope representations lead to novel proximal algorithms for statistical optimisation of composite objective functions which include both non-smooth and non-convex objectives. We illustrate our methodology with regularized Logistic and Poisson regression and non-convex bridge penalties with a fused lasso norm. We provide a discussion of convergence of non-descent algorithms with acceleration and for non-convex functions. Finally, we provide directions for future research.

1 Introduction

The paper introduces proximal algorithms for statistical optimization problems built from fit measures and regularization penalties, emphasizing splitting, envelopes, and applications to convex and non-convex objectives.

  • Motivation: The paper frames statistical optimization around minimizing a measure of fit together with a regularization penalty.This formulation covers sparse regression, spatial smoothing, covariance estimation, image processing, and nonlinear curve fitting.
  • Proximal framework: Proximal algorithms solve optimization problems by evaluating proximal operators of terms in the objective.The paper surveys related approaches including proximal gradient, proximal point, ADMM, Douglas-Rachford splitting, and half-quadratic optimization.
  • Convergence: Acceleration can produce non-descent algorithms and an order-of-magnitude efficiency increase under suitable convexity and smoothness conditions.The paper illustrates acceleration for sparse logistic regression with a fused-lasso penalty.
  • Applications: The framework addresses composite objectives with smooth fit terms and non-smooth regularizers, while allowing non-convexity when explicitly stated.Applications include logistic and Poisson regression, fused lasso penalties, and bridge penalties.
  • Proximal framework: Splitting introduces a latent or slack variable to reformulate an unconstrained problem as an equivalent constrained optimization problem.This supports composite penalties such as φ(Bx), including fused-lasso constructions based on discrete differences.
  • Envelope methods: Envelope representations introduce latent variables through linear or quadratic forms, including convex-dual representations of the fit term.The paper develops Moreau, forward-backward, Douglas-Rachford, half-quadratic, and related envelope perspectives.

2 Proximal operators and Moreau envelopes

Proximal operators and Moreau envelopes provide the paper’s core interpretation of optimization steps, connecting regularization, projection, gradient descent, and fixed-point methods.

  • Moreau envelope: The Moreau envelope regularizes a function from below, while the proximal operator returns the minimizer balancing function value against distance from the input.The parameter γ controls this trade-off.
  • Envelope perspective: The paper views proximal fixed-point algorithms as gradients of suitably defined envelope functions.Constructing different envelopes yields new optimization algorithms and connects envelope methods to Lagrangian approaches.
  • Proximal interpretations: A proximal operator acts like a gradient-descent step for a regularized version of the original function.The parameter γ functions as a step-size parameter in this interpretation.
  • Proximal interpretations: For a convex-set indicator, the proximal operator becomes the ordinary Euclidean projection, extending projection to general functions.This links proximal methods to constrained optimization and quadratic majorization.
  • Fixed-point interpretation: Repeated proximal updates characterize minimizers through fixed points: proxγf(x⋆) = x⋆ exactly when x⋆ minimizes f.At convergence, the Moreau-envelope gradient is zero at the minimizing point.
  • Computation: The practical usefulness of proximal algorithms depends on evaluating the proximal operator in closed form or at modest computational cost.The paper lists closed-form operators for common penalties and likelihood-related terms.

3 Proximal Algorithms

The paper develops proximal-gradient and higher-order algorithms for composite objectives, establishing convex convergence results and extending the framework to selected non-convex penalties.

  • Proximal gradient: Proximal-gradient methods alternate a gradient step for the differentiable loss with a proximal-operator step for the non-differentiable penalty.This structure targets objectives of the form F(x) = l(x) + φ(x).
  • Proximal gradient: The proximal-gradient update is motivated both as a majorization-minimization method and as a forward-backward fixed-point iteration.A Lipschitz-continuous gradient permits the required majorizing function for γ ∈ (0, 1/λ_l].
  • Proximal gradient: Under the stated convexity, domain, and attainment conditions, proximal gradient converges at rate 1/t with fixed step size γ = 1/λ_l.The method can also be interpreted as finding a fixed point of a forward-backward operator.
  • Non-convex optimization: The framework also applies to selected non-convex regularization penalties, including Lq penalties for 0 ≤ q ≤ 1.The paper gives an example of this non-convex case.
  • Proximal Newton: Proximal Newton methods replace the linear approximation underlying proximal gradient with higher-order expansions and can use Hessian approximations.These choices connect the method to quasi-Newton and half-quadratic approaches.
  • Proximal Newton: Second-order information can make proximal methods possible for some non-convex problems and can convexify some objectives.The paper also reports extremely fast convergence when second-order information is used in a fused-lasso simulation.

4 Related Algorithms: ADMM, Divide and Concur, Bregman Divergences

The paper connects proximal optimization with variable splitting, duality, ADMM, Bregman divergences, and exponential-family models. These reformulations decouple objective terms while preserving relationships among primal, dual, and constrained problems.

  • Variable Splitting: Variable splitting introduces latent or slack variables to decouple fit and penalty terms in constrained formulations.The resulting primal problem can be related to dual formulations through Lagrangians and conjugacy.
  • Dual Ascent: Dual ascent updates the dual variable using the constraint residual Ax − y, with a step size α_k.Under strong duality, primal and dual optimal values coincide and a primal optimum can be recovered from a dual optimum.
  • Augmented Lagrangian: Augmented Lagrangians stabilize dual-ascent formulations by adding a ridge-like quadratic term whose magnitude is controlled by γ.The dual update remains unchanged relative to standard dual ascent, while the primal update gains regularization.
  • ADMM: ADMM alternates optimization over split variables, with the first two updates given by proximal operators of the fit and penalty terms.It combines variable splitting with the augmented Lagrangian and differs from dual ascent by optimizing x and z separately.
  • Bregman Divergences: Bregman divergences connect exponential-family natural and mean-value parameterizations through the cumulant-generating function and its Legendre dual.The expected value satisfies μ(θ) = b′(θ), identifying the dual variable with the mean-value parameterization.

5 Envelope Methods

The paper develops envelope-based views of proximal algorithms, including forward-backward, Douglas-Rachford, half-quadratic, and Bregman-divergence envelopes. Their gradients or proximal mappings generate algorithms for convex and selected non-convex objectives.

  • Forward-Backward Envelope: Forward-backward envelope stationary points solve the original composite problem through x = prox_γφ(x − γ∇l(x)).The construction assumes a strongly convex smooth loss and a proper lower semicontinuous convex penalty.
  • Forward-Backward Envelope: The forward-backward envelope has a descent property under the stated convexity and smoothness conditions.Applying the proximal operator of γφ decreases the envelope value and helps identify stationary points.
  • Douglas-Rachford Envelope: The Douglas-Rachford envelope is interpreted as a backward-backward envelope and yields proximal iterations converging to the solution of min_x {l(x) + φ(x)}.It uses the Moreau envelope of l and can be viewed as a special case of a forward-backward envelope.
  • Half-Quadratic Envelope: Half-quadratic envelopes support quasi-Newton algorithms for L2 loss and can be combined with non-convex penalties.The associated iterative mappings connect gradient linearization and quasi-Newton updates.
  • Bregman-Divergence Envelope: Bregman-divergence envelopes enable non-smooth regularization in exponential-family models, illustrated with logistic and Poisson regression.The D-Moreau envelope supports alternating Bregman projection methods for objectives combining divergence terms with penalties.

6 Proximal Algorithms for Composite Functions

For composite penalties such as φ(Bx), the paper uses splitting, proximal operators, and envelopes to reformulate optimization problems into tractable subproblems. These constructions connect primal-dual methods, augmented Lagrangians, majorization, and fixed-point algorithms.

  • Composite Objectives: Composite penalties φ(Bx) are common in models with structural constraints or correlations, including fused-lasso difference operators.The paper focuses on formulations that decouple φ from B while preserving the primal solution.
  • Splitting: Splitting replaces an unconstrained objective with an equivalent constrained problem containing latent variables, enabling separate treatment of objective terms.The associated split forms can be interpreted through Lagrangian formulations and convex conjugacy.
  • Proximal Construction: Proximal operators and Moreau identities simplify repeated majorization steps and allow movement between primal and dual objective formulations.The paper presents these properties as a way to shorten constructions and convergence arguments.
  • ADMM Connection: ADMM arises when a squared penalty is added to the split formulation, producing alternating conditional solutions for x and z.These conditional solutions are given by proximal points and correspond to an augmented-Lagrangian formulation.
  • Surrogates and Majorization: Majorization and surrogate envelopes can induce proximal operators for approximating subproblem solutions, including linearized ADMM and split inexact Uzawa methods.The approach uses approximations or envelopes when direct proximal solutions are unavailable or inefficient.
  • Fixed-Point Algorithms: Non-expansive fixed-point operators guarantee convergence by Opial’s theorem, with linear convergence when the operator is a contraction.The construction then recovers the solution through x⋆ = A^-1 applied after finding v⋆.

7 Applications

The applications demonstrate proximal methods across logistic and Poisson regression, composite penalties, and non-convex bridge penalties, with acceleration, second-order information, and exact proximal operators improving practical optimization behavior.

  • Logit Fused Lasso: The logistic regression example uses a quadratic majorizer and proximal gradient updates for a sparse composite objective with an L1 penalty.The majorizer uses a Lipschitz constant based on the design matrix, with penalty coefficient set to 0.1σmax(A).
  • Logit Fused Lasso: Acceleration gives a clear efficiency advantage in logistic regression, although the accelerated objective sequence is non-descent.Figure 2 compares adjusted objective values per iteration with and without Nesterov acceleration.
  • Logit Fused Lasso: A second-order proximal composite formulation converges extremely quickly to the same solution precision as the alternative multinomial logistic formulation.The comparison uses a composite L1 penalty and runs both formulations until the same numeric precision is reached.
  • Poisson Fused Lasso: For Poisson regression with a fused L1 penalty, backtracking replaces the constant gradient step because the loss is convex but not Lipschitz.The design uses first-order differences through D(1)x, and Figure 4 compares objective values with and without acceleration.
  • L2-norm loss plus Lq-norm penalty for 0 < q < 1: The non-convex bridge penalty uses a set-valued closed-form proximal operator and KL-based forward-backward convergence results.The convergence result implies that the choice among proximal-map solutions does not affect convergence properties under the stated conditions.
  • L2-norm loss plus Lq-norm penalty for 0 < q < 1: Bridge-penalty estimates can jump to sparse solutions as q varies, and the exact proximal operator is applied to a prostate cancer regularization path.Figure 5 compares MSE across q and penalty weight, while Figure 6 shows the resulting regularization path.

8 Discussion

The discussion frames proximal algorithms as a broad optimization framework for statistical problems, including non-convex objectives, and identifies several directions for extending their use.

  • Proximal algorithms extend classical gradient methods and provide iterative shrinkage approaches applicable to optimization problems in statistics.
  • The paper describes a framework for constructing solutions to composite statistical objectives using envelopes and easily evaluated closed-form proximal operators.
  • The framework encompasses non-smooth and non-convex optimization, including functions satisfying the Kurdyka-Lojasiewicz inequality.
  • Nesterov acceleration and related tools are discussed as ways to address slow convergence in many MM block descent algorithms.
  • Future work includes Divide and Concur methods for mixed exponential family models, links between proximal splitting and variational Bayes, and combinations with MCMC.

A Convergence

The convergence analysis establishes conditions for forward-backward proximal methods, objective decrease, and an O(1/k) convergence bound, with stronger guarantees under additional structure.

  • The forward-backward proximal solution is analyzed using proximal minimizing properties, quadratic minorization, quadratic majorization, and Bregman-divergence arguments.
  • The analysis assumes lower semi-continuity of l and φ, Lipschitz continuity of ∇l, and independently evaluable, non-empty proximal operators.
  • The proximal formulation uses translation properties and a projection-like minimization map P(w) defined through the divergence D.
  • Objective decrease is ensured by choosing λ ≥ γ, while convexity can improve the resulting bounds.
  • The compounded errors yield an O(1/k) convergence bound, which can be improved by adding momentum based on first-derivative information.

B Nesterov Acceleration

Nesterov acceleration constructs updates from convex combinations of proximal bounds and introduces momentum through a sequence of iteration parameters.

  • For convex φ, upper bounds associated with z = x and z = x⋆ are combined using a convex-combination parameter θ.
  • The intermediate variable w is defined from the preceding steps used in the accelerated update.
  • A sequence θt produces an update equal to the current state plus a momentum term proportional to the direction x − x−.

C Quasi-convex Convergence

For quasi-convex objectives with finite global minima, proximal iterates converge under the stated conditions, including for certain non-convex functions.

  • The setting assumes a quasi-convex, continuous objective with a non-empty set of finite global minima.
  • The proximal iterates converge to global minima even when non-convexity makes the proximal operator set-valued.
  • The result covers functions such as |x|q for 0 < q < 1 and suitable ranges of log(x) and tanh(x).
  • The iterates form a finite-length Fejér sequence and converge to a critical point under the stated conditions.

D Non-convex: Kurdyka- Lojasiewicz (KL)

The KL condition supports convergence analysis by guaranteeing summability and finite length of discrete subgradient trajectories. The section connects this framework to alternating minimisation and augmented-Lagrangian formulations, while noting uniform convexity as one source of KL functions.

  • The KL condition guarantees summability and therefore a finite-length discrete subgradient trajectory.
  • KL properties can establish convergence for alternating minimisation algorithms.
  • A typical application solves min_x {l(x) + φ(x)} through an augmented Lagrangian with a relaxation parameter ρ.
  • Uniformly convex functions are identified as a useful class satisfying the KL condition.
Loading 1502.03175v3…