← Back to all news
arXiv Machine Learning By Xiaoyu Li, Junwei Yu, Jiaojiao Jiang, Junbin Gao, Andi Han

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

Read the original on arXiv Machine Learning →

arXiv:2606. 20082v1 Announce Type: cross Abstract: 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 $\Theta(\varepsilon^{-1}\log(n/d))$ iterations.

Summary generated by The Flow from the publisher's feed. The full article lives at arXiv Machine Learning.

Related stories

arXiv Machine Learning
Aug 12

High-Dimensional Calibration from Swap Regret

arXiv:2505. 21460v2 Announce Type: replace Abstract: We study online calibration of multi-dimensional forecasts over an arbitrary convex set $P \subset \mathbb{R}^d$ relative to an arbitrary norm $|\cdot|$.

By Maxwell Fishelson, Noah Golowich, Mehryar Mohri, Jon Schneider
More like this →
arXiv Machine Learning
Jul 14

Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

arXiv:2607. 10808v1 Announce Type: new Abstract: The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action $x_t \in \mathcal{X} \subset \mathbb{R}^d$, a convex loss function $f_t$ and a convex constraint function $g_t$ that drives the constraint $g_t(x)\le 0$ are revealed.

By Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze
benchmarks
More like this →