Cover Image

Learnability of Parameter-Bounded Bayes Nets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattacharyya, Arnab, Choo, Davin, Gayen, Sutanu, Myrisiotis, Dimitrios
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Total Variation Distance Meets Probabilistic Inference
by: Bhattacharyya, Arnab, et al.
Published: (2023)

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Computational Explorations of Total Variation Distance
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Learning High-dimensional Gaussians from Censored Data
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Proximity to Losslessly Compressible Parameters
by: Farrugia-Roberts, Matthew
Published: (2023)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
by: Jacot, Arthur
Published: (2025)

Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set
by: Choo, Davin, et al.
Published: (2024)

Product distribution learning with imperfect advice
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Distribution Learning Meets Graph Structure Sampling
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
by: Khanal, Bikram, et al.
Published: (2024)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
by: Li, Xiaoyu, et al.
Published: (2025)

Circuit Complexity Bounds for Visual Autoregressive Model
by: Ke, Yekun, et al.
Published: (2025)

Learning multivariate Gaussians with imperfect advice
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Online bipartite matching with imperfect advice
by: Choo, Davin, et al.
Published: (2024)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
by: Chen, Bo, et al.
Published: (2024)

Envy-Free House Allocation with Minimum Subsidy
by: Choo, Davin, et al.
Published: (2024)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
by: Wang, Jie, et al.
Published: (2024)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
by: Li, Zhiyuan, et al.
Published: (2024)

Ask, and it shall be given: On the Turing completeness of prompting
by: Qiu, Ruizhong, et al.
Published: (2024)

Large Language Models on Small Resource-Constrained Systems: Performance Characterization, Analysis and Trade-offs
by: Seymour, Liam, et al.
Published: (2024)

Data Debugging is NP-hard for Classifiers Trained with SGD
by: Guo, Zizheng, et al.
Published: (2024)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
by: Cao, Yang, et al.
Published: (2025)

A Logic for Expressing Log-Precision Transformers
by: Merrill, William, et al.
Published: (2022)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
by: Jacobs, Peter Matthew, et al.
Published: (2026)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
by: Huang, Jizhou, et al.
Published: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
by: Dwork, Cynthia, et al.
Published: (2023)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
by: Rohatgi, Dhruv, et al.
Published: (2025)

How Global Calibration Strengthens Multiaccuracy
by: Casacuberta, Sílvia, et al.
Published: (2025)