Search: “computational-hardness”

Smart search ranks by meaning as well as keywords (one row per story, last 45 days).

Benign Loss Landscapes Can Coexist with Worst-Case Hardness

Theory paper shows tree tensor networks contain worst-case hard targets yet benign loss landscapes, with difficulty arising from degenerate saddles.

The paper studies tree tensor networks (TTNs), which generalize deep linear networks and Tucker decompositions and embed arbitrary read-once Boolean formulas. It proves that every local minimum that is minimum-norm is global for every realizable target, so bad local minima do not distinguish typical from worst-case problems. Instead, learning difficulty arises from high-order degenerate saddle points caused by rank-deficiency, illustrated via a parity function case study, linking landscape geometry to computational hardness.

arXiv cs.AI / cs.LG / cs.CL·Sep 11, 16:57 UTC · 5d agoAI research

16

Implementing a White-Box Undetectable Backdoor for Random Fourier Features

Researchers implement Goldwasser's CLWE-based undetectable backdoor for Random Fourier Features models in numpy/scipy, confirming practical realizability with no detectable differences from clean models.

The paper provides an end-to-end implementation of the Goldwasser et al. white-box undetectable backdoor for models trained with the Random Fourier Features algorithm, using only numpy and scipy. It derives two samplers for the core GP_d(b_k) distribution: a rejection-sampling proxy and an exact closed-form sampler verified against its analytic form. Statistical indistinguishability tests covering weight-space and functional black-box comparisons found no detectable difference between backdoored and clean models across sparsity ratios. The underlying lattice hardness reduction was not reproduced, and the work demonstrates the threat is realizable with commodity scientific-computing tools rather than specialized cryptographic infrastructure.

arXiv cs.CR·Sep 14, 22:18 UTC · 2d agoResearch

50

Graph Machine: Towards Better Pretraining via Edges

Researchers propose Graph Machine, an O(n)-state sparse architecture that replaces 75% of Qwen3-0.6B dense layers with only slight loss change.

The paper introduces the Graph Machine (GM), an architecture that maintains an O(n)-sized state accessed through sparse, dynamic routing via pointer-like edges updated differentiably by a referral mechanism resembling pointer chasing. The authors replaced 75% of dense Transformer layers in Qwen3-0.6B with GM sparse layers and pretrained from scratch on 15.7B tokens. Retrieving 2 of 4,096 tokens per KV head in each sparse layer degrades loss only slightly, while retrieving 4 marginally improves loss over the dense baseline.

Hugging Face daily papers·Sep 1, 20:00 UTC · 15d agoAI research

30

A Note on Sphere Packing Bounds for Tuple Lattice Sieving

Proves upper bounds on k-irreducible unit vector set rates, yielding nearly tight asymptotics relevant to tuple lattice sieving in cryptanalysis.

The paper bounds the maximal asymptotic rate of k-irreducible sets of unit vectors via spherical code packing bounds. It shows R_k is sandwiched between (1/2 - o(1)) log2(k)/k and (1 + o(1)) log2(k)/k for large k. These almost-tight bounds inform subexponential complexity analyses of tuple lattice sieving, which underpins security estimates for lattice-based cryptography.

arXiv cs.CR·Sep 8, 03:20 UTC · 9d agoResearch

15

Has MIMO decoding been proved hard from lattice problems?

Researchers show the published lattice-hardness proof for MIMO decoding fails, as Regev's LWE reduction structure does not carry over to non-modular MIMO.

The paper re-examines Dean and Goldsmith's proposed polynomial-time reduction from lattice problems to MIMO decoding, which adapted Regev's reduction for learning with errors (LWE). Prior works had presented attacks and counterexamples against the construction, leaving the reduction's precise validity unclear. The authors identify which structural features of the LWE reduction fail to transfer to the non-modular MIMO setting, showing the published proof does not establish the claimed hardness of MIMO decoding. They distinguish flaws in the hardness proof from direct attacks on specific parameter choices and do not rule out physical layer security for MIMO systems in general.

arXiv cs.CR·Sep 4, 11:23 UTC · 12d agoResearch

25

MIT creates method to force AI to comply with safety rules

MIT researchers published HardFlow, a method enforcing hard safety constraints on flow-matching generative models' final outputs without retraining.

