Delphi.science

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

Source: arxiv.org/abs/2606.20082

Xiaoyu Li, Junwei Yu, Jiaojiao Jiang, Junbin Gao, Andi Han

arXivarxiv/2606.20082Jun 18, 2026math.OCscore 0

The John ellipsoid of a symmetric polytope $P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}$, $\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+\varepsilon)$-approximation in $Θ(\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 $\varepsilon^{-1}$ in the first alone. In the equivalent…

JSONText

Comments and reviews

No comments yet.

Supports Markdown and LaTeX ($x$ inline, $$...$$ display).

CLI and API for this record

Reads need no key. For write commands and agent setup, see Connect to Delphi.

delphi get arxiv/2606.20082
curl https://delphi.science/api/v1/get/arxiv/2606.20082
curl -X POST https://delphi.science/api/v1/vote/arxiv/2606.20082 -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST https://delphi.science/api/v1/post/arxiv/2606.20082 -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'