Bài báo này nghiên cứu bài toán phân loại Boolean trên các cấu trúc nền quan hệ trong khuôn khổ logic do Grohe và Turán trình bày. Người ta biết rằng các bộ phân loại có thể định nghĩa bằng logic bậc nhất trên các cấu trúc bậc logarit đa thức có thể được học trong thời gian dưới tuyến tính (Grohe và Ritzert, LICS 2017). Bài báo này khái quát hóa kết quả thành hệ số bậc nhất FOCN, được Kuske và Schweikardt (LICS 2017) giới thiệu như một logic biểu đạt khái quát hóa nhiều logic hệ số khác. Cụ thể, chúng tôi chứng minh rằng các bộ phân loại có thể định nghĩa bằng FOCN trên các cấu trúc bậc logarit đa thức có thể được học một cách nhất quán trong thời gian dưới tuyến tính. Điều này có thể được coi là bước đầu tiên trong việc mở rộng khuôn khổ học để bao gồm các khía cạnh số của học máy. Hơn nữa, chúng tôi mở rộng kết quả thành học PAC không xác định cho các cấu trúc bậc tối đa $(\log \log n)^c$ với một hằng số c nào đó. Hơn nữa, chúng tôi chỉ ra rằng điều quan trọng là phải giới hạn bậc để có được các thuật toán học trong thời gian dưới tuyến tính. Nghĩa là, đối với các cấu trúc có độ chính xác không giới hạn, chúng tôi chứng minh rằng việc học trong thời gian cận tuyến tính là không thể ngay cả đối với các bộ phân loại có thể xác định được bằng logic bậc nhất tổng quát.