MIT researchers led by Zeyang Li and Navid Azizan developed HardFlow, a trajectory-optimization method that enforces strict, non-negotiable constraints on flow-matching generative models by checking rule satisfaction only at the final generation step. Published in IEEE TPAMI, it outperformed six rival projection and guidance methods on four simulated benchmarks including D3IL robotic manipulation, Maze2D, physical process control, and image editing. All results are simulation-only, with no independent reproduction yet reported.

Hacker News · security·Sep 14, 16:18 UTC · 2d agoAI researchHN 24↑ · 25 comments

25

Sound Debloating of Redundant Checks in Zero-Knowledge Machine-Learning Circuits

Automated framework soundly removes up to 48.7% of redundant constraints in ezkl and zkml ZK-ML circuits, cutting prover time by up to 72.8%.

The framework uses whole-circuit abstract interpretation and a provenance graph to verify that each removed redundant check (range proofs, sign lookups, bit decompositions) remains entailed by the rest of the circuit, provably preserving soundness. It was evaluated on MLP, CNN, RNN, and transformer circuits generated by ezkl and zkml, with up to 25.3 million constraints. It removes up to 48.7% of constraints and reduces prover time by up to 72.8% without weakening security. Under-constrained circuits in deployed ZK systems have previously enabled attackers to forge transactions and bypass verification.

arXiv cs.CR·Sep 9, 13:27 UTC · 7d agoResearch1

35

MAxBench: A Multinomial Concept Recovery Benchmark

MAxBench evaluates multinomial concept recovery methods, finding affine subspaces steer most reliably but none consistently beats prompting.

MAxBench is a geometry-agnostic evaluation framework for multinomial concept representations in language models, based on sampling from recovered concept representations. It compares 10 localization methods covering 5 geometry types across 6 concepts and 4 models. Findings show affine subspaces steer more reliably than rank-one or linear subspaces due to better non-zero offsets, manifold steering is competitive where applicable, and no method consistently outperforms prompting.

arXiv cs.AI / cs.LG / cs.CL·Sep 11, 17:08 UTC · 5d agoAI research

18

Proximity Gaps for Gabidulin Codes and Applications

Researchers prove proximity-gap bounds for rank-metric and Gabidulin codes, enabling the first polynomial commitment scheme framework based on rank-metric error-correcting codes.

The paper proves every linear rank-metric code admits a proximity gap for deltas up to (d-1)/(3n) with error at most q^(e+1)/q^m, and improves the gap to (d-1)/(2n) for Gabidulin codes with error at most 10q^(n-1)/q^m, matching bounds for Reed-Solomon codes. A constructed infinite family of constant-rate Gabidulin codes shows the (d-1)/(2n) bound is tight, and a counterexample establishes a lower bound on the error at the d/(3n) gap. Applications include an IOPP for interleaved Gabidulin codes adapted from the Ligero IOPP and a q-linearized polynomial commitment scheme adapted from Ligero-based PCS, reportedly the first PCS framework based on rank-metric codes.

arXiv cs.CR·Sep 9, 07:45 UTC · 7d agoResearch

20

Cross-Model Agreement as a Deployment-Time Reliability Signal for Automatic Polyp Segmentation

Referee-Based Quality Estimation flags unreliable polyp segmentations at inference without ground truth, reaching ROC-AUC 0.960 with SegFormer-B0 referees.

RBQE measures agreement between a primary segmentation model and an independently trained referee on a 1,223-image external benchmark drawn from four public datasets. A cross-architecture SegFormer-B0 referee achieves the strongest signal (ROC-AUC 0.960), beating a Test-Time Augmentation baseline by 0.055 ROC-AUC under an identical protocol. Excluding trivially separable empty-mask cases, ROC-AUC falls to 0.876 (SegFormer-B0) and 0.783 (same-architecture control), but RBQE's margin over baselines widens. Progressive rejection of low-agreement predictions increases mean Dice of retained outputs, supporting selective prediction at the cost of one extra forward pass.

arXiv cs.AI / cs.LG / cs.CL·Sep 9, 17:32 UTC · 7d agoAI research

30

Evaluating Context Segmentation in Locally Deployable SLMs for Cybersecurity CTF Tasks

Context segmentation framework boosts memory-constrained gemma-4 agents on picoCTF, solving 18.52% of tasks standard execution fails, highlighting local SLM offensive risk.

