Read these and you are on the edge of what is currently happening.
That is, you have a learning problem with some fit criterion that is non-convex. Maybe you choose a different objective function, or different parameterization of the problem, so that it is convex. Then you can use a convex solver to find the guaranteed optimum of the "wrong" problem. Using convex relaxations has been a trend for perhaps 20 years - it avoids a whole bunch of nagging "what if my solution is just a local max" questions.
Or, you can use older techniques, like expectation-maximization, or in general, alternating minimization, that are adapted for these kinds of learning problems. Learning problems often have observed variables, and hidden variables, and if you knew the hidden variables, the optimization problem would be easier. These algorithms work on such problems. But, they don't find the global maximum. So you have found a possibly-good solution to the "right" problem.
Lately, some very interesting results have shown that, under some conditions, there are probabilistic guarantees that the second approach will find the global optimum [e.g., https://arxiv.org/abs/1408.2156]. Since the second approach often scales much better, people are naturally interested.