我々は、オンライン学習におけるラベルなしデータの有効性に関する30年以上にわたる未解決問題を、帰納的学習と標準的オンライン学習の誤り境界の差を精密に定量化することによって解決した。本研究では、Littlestone次元が ( d ) である任意の概念クラスに対して、帰納的誤り境界が少なくとも ( \Omega(\sqrt{d}) ) であることを証明した。これは、Ben-David、Kushilevitz、Mansour（1995年、1997年）およびHanneke、Moran、Shafer（2023年）によって得られた従来の下界 ( \Omega(\log \log d) )、( \Omega(\sqrt{d}) )、( \Omega(\sqrt{\log d}) ) に対して指数的に改善する結果である。さらに、我々の下界がタイトであることも示した：任意の ( d ) に対して、Littlestone次元が ( d ) であるクラスが存在し、その帰納的誤り境界は ( O(\sqrt{d}) ) となる。この上界は、Ben-Davidら（1997年）が得た従来の最良上界 ( \frac{2}{3}d ) よりも改善している。これらの結果は、帰納的学習と標準的オンライン学習の間に二次的なギャップが存在することを示しており、ラベルなしインスタンス列に対する先進的なアクセスが学習性能に与える利点を強調している。これは、PAC学習設定において帰納的学習と標準的学習が類似したサンプル複雑性を示すのと対照的である。