  When training an estimator such as a neural network for tasks like image
denoising, it is often preferred to train one estimator and apply it to all
noise levels. The de facto training protocol to achieve this goal is to train
the estimator with noisy samples whose noise levels are uniformly distributed
across the range of interest. However, why should we allocate the samples
uniformly? Can we have more training samples that are less noisy, and fewer
samples that are more noisy? What is the optimal distribution? How do we obtain
such a distribution? The goal of this paper is to address this training sample
distribution problem from a minimax risk optimization perspective. We derive a
dual ascent algorithm to determine the optimal sampling distribution of which
the convergence is guaranteed as long as the set of admissible estimators is
closed and convex. For estimators with non-convex admissible sets such as deep
neural networks, our dual formulation converges to a solution of the convex
relaxation. We discuss how the algorithm can be implemented in practice. We
evaluate the algorithm on linear estimators and deep networks.
