Show simple item record  

dc.contributor.authorKabán, Ataen_NZ
dc.contributor.authorDurrant, Robert J.en_NZ
dc.date.accessioned2020-11-17T19:53:47Z
dc.date.available2020-11-17T19:53:47Z
dc.date.issued2020
dc.identifier.citationKabán, A., & Durrant, R. J. (2020). Structure from randomness in halfspace learning with the zero-one loss. Journal of Artificial Intelligence Research, 69, 733–764. https://doi.org/10.1613/jair.1.11506en
dc.identifier.urihttps://hdl.handle.net/10289/13964
dc.description.abstractWe prove risk bounds for halfspace learning when the data dimensionality is allowed to be larger than the sample size, using a notion of compressibility by random projection. In particular, we give upper bounds for the empirical risk minimizer learned efficiently from randomly projected data, as well as uniform upper bounds in the full high-dimensional space. Our main findings are the following: i) In both settings, the obtained bounds are able to discover and take advantage of benign geometric structure, which turns out to depend on the cosine similarities between the classifier and points of the input space, and provide a new interpretation of margin distribution type arguments. ii) Furthermore our bounds allow us to draw new connections between several existing successful classification algorithms, and we also demonstrate that our theory is predictive of empirically observed performance in numerical simulations and experiments. iii) Taken together, these results suggest that the study of compressive learning can improve our understanding of which benign structural traits – if they are possessed by the data generator – make it easier to learn an effective classifier from a sample.en_NZ
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.publisherAI Access Foundationen_NZ
dc.relation.urihttps://jair.org/index.php/jair/article/view/11506/26620
dc.rights© 2020 AI Access Foundation.
dc.titleStructure from randomness in halfspace learning with the zero-one lossen_NZ
dc.typeJournal Article
dc.identifier.doi10.1613/jair.1.11506en_NZ
dc.relation.isPartOfJournal of Artificial Intelligence Researchen_NZ
pubs.begin-page733
pubs.elements-id258225
pubs.end-page764
pubs.publication-statusPublished onlineen_NZ
pubs.volume69en_NZ
dc.identifier.eissn1076-9757en_NZ


Files in this item

This item appears in the following Collection(s)

Show simple item record