Copertina

On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Giapitzakis, George, Fountoulakis, Kimon, Nichani, Eshaan, Lee, Jason D.
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
di: de Luca, Artur Back, et al.
Pubblicazione: (2025)

Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
di: Qharabagh, Muhammad Fetrat, et al.
Pubblicazione: (2026)

Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks
di: Nichani, Eshaan, et al.
Pubblicazione: (2023)

How Transformers Learn Causal Structure with Gradient Descent
di: Nichani, Eshaan, et al.
Pubblicazione: (2024)

Quantitative Bounds for Length Generalization in Transformers
di: Izzo, Zachary, et al.
Pubblicazione: (2025)

Understanding Factual Recall in Transformers via Associative Memories
di: Nichani, Eshaan, et al.
Pubblicazione: (2024)

Positional Attention: Expressivity and Learnability of Algorithmic Computation
di: de Luca, Artur Back, et al.
Pubblicazione: (2024)

Emergence and scaling laws in SGD learning of shallow neural networks
di: Ren, Yunwei, et al.
Pubblicazione: (2025)

Fine-Tuning Dynamics of In-Context Factual Recall in Transformers
di: Huang, Ruomin, et al.
Pubblicazione: (2026)

Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networks
di: Fu, Hengyu, et al.
Pubblicazione: (2024)

Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory
di: Kim, Juno, et al.
Pubblicazione: (2026)

Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
di: Fountoulakis, Kimon, et al.
Pubblicazione: (2026)

Optimality of Message-Passing Architectures for Sparse Graphs
di: Baranwal, Aseem, et al.
Pubblicazione: (2023)

Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval
di: Barnfield, Nicholas, et al.
Pubblicazione: (2026)

Learning Compositional Functions with Transformers from Easy-to-Hard Data
di: Wang, Zixuan, et al.
Pubblicazione: (2025)

Simulation of Graph Algorithms with Looped Transformers
di: de Luca, Artur Back, et al.
Pubblicazione: (2024)

Analysis of Corrected Graph Convolutions
di: Wang, Robert, et al.
Pubblicazione: (2024)

Fine-Tuning Language Models with Just Forward Passes
di: Malladi, Sadhika, et al.
Pubblicazione: (2023)

Local Graph Clustering with Noisy Labels
di: de Luca, Artur Back, et al.
Pubblicazione: (2023)

On Statistical Estimation of Edge-Reinforced Random Walks
di: Qinghua, et al.
Pubblicazione: (2025)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
di: Joshi, Nirmit, et al.
Pubblicazione: (2024)

Towards Understanding Transformers in Learning Random Walks
di: Shi, Wei, et al.
Pubblicazione: (2025)

Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
di: Diakonikolas, Ilias, et al.
Pubblicazione: (2025)

Repelling Random Walks
di: Reid, Isaac, et al.
Pubblicazione: (2023)

Revisiting Random Walks for Learning on Graphs
di: Kim, Jinwoo, et al.
Pubblicazione: (2024)

Descriptive Kernel Convolution Network with Improved Random Walk Kernel
di: Lee, Meng-Chieh, et al.
Pubblicazione: (2024)

Differentially Private Decentralized Learning with Random Walks
di: Cyffers, Edwige, et al.
Pubblicazione: (2024)

Settling the Sample Complexity of Online Reinforcement Learning
di: Zhang, Zihan, et al.
Pubblicazione: (2023)

Learning Long Range Dependencies on Graphs via Random Walks
di: Chen, Dexiong, et al.
Pubblicazione: (2024)

Statistical Complexity of Quantum Learning
di: Banchi, Leonardo, et al.
Pubblicazione: (2023)

Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs
di: Choromanski, Krzysztof, et al.
Pubblicazione: (2024)

Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining
di: Ren, Yunwei, et al.
Pubblicazione: (2026)

The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
di: Damian, Alex, et al.
Pubblicazione: (2025)

Random Walk Learning and the Pac-Man Attack
di: Chen, Xingran, et al.
Pubblicazione: (2025)

Random Walk Guided Hyperbolic Graph Distillation
di: Long, Yunbo, et al.
Pubblicazione: (2025)

Statistical Learning Theory in Lean 4: Empirical Processes from Scratch
di: Zhang, Yuanhe, et al.
Pubblicazione: (2026)

Flock: A Knowledge Graph Foundation Model via Learning on Random Walks
di: Kim, Jinwoo, et al.
Pubblicazione: (2025)

Learning From Simplicial Data Based on Random Walks and 1D Convolutions
di: Frantzen, Florian, et al.
Pubblicazione: (2024)

Policy Mirror Descent with Lookahead
di: Protopapas, Kimon, et al.
Pubblicazione: (2024)

Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchies
di: Mathys, Joël, et al.
Pubblicazione: (2025)