The paper introduces context segmentation, a two-level agentic framework that divides long-horizon CTF exploitation tasks into contextually isolated sub-problems to counter context bloat and cognitive degradation from accumulated tool-call outputs. It evaluates memory-constrained gemma-4 models on the picoCTF dataset; the E4B model achieves competitive rewards with superior token efficiency compared to brute-force retries. It solves 18.52% of tasks that standard agentic execution fails to complete. The work frames locally deployed open-weight SLMs as an escalating risk since they bypass proprietary API guardrails; code is released on GitHub.

arXiv cs.CR·Sep 11, 13:34 UTC · 5d agoAI safety & security1

32

Witness Encryption via Prime-Order Generic Groups

Unconditional witness encryption construction for NP in the generic-group model, plus first superconstant NP-hardness result for homogeneous MinRank.

A cryptography paper unconditionally constructs witness encryption for NP in the classical generic-group model using an ordinary cyclic group of prime order. For SAT instances of size n, encryption and decryption run in poly(n) time with correctness error 2^-n^Ω(1), while generic adversaries making n^Θ(log n) queries achieve at most n^-Θ(log n) distinguishing advantage. It also proves the first superconstant-factor NP-hardness of approximation for homogeneous MinRank under randomized reductions.

arXiv cs.CR·Sep 16, 07:54 UTC · 21h agoResearch

20

AI models' written reasoning steps correspond to distinct internal patterns, a new study finds

KAIST and Naver AI Lab researchers show LLM reasoning steps like extraction and computation map to distinct activation patterns, strongest in middle layers.

Researchers at KAIST and Naver AI Lab defined eight recurring reasoning operations, including extraction, decomposition, formula recall, deduction, and computation, and showed they correspond to separable activation patterns in Qwen2.5-7B, Qwen3-8B, and Gemma4-31B on math tasks, with GPT-5 labeling solution segments. The separation peaks in middle layers, holds even when a computation step produces a wrong answer, and goes beyond surface-level token choice. Findings replicated on Llama-3-8B, and classifiers trained on Qwen3-8B transferred to GPQA-Diamond and MATH-500. The authors note that using internal states for error detection or mid-generation steering remains future work.

The Decoder·Sep 12, 13:39 UTC · 4d agoAI research2

42

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Procedural Graph framework stores procedural knowledge as triplets and self-evolves via LLM refinement, beating memory-based baselines across datasets, tasks, and LLMs.

The Procedural Graph organizes procedural knowledge into (procedure, relation, procedure) triplets; at each decision step the framework localizes the agent's active node and a guidance model translates the surrounding subgraph into step-level guidance that biases the solver's next action. An LLM refiner contrasts failed with successful trajectories and edits the graph's topology and attributes, retaining rejected edits to discourage repetition. Starting from a minimal skeleton, the loop builds graphs that match or surpass hand-designed ones and can repair flawed expert priors, delivering consistent gains over memory-based baselines across multiple datasets, task types, and LLMs.

Hugging Face daily papers·Sep 7, 20:00 UTC · 9d agoAI research1

36

Normal Alignment: Improved Cryptanalytic Sign Recovery on Hard-Label Networks

Researchers propose Normal Alignment, improving cryptanalytic sign recovery for hard-label neural networks and enabling polynomial-time full model extraction.

The paper improves on Carlini et al.'s EUROCRYPT 2025 cryptanalytic extraction of hard-label (S1) DNNs, whose Future Toggle sign-recovery method offered only marginal advantage over random guessing and triggered exponential-time enumeration on errors. Normal Alignment infers neuron signs via expected length differences between projected normals of adjacent decision facets at dual points, delivering higher voting accuracy and low-confidence errors. Combined with the SOE extension, it achieves exact polynomial-time full sign recovery: CIFAR-10 (192-64x8-10) and MNIST (64-96x3-32-10) models are fully recovered where the prior method required 2^52 or 2^82 sign guesses.

arXiv cs.CR·Sep 16, 14:42 UTC · 14h agoResearch

30

Scaling Verification of Cryptographic Software with Aeneas, Rust, and Lean

Microsoft SymCrypt implementations of SHA-3 and ML-KEM verified in Lean via Aeneas-extracted Rust models, with AI agents writing proofs.

