Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models.
Ilias DiakonikolasDaniel M. KaneYuxin SunPublished in: COLT (2022)
Keyphrases
- lower bound
- learning process
- prior knowledge
- learning models
- supervised learning
- learned models
- upper bound
- online learning
- accurate models
- dynamic programming
- objective function
- structured prediction
- learning problems
- markov random field
- image registration
- probabilistic model
- closed form
- upper and lower bounds
- active learning
- neural network
- optimal cost