Alternative Measures of Computational Complexity with Applications to Agnostic Learning

@incollection{citeulike:2605457, abstract = {We address a fundamental problem of complexity theory - the inadequacy of worst-case complexity for the task of evaluating the computational resources required for real life problems. While being the best known measure and enjoying the support of a rich and elegant theory, worst-case complexity seems gives rise to over-pessimistic complexity values. Many standard task, that are being carried out routinely in machine learning applications, are NP-hard, that is, infeasible from the worst-case-complexity perspective. In this work we offer an alternative measure of complexity for approximations-optimization tasks. Our approach is to define a hierarchy on the set of inputs to a learning task, so that natural ('real data') inputs occupy only bounded levels of this hierarchy and that there are algorithms that handle in polynomial time each such bounded level.}, author = {Ben-David, Shai }, citeulike-article-id = {2605457}, doi = {10.1007/11750321\_22}, journal = {Theory and Applications of Models of Computation}, keywords = {agnostic-learning, algorithmics, ml-philosophy, natural-optimization}, pages = {231--235}, posted-at = {2008-03-28 10:28:56}, priority = {2}, title = {Alternative Measures of Computational Complexity with Applications to Agnostic Learning}, url = {http://dx.doi.org/10.1007/11750321\_22}, year = {2006} }

TY - CHAP ID - citeulike:2605457 L3 - citeulike-article-id:2605457 TI - Alternative Measures of Computational Complexity with Applications to Agnostic Learning JF - Theory and Applications of Models of Computation SP - 231 EP - 235 N2 - We address a fundamental problem of complexity theory - the inadequacy of worst-case complexity for the task of evaluating the computational resources required for real life problems. While being the best known measure and enjoying the support of a rich and elegant theory, worst-case complexity seems gives rise to over-pessimistic complexity values. Many standard task, that are being carried out routinely in machine learning applications, are NP-hard, that is, infeasible from the worst-case-complexity perspective. In this work we offer an alternative measure of complexity for approximations-optimization tasks. Our approach is to define a hierarchy on the set of inputs to a learning task, so that natural ('real data') inputs occupy only bounded levels of this hierarchy and that there are algorithms that handle in polynomial time each such bounded level. KW - agnostic-learning KW - algorithmics KW - ml-philosophy KW - natural-optimization AU - Ben-David, Shai PY - 2006/// UR - http://dx.doi.org/10.1007/11750321_22 ER -