Research map / Learning theory and algorithms / Matrix and tensor methods
Semismooth Newton Algorithm for Efficient Projections onto $\ell_1, ∞$-norm Ball
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace sorting/Newton root-finding with semismooth Newton (LU-based Newton step, linear time per iteration) | l1,inf-ball Euclidean projection · Synthetic 10000x10000 matrix, C from 0.01 to 0.5 ||A||_{1,inf} | running time (s): about 3.3x-12.4x faster than SBM and about 2.4x-3.4x faster than NRFM in Table 1 | Helped |
| semismooth Newton with LU-based Newton step instead of Newton with per-iteration l1 projections (NRFM) | l1,inf-ball projection on School dataset · School, C/d in {0.01..1.0} | projection time (s): SNA faster than NRFM for all C except C/d=0.01 where they tie at 0.002 s | Mixed |
| increase data dimension d (synthetic, m=1000) with the proposed method | projection runtime scaling · Synthetic, d from 1e3 to 1e5 | CPU time (s) | No clear effect |
| apply proposed projection inside projected gradient for multitask Lasso with l1,inf constraint | MTLC on School · School real-world dataset | projection time (s): SNA outperforms SBM and NRFM in projection time across C | Helped |
Closest papers by meaning
- A Unified Semismooth Newton Approach to Multitask and Multivariate Square-Root Lasso Problems (NeurIPS 2026 · similarity 0.86)
- Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees (ICML 2025 · similarity 0.86)
- Inexact Newton-type Methods for Optimisation with Nonnegativity Constraints (ICML 2024 · similarity 0.85)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.84)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.84)
- Scalable First-order Method for Certifying Optimal k-Sparse GLMs (ICML 2025 · similarity 0.84)
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.