The paper develops a methodology for verifying production Rust cryptographic code by using Aeneas to extract pure models into Lean, avoiding low-level pointer and aliasing reasoning. Applied to Microsoft's SymCrypt, it verifies SHA-3 and ML-KEM implementations ported from C to Rust and extends SymCrypt with FrodoKEM, ML-DSA, and HPKE. A 237 KLOC Lean development establishes safety, panic-freedom, and functional correctness of 16.7 KLOC of Rust supporting post-quantum cipher suites on x86-64 and ARM. AI agents autonomously write formal proofs verified by the Lean kernel, and evaluation shows verified Rust meets SymCrypt's performance and portability requirements.

arXiv cs.CR·Sep 14, 14:32 UTC · 2d agoResearch1

42

Optimizing Credential Blast Radius Through Trust Boundaries and Delegation Under Post-Quantum Authentication Costs

Academic paper models credential blast radius optimization across trust domains under post-quantum latency costs, cutting expected impact by up to 36%.

The paper formulates the joint selection of trust domains and credential-derivation structures under policy and latency constraints as an NP-hard optimization problem, showing the scalarized two-domain direct-issuance case reduces to a weighted minimum cut. In 195 of 230 exhaustive synthetic comparisons, joint optimization produced lower credential blast radius than choosing boundaries first, especially under chained delegation. A trace-derived replay using measured post-quantum authentication costs found the best design reduced expected impact by up to 36% relative to a single domain within the latency budget.

arXiv cs.CR·Sep 3, 23:42 UTC · 13d agoResearch

26

Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

Researchers certify a dependency-preserving upper bound of 2^-164.81 on honest decapsulation failure for ML-KEM-768 within an explicit ROM/CBD abstraction.

The paper models ML-KEM-768's domain-separated public-matrix streams as independent uniform ring elements and secret polynomials as CBD2 primitives, explicitly not claiming an information-theoretic result about the fixed SHAKE instantiation in FIPS 203. It preserves dependencies from the public matrix and both ciphertext-compression terms, using a graph-coupled reference, a proper-ideal bivariate Fourier transport, and a 256-coordinate union bound. The certified bound is Pr[K' != K] <= 2^-164.81, with the exponent 164.8107162... exceeding the 164.81 threshold by only about 0.0007162 bits; 164.82 is not certified. The bound applies to messages fixed independently of the randomness under honest encryption and decapsulation, and is not an exact DFR, a fixed-SHAKE equivalence, or a new IND-CCA reduction.

arXiv cs.CR·Sep 9, 10:13 UTC · 7d agoResearch1

30

Efficient Branch-and-Bound Testing and Verification of zkVMs

ZEBRA verifies zkVM constraint systems via branch-and-bound cardinality counting, finding 11 zero-day bugs across five real-world zkVMs and running 51.5x faster than SMT verification.

ZEBRA reduces zkVM correctness to a solution-set cardinality problem requiring that each constraint system admit exactly one valid execution trace, eliminating redundancies like null-row padding and non-deterministic permutations before counting. It lifts analysis from finite-field witnesses to an integer interval lattice, exploiting that constraints across 5 real-world zkVMs use only 14.0% of theoretical connectivity capacity on average, enabling tight interval propagation. A parallel branch-and-bound search produces concrete counterexamples or certifies absence of violations within a bounded region. ZEBRA discovers 11 zero-day bugs (6 independently confirmed, 3 fixed), is 51.5x faster than SMT-based verification, and verifies 16.5 percentage points more instances.

arXiv cs.CR·Sep 14, 04:35 UTC · 3d agoResearch

45

harshatheg/Qwen-2.5-1B-RLCD — new model trending #30 on Hugging Facenew

A community MLX inference engine evaluates constrained JSON schema fields in parallel on Apple Silicon, reporting 5.6-7.0x latency speedups with guaranteed schema validity.

The repository harshatheg/Qwen-2.5-1B-RLCD appeared at #30 on Hugging Face trending, but its content describes Parallel Constrained Decoding, an MLX-based inference engine for structured extraction and classification on Apple Silicon Macs. Benchmarked with mlx-community/Qwen2.5-1.5B-Instruct-4bit on an M4 Max, it reports 5.6x-7.0x latency reductions (e.g., 1,900 ms to 270 ms for a 28-field support triage task) with 100% syntactic validity and calibrated field-level probabilities. The engine prefills a single KV-cache, broadcasts it across all schema fields, and slices logits to valid candidate tokens for enum fields with up to 255 choices.

