{"ID":2850898,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22088","arxiv_id":"2510.22088","title":"Quasi-Self-Concordant Optimization with Lewis Weights","abstract":"In this paper, we study the problem $\\min_{x\\in \\mathbb{R}^{d},Nx=v}\\sum_{i=1}^{n}f((Ax-b)_{i})$ for a quasi-self-concordant function $f:\\mathbb{R}\\to\\mathbb{R}$, where $A,N$ are $n\\times d$ and $m\\times d$ matrices, $b,v$ are vectors of length $n$ and $m$ with $n\\ge d.$ We show an algorithm based on a trust-region method with an oracle that can be implemented using $\\widetilde{O}(d^{1/3})$ linear system solves, improving the $\\widetilde{O}(n^{1/3})$ oracle by {[}Adil-Bullins-Sachdeva, NeurIPS 2021{]}. Our implementation of the oracle relies on solving the overdetermined $\\ell_{\\infty}$-regression problem $\\min_{x\\in\\mathbb{R}^{d},Nx=v}\\|Ax-b\\|_{\\infty}$. We provide an algorithm that finds a $(1+ε)$-approximate solution to this problem using $O((d^{1/3}/ε+1/ε^{2})\\log(n/ε))$ linear system solves. This algorithm leverages $\\ell_{\\infty}$ Lewis weight overestimates and achieves this iteration complexity via a simple lightweight IRLS approach, inspired by the work of {[}Ene-Vladu, ICML 2019{]}. Experimentally, we demonstrate that our algorithm significantly improves the runtime of the standard CVX solver.","short_abstract":"In this paper, we study the problem $\\min_{x\\in \\mathbb{R}^{d},Nx=v}\\sum_{i=1}^{n}f((Ax-b)_{i})$ for a quasi-self-concordant function $f:\\mathbb{R}\\to\\mathbb{R}$, where $A,N$ are $n\\times d$ and $m\\times d$ matrices, $b,v$ are vectors of length $n$ and $m$ with $n\\ge d.$ We show an algorithm based on a trust-region met...","url_abs":"https://arxiv.org/abs/2510.22088","url_pdf":"https://arxiv.org/pdf/2510.22088v1","authors":"[\"Alina Ene\",\"Ta Duy Nguyen\",\"Adrian Vladu\"]","published":"2025-10-24T23:57:48Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\"]","methods":"[]","has_code":false}