ParetoTrace: Minimax Recovery of MGDA Directions from Partial Gradient Geometry

Multiple gradient descent (MGDA) finds a direction that descends on every objective at once. It needs the Gram matrix of task gradients, and building that matrix exactly is the bottleneck as objectives multiply, so a prevailing response is to substitute cheaper geometry. We ask what the observed geometry determines, and answer exactly. Observing Gram-vector products leaves a family of consistent Grams, and we characterize which quantities are identical across it. The MGDA objective is not: it can only be narrowed to a computable range. The worst-task descent margin is, at any weighting the observations already span, and reading it costs no action beyond those already taken. Two methods follow. ParetoTrace-Direct contracts every parameter block, leaving one consistent Gram and returning the exact direction with no queries. It is $14.9\times$ faster than serial task gradients at $32$ objectives, where four of six external implementations exhaust an NVIDIA A100 40 GB card. ParetoTrace-Stream buys products one at a time and stops once the range certifies. It is $1.97\times$ faster than contraction where materializing the Gram exhausts the card, and has lower worst-task loss and higher held-out accuracy than the strongest cheap baseline on all three seeds. That baseline lets one task run away to a loss of $41.0$ while ours stays under $8.1$. In replay on a training run it drives, the sharp endpoint certifies $37$ of $100$ updates against the cheaper rule's $27$, never later, while a numerical guard limits the live run to $19$, and a line search on its exact responses keeps every task loss non-increasing on its minibatch at $60$ of $60$ updates. Used as an instrument, the characterization shows that MGDA-UB sener2018multi, the standard cheap substitute, increases at least one task loss at forty CelebA objectives on every trunk and batch size we tested.