Data-Driven Algorithm Design.
The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. Although there is a large literature on empirical approaches to selecting the best algorithm for a given application domai...
| Publicado en: | Communications of the ACM Vol. 63; no. 6; pp. 87 - 95 |
|---|---|
| Autores principales: | , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Jun2020
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=143468379&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 143468379 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Jun2020 vid: 63 iid: 6 pid: 68 pub: Association for Computing Machinery artinfo: ui: 143468379 10.1145/3394625 ppf: 87 ppct: 8 formats: tig: atl: Data-Driven Algorithm Design. aug: au: Gupta, Rishi Roughgarden, Tim affil: Department of Computer Science, Stanford University, Stanford, CA, USA Department of Computer Science, Columbia University, New York, USA su: Algorithms Machine learning Mathematical optimization Mathematical proofs Decision theory sug: subj: Algorithms Machine learning Mathematical optimization Mathematical proofs Decision theory ab: The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. Although there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem. We model the problem of identifying a good algorithm from data as a statistical learning problem. Our framework captures several state-of-the-art empirical and theoretical approaches to the problem, and our results identify conditions under which these approaches are guaranteed to perform well. We interpret our results in the contexts of learning greedy heuristics, instance feature- based algorithm selection, and parameter tuning in machine learning. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2020 holdings: @attributes: islocal: N |
|---|