  We study the generation of prediction intervals in regression for uncertainty
quantification. This task can be formalized as an empirical constrained
optimization problem that minimizes the average interval width while
maintaining the coverage accuracy across data. We strengthen the existing
literature by studying two aspects of this empirical optimization. First is a
general learning theory to characterize the optimality-feasibility tradeoff
that encompasses Lipschitz continuity and VC-subgraph classes, which are
exemplified in regression trees and neural networks. Second is a calibration
machinery and the corresponding statistical theory to optimally select the
regularization parameter that manages this tradeoff, which bypasses the
overfitting issues in previous approaches in coverage attainment. We
empirically demonstrate the strengths of our interval generation and
calibration algorithms in terms of testing performances compared to existing
benchmarks.
