{
  "abstract": "We study the query complexity of sampling from smooth distributions on $\\mathbb R^d$ using first-order oracles. For $d$-dimensional strongly log-concave targets with condition number $κ=2$, we prove that any randomized sampler requires $\\exp({Ω(\\log^{1/3} d)})$ queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with $L$-smooth potentials satisfying an $α$-log-Sobolev inequality with $κ= L/α$, we prove an $Ω(κ)$ query lower bound for $d\\gtrsim\\log^2κ$. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2611.05813",
  "author_total": 2,
  "authors": [
    {
      "name": "Huanjian Zhou"
    },
    {
      "name": "Taiji Suzuki"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/bambcpz7z5zef.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2611.05813",
  "fulltext_url": null,
  "id": "bambcpz7z5zef",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2611.05813",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.ST"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "arxiv",
      "stat.TH"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2611.05813",
  "pmcid": null,
  "pmid": null,
  "published": "2026-11-04",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/bambcpz7z5zef.ris",
  "sources": [
    {
      "first_seen": "2026-11-05T15:21:00Z",
      "native_id": "2611.05813",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2611.05813"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.ST",
      "subfield": "statistics"
    }
  ],
  "title": "Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities",
  "title_text": "Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities",
  "type": "preprint",
  "updated_at": "2026-11-09T00:20:32Z",
  "url": "https://research.draconitic.com/paper/bambcpz7z5zef",
  "venue": "arXiv",
  "versions": []
}