Research map / Learning theory and algorithms / Sample complexity
Quasi-Self-Concordant Optimization with $\ell_{\infty}$ Lewis Weights
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a trust-region method for quasi-self-concordant minimization whose oracle uses an IRLS-based l_infinity regression solver with Lewis weight overestimates, cutting linear-system solves per iteration from Õ(n^{1/3}) to Õ(d^{1/3}).
Problem
Minimizing sum of quasi-self-concordant functions of linear residuals, min over Nx=v of sum f((Ax-b)_i), in the overdetermined regime n>>d, where existing methods' iteration counts scale with n.
Approach
Combines an l_infinity-box trust-region Newton method with a simple IRLS solver for l_infinity regression that initializes dual weights from l_infinity Lewis weight overestimates, so each oracle call needs only Õ(d^{1/3}) linear system solves instead of Õ(n^{1/3}).
Key results
- On large instances (e.g., 100000x100 random matrices), the proposed method runs in 1.3 s vs 0.5 s for Newton's method, with objective gaps around 1e-9 or smaller.
- Experiments on l_p+l_2 regression with p=8 show the method is significantly faster than CVX on small instances while matching Newton's method runtime there.
- Theoretical oracle uses O(d^{1/3} log n) linear system solves per subproblem versus Õ(n^{1/3}) in prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ours instead of Newton | QSC optimization · Random Matrices (100000×100) | runtime (s): 0.5 -> 1.3 | Hurt |
| Use Ours instead of Newton | QSC optimization · Song Year Prediction (463811×90) | runtime (s): 2.7 -> 7.5 | Hurt |
| Use Ours instead of Newton | QSC optimization · Consumption of Power (1844352×11) | runtime (s): 3.0 -> 6.5 | Hurt |
| Use Ours instead of Newton | QSC optimization · Protein Property (41157×9) | runtime (s): 0.2 -> 0.3 | Hurt |
Surprising findings
- Newton's method, which has weaker theoretical guarantees, is faster in practice than the proposed algorithm on large instances (0.5s vs 1.3s on random matrices).
Limitations
- Implementation gap versus Newton's method on large instances (slower by ~2-3x).
- Residual solver only achieves a constant-factor approximation rather than (1+eps) for the QSC subproblem.
- Iteration bounds depend on the l_infinity diameter R and QSC parameter C.
Experimental setup
Datasets: Song Year Prediction (UCI) Consumption of Power (UCI) Protein Property (UCI) random matrices
Benchmarks: random matrices 100000x100 Song Year Prediction Consumption of Power Protein Property
Metrics: runtime (s) absolute objective gap
Baselines: Adil-Bullins-Sachdeva (NeurIPS 2021) CVX Newton's method with line search
Builds on: Adil-Bullins-Sachdeva quasi-self-concordant optimization Ene-Vladu IRLS for l_p regression Lewis weight overestimates (Cohen-Peng) box-constrained Newton method
Closest papers by meaning
- Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization (NeurIPS 2021 · similarity 0.89)
- Improved Convergence for $\ell_1$ and $\ell_∞$ Regression via Iteratively Reweighted Least Squares (ICML 2019 · similarity 0.86)
- Self-Concordant Analysis of Frank-Wolfe Algorithms (ICML 2020 · similarity 0.85)
- Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation (ICLR 2025 · similarity 0.84)
- Simple Randomized Rounding for Max-Min Eigenvalue Augmentation (ICML 2025 · similarity 0.84)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.