pth-Order Oracle Complexity for Monotone Variational Inequalities
Monteiro and Svaiter gave a second-order method for smooth monotone variational inequalities converging at O(T^-1.5), later improved to O(T^-1.75) for the convex-concave minimax subset. Whether the conjectured complexity for general monotone variational inequalities could be improved was open. A large-step inexact Halpern iteration achieves O(T^-2), and O(T^-p) at pth order.
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Variational inequalities
- Posed by
- Renato D. C. Monteiro, Benar F. Svaiter
- Year posed
- 2012
- Years open
- 14y
- Solved
- 2026-08-09
- Model
- Claude Opus 4.6 and GPT-5.6 Sol
- Vendor
- Anthropic, OpenAI
- Collaborators
- Lesi Chen, Xinliang Zhang, Hengyu Wang, Chengchang Liu, Yongchao Chen, Jingzhao Zhang
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 12 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Improves every prior result for p >= 2 and matches the classical extragradient method at p = 1.
What the AI did
The paper records the sequence: an O(T^-(p-1)) rate was obtained with Claude Opus 4.6, and on verifying it the authors conjectured a better O(T^-p) result, for which Xinliang Zhang then found a proof with GPT-5.6 Sol. The results were subsequently verified by the human authors, who also link the model's initial proof as a public ChatGPT transcript.
Verification
A preprint days old. The initial AI proof is published as a shareable transcript, which is unusual and welcome, but it is a record of provenance rather than a check by anyone independent.
Source
- PaperarXiv