Nonconvex? NP!
(No Problem!)
Lecturer: Ryan Tibshirani
Convex Optimization 10-725/36-725
1
Last time: integer programming
Given convex function f, convex set C, J ⊆ {1, . . . n}, an integer
program is a problem of the form
min
x
f(x)
subject to x ∈ C
x
j
∈ Z, j ∈ J
IPs are like twisted cousin of convex optimization. Much harder to
solve, but there is a huge literature on the topic. Key ideas:
•
Lower and upper bounds
•
Branch and bound method
•
Cutting plane method
Application to modern statistical problems is growing, and exciting.
E.g., least median of squares regression, best subset selection
2
My soap box
Recently, it’s been said that statisticians should pay more attention
to IPs. I agree
But just because we can solve a nonconvex problem by formulating
it as IP, doesn’t mean we should prefer its solution over that from
related convex program
•
The lasso is not a heuristic for best subset selection
•
It’s an estimator, with its own properties
•
An `
1
penalty shrinks coefficients (unlike `
0
); this can hurt or
help, depending on the situation
•
Even if we could always solve best subset selection efficiently,
it would be unwise to think that we should always prefer it
Optimizers should be more aware of the bias-variance tradeoff
3
We (Hastie, Tibshirani x 2) are putting together some experiments
to make this point salient. Preview:
●
●
●
●
0.0 0.2 0.4 0.6 0.8
0.168 0.170 0.172 0.174 0.176 0.178
SNR= 6.0 , Prop var exp= 0.83
Pairwise Correlation
Relative Test Error = MSE/Var(y)
●
●
●
●
●
●
●
●
●
●
●
●
lasso
subset
relaxed
fs
●
●
●
●
0.0 0.2 0.4 0.6 0.8
0.340 0.342 0.344 0.346 0.348 0.350 0.352
SNR= 2.5 , Prop var exp= 0.66
Pairwise Correlation
Relative Test Error = MSE/Var(y)
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0.0 0.2 0.4 0.6 0.8
0.580 0.585 0.590 0.595 0.600 0.605
SNR= 1.0 , Prop var exp= 0.4
Pairwise Correlation
Relative Test Error = MSE/Var(y)
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0.0 0.2 0.4 0.6 0.8
0.75 0.76 0.77 0.78 0.79 0.80
SNR= 0.5 , Prop var exp= 0.22
Pairwise Correlation
Relative Test Error = MSE/Var(y)
●
●
●
●
●
●
●
●
●
●
●
●
4
Outline
Today:
•
Convex versus nonconvex?
•
Classical nonconvex problems
•
Eigen problems
•
Graph problems
•
Nonconvex proximal operators
•
Discrete problems
•
Infinite-dimensional problems
•
Statistical problems
•
Miscellaneous
5
