Research map / Adversarial robustness and security / Certified and empirical robustness
On Robustness to Adversarial Examples and Polynomial Optimization
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 |
|---|---|---|---|
| Use exact linear optimization for degree-1 PTFs | Linear-time exact adversarial optimization · Degree-1 PTF robust learning | robustness factor γ: γ=1 | Helped |
| Use an SDP relaxation with randomized rounding for degree-2 optimization | Degree-2 PTFs · Degree-2 PTF robust learning | robustness factor γ: O(\sqrt{\log n}) | Helped |
| Use the degree-2 SDP optimization algorithm to search for adversarial examples | Degree-2 PTFs · Degree-2 PTF adversarial-example search | attack radius factor: O(\sqrt{\log n}) | Helped |
| Require polynomial-time robust learning with robustness factor below the QP hardness threshold | Degree-2 PTFs · Degree-2 PTF robust learning | robustness factor γ: o(\sqrt{\eta_{approx}}) | Hurt |
| Require optimal robustness for degree-2 and higher PTFs | Degree-2 and higher PTFs · Optimal robust learning | robustness factor γ: γ=1 | Hurt |
| Require robust learning below the stated logarithmic hardness threshold | Degree-2 and higher PTFs · Robust learning | robustness factor γ: γ=o(\log^c n) | Hurt |
Closest papers by meaning
- Certified Adversarial Robustness with Additive Noise (NeurIPS 2019 · similarity 0.91)
- Adversarial Training and Provable Robustness: A Tale of Two Objectives (AAAI 2021 · similarity 0.91)
- Adversarial Robustness Guarantees for Random Deep Neural Networks (ICML 2021 · similarity 0.89)
- Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks (ICML 2020 · similarity 0.89)
- Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.89)
- Precise Accuracy / Robustness Tradeoffs in Regression: Case of General Norms (ICML 2024 · similarity 0.88)
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.