Research map / Learning theory and algorithms / Sample complexity
A Theory of the Risk for Optimization with Relaxation and its Application to Support Vector Machines
Marco C. Campi, Simone Garatti
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 the new two-sided complexity-based bound instead of the prior bound | risk certificate · N=1000, beta=1e-5, c=40, r=100 | upper bound on risk: 0.419 -> 0.2 | Improved |
| use the new bound instead of the prior bound | risk certificate · N=1000, beta=1e-5, c=320, r=250 | upper bound on risk: 1 -> 0.65 | Improved |
| use the new bound instead of the prior bound | risk certificate · N=2000, beta=1e-5, c=40, r=100 | upper bound on risk: 0.288 -> 0.10 | Improved |
| use the new bound instead of the prior bound | risk certificate · N=2000, beta=1e-5, c=10, r=0 | upper bound on risk: 0.04 -> 0.018 | Improved |
| increase sample size from N=1000 to N=2000 | new risk bound · beta=1e-5, c=40, r=100 | upper bound on risk: 0.2 -> 0.10 | Improved |
| decrease regularization penalty rho from 1 toward (3/5)^14 | SVR · noisy sinc, sigma=1 | complexity s* and risk | Hurt |
| choose Gaussian kernel width sigma=1 over 10^-2, 10^-1, 10, 1e1 range | SVR · noisy sinc cost vs s*/N | cost at given complexity | Improved |
| use smaller sigma (finer basis functions) | SVR · noisy sinc | cost and risk | Mixed |
| select rho=(3/5)^9 via cost-risk plot | SVR · noisy sinc, N=2000 | risk interval: [0.032, 0.08] | Improved |
| validate Theorem 1 by Monte Carlo over 200 resamples | risk bounds · noisy sinc, N=2000, beta=1e-4 | containment of true risk: 200 of 200 inside | Improved |
Closest papers by meaning
- Solving L1-regularized SVMs and Related Linear Programs: Revisiting the Effectiveness of Column and Constraint Generation (JMLR 2022 · similarity 0.88)
- On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks (NeurIPS 2017 · similarity 0.86)
- On the Efficiency of ERM in Feature Learning (NeurIPS 2024 · similarity 0.86)
- Faster Algorithms for Structured Linear and Kernel Support Vector Machines (ICLR 2025 · similarity 0.85)
- A Survey of Learning Criteria Going beyond the Usual Risk (Abstract Reprint) (AAAI 2024 · similarity 0.85)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 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.
