Black-box optimization considers optimization of problems which are only known via access to an objective function measuring the quality a given search point. Typical generic solvers to such problems include local search, but also many nature-inspired search heuristics such as Simulated Annealing and Evolutionary Algorithms. There is a growing community of theoretical computer scientists working on explaining the principles which make these search heuristics successful. In particular, recent progress shows that many of the considered approaches perform very well for optimization under uncertainty. In this talk I will discuss uncertainty stemming from noisy objective functions, where certain algorithms are particularly robust to noise, while others fail. I will show what distinguishes the successful algorithms from the less successful and present the used techniques (which deal with the analysis of stochastic processes) in a manner accessible to a wider audience