Cover Image

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gaitonde, Jason, Moitra, Ankur, Mossel, Elchanan
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Better Models and Algorithms for Learning Ising Models from Dynamics
by: Gaitonde, Jason, et al.
Published: (2025)

Sample-Efficient Linear Regression with Self-Selection Bias
by: Gaitonde, Jason, et al.
Published: (2024)

On Algorithmic Robustness of Corrupted Markov Chains
by: Gaitonde, Jason, et al.
Published: (2025)

Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

Learning $\mathsf{AC}^0$ Under Graphical Models
by: Chandrasekaran, Gautam, et al.
Published: (2026)

Learning and Testing Convex Functions
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
by: Moitra, Ankur, et al.
Published: (2026)

Steering diffusion models with quadratic rewards: a fine-grained analysis
by: Moitra, Ankur, et al.
Published: (2026)

On Learning Parities with Dependent Noise
by: Golowich, Noah, et al.
Published: (2024)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
by: Kothari, Pravesh K., et al.
Published: (2024)

Model Stealing for Any Low-Rank Language Model
by: Liu, Allen, et al.
Published: (2024)

Learning Juntas under Markov Random Fields
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Learning quantum Hamiltonians at any temperature in polynomial time
by: Bakshi, Ainesh, et al.
Published: (2023)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

Structure learning of Hamiltonians from real-time evolution
by: Bakshi, Ainesh, et al.
Published: (2024)

Reconstructing Riemannian Metrics From Random Geometric Graphs
by: Huang, Han, et al.
Published: (2025)

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
by: Rohatgi, Dhruv, et al.
Published: (2025)

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Influence Maximization in Ising Models
by: Chen, Zongchen, et al.
Published: (2023)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
by: Nath, Ankur, et al.
Published: (2024)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
by: Bakshi, Ainesh, et al.
Published: (2025)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

The Power of Two Matrices in Spectral Algorithms for Community Recovery
by: Dhara, Souvik, et al.
Published: (2022)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
by: Mishra, Nina, et al.
Published: (2025)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

Breaking the $T^{2/3}$ Barrier for Sequential Calibration
by: Dagan, Yuval, et al.
Published: (2024)

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)

Finding the root in random nearest neighbor trees
by: Brandenberger, Anna, et al.
Published: (2024)

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
by: Gu, Yuzhou, et al.
Published: (2024)

Provable Quantization with Randomized Hadamard Transform
by: Feng, Ying, et al.
Published: (2026)

Improving LSH via Tensorized Random Projection
by: Verma, Bhisham Dev, et al.
Published: (2024)

Finding the Root in Random Nearest Neighbor Trees
by: Anna Brandenberger, et al.
Published: (2026)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
by: Gao, Jie, et al.
Published: (2025)

A Perfectly Truthful Calibration Measure
by: Hartline, Jason, et al.
Published: (2025)

Smooth Calibration and Decision Making
by: Hartline, Jason, et al.
Published: (2025)