Eine schärfere Verallgemeinerungsgrenze für Ridge-Regression mit Divide-and-Conquer

Wir untersuchen das Problem des verteilten maschinellen Lernens, bei dem die n Merkmals-Antwort-Paare zufällig und gleichmäßig auf m Maschinen verteilt werden. Ziel ist es, ein empirisches Risikominderungsproblem (ERM) mit minimalem Kommunikationsaufwand annähernd zu lösen. Die vor several Jahren vorgeschlagene Divide-and-Conquer (DC)-Methode ermöglicht es jeder Arbeitsmaschine, das gleiche ERM-Problem unabhängig unter Verwendung ihrer lokalen Merkmals-Antwort-Paare zu lösen und die Treibermaschine kombiniert die Lösungen. Dieser Ansatz erfolgt in einem Schritt und ist somit äußerst kommunikations-effizient. Obwohl die DC-Methode in vielen vorherigen Arbeiten untersucht wurde, wurde vorher diese Arbeit keine angemessene Verallgemeinerungsgrenze etabliert. Für das Ridge-Regression-Problem zeigen wir, dass der Vorhersagefehler der DC-Methode bei ungesehenen Testproben höchstens ε-mal größer ist als der optimale. In früheren Arbeiten gab es Grenzen mit konstantem Faktor, deren Stichprobenkomplexität quadratisch von d abhängt, was nicht mit den meisten realen Problemstellungen übereinstimmt. Im Gegensatz dazu sind unsere Grenzen viel stärker. Erstens ist unsere 1 + ε Fehlergrenze viel besser als ihre konstanten Faktorgrenzen. Zweitens ist unsere Stichprobenkomplexität lediglich linear in Bezug auf d.