Vi fortsätter studien av beräkningsbegränsningar i att lära sig robusta klassificeringar, efter det senaste arbetet av Bubeck, Lee, Price och Razenshteyn. För det första visar vi klassificeringsuppgifter där beräkningseffektiva robusta klassificeringar inte finns, inte ens när beräkningsmässigt obundna robusta klassificeringar gör det. Vi förlitar oss på hårdheten i avkodning problem med förbearbetning på koder och gitter. För det andra visar vi klassificeringsuppgifter där effektiva robusta klassificeringar finns, men de är beräknings svårt att lära. Bubeck m.fl. visade exempel på sådana uppgifter i smallperturbation-systemet där den robusta klassificeraren kan återhämta sig från ett konstant antal perturbed bits. Faktum är, som vi observerar, att frågan om huruvida det finns en robust klassificerare med stor perturbation för deras uppgift är relaterad till viktiga öppna frågor i beräkningstalsteorin. Vi visar två sådana klassificeringsuppgifter i stor-perturbation regim: den första bygger på förekomsten av enkelriktade funktioner, ett minimalt antagande i kryptografi; och den andra på hårdheten i inlärning paritet med buller problem. För den andra uppgiften, inte bara en nonrobust klassificerare finns, men också en effektiv algoritm som genererar färska nya märkta prover ges tillgång till polynomiskt många utbildningsexempel (benämns som generation av ). För det tredje visar vi att varje sådan uppgift innebär existensen av kryptografiska primitiva funktioner som enkelriktade funktioner eller till och med former av kryptering med öppen nyckel. Detta leder oss till ett win-win scenario: antingen kan vi snabbt lära oss en effektiv robust klassificering (förutsatt att en finns), eller så kan vi bygga nya fall av populära och användbara kryptografiska primitiva.
Enligt standardiserade kryptografiska antaganden konstruerar REF ett inlärningsproblem för vilket en beräkningseffektiv icke-robust-klassifier finns, ingen effektiv robust klassifier finns, men det finns en ineffektiv robust klassifier.
Computational Limitations in Robust Classification and Win-Win Results
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Mathematics', 'Computer Science']}