English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Over recent years, devising classification algorithms that are robust toadversarial perturbations has emerged as a challenging problem. In particular,deep neural nets (DNNs) seem to be susceptible to small imperceptible changesover test instances. However, the line of work in provable robustness, so far,has been focused on information-theoretic robustness, ruling out even theexistence of any adversarial examples. In this work, we study whether there isa hope to benefit from algorithmic nature of an attacker that searches foradversarial examples, and ask whether there is any learning task for which itis possible to design classifiers that are only robust against polynomial-timeadversaries. Indeed, numerous cryptographic tasks can only be secure againstcomputationally bounded adversaries, and are indeed impossible forcomputationally unbounded attackers. Thus, it is natural to ask if the samestrategy could help robust learning.  We show that computational limitation of attackers can indeed be useful inrobust learning by demonstrating the possibility of a classifier for somelearning task for which computational and information theoretic adversaries ofbounded perturbations have very different power. Namely, while computationallyunbounded adversaries can attack successfully and find adversarial exampleswith small perturbation, polynomial time adversaries are unable to do so unlessthey can break standard cryptographic hardness assumptions. Our results,therefore, indicate that perhaps a similar approach to cryptography (relying oncomputational hardness) holds promise for achieving computationally robustmachine learning. On the reverse directions, we also show that the existence ofsuch learning task in which computational robustness beats informationtheoretic robustness requires computational hardness by implying (average-case)hardness of NP.

Adversarially Robust Learning Could Leverage Computational Hardness