The Concave-Convex Procedure
Abstract
The concave-convex procedure (CCCP) is a way to construct discrete-time iterative dynamical systems that are guaranteed to decrease global optimization and energy functions monotonically. This procedure can be applied to almost any optimization problem, and many existing algorithms can be interpreted in terms of it. In particular, we prove that all expectation-maximization algorithms and classes of Legendre minimization and variational bounding algorithms can be reexpressed in terms of CCCP. We show that many existing neural network and mean-field theory algorithms are also examples of CCCP. The generalized iterative scaling algorithm and Sinkhorn's algorithm can also be expressed as CCCP by changing variables. CCCP can be used both as a new way to understand, and prove the convergence of, existing optimization algorithms and as a procedure for generating new algorithms.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Theorem 2 in Yuille & Rangarajan (2002) and Theorem 2 in Yuille & Rangarajan (2003) state that the update rule Eq. (31) is guaranteed to monotonically decrease the energy E as a function of time.
“Theorem 2 in Yuille & Rangarajan (2002) and Theorem 2 in Yuille & Rangarajan (2003) state that the update rule Eq. (31) is guaranteed to monotonically decrease the energy E as a function of time.”
From Hopfield Networks is All You Need (2020) · cites this paper as Yuille & Rangarajan, 2003
Cites
Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Deep learning in medical image registration: a review
Fu, Y., Lei, Y., Wang, T., Curran, W. J., Liu, T., & Yang, X. (2020) · Physics in Medicine & Biology · doi:10.1088/1361-6560/ab843e · Cited by 661 · see citing works
Zero-Shot Learning via Semantic Similarity Embedding
Zhang, Z., & Saligrama, V. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.474 · Cited by 629 · see citing works
Hopfield Networks is All You Need
Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G. K., et al. (2020) · arXiv · doi:10.48550/arxiv.2008.02217 · Cited by 236 · see citing works
“(A20) is the Concave-Convex Procedure (CCCP) for minimizing the energy E.”
BackgroundMethodInfluentialNon-maximum Suppression for Object Detection by Passing Messages Between Windows
Rothe, R., Guillaumin, M., & Van Gool, L. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-16865-4_19 · Cited by 218 · see citing works
Deep Differentiable Random Forests for Age Estimation
Shen, W., Guo, Y., Wang, Y., Zhao, K., Wang, B., & Yuille, A. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2019.2937294 · Cited by 91 · see citing works
Self-citationTowards Unified Object Detection and Semantic Segmentation
Dong, J., Chen, Q., Yan, S., & Yuille, A. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-10602-1_20 · Cited by 70 · see citing works
Self-citationIntegrating many co-splicing networks to reconstruct splicing regulatory modules
Dai, C., Li, W., Liu, J., & Zhou, X. J. (2012) · BMC Systems Biology · doi:10.1186/1752-0509-6-s1-s17 · Cited by 20 · see citing works
Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models
Millidge, B., Salvatori, T., Song, Y., Lukasiewicz, T., & Bogacz, R. (2022) · arXiv · doi:10.48550/arxiv.2202.04557 · Cited by 19 · see citing works
Quantum computing and supervised machine learning
Oneto, L., Ridella, S., & Anguita, D. (2017) · Quantum Inspired Computational Intelligence · doi:10.1016/b978-0-12-804409-4.00002-4 · Cited by 11 · see citing works
- Authors
- Yuille, A. L., & Rangarajan, A.
- Affiliations
- Smith-Kettlewell Eye Research Institute (US)
- University of Florida (US)
- Corresponding author
- Yuille, A. L.
- Rangarajan, Anand
- Venue
- Neural Computation
- Publisher
- MIT Press
- Published
- 2003-04-01
- Volume
- 15
- Issue
- 4
- Pages
- 915-936
- ISSN
- 0899-7667 (ISSN-L)
- 1530-888X
- OpenAlex
- W2166765763
- Cited by
- 1,151
- References
- 1
- Citations by year
- 2026: 27 · 2025: 29 · 2024: 57 · 2023: 53 · 2022: 74 · 2021: 64 · 2020: 80 · 2019: 73 · 2018: 85 · 2017: 79 · 2016: 77 · 2015: 83 · 2014: 78 · 2013: 88 · 2012: 67
- FWCI
- 4.60
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Neural Computation (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Science Foundation
- National Institutes of Health (5r01ey012691-03)
- University of California, Los Angeles
- National Eye Institute (R01-EY 12691-01)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- concave-convex procedure, global optimization, energy function, expectation-maximization algorithm, mean-field theory, neural network algorithms, Sinkhorn algorithm, convergence proof
- MeSH terms
- Algorithms, Energy Metabolism, Neural Networks, Computer
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
