Machine learning often deals with optimization of a function which has many local minimas. Feedforward neural networks with hidden units is a good example. Whether these functions are discrete or continuous, there is no method which achieves a global minimum and stops. It is easy to prove that there is no general algorithm to find a global minimum of a continuous function even if it is one-dimensional and smooth (has infinitely many derivatives). In practice, all algorithms for learning neural networks stuck into a local minimum. It is easy to check this: create a random neural network, make a big set of its responses to random inputs, then try to learn another neural network with the same architecture to copy the responses. While the perfect solution exists, neither backpropagation not any other learning algorithm will be able to discover it, starting from a random set of weights.
Some learning methods, like simulated annealing or genetic algorithms, explore many local minimas. For continuous functions there are methods like gradient descent, which find the closest local minimum. They are much faster, thats why they are widely used in practice. But given enough time, the former group of methods outperforms the later in terms of training set error. But with reasonable time constraints, for real world problems, the latter group is usually better.
For some models, like logistic regression, there is one local minimum, the function is convex, the minimization converges to the minimum, but the models themselves are simplistic.
Thats the bitter truth.
Note also that proof of convergence and proof of convergence to the best solution are two different things. K-means algorithm is an example of this.
Finally, for some models we don't know how to learn at all. For example, if the output is an arbitrary computable function of inputs, we don't know good algorithms which, in reasonable time, find a Turing or equivalent machine implementing this function. For instance, if f(1)=2, f(2)=3, f(3)=5, f(4)=7, ..., f(10)=29 (ten first primes), we don't know any learning algorithm which would be able to predict, in reasonable time, that f(11)=31, unless it already knows the concept of prime numbers.