Kernels are efficient in representing nonlocal dependence and are widely used to design operators between function spaces or high-dimensional data. Thus, learning kernels in operators from data is an inverse problem of general interest. Due to the nonlocal dependence, the inverse problem is often severely ill-posed with a data-dependent operator that is nearly singular. Therefore, regularization is necessary. However, little information is available to select a proper regularization norm in many applications. We overcome the challenge by introducing a new regularization norm based on an RKHS that is determined by the nonlocal operator and data. It leads to convergent estimators that are robust to noise, outperforming the widely used L2 or l2 regularizers. We will discuss both direct and iterative methods for implementation.