The notion of convexity underlies a lot of beautiful mathematics. When combined with computation, it gives rise to the area of convex optimization that has had a huge impact on understanding and improving the world we live in. However, convexity does not provide all the answers. Many procedures in statistics, machine learning and nature at large—Bayesian inference, deep learning, protein folding—successfully solve non-convex problems that are NP-hard, i.e., intractable on worst-case instances. Moreover, often nature or humans choose methods that are inefficient in the worst case to solve problems in P.
Can we develop a theory to resolve this mismatch between reality and the predictions of worst-case analysis? Such a theory could identify structure in natural inputs that helps sidestep worst-case complexity.
If you want to change selection, open document below and click on "Move attachment"
Off the Convex Path – Off the convex path Off the Convex Path – Off the convex path About Contact Subscribe Off the Convex Path Contributors Sanjeev Arora Moritz Hardt Nisheeth Vishnoi Nadav Cohen Mission statement The notion of convexity underlies a lot of beautiful mathematics. When combined with computation, it gives rise to the area of convex optimization that has had a huge impact on understanding and improving the world we live in. However, convexity does not provide all the answers. Many procedures in statistics, machine learning and nature at large—Bayesian inference, deep learning, protein folding—successfully solve non-convex problems that are NP-hard, i.e., intractable on worst-case instances. Moreover, often nature or humans choose methods that are inefficient in the worst case to solve problems in P. Can we develop a theory to resolve this mismatch between reality and the predictions of worst-case analysis? Such a theory could identify structure in natural inputs that helps sidestep worst-case complexity. This blog is dedicated to the idea that optimization methods—whether created by humans or nature, whether convex or nonconvex—are exciting objects of study and, often lead to useful alg Summary
| status | not read | | reprioritisations | |
|---|
| last reprioritisation on | | | suggested re-reading day | |
|---|
| started reading on | | | finished reading on | |
|---|
Details