{"ID":2842414,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10576","arxiv_id":"2511.10576","title":"Tight Robustness Certification Through the Convex Hull of $\\ell_0$ Attacks","abstract":"Few-pixel attacks mislead a classifier by modifying a few pixels of an image. Their perturbation space is an $\\ell_0$-ball, which is not convex, unlike $\\ell_p$-balls for $p\\geq1$. However, existing local robustness verifiers typically scale by relying on linear bound propagation, which captures convex perturbation spaces. We show that the convex hull of an $\\ell_0$-ball is the intersection of its bounding box and an asymmetrically scaled $\\ell_1$-like polytope. The volumes of the convex hull and this polytope are nearly equal as the input dimension increases. We then show a linear bound propagation that precisely computes bounds over the convex hull and is significantly tighter than bound propagations over the bounding box or our $\\ell_1$-like polytope. This bound propagation scales the state-of-the-art $\\ell_0$ verifier on its most challenging robustness benchmarks by 1.24x-7.07x, with a geometric mean of 3.16.","short_abstract":"Few-pixel attacks mislead a classifier by modifying a few pixels of an image. Their perturbation space is an $\\ell_0$-ball, which is not convex, unlike $\\ell_p$-balls for $p\\geq1$. However, existing local robustness verifiers typically scale by relying on linear bound propagation, which captures convex perturbation spa...","url_abs":"https://arxiv.org/abs/2511.10576","url_pdf":"https://arxiv.org/pdf/2511.10576v2","authors":"[\"Yuval Shapira\",\"Dana Drachsler-Cohen\"]","published":"2025-11-13T18:15:37Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}