この論文では、GroheとTuranによって提示された論理フレームワーク内のリレーショナル背景構造のブール分類問題を研究します。多項対数程度の構造では、一次論理として定義可能な分類器は、下位線形時間内に学習できることが知られている（Grohe and Ritzert、LICS 2017）。この論文は、KuskeとSchweikardt（LICS 2017）がさまざまな異なる係数ロジックを一般化する表現力のあるロジックとして紹介した一次論理係数FOCNで結果を一般化します。具体的には、多項対数程度の構造クラスに対してFOCNとして定義可能な分類器は、一貫して下位線形時間内に学習できることを証明します。これは、機械学習の数値的側面を含むように学習フレームワークを拡張する最初のステップと見なすことができます。また、任意の定数 c に対して、最大 $(\log \log n)^c$ 程度の構造クラスに対する不確定 PAC 学習に結果を拡張します。さらに、下位線形時間学習アルゴリズムを得るためには、程度を制限することが重要であることを示している。すなわち、程度が制限されない構造の場合、一般的な一次論理として定義可能な分類器についても、下位線形時間内に学習が不可能であることを証明する。
