English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Greedy decision tree learning heuristics are mainstays of machine learningpractice, but theoretical justification for their empirical success remainselusive. In fact, it has long been known that there are simple target functionsfor which they fail badly (Kearns and Mansour, STOC 1996).  Recent work of Brutzkus, Daniely, and Malach (COLT 2020) considered thesmoothed analysis model as a possible avenue towards resolving this disconnect.Within the smoothed setting and for targets $f$ that are $k$-juntas, theyshowed that these heuristics successfully learn $f$ with depth-$k$ decisiontree hypotheses. They conjectured that the same guarantee holds more generallyfor targets that are depth-$k$ decision trees.  We provide a counterexample to this conjecture: we construct targets that aredepth-$k$ decision trees and show that even in the smoothed setting, theseheuristics build trees of depth $2^{\Omega(k)}$ before achieving high accuracy.We also show that the guarantees of Brutzkus et al. cannot extend to theagnostic setting: there are targets that are very close to $k$-juntas, forwhich these heuristics build trees of depth $2^{\Omega(k)}$ before achievinghigh accuracy.

Decision tree heuristics can fail, even in the smoothed setting