Gopalan, Kalai, Klivans gave an algorithm https://dl.acm.org/citation.cfm?id=1374376.1374451 for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given black-box query access to a target function. They use discrete Fourier analysis. Question: How might one extend this to learning decision trees over $\mathbb{R}^n$? Obviously there is no "uniform distribution", unless we limit the domain to a (say) ball, which I'm perfectly happy to do.

  • 1
    $\begingroup$ A hazy idea: their proof doesn't extend to the Gaussian measure, using Hermite instead of Fourier (and mimicking the argument)? $\endgroup$ – Clement C. Jun 4 at 17:25
  • $\begingroup$ Hmm, interesting idea, I'll give it some thought. $\endgroup$ – Aryeh Jun 4 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.