Proximal Gradient Methods for Composite Optimization

34 concepts33 papers1 proposal

Many foundational problems in machine learning require optimizing an objective function that splits cleanly into two parts: a smooth loss function and a non-smooth regularizer. We can express this composite structure as:

$$\min_{x} \{ f(x) + g(x) \}$$

Here, $f(x)$ represents a differentiable loss term (such as least-squares or logistic regression), while $g(x)$ represents a non-differentiable penalty term (such as the $\ell_1$-norm for sparsity or an indicator function for structural constraints).

Standard gradient descent fails here because the gradient of $g(x)$ is not defined everywhere. While subgradient methods can handle non-smoothness, they converge slowly and fail to exploit the smoothness of $f(x)$. More importantly, subgradient steps often destroy the exact structural properties we care about—such as setting coefficients to true zeros in a sparse model.

Proximal gradient methods solve this dilemma by decoupling the smooth and non-smooth components into a two-step iterative process.


The Intuition of Proximal Splitting

Instead of treating the composite objective as a single unmanageable function, proximal methods split the update cycle into two distinct operations:

  1. The Forward (Gradient) Step: We take a standard gradient step using only the smooth function $f(x)$. This moves the parameters in a direction that minimizes the empirical loss.
  2. The Backward (Proximal) Step: We pass this intermediate proposal through a proximal operator associated with $g(x)$.

Mathematically, the proximal operator $\text{prox}_{\gamma g}(y)$ solves a localized optimization subproblem:

$$\text{prox}_{\gamma g}(y) = \arg\min_{x} \left\{ g(x) + \frac{1}{2\gamma} \|x - y\|^2 \right\}$$

Intuitively, the proximal operator balances two competing goals: it finds a point that minimizes the non-smooth penalty $g(x)$ while ensuring we do not move too far away from our gradient-updated proposal $y$. For many common regularizers, this subproblem has an elegant, closed-form solution. For example, when $g(x)$ is the $\ell_1$-norm, the proximal operator is simply the soft-thresholding operator, which cleanly snaps small values exactly to zero.

As shown by Agarwal et al. (2010), this simple decomposition allows first-order gradient methods to achieve fast geometric (linear) convergence rates for a wide class of high-dimensional statistical recovery problems, effectively bridging the gap between statistical theory and optimization efficiency.


Scaling to Large Datasets: Stochasticity and Variance Reduction

In modern large-scale applications, computing the full gradient of $f(x)$ over millions of data points is computationally prohibitive. Instead, we rely on stochastic gradient descent (SGD) or mini-batch updates. However, the inherent variance of stochastic gradients introduces noise that can destabilize the proximal step, causing the parameters to bounce around the optimum.

To address this, researchers integrated proximal operators with variance-reduction frameworks. The core idea is to use periodic full-gradient snapshots or running gradient averages to systematically cancel out stochastic noise.

Standard Proximal SGD:
[Iterate x_t] ──> [Stochastic Gradient of f] ──> [Proximal Operator of g] ──> [Noisy Iterate x_{t+1}]

Variance-Reduced Proximal SGD:
[Iterate x_t] ──> [Variance-Corrected Gradient] ──> [Proximal Operator of g] ──> [Stable Iterate x_{t+1}]
  • Prox-SVRG: Xiao et al. (2014) demonstrated that integrating proximal mappings with Stochastic Variance Reduced Gradient (SVRG) allows the algorithm to maintain a stable, geometric convergence rate. By resetting the gradient estimate periodically, it eliminates the variance that plagues standard stochastic methods on regularized models like Lasso.
  • SAGA: Defazio et al. (2014) developed an incremental gradient method that supports non-strongly convex composite objectives without requiring periodic full-gradient passes. They showed that utilizing unbiased gradient estimators enables direct support for non-smooth penalties via proximal operators without sacrificing theoretical convergence guarantees.

By applying the proximal operator after mini-batch updates (Konečný et al., 2015) or within incremental aggregated frameworks (Vanli et al., 2018), these methods ensure that structured sparsity and constraints are strictly enforced throughout the entire optimization trajectory.


When the smooth loss function $f(x)$ is nonconvex—as is frequently the case in deep learning, matrix factorization, or robust estimation—proving convergence becomes significantly more challenging.

To handle objectives composed of a smooth nonconvex term and a nonsmooth convex term, Li et al. (2018) and Li et al. (2022) introduced simplified variance-reduced proximal frameworks (such as ProxSVRG+). These methods integrate the proximal operator directly into the variance-reduced stochastic update step, drastically reducing the frequency of full gradient evaluations and the total number of proximal oracle calls needed to find stationary points or escape saddle points.


Incorporating Momentum and Acceleration

Can we combine the structural benefits of proximal splitting with the speed of accelerated optimization methods like the Heavy-Ball method?

The challenge with momentum is that inertial steps can cause the algorithm to overshoot, potentially violating constraints or destroying sparsity. However, incorporating proximal operators directly into the inertial update loop acts as a stabilizing correction.

Aujol et al. (2023) analyzed the Heavy-Ball method through the lens of the Łojasiewicz property, proving that incorporating proximal operators allows momentum-based acceleration to be safely applied to problems where gradients are not everywhere defined. Similarly, Wei et al. (2025) demonstrated that combining gradient extrapolation tricks with proximal steps achieves global accelerated convergence while preserving the core structural properties of the regularizer.


Modern Extensions and Ecosystem Integration

The proximal gradient paradigm has expanded to fit nearly every corner of modern machine learning optimization:

  • Adaptive Learning Rates: Standard adaptive frameworks (like Adam) often lack the proximal extensions required for composite optimization. Kavis et al. (2019) developed universal, adaptive proximal algorithms to handle structured sparsity and non-differentiable penalties in a unified way.
  • Data Shuffling: In practice, engineers process data by shuffling epochs rather than sampling uniformly. Liu et al. (2024) provided the first theoretical guarantees for the last-iterate convergence of proximal shuffling gradient methods, proving that epoch-based data processing safely coexists with non-smooth constraints.
  • Distributed Systems: When training massive models across clusters, communication bottlenecks are severe. Rodomanov et al. (2025) integrated proximal operators into accelerated error-feedback mechanisms, allowing for communication-efficient distributed optimization under sparse regularization.
  • Minimax Optimization: For complex adversarial or saddle-point problems satisfying the Polyak-Łojasiewicz condition, Huang (2025) integrated proximal mappings into momentum-based variance reduction steps, ensuring mathematically well-defined updates even when the minimax objective is non-differentiable everywhere.

Key Foundational Work

Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010) — contributed 1 concept elements to this direction.
Regularized Risk Minimization by Nesterov's Accelerated Gradient Methods: Algorithmic Extensions and Empirical Studies (2010) — contributed 1 concept elements to this direction.
Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_composite_objective_optimization_6a6c07ae,
  title = {composite objective optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/composite-objective-optimization/rdr_6a6c07ae89e944fba20c791574b20a49},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_composite_objective_optimization_6a6c07ae_v1,
  title = {composite objective optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/composite-objective-optimization/rdr_6a6c07ae89e944fba20c791574b20a49/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake