The concave-convex procedure. (English) Zbl 1022.68112

Summary: 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.


68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] DOI: 10.1016/0041-5553(67)90040-7
[2] DOI: 10.1088/0266-5611/14/6/006 · Zbl 0913.65128
[3] DOI: 10.1214/aoms/1177692379 · Zbl 0251.62020
[4] DOI: 10.1109/34.588021 · Zbl 05111233
[5] Dempster A. P., Journal of the Royal Statistical Society, B 39 pp 1– (1977)
[6] DOI: 10.1162/neco.1989.1.3.348
[7] DOI: 10.1038/326689a0
[8] DOI: 10.1162/neco.1995.7.5.1079 · Zbl 05480389
[9] DOI: 10.1016/0167-7152(86)90016-7 · Zbl 0585.62052
[10] DOI: 10.1109/34.566806 · Zbl 05110531
[11] DOI: 10.1023/A:1007665907178 · Zbl 0945.68164
[12] DOI: 10.1162/neco.1994.6.2.181
[13] DOI: 10.1006/inco.1996.2612 · Zbl 0872.68158
[14] DOI: 10.1016/0893-6080(94)90081-7 · Zbl 0809.90110
[15] DOI: 10.2307/1390605
[16] DOI: 10.1049/ip-vis:19941316
[17] DOI: 10.1103/PhysRevA.40.501
[18] DOI: 10.1016/0893-6080(90)90055-P
[19] DOI: 10.1016/S0031-3203(99)00077-1
[20] DOI: 10.1162/neco.1996.8.5.1041 · Zbl 05475395
[21] DOI: 10.1162/089976699300016313
[22] DOI: 10.1109/TSMC.1976.4309519
[23] DOI: 10.1214/aoms/1177703591 · Zbl 0134.25302
[24] DOI: 10.1103/PhysRevE.47.4524
[25] DOI: 10.1162/neco.1990.2.1.1
[26] DOI: 10.1162/neco.1994.6.3.341
[27] DOI: 10.1162/08997660260028674 · Zbl 1051.68121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.