Non-Convex Optimization for Machine Learning
From the preface:<p>&gt; Put a bit more dramatically, [this monograph] will seek to show how problems that were once avoided, having been shown to be NP-hard to solve, now have solvers that operate in near-linear time, by carefully analyzing and exploiting additional task structure!<p>This is something I&#x27;ve noticed in my own research on inverse problems (signal recovery over the action of compact groups).  And it&#x27;s really quite mind-blowing.  What this means is that you can <i>randomly</i> generate problems, and these will be NP-hard to solve.  However, assuming the problem is <i>not</i> randomly generated (i.e., there is some regularity in the generative process that produced the data), there often appears to be some inherent structure that can be exploited to solve the problem quickly to its global optimum.<p>I feel like future research will focus on finding the line that divides the &quot;tractable&quot; problems from the &quot;intractable&quot; ones.