Hugging Face trending models·Sep 16, 01:35 UTC · 1d agoAI tools & infra

15

Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Researchers introduce Procedural Graphs, self-evolving (procedure, relation, procedure) structures guiding LLM agent tool use and planning.

Procedural Graphs organize procedural knowledge into (procedure, relation, procedure) triplets to guide LLM agent actions, addressing drift such as lost objectives, out-of-order tool calls, and repeated unproductive steps. At each decision step the framework localizes the active node and a guidance model translates the surrounding subgraph into step-level situational guidance. An LLM refiner edits graph topology by contrasting failed with successful trajectories, and across datasets, task types and LLMs the approach outperforms memory-based baselines and matches or surpasses hand-designed graphs.

arXiv cs.AI / cs.LG / cs.CL·Sep 8, 17:59 UTC · 8d agoAI research1

25

Import AI 470: No rights for machines; automating environment generation with SPADE; and building better GPU kernels with Hawkeye

METR analysis finds AI accelerating cyber vulnerability discovery, while SPADE self-play environment generation improves Qwen3 reasoning benchmark scores at 30B scale.

Import AI 470 discusses a METR research note reporting differential acceleration from AI: major acceleration in reported cyber vulnerabilities (cURL, OpenSSL, Firefox, Microsoft, NVD, OSV), minor acceleration in mathematics, and no measurable acceleration in AI-research optimization benchmarks. It also covers SPADE, a self-play framework from a multi-university team (University of Washington, Stanford, MIT, CMU, and others) that co-evolves executable training environments and agent capability using Environment Designer and Reasoning Agent roles with hint-based regret rewards. Trained on Qwen3-4B-Instruct-2507, Qwen3-8B, and Qwen3-30B-A3B-Instruct-2507 via GRPO (400 rollouts of 25 environments), SPADE lifted the 30B-A3B game-environment suite average to 58.3, +8.1 over base, and improved tool-use results across backbones. The issue also references Hawkeye for building better GPU kernels.

Import AI·Aug 24, 13:12 UTC · 23d agoAI research1

42

Towards a Deterministic Math Solver for Clinical Language Models

Paper shows handing arithmetic to a deterministic Python solver beats direct model calculation at 32B but not reliably at 7B on MedCalc-Bench.

Researchers test a Program-Solve interface where clinical LLMs write case-specific Python executed by a restricted local solver instead of doing arithmetic directly. On MedCalc-Bench Verified (1,100 cases, 55 calculators), Qwen2.5-32B-AWQ scored 90.53% with solver handoff versus 83.47% with direct arithmetic (+7.05 points), while Qwen2.5-7B gained an unreliable +3.29 points with a confidence interval spanning zero. The authors audited the benchmark against clinical guidelines and flagged 16 of 55 calculators for version, use, or coefficient concerns.

Hugging Face daily papers·Sep 8, 20:00 UTC · 8d agoAI research

25

Quenched Ensemble Sampling

Quenched Ensemble Sampling generalizes nested sampling's hard energy constraint to repulsive potentials, traversing first-order phase transitions where tempering fails.

Quenched Ensemble Sampling generalizes nested sampling's hard energy constraint into a family of repulsive potentials at the energy boundary, preserving monotone energy descent while making the constrained target amenable to scalable gradient-based kernels. On synthetic phase-transition models it estimates marginal likelihood and draws posterior samples across first-order transitions where popular alternatives such as tempering fail. Applications include marginal likelihood estimation for Bayesian neural network architecture comparison and partition function estimation in a high-dimensional continuous lattice field theory.

arXiv cs.AI / cs.LG / cs.CL·Sep 14, 17:16 UTC · 2d agoAI research1

15

Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

Researchers prove off-policy evaluation under history-dependent logging requires exponentially many episodes, resolving a hardness question for model-based POMDP evaluation.

The paper constructs POMDPs with at most two latent states per stage, three actions, and a three-memory-state logger where evaluating a known deterministic target policy to accuracy 1/8 requires Θ((3/2)^H log(1/δ)) episodes for any horizon H≥3. Coverage and outcome-revealing conditions hold with constants independent of H, yet a reset erases the unknown transition that determines the target value. The authors characterize the resulting statistical experiment exactly, derive a matching optimal estimator, and validate predictions on a two-lane gridworld. This settles the history-dependent-logging, model-based case posed by Zhang and Jiang (arXiv:2503.01134).

