cs.LGNov 8, 2026

Resolvent Ellipsoid for Minty Set Inclusions

Authors: Ashkan Soleymani, Gabriele Farina, Patrick Jaillet

Organizations: Massachusetts Institute of Technology

Abstract

We study Minty set inclusion on a compact convex set X⊆Rd\mathcal{X} \subseteq \mathbb{R}^d with a set-valued operator A:X⇉RdA : \mathcal{X} \rightrightarrows \mathbb{R}^d. Under the Minty promise, the goal is to compute x∈Xx \in \mathcal{X} and u∈A(x)u \in A(x) such that sup⁡y∈X⟨u,x−y⟩≤ε\sup_{y \in \mathcal{X}} \langle u, x - y \rangle \le \varepsilon. Our approach is geometric and we work in the fixed-scale constrained-resolvent oracle model, where a query at anchor aa is assumed to return a resolvent point x+x^+ together with the Yosida vector gη(a)=(a−x+)/ηg_η(a) = (a - x^+)/η. We prove that each oracle response yields a sharp dichotomy: either the returned point provides an ε\varepsilon-SVI certificate, or the Yosida vector defines a strict separating normal for the Minty set. Thus, a single black-box resolvent query supplies either a certified candidate solution or a valid geometric cut. Combining this separation principle with the ellipsoid method, we obtain RESOLVENT-ELLIPSOID, an algorithm that computes an ε\varepsilon-SVI in O ⁣(poly⁡(d,log⁡(1/ε)))\mathcal{O}\!\left(\operatorname{poly}(d, \log(1/\varepsilon))\right) black-box oracle calls to the fixed-scale constrained resolvent. For monotone inclusions, our algorithm gives, to our knowledge, the first O ⁣(poly(d,log⁡(1/ε)))\mathcal{O}\!\left(\mathrm{poly}(d, \log(1/\varepsilon))\right) black-box guarantee in the fixed-scale resolvent model.

Figures & tables

Explore similar work

CardsList
  1. Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

    Jun 18, 2026Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2Query ComplexityOracle Complexity