{"id":"arxiv/2606.20082","url":"https://arxiv.org/abs/2606.20082","tags":["math.OC","cs.DS","cs.LG"],"score":0,"title":"Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model","domain":"math.OC","source":"arxiv","authors":["Xiaoyu Li","Junwei Yu","Jiaojiao Jiang","Junbin Gao","Andi Han"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-18","reactions":{}}