On the Convergence of the Convex-Concave Procedure

author: Bharath K. Sriperumbudur, Department of Electrical and Computer Engineering, UC San Diego
published: Jan. 19, 2010, recorded: December 2009, views: 369

Slides

Slides
0:00	On the Convergence of the Concave-Convex
0:33	Outline
0:53	D.C. Program
2:18	Sparse Support Vector Machines
3:05	The Concave-Convex Procedure
4:05	Majorization-Minimization Algorithm
5:33	Linear Majorization
6:22	Convergence Analysis of CCCP
7:55	Global Convergence of Iterative Algorithms
9:04	Point-to-set Map
10:10	Zangwill’s Global Convergence Theorem
11:26	Global Convergence Theorem for CCCP-I
12:25	Proof Idea
13:28	Global Convergence Theorem for CCCP-II
14:21	Extensions
15:29	Global Convergence Theorem for Constrained CCP
16:31	Local Convergence of CCCP
17:03	Summary
19:56	References

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

The concave-convex procedure (CCCP) is a majorization-minimization algorithm that solves d.c. (difference of convex functions) programs as a sequence of convex programs. In machine learning, CCCP is extensively used in many learning algorithms like sparse support vector machines (SVMs), transductive SVMs, sparse principal component analysis, etc. Though widely used in many applications, the convergence behavior of CCCP has not gotten a lot of specific attention. In this paper, we provide a rigorous analysis of the convergence of CCCP by addressing these questions:

(i) When does CCCP find a local minimum or a stationary point of the d.c. program under consideration?
(ii) When does the sequence generated by CCCP converge?

We also present an open problem on the issue of local convergence of CCCP.