{ "id": "ep20dqc16s", "slug": "proximal-gradient-method", "title": "Proximal gradient method", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Non-geographic · 1946 to 2000: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" } ] }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Non-geographic · 2001 to 2020: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms" } ] } ], "excerpt": "The proximal gradient method, also known as proximal gradient methods, is a first-order algorithm minimizing smooth plus nonsmooth objectives, popularized as ISTA for l1-regularized problems.", "snippet": "The proximal gradient method, also known as proximal gradient methods, is a first-order algorithm minimizing smooth plus nonsmooth objectives, popularized as ISTA for l1-regularized problems.", "node": "technology.computing.ai.algorithms", "markdown": "# Proximal gradient method\n\nThe proximal gradient method is an iterative first-order algorithm for minimizing an objective of the form \\( f(x) + h(x) \\), where \\( f \\) is smooth with a Lipschitz-continuous gradient (gradient changes at most proportionally to distance moved) and \\( h \\) is convex and possibly nonsmooth, by alternating a gradient step on \\( f \\) with an evaluation of the proximal operator of \\( h \\). It is widely used for l1-regularized problems, popularized in signal and image processing under the name ISTA.[1](https://www.lamsade.dauphine.fr/~croyer/ensdocs/PGL/LectureNotesOML-PGL.pdf) Proximal algorithms as a family play a role for nonsmooth, constrained, large-scale, or distributed problems analogous to the role [Newton's method](https://www.edgepedia.org/newtons-method) plays for unconstrained smooth problems of modest size.[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) The decomposition of the objective into a smooth and a nonsmooth part is not unique, so different splittings of the same problem lead to different implementations.[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf)\n\n| Key fact | Value |\n|---|---|\n| Objective class | \\( f(x) + h(x) \\), \\( f \\) convex and smooth, \\( h \\) closed proper convex, possibly extended-valued (so it can encode constraints)[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) |\n| Proximal operator | \\( \\mathrm{prox}_{\\alpha h}(x) = \\arg\\min_z \\{ \\alpha h(z) + \\tfrac{1}{2}\\|z - x\\|^2 \\} \\)[3](https://link.springer.com/article/10.1007/s10107-026-02377-7) |\n| l1 prox | Component-wise soft-thresholding: \\( x_i - t \\) if \\( x_i \\ge t \\), \\( 0 \\) if \\( x_i \\in [-t, t] \\), \\( x_i + t \\) if \\( x_i \\le -t \\)[4](http://www.damtp.cam.ac.uk/user/hf323/M19-OPT/lecture6.pdf) |\n| Step size | Fixed \\( \\lambda \\in (0, 1/L] \\) guarantees convergence; the method actually converges for steps below \\( 2/L \\)[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) |\n| Plain rate | \\( F(x^k) - F(x^*) = O(1/k) \\) in function values[5](https://dl.acm.org/doi/10.1137/080716542) |\n| Accelerated rate | \\( O(1/k^2) \\) (FISTA) at the same per-iteration cost[5](https://dl.acm.org/doi/10.1137/080716542) |\n| Strongly convex case | Linear rate \\( (L - \\mu)/(L + \\mu) \\) with optimal step \\( \\lambda^{*} = 2/(L + \\mu) \\)[6](https://research.dial.uclouvain.be/server/api/core/bitstreams/102a9b4c-7607-4c59-8f36-5fd4203bcf84/content) |\n\n## How it works\n\nThe proximal operator of a function \\( h \\) is\n\n\\[ \\mathrm{prox}_{h}(v) = \\arg\\min_{x} \\; h(x) + \\tfrac{1}{2}\\|x - v\\|^{2}, \\]\n\na generalized projection that trades off staying near \\( v \\) against reducing \\( h \\).[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) It generalizes ordinary projection: the proximal operator of the indicator function of a convex set is projection onto that set, so proximal algorithms extend algorithms for finding points in intersections of convex sets.[7](https://lcondat.github.io/publis/Condat_SIAM_Review.pdf)\n\nFor the l1 norm the proximal subproblem has a closed form, the soft-thresholding (shrinkage) operator, applied component-wise:[4](http://www.damtp.cam.ac.uk/user/hf323/M19-OPT/lecture6.pdf)\n\n\\[ \\big(\\mathrm{prox}_{t\\|\\cdot\\|_{1}}(x)\\big)_{i} = \\begin{cases} x_{i} - t & x_{i} \\ge t, \\\\ 0 & x_{i} \\in [-t, t], \\\\ x_{i} + t & x_{i} \\le -t. \\end{cases} \\]\n\nBecause coefficients smaller in magnitude than the threshold are set exactly to zero, soft-thresholding promotes zero components in the iterates and yields sparser solutions.[1](https://www.lamsade.dauphine.fr/~croyer/ensdocs/PGL/LectureNotesOML-PGL.pdf)\n\n## How it is done\n\nOne iteration is a gradient step on the smooth term followed by a proximal step:[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf)\n\n\\[ x^{k+1} := \\mathrm{prox}_{\\lambda_{k} h}\\big(x^{k} - \\lambda_{k} \\nabla f(x^{k})\\big). \\]\n\nThe solution is characterized as a fixed point, \\( w^{*} = \\mathrm{prox}_{\\lambda h}(w^{*} - \\lambda \\nabla f(w^{*})) \\) for any \\( \\lambda > 0 \\).[8](https://www.cs.ubc.ca/~schmidtm/Courses/5XX-S20/S6.pdf) Under the Lipschitz condition \\( \\|\\nabla f(x) - \\nabla f(y)\\| \\le L \\|x - y\\| \\), a fixed step \\( \\lambda \\in (0, 1/L] \\) gives a global sublinear rate \\( O(1/k) \\) in objective value, and the iterates converge to a global minimum.[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) • [9](https://ar5iv.labs.arxiv.org/html/1803.01621) The \\( 1/L \\) bound is conservative: the method actually converges for step sizes below \\( 2/L \\), though above \\( 1/L \\) it is no longer a majorization-minimization method.[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) Guaranteed improvement holds for \\( \\lambda < 2/L \\), and practical backtracking methods work better than the worst-case rule.[8](https://www.cs.ubc.ca/~schmidtm/Courses/5XX-S20/S6.pdf)\n\nWhen \\( L \\) is not known or computable, for example for \\( f(x) = \\tfrac{1}{2}\\|Ax - b\\|^{2} \\), where \\( L \\) is the largest eigenvalue of \\( A^{T}A \\), backtracking is used: starting from \\( L_{0} > 0 \\) and \\( \\eta > 1 \\), one finds the smallest nonnegative integer \\( i_{k} \\) such that \\( F(p_{\\bar{L}}(x_{k-1})) \\le Q_{\\bar{L}}(p_{\\bar{L}}(x_{k-1}), x_{k-1}) \\) with \\( \\bar{L} = \\eta^{i_{k}} L_{k-1} \\).[5](https://dl.acm.org/doi/10.1137/080716542)\n\nIf \\( f \\) is \\( \\mu \\)-strongly convex, convergence is linear. The best possible worst-case rate is achieved by the step \\( \\lambda^{*} = 2/(L + \\mu) \\), giving the optimal rate \\( (L - \\mu)/(L + \\mu) \\); this step interpolates between the short step \\( 1/L \\), which is optimal without strong convexity, and the long step \\( 1/\\mu \\).[6](https://research.dial.uclouvain.be/server/api/core/bitstreams/102a9b4c-7607-4c59-8f36-5fd4203bcf84/content)\n\nThe fast iterative shrinkage-thresholding algorithm (FISTA) preserves the computational simplicity of ISTA while achieving a global convergence rate proven significantly better, both theoretically and practically.[5](https://dl.acm.org/doi/10.1137/080716542) [Acceleration](https://www.edgepedia.org/acceleration) adds an extrapolation (momentum) step before the proximal gradient step,[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) for example\n\n\\[ y^{k+1} := x^{k} + \\omega_{k}(x^{k} - x^{k-1}), \\qquad \\omega_{k} = \\frac{k}{k+3}, \\]\n\nfollowed by a proximal gradient step at \\( y^{k+1} \\), yielding an \\( O(1/k^{2}) \\) objective rate for \\( \\lambda \\in (0, 1/L] \\).[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) Acceleration reaches the optimal \\( O(1/\\sqrt{\\varepsilon}) \\) rate in the suboptimality \\( \\varepsilon \\), and such methods are called optimal first-order methods because their worst-case rate cannot be improved further.[10](https://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/08-prox-grad.pdf) • [2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) The dominant computational steps of ISTA and FISTA are essentially the same, one gradient evaluation and one prox computation.[5](https://dl.acm.org/doi/10.1137/080716542) • [11](https://www.cse.iitb.ac.in/~cs709/notes/readingAssignment/mo25_ch10.pdf)\n\n## Origin\n\nThe method grew out of two earlier lines of work. One is the [proximal point algorithm](https://www.edgepedia.org/proximal-point-algorithm), an iteration \\( z^{k+1} = J_{c_{k}}(z^{k}) \\) built on the resolvents of a maximal monotone operator, whose convergence theorem already allowed the resolvents to be evaluated approximately, so long as the sum of all errors is finite.[12](https://faculty.engineering.asu.edu/bertsekas/wp-content/uploads/sites/129/2020/03/Eckstein_Bertsekas_D-R.pdf) The other is forward-backward splitting within the general framework of splitting methods, to which the ISTA-type scheme can be traced back.[5](https://dl.acm.org/doi/10.1137/080716542)\n\nFISTA was reported by Amir Beck and Marc Teboulle in the SIAM Journal on Imaging Sciences in 2009.[5](https://dl.acm.org/doi/10.1137/080716542) A later refinement of the analysis, a pivotal inequality for ISTA and FISTA under a strongly convex smooth part, was reported by Li, Bowen, Shi, Bin, and Ya-Xiang Yuan in 2022.[13](https://doi.org/10.13140/rg.2.2.26693.93927)\n\n## Variants\n\nBeyond plain ISTA and FISTA, the main variants change the step-size strategy or the metric. Backtracking variants handle an unknown Lipschitz constant.[5](https://dl.acm.org/doi/10.1137/080716542) Variable metric forward-backward (VMFB) algorithms and quasi-Newton proximal methods improve performance and robustness to ill-conditioning.[9](https://ar5iv.labs.arxiv.org/html/1803.01621) Adaptive proximal gradient methods adjust stepsizes at no added per-iteration cost, converge assuming only local Lipschitzness of the gradient, and allow larger stepsizes than earlier adaptive schemes.[14](https://proceedings.neurips.cc/paper_files/paper/2024/file/b676cbd80be73a4a7af178f12035a801-Paper-Conference.pdf) A 2024 line of adaptive methods is universal across Hölder smoothness regimes without approximation, exploiting plain Hölder inequalities rather than \\( \\varepsilon \\)-oracles or line searches while remaining linesearch-free.[15](https://proceedings.mlr.press/v235/oikonomidis24a.html) [Stochastic](https://www.edgepedia.org/stochastic) and inexact variants adaptively control the accuracy of gradient estimates and even allow biased estimates.[16](https://arxiv.org/pdf/2507.14479) OptISTA, a recent accelerated method, converges faster than FISTA and exactly matches the lower bound for black-box first-order methods.[3](https://link.springer.com/article/10.1007/s10107-026-02377-7) A 2024 study of linear convergence shows that under strong convexity of the smooth part, ISTA's behavior is linear rather than logarithmic, and FISTA has a faster linear rate than ISTA.[17](https://link.springer.com/article/10.1007/s40305-024-00561-0)\n\n## Applications\n\nThe canonical application is l1-regularized least squares, the lasso and compressed-sensing problem, where the proximal step is soft-thresholding.[4](http://www.damtp.cam.ac.uk/user/hf323/M19-OPT/lecture6.pdf) The method was popularized in signal and image processing under the name ISTA.[1](https://www.lamsade.dauphine.fr/~croyer/ensdocs/PGL/LectureNotesOML-PGL.pdf) Wavelet-based image deblurring is the standard numerical demonstration of acceleration, with FISTA faster than ISTA by several orders of magnitude.[5](https://dl.acm.org/doi/10.1137/080716542) In matrix completion, the proximal update for the nuclear-norm-type regularizer requires a singular value decomposition (SVD).[10](https://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/08-prox-grad.pdf) Because ISTA-class methods are simple, they are adequate for large-scale problems even with dense matrix data, though they converge quite slowly without acceleration.[5](https://dl.acm.org/doi/10.1137/080716542)\n\n## Limitations and alternatives\n\nThe convergence theory assumes the proximal subproblem is solved exactly; in general, all bets are off if it is only minimized approximately.[10](https://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/08-prox-grad.pdf) The proximal operator itself is an optimization subproblem, a failure mode when no closed form exists.[2](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf) Exact evaluation can be expensive for some regularizers, such as the nuclear norm when it requires an SVD, whereas the l1 proximal operator is computed by soft-thresholding in linear time; practical remedies include diagonal or Barzilai-Borwein Hessian approximations, orthant-wise (two-metric) methods, inexact proximal evaluations, and combinations with L-BFGS or Hessian-free methods.[8](https://www.cs.ubc.ca/~schmidtm/Courses/5XX-S20/S6.pdf) For matrix completion, where each prox step is an SVD, backtracking and acceleration can be disadvantageous because backtracking means multiple SVDs per iteration; over a fine enough grid of regularization values, plain proximal gradient can often perform just as well without acceleration.[10](https://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/08-prox-grad.pdf)\n\nClassical convergence theory also requires the derivative of the smooth part to be globally Lipschitz continuous, which can be restrictive in practice; convergence results that drop this assumption give up convergence rates.[18](https://ar5iv.labs.arxiv.org/html/2112.01798) The method belongs to a family of splitting algorithms for sums of monotone operators that also includes ADMM, Douglas-Rachford splitting, and the Pock-Chambolle algorithm; these first-order methods have minimal memory requirements suited to large-scale problems but suffer from low convergence speed.[9](https://ar5iv.labs.arxiv.org/html/1803.01621) Direct head-to-head benchmarks against [subgradient methods](https://www.edgepedia.org/subgradient-method), coordinate descent, and L-BFGS on l1-regularized problems are not settled by published comparisons; L-BFGS hybrids and quasi-Newton proximal variants appear as remedies for ill-conditioning rather than as benchmarked alternatives.[8](https://www.cs.ubc.ca/~schmidtm/Courses/5XX-S20/S6.pdf) • [9](https://ar5iv.labs.arxiv.org/html/1803.01621)\n\n## References\n\n1. [Lecture notes on proximal methods and regularization (Dauphine)](https://www.lamsade.dauphine.fr/~croyer/ensdocs/PGL/LectureNotesOML-PGL.pdf)\n2. [Proximal Algorithms (Parikh & Boyd, Foundations and Trends in Optimization)](https://stanford.edu/%7Eboyd/papers/pdf/prox_algs.pdf)\n3. [Optimized methods for composite optimization: a reduction perspective (Mathematical Programming)](https://link.springer.com/article/10.1007/s10107-026-02377-7)\n4. [Lecture 6: Proximal gradient methods (Cambridge)](http://www.damtp.cam.ac.uk/user/hf323/M19-OPT/lecture6.pdf)\n5. [A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems (Beck & Teboulle, SIAM J. Imaging Sciences 2(1), 2009), publisher/DOI record](https://dl.acm.org/doi/10.1137/080716542)\n6. [Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization](https://research.dial.uclouvain.be/server/api/core/bitstreams/102a9b4c-7607-4c59-8f36-5fd4203bcf84/content)\n7. [Proximal Splitting Algorithms in Signal Processing (Condat, SIAM Review)](https://lcondat.github.io/publis/Condat_SIAM_Review.pdf)\n8. [First-Order Optimization Algorithms for Machine Learning, Proximal-Gradient (UBC, Schmidt)](https://www.cs.ubc.ca/~schmidtm/Courses/5XX-S20/S6.pdf)\n9. [Proximal gradient algorithms: Applications in signal processing](https://ar5iv.labs.arxiv.org/html/1803.01621)\n10. [Proximal Gradient Descent and Acceleration (Tibshirani, CMU lecture)](https://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/08-prox-grad.pdf)\n11. [The Proximal Gradient (book chapter, ch. 10)](https://www.cse.iitb.ac.in/~cs709/notes/readingAssignment/mo25_ch10.pdf)\n12. [On the Douglas, Rachford splitting method and the proximal point algorithm for maximal monotone operators (Eckstein & Bertsekas)](https://faculty.engineering.asu.edu/bertsekas/wp-content/uploads/sites/129/2020/03/Eckstein_Bertsekas_D-R.pdf)\n13. [Li, Bowen, Shi, Bin, Ya-Xiang Yuan (2022). Proximal Subgradient Norm Minimization of ISTA and FISTA. .](https://doi.org/10.13140/rg.2.2.26693.93927)\n14. [Adaptive Proximal Gradient Method for Convex Optimization (NeurIPS 2024)](https://proceedings.neurips.cc/paper_files/paper/2024/file/b676cbd80be73a4a7af178f12035a801-Paper-Conference.pdf)\n15. [Adaptive Proximal Gradient Methods Are Universal Without Approximation (PMLR v235, 2024)](https://proceedings.mlr.press/v235/oikonomidis24a.html)\n16. [On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation (arXiv, 2025)](https://arxiv.org/pdf/2507.14479)\n17. [Linear Convergence of ISTA and FISTA (Springer, 2024)](https://link.springer.com/article/10.1007/s40305-024-00561-0)\n18. [Convergence Properties of Monotone and Nonmonotone Proximal Gradient Methods Revisited](https://ar5iv.labs.arxiv.org/html/2112.01798)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/08-prox-grad.pdf" ], "url": "https://www.edgepedia.org/proximal-gradient-method", "markdown_url": "https://www.edgepedia.org/proximal-gradient-method.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Proximal gradient method\", Edgepedia (EdgeChat), https://www.edgepedia.org/proximal-gradient-method. Edgepedia Community License 1.0.", "credit_md": "\"[Proximal gradient method](https://www.edgepedia.org/proximal-gradient-method)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/proximal-gradient-method](https://www.edgepedia.org/proximal-gradient-method). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Proximal gradient method\", Edgepedia (EdgeChat), https://www.edgepedia.org/proximal-gradient-method. Edgepedia Community License 1.0.", "speakable": "The proximal gradient method, also known as proximal gradient methods, is a first-order algorithm minimizing smooth plus nonsmooth objectives, popularized as ISTA for l1-regularized problems." }