  Variational regularization techniques are dominant in the field of
mathematical imaging. A drawback of these techniques is that they are dependent
on a number of parameters which have to be set by the user. A by now common
strategy to resolve this issue is to learn these parameters from data. While
mathematically appealing this strategy leads to a nested optimization problem
(known as bilevel optimization) which is computationally very difficult to
handle. It is common when solving the upper-level problem to assume access to
exact solutions of the lower-level problem, which is practically infeasible. In
this work we propose to solve these problems using inexact derivative-free
optimization algorithms which never require exact lower-level problem
solutions, but instead assume access to approximate solutions with controllable
accuracy, which is achievable in practice. We prove global convergence and a
worstcase complexity bound for our approach. We test our proposed framework on
ROFdenoising and learning MRI sampling patterns. Dynamically adjusting the
lower-level accuracy yields learned parameters with similar reconstruction
quality as highaccuracy evaluations but with dramatic reductions in
computational work (up to 100 times faster in some cases).
