Research map / Learning theory and algorithms / Sample complexity
Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
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 an ℓ2,1 constraint instead of an ℓ1 constraint for general-alphabet logistic regression (ablation) | Pairwise graphical model structure learning · General discrete pairwise graphical models | sample complexity dependence on alphabet size: k^5 -> k^4 | Helped |
| Use ℓ2,1-constrained logistic regression rather than Sparsitron | General pairwise graphical model structure learning · 3-by-3 grid, k=4 and k=6 | samples required for graph recovery | Helped |
| Apply ℓ1-constrained logistic regression without an incoherence condition | Ising model structure learning · Diamond graph simulation with incoherence value above 1 | exact graph recovery | Helped |
| Optimize the constrained regressions using mirror descent | Proposed logistic-regression graph recovery algorithms · Ising and general pairwise graphical models | runtime while retaining statistical guarantees: \tilde{O}(n^2) | Helped |
Closest papers by meaning
- The Multiple Quantile Graphical Model (NeurIPS 2016 · similarity 0.87)
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.87)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.86)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.86)
- A Provably Accurate Randomized Sampling Algorithm for Logistic Regression (AAAI 2024 · similarity 0.86)
- Learning Local Neighborhoods of Non-Gaussian Graphical Models (AAAI 2025 · similarity 0.86)
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.