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

Sep 24, 2026

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

We characterize, up to logarithmic factors, the optimal higher-order oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximal monotone set-valued operator. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. This framework recovers the composite Fast Extragradient method in the first-order setting and yields natural higher-order extensions through Taylor approximations of the smooth operator at the extrapolated point. For every p≥2p\geq 2, assuming that the (p−1)(p-1)th derivative of the single-valued operator is LpL_p-Lipschitz continuous and the initial distance to a solution is at most RR, we combine AEP with a bisection line search to obtain a ppth-order method that attains a tangent residual of at most ε\varepsilon in O~((LpRp/ε)23p−1)\widetilde{O}((L_p R^{p}/\varepsilon)^{\frac{2}{3p-1}}) oracle calls. We complement this result with a worst-case lower bound of Ω((LpRp/ε)23p−1)Ω((L_p R^p/\varepsilon)^{\frac{2}{3p-1}}) for every deterministic algorithm in the ppth-order oracle model, without imposing any prescribed update structure. For the subclass of smooth nonexpansive fixed-point problems, we further establish a lower bound of Ω(min⁡{R/ε,(LpRp/ε)23p−1})Ω(\min\{R/\varepsilon, {(L_p R^{p}/\varepsilon)}^{\frac{2}{3p-1}}\}). By choosing between AEP and Halpern iteration, we match this lower bound up to logarithmic factors, thereby also settling the deterministic oracle complexity of smooth nonexpansive fixed-point problems.
Oct 4, 2026

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point yy and a certificate g∈G(y)g\in G(y) with (E∥F(y)+g∥2)1/2≤ε(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon using O(n+nLR/ε)\mathcal{O}(n+\sqrt{n}LR/\varepsilon) expected component evaluations and resolvent evaluations. It removes the additive nlog⁡nn\log n cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength L/nL/\sqrt{n}. Carrying an operator estimate between the remaining stages limits their total cost to O(n)\mathcal{O}(n). A matching Ω(n+nLR/ε)Ω(n+\sqrt{n}LR/\varepsilon) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<ε≤LR/20<\varepsilon\le LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
Jun 18, 2026

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

The John ellipsoid of a symmetric polytope P={x∈Rd:∥Ax∥∞≤1}P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}, A∈Rn×d\mathbf{A}\in\mathbb{R}^{n\times d}, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a (1+ε)(1+\varepsilon)-approximation in Θ(ε−1log⁡(n/d))Θ(\varepsilon^{-1}\log(n/d)) iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical ε−1\varepsilon^{-1} in the first alone. In the equivalent D-optimal-design form min⁡p∈Δn−log⁡det⁡(∑ipiaiai⊤)\min_{\mathbf{p}\inΔ_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top), the leverage-score oracle is exactly the first-order oracle and the (1+ε)(1+\varepsilon)-John guarantee the Frank-Wolfe gap g(p)≤εdg(\mathbf{p})\le\varepsilon d; through this dictionary the costs come apart. The ε−1\varepsilon^{-1} is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly Θ(1/T)Θ(1/T), however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in C(A)+O(κlog⁡(1/ε))C(\mathbf{A})+O(\sqrtκ\log(1/\varepsilon)) queries after an ε\varepsilon-independent setup C(A)C(\mathbf{A}), and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon)) steps, for a total of C(A)+O(d2log⁡log⁡(1/ε))C(\mathbf{A})+O(d^2\log\log(1/\varepsilon)) queries. The accuracy dependence is thus doubly logarithmic after an ε\varepsilon-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.