arXiv:2605.12341v2 Announce Type: replace Abstract: Split conformal prediction constructs prediction sets with finite-sample coverage guarantees, but its calibration stage is limited to adjusting a single threshold parameter. Hence, the shape of the prediction sets must be fixed beforehand, typically by fitting it on a reserved part of the calibration data. We introduce multi-variable conformal prediction (MCP), a framework that jointly optimizes and calibrates multiple prediction-set parameters in a single optimization problem, eliminating calibration data split without sacrificing finite-sample coverage guarantees. Building on scenario theory, a principled framework for certifying data-driven decisions, we propose two tractable variants: RemMCP, grounded in constrained optimization with constraint removal, which generalizes split conformal prediction; and RelMCP, based on penalized optimization with constraint relaxation, which also supports non-convex problems, albeit at a higher computational cost. In experiments with ellipsoidal and multi-modal prediction sets, RemMCP and a heuristic, adaptive version of RelMCP consistently meet the target coverage, with lower variance across calibration runs than baselines with calibration data split, and in most settings with smaller or comparable prediction sets.