arXiv cs.AI / cs.LG / cs.CL·Sep 16, 17:56 UTC · 11h agoAI research

20

GAUGE: A Formal Framework for Measuring Cryptographic Security under Heterogeneous Adversary Cost Models

GAUGE frames cryptographic security as profiles over adversary cost models, certifying a ranking reversal between ML-KEM-512 and AES-128 from a 4–5% memory pricing shift.

GAUGE represents cryptographic security as a function over admissible adversary cost models (a security profile), proves profiles are piecewise-linear and concave, and establishes a rating trilemma when two profiles cross. A polynomial-time linear-programming procedure certifies whether the ranking of two schemes is robust, reverses under admissible models, or is genuinely incomparable. Applied to NIST post-quantum standards, the framework certifies a ML-KEM-512 versus AES-128 ranking reversal from a 4–5% shift in memory pricing and measures lattice-sieving cost drift of 9.79 bits per year over eight years. A hybrid X25519 + ML-KEM-768 handshake reduces combined-break probability twenty-fold at a 2.3 kilobyte cost.

arXiv cs.CR·Sep 15, 14:55 UTC · 1d agoResearch

48

Beneath the Surface of Chains-of-Thought: A Mechanistic Interpretation of Reasoning Operations in LLMs

Study shows LLM reasoning operations like planning and deduction are geometrically separable in hidden states, with separability peaking in middle layers.

Researchers investigate whether functional reasoning operations — problem formulation, goal decomposition, deduction — have corresponding geometric structure in LLM hidden representations. They find operations are separable in held-out representations with separability peaking in middle layers, ruling out lexical and positional confounds; token-wise operation alignment becomes more distributed across layers, and identical surface tokens are represented differently depending on their surrounding chunk. Attention-masking interventions show chunk-onset operation-aligned representations depend on preceding reasoning context; code is released on GitHub (naver-ai/beneath-cot).

Hugging Face daily papers·Sep 3, 20:00 UTC · 13d agoAI research1

40

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

Lower bounds show heterogeneous asynchronous optimization cannot match homogeneous rates under standard similarity assumptions; strong interpolation plus local PL condition closes the gap.

The paper examines whether pessimistic optimal time complexities for asynchronous distributed optimization with heterogeneous workers (different data distributions) can be overcome. It proves improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm, and that the weak interpolation assumption alone is also insufficient. Combining strong interpolation with the local Polyak-Lojasiewicz condition yields a new time complexity bound matching the best-known homogeneous dependence on worker computation times without requiring identical data distributions.

arXiv cs.AI / cs.LG / cs.CL·Sep 15, 17:24 UTC · 1d agoAI research

10

Coding Agents Have Converged: Why the SWE-bench Leaderboard Can No Longer Order Its Top Entries, and What to Measure Instead

Audit of 254 SWE-bench submissions finds top coding-agent entries statistically inseparable, so small leaderboard gaps no longer establish rank.

The paper audits 254 SWE-bench submissions across four splits without running models. On Verified, the top two entries each resolve 396 of 500 instances, and exact paired McNemar tests separate none of the 29 adjacent top-thirty pairs at alpha=0.05. Within-model scaffold score ranges reach 29.8 percentage points, versus an 8.8-point spread among the top thirty. The authors release a five-step audit protocol and recommend reporting comparison-set-specific resolution and model-scaffold provenance.

arXiv cs.AI / cs.LG / cs.CL·Sep 15, 16:29 UTC · 1d agoAI research

40

A positive resolution of the gap-entropy conjecture

New proof resolves the gap-entropy conjecture for Gaussian bandits, bounding optimal best-arm identification samples by H(log(1/delta)+Ent(I)) up to constants.

A paper proves the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in [0,1], and a unique optimal arm. It shows the optimal expected sample count, averaged over arm-label permutations, is within absolute constant factors of H(log(1/delta)+Ent(I)), where H sums squared gaps and Ent(I) is the instance's gap-entropy. It also gives an instance-independent algorithm bounded by a constant multiple of this quantity plus a g^-2 loglog(e^e/g) term for the smallest gap g.

arXiv cs.AI / cs.LG / cs.CL·Sep 9, 17:57 UTC · 7d agoAI research

15