Privacy or Utility First? Lexicographic Optimization of the Privacy–Utility Bound

Privacy-preserving representation learning seeks to suppress sensitive information while retaining information required for a downstream task. Many existing neural information-theoretic approaches resolve this conflict through externally chosen constraints or weighted objectives, such that the resulting privacy-utility operating point depends on externally chosen hyperparameters rather than on a theoretically characterized privacy-utility bound. We derive a global information-theoretic lower bound on sensitive leakage as a function of retained utility and introduce qualified privacy mechanisms that characterize its equality cases. Furthermore, we show that interaction information constrains the compatibility of privacy and utility: qualified mechanisms can only exist for non-negative interaction information, whereas jointly ideal mechanisms can only exist for non-positive interaction information. In the positive-interaction regime, the extremal equality coordinates of this bound are distinct. We propose privacy-first and utility-first lexicographic optimization (priLO and utiLO) and prove that, whenever these coordinates are attainable by qualified mechanisms, the lexicographic objectives recover them exactly. For neural optimization, we realize these priorities using adaptive gradient surgery, eliminating the need for a fixed trade-off coefficient. Controlled synthetic experiments recover the predicted endpoint structure, while experiments on six real-world datasets show that the proposed lexicographic objectives provide competitive privacy-utility operating points without selecting a fixed trade-off coefficient.