{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T01:41:49Z","timestamp":1772847709579,"version":"3.50.1"},"reference-count":92,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,12,12]],"date-time":"2012-12-12T00:00:00Z","timestamp":1355270400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s10994-012-5323-6","type":"journal-article","created":{"date-parts":[[2012,12,11]],"date-time":"2012-12-11T21:44:56Z","timestamp":1355262296000},"page":"431-460","source":"Crossref","is-referenced-by-count":14,"title":["Computational complexity of kernel-based density-ratio estimation: a condition number analysis"],"prefix":"10.1007","volume":"90","author":[{"given":"Takafumi","family":"Kanamori","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taiji","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masashi","family":"Sugiyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,12]]},"reference":[{"key":"5323_CR1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1111\/j.2517-6161.1966.tb00626.x","volume":"28","author":"S. M. Ali","year":"1966","unstructured":"Ali, S. M., & Silvey, S. D. (1966). A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society. Series B. Methodological, 28, 131\u2013142.","journal-title":"Journal of the Royal Statistical Society. Series B. Methodological"},{"key":"5323_CR2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1090\/S0002-9947-1950-0051437-7","volume":"68","author":"N. Aronszajn","year":"1950","unstructured":"Aronszajn, N. (1950). Theory of reproducing kernels. Transactions of the American Mathematical Society, 68, 337\u2013404.","journal-title":"Transactions of the American Mathematical Society"},{"key":"5323_CR3","first-page":"158","volume-title":"Numerical methods and application","author":"O. Axelsson","year":"2002","unstructured":"Axelsson, O., & Neytcheva, M. (2002). Robust preconditioners for saddle point problems. In Numerical methods and application (pp. 158\u2013166)."},{"key":"5323_CR4","doi-asserted-by":"crossref","first-page":"2768","DOI":"10.1016\/j.cma.2009.04.004","volume":"198","author":"S. Badia","year":"2009","unstructured":"Badia, S., Nobile, F., & Vergara, C. (2009). Robin-robin preconditioned Krylov methods for fluid-structure interaction problems. Computer Methods in Applied Mechanics and Engineering, 198, 2768\u20132784.","journal-title":"Computer Methods in Applied Mechanics and Engineering"},{"key":"5323_CR5","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Schafer, G., & Vredeveld, T. (2006). Average-case and smoothed competitive analysis of the multilevel feedback algorithm. Open Access publications from Maastricht University (urn:nbn:nl:ui:27-17093). Maastricht University."},{"key":"5323_CR6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s10208-005-0176-2","volume":"7","author":"C. Beltran","year":"2006","unstructured":"Beltran, C., & Pardo, L. M. (2006). Estimates on the distribution of the condition number of singular matrices. Foundations of Computational Mathematics, 7, 87\u2013134.","journal-title":"Foundations of Computational Mathematics"},{"key":"5323_CR7","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s10444-011-9173-8","volume":"35","author":"M. Benzi","year":"2011","unstructured":"Benzi, M., Haber, E., & Taralli, L. (2011). A preconditioning technique for a class of PDE-constrained optimization problems. Advances in Computational Mathematics, 35, 149\u2013173.","journal-title":"Advances in Computational Mathematics"},{"key":"5323_CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/1390156.1390164","volume-title":"Proceedings of 25th annual international conference on machine learning (ICML2008)","author":"S. Bickel","year":"2008","unstructured":"Bickel, S., Bogojeska, J., Lengauer, T., & Scheffer, T. (2008). Multi-task learning for HIV therapy screening. In Proceedings of 25th annual international conference on machine learning (ICML2008) (pp. 56\u201363). Helsinki: Omnipress."},{"key":"5323_CR9","first-page":"2137","volume":"10","author":"S. Bickel","year":"2009","unstructured":"Bickel, S., Br\u00fcckner, M., & Scheffer, T. (2009). Discriminative learning under covariate shift. Journal of Machine Learning Research, 10, 2137\u20132155.","journal-title":"Journal of Machine Learning Research"},{"key":"5323_CR10","first-page":"905","volume-title":"Proc. of the 13th annual ACM-SIAM symp. on discrete algorithms","author":"A. Blum","year":"2002","unstructured":"Blum, A., & Dunagan, J. (2002). Smoothed analysis of the perceptron algorithm for linear programming. In Proc. of the 13th annual ACM-SIAM symp. on discrete algorithms (pp. 905\u2013914)."},{"key":"5323_CR11","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/0215026","volume":"15","author":"L. Blum","year":"1986","unstructured":"Blum, L., & Shub, M. (1986). Evaluating rational functions: infinite precision is finite cost and tractable on average. SIAM Journal on Computing, 15, 384\u2013398.","journal-title":"SIAM Journal on Computing"},{"key":"5323_CR12","doi-asserted-by":"crossref","first-page":"2769","DOI":"10.1137\/100782954","volume":"31","author":"P. B\u00fcrgisser","year":"2010","unstructured":"B\u00fcrgisser, P., & Cucker (2010). Smoothed analysis of Moore-Penrose inversion. SIAM Journal on Matrix Analysis and Applications, 31, 2769\u20132783.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"5323_CR13","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s00037-006-0213-6","volume":"15","author":"P. B\u00fcrgisser","year":"2006","unstructured":"B\u00fcrgisser, P., Cucker, F., & de Naurois, P. (2006a). The complexity of semilinear problems in succinct representation. Computational Complexity, 15, 197\u2013235.","journal-title":"Computational Complexity"},{"key":"5323_CR14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.crma.2006.05.014","volume":"343","author":"P. B\u00fcrgisser","year":"2006","unstructured":"B\u00fcrgisser, P., Cucker, F., & Lotz, M. (2006b). General formulas for the smoothed analysis of condition numbers. Comptes Rendus de L\u2019Acad\u00e9mie des Sciences. Series 1, Mathematics, 343, 145\u2013150.","journal-title":"Comptes Rendus de L\u2019Acad\u00e9mie des Sciences. Series 1, Mathematics"},{"key":"5323_CR15","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.matpur.2006.06.001","volume":"86","author":"P. B\u00fcrgisser","year":"2006","unstructured":"B\u00fcrgisser, P., Cucker, F., & Lotz, M. (2006c). Smoothed analysis of complex conic condition numbers. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es, 86, 293\u2013309.","journal-title":"Journal de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"key":"5323_CR16","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1214\/09-AOP489","volume":"38","author":"P. B\u00fcrgisser","year":"2010","unstructured":"B\u00fcrgisser, P., Cucker, F., & Lotz, M. (2010). Coverage processes on spheres and condition numbers for linear programming. Annals of Probability, 38, 570\u2013604.","journal-title":"Annals of Probability"},{"key":"5323_CR17","volume-title":"Proceedings of NIPS workshop on statistical methods for computational experiments in visual processing and computer vision","author":"B. Caputo","year":"2002","unstructured":"Caputo, B., Sim, K., Furesjo, F., & Smola, A. (2002). Appearance-based object recognition using SVMs: which kernel should I use? In Proceedings of NIPS workshop on statistical methods for computational experiments in visual processing and computer vision."},{"key":"5323_CR18","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1162\/neco.2007.19.5.1155","volume":"19","author":"O. Chapelle","year":"2007","unstructured":"Chapelle, O. (2007). Training a support vector machine in the primal. Neural Computation, 19, 1155\u20131178.","journal-title":"Neural Computation"},{"key":"5323_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1023\/A:1015460004163","volume":"114","author":"D. Cheung","year":"2002","unstructured":"Cheung, D., & Cucker, F. (2002). Probabilistic analysis of condition numbers for linear programming. Journal of Optimization Theory and Applications, 114, 55\u201367.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"5323_CR20","first-page":"229","volume":"2","author":"I. Csisz\u00e1r","year":"1967","unstructured":"Csisz\u00e1r, I. (1967). Information-type measures of difference of probability distributions and indirect observation. Studia Scientiarum Mathematicarum Hungarica, 2, 229\u2013318.","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"5323_CR21","first-page":"94","volume":"94","author":"F. Cucker","year":"2002","unstructured":"Cucker, F., & Wschebor, M. (2002). On the expected condition number of linear programming problems. Numerische Mathematik, 94, 94\u2013419.","journal-title":"Numerische Mathematik"},{"key":"5323_CR22","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1090\/S0025-5718-1988-0929546-7","volume":"50","author":"J. Demmel","year":"1988","unstructured":"Demmel, J. (1988). The probability that a numerical analysis problem is difficult. Mathematics of Computation, 50, 449\u2013480.","journal-title":"Mathematics of Computation"},{"key":"5323_CR23","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611971446","volume-title":"Applied numerical linear algebra","author":"J. W. Demmel","year":"1997","unstructured":"Demmel, J. W. (1997). Applied numerical linear algebra. Philadelphia: SIAM."},{"key":"5323_CR24","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02288367","volume":"1","author":"C. Eckart","year":"1936","unstructured":"Eckart, C., & Young, G. (1936). The approximation of one matrix by another of lower rank. Psychometrika, 1, 211\u2013218.","journal-title":"Psychometrika"},{"key":"5323_CR25","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1137\/0609045","volume":"9","author":"A. Edelman","year":"1988","unstructured":"Edelman, A. (1988). Eigenvalues and condition numbers of random matrices. SIAM Journal on Matrix Analysis and Applications, 9, 543\u2013560.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"5323_CR26","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1090\/S0025-5718-1992-1106966-2","volume":"58","author":"A. Edelman","year":"1992","unstructured":"Edelman, A. (1992). On the distribution of a scaled condition number. Mathematics of Computation, 58, 185\u2013190.","journal-title":"Mathematics of Computation"},{"key":"5323_CR27","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1137\/040614256","volume":"27","author":"A. Edelman","year":"2005","unstructured":"Edelman, A., & Sutton, B. D. (2005). Tails of condition number distributions. SIAM Journal on Matrix Analysis and Applications, 27, 547\u2013560.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"5323_CR28","first-page":"131","volume-title":"Dataset shift in machine learning","author":"A. Gretton","year":"2009","unstructured":"Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., & Sch\u00f6lkopf, B. (2009). Covariate shift by kernel mean matching. In J. Qui\u00f1onero-Candela, M. Sugiyama, A. Schwaighofer, & N. Lawrence (Eds.), Dataset shift in machine learning (pp. 131\u2013160). Cambridge: MIT Press."},{"key":"5323_CR29","first-page":"35","volume":"2","author":"W. W. Hager","year":"2006","unstructured":"Hager, W. W., & Zhang, H. (2006). A survey of the nonlinear conjugate gradient methods. Pacific Journal of Optimization, 2, 35\u201358.","journal-title":"Pacific Journal of Optimization"},{"key":"5323_CR30","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/ICDM.2008.49","volume-title":"Proceedings of IEEE international conference on data mining (ICDM2008)","author":"S. Hido","year":"2008","unstructured":"Hido, S., Tsuboi, Y., Kashima, H., Sugiyama, M., & Kanamori, T. (2008). Inlier-based outlier detection via direct density ratio estimation. In Proceedings of IEEE international conference on data mining (ICDM2008), Pisa, Italy (pp. 223\u2013232)."},{"key":"5323_CR31","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s10115-010-0283-2","volume":"26","author":"S. Hido","year":"2011","unstructured":"Hido, S., Tsuboi, Y., Kashima, H., Sugiyama, M., & Kanamori, T. (2011). Statistical outlier detection using direct density ratio estimation. Knowledge and Information Systems, 26, 309\u2013336.","journal-title":"Knowledge and Information Systems"},{"key":"5323_CR32","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix analysis","author":"R. Horn","year":"1985","unstructured":"Horn, R., & Johnson, C. (1985). Matrix analysis. Cambridge: Cambridge University Press."},{"key":"5323_CR33","first-page":"1391","volume":"10","author":"T. Kanamori","year":"2009","unstructured":"Kanamori, T., Hido, S., & Sugiyama, M. (2009). A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 10, 1391\u20131445.","journal-title":"Journal of Machine Learning Research"},{"key":"5323_CR34","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s10994-011-5266-3","volume":"86","author":"T. Kanamori","year":"2012","unstructured":"Kanamori, T., Suzuki, T., & Sugiyama, M. (2012). Statistical analysis of kernel-based least-squares density-ratio estimation. Machine Learning, 86, 335\u2013367.","journal-title":"Machine Learning"},{"key":"5323_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v011.i09","volume":"11","author":"A. Karatzoglou","year":"2004","unstructured":"Karatzoglou, A., Smola, A., Hornik, K., & Zeileis, A. (2004). Kernlab\u2014an S4 package for kernel methods in\u00a0R. Journal of Statistical Software, 11, 1\u201320.","journal-title":"Journal of Statistical Software"},{"key":"5323_CR36","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1002\/sam.10124","volume":"5","author":"Y. Kawahara","year":"2011","unstructured":"Kawahara, Y., & Sugiyama, M. (2011). Sequential change-point detection based on direct density-ratio estimation. Statistical Analysis and Data Mining, 5, 114\u2013127.","journal-title":"Statistical Analysis and Data Mining"},{"key":"5323_CR37","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0022-247X(71)90184-3","volume":"33","author":"G. S. Kimeldorf","year":"1971","unstructured":"Kimeldorf, G. S., & Wahba, G. (1971). Some results on Tchebycheffian spline functions. Journal of Mathematical Analysis and Applications, 33, 82\u201395.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"5323_CR38","doi-asserted-by":"crossref","first-page":"800","DOI":"10.20965\/jaciii.2011.p0800","volume":"15","author":"M. Kimura","year":"2011","unstructured":"Kimura, M., & Sugiyama, M. (2011). Dependence-maximization clustering with least-squares mutual information. Journal of Advanced Computational Intelligence and Intelligent Informatics, 15, 800\u2013805.","journal-title":"Journal of Advanced Computational Intelligence and Intelligent Informatics"},{"key":"5323_CR39","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0377-0427(88)90402-5","volume":"22","author":"E. Kostlan","year":"1988","unstructured":"Kostlan, E. (1988). Complexity theory of numerical linear algebra. Journal of Computational and Applied Mathematics, 22, 219\u2013230.","journal-title":"Journal of Computational and Applied Mathematics"},{"key":"5323_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-74503-9","volume-title":"Linear and nonlinear programming","author":"D. Luenberger","year":"2008","unstructured":"Luenberger, D., & Ye, Y. (2008). Linear and nonlinear programming. Berlin: Springer."},{"key":"5323_CR41","first-page":"1024","volume-title":"ISAAC","author":"B. Manthey","year":"2009","unstructured":"Manthey, B., & R\u00f6glin, H. (2009). Worst-case and smoothed analysis of k-means clustering with Bregman divergences. In ISAAC (pp. 1024\u20131033)."},{"key":"5323_CR42","first-page":"536","volume-title":"Proceedings of the 1998 conference on advances in neural information processing systems II","author":"S. Mika","year":"1999","unstructured":"Mika, S., Sch\u00f6lkopf, B., Smola, A., M\u00fcller, K.-R., Scholz, M., & R\u00e4tsch, G. (1999). Kernel PCA and de-noising in feature spaces. In Proceedings of the 1998 conference on advances in neural information processing systems II (pp. 536\u2013542). Cambridge: MIT Press."},{"key":"5323_CR43","volume-title":"Studies in numerical analysis","author":"J. J. Mor\u00e9","year":"1984","unstructured":"Mor\u00e9, J. J., & Sorensen, D. C. (1984). Newton\u2019s method. In G. H. Golub (Ed.), Studies in numerical analysis. pub-MATH-ASSOC-AMER."},{"key":"5323_CR44","volume-title":"Geometry, topology and physics","author":"M. Nakahara","year":"2003","unstructured":"Nakahara, M. (2003). Geometry, topology and physics (2nd ed.). London: Taylor & Francis.","edition":"2"},{"key":"5323_CR45","doi-asserted-by":"crossref","first-page":"5847","DOI":"10.1109\/TIT.2010.2068870","volume":"56","author":"X. Nguyen","year":"2010","unstructured":"Nguyen, X., Wainwright, M. J., & Jordan, M. I. (2010). Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56, 5847\u20135861.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5323_CR46","doi-asserted-by":"crossref","DOI":"10.1007\/b98874","volume-title":"Numerical optimization","author":"J. Nocedal","year":"1999","unstructured":"Nocedal, J., & Wright, S. J. (1999). Numerical optimization. Berlin: Springer."},{"key":"5323_CR47","volume-title":"Dataset shift in machine learning","year":"2009","unstructured":"Qui\u00f1onero-Candela, J., Sugiyama, M., Schwaighofer, A., & Lawrence, N. (Eds.) (2009). Dataset shift in machine learning. Cambridge: MIT Press."},{"key":"5323_CR48","isbn-type":"print","volume-title":"R: a language and environment for statistical computing","author":"R Development Core Team","year":"2009","unstructured":"R Development Core Team (2009). R: a language and environment for statistical computing. Vienna: R\u00a0Foundation for Statistical Computing. ISBN 3-900051-07-0.","ISBN":"https:\/\/id.crossref.org\/isbn\/3900051070"},{"key":"5323_CR49","volume-title":"International joint conference on artificial intelligence","author":"N. Ratliff","year":"2007","unstructured":"Ratliff, N., & Bagnell, J. D. (2007). Kernel conjugate gradient for fast kernel machines. In International joint conference on artificial intelligence."},{"key":"5323_CR50","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1007618119488","volume":"42","author":"G. R\u00e4tsch","year":"2001","unstructured":"R\u00e4tsch, G., Onoda, T., & M\u00fcller, K.-R. (2001). Soft margins for adaboost. Machine Learning, 42, 287\u2013320.","journal-title":"Machine Learning"},{"key":"5323_CR51","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1287\/moor.12.1.121","volume":"12","author":"J. Renegar","year":"1987","unstructured":"Renegar, J. (1987). On the efficiency of newton\u2019s method in approximating all zeros of a system of complex polynomials. Mathematics of Operations Research, 12, 121\u2013148.","journal-title":"Mathematics of Operations Research"},{"key":"5323_CR52","doi-asserted-by":"crossref","unstructured":"Renegar, J. (1995). Incorporating condition measures into the complexity theory of linear programming. SIAM Journal on Optimization, 5.","DOI":"10.1137\/0805026"},{"key":"5323_CR53","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex analysis","author":"R. T. Rockafellar","year":"1970","unstructured":"Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press."},{"key":"5323_CR54","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-006-0055-7","volume":"110","author":"H. R\u00f6glin","year":"2007","unstructured":"R\u00f6glin, H., & V\u00f6cking, B. (2007). Smoothed analysis of integer programming. Mathematical Programming, 110, 21\u201356.","journal-title":"Mathematical Programming"},{"key":"5323_CR55","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1137\/S0895479803436202","volume":"28","author":"A. Sankar","year":"2006","unstructured":"Sankar, A., Spielman, D. A., & Teng, S.-H. (2006). Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications, 28, 446\u2013476.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"5323_CR56","first-page":"1458","volume-title":"Advances in neural information processing systems","author":"M. Schmidt","year":"2011","unstructured":"Schmidt, M., Le Roux, N., & Bach, F. (2011). Convergence rates of inexact proximal-gradient methods for convex optimization. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, & K. Weinberger (Eds.), Advances in neural information processing systems (Vol.\u00a024, pp. 1458\u20131466)."},{"key":"5323_CR57","volume-title":"Learning with kernels","author":"B. Sch\u00f6lkopf","year":"2002","unstructured":"Sch\u00f6lkopf, B., & Smola, A. J. (2002). Learning with kernels. Cambridge: MIT Press."},{"key":"5323_CR58","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0378-3758(00)00115-4","volume":"90","author":"H. Shimodaira","year":"2000","unstructured":"Shimodaira, H. (2000). Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90, 227\u2013244.","journal-title":"Journal of Statistical Planning and Inference"},{"key":"5323_CR59","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/978-1-4612-2740-3_40","volume-title":"From topology to computation: proceedings of the smalefest","author":"M. Shub","year":"1993","unstructured":"Shub, M. (1993). Some remarks on B\u00e9zout\u2019s theorem and complexity theory. In From topology to computation: proceedings of the smalefest (pp. 443\u2013455). Berlin: Springer."},{"key":"5323_CR60","unstructured":"Shub, M., & Smale, S. (1994). Complexity of B\u00e9zout\u2019s theorem. V: polynomial time. Theoretical Computer Science, 133."},{"key":"5323_CR61","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0733008","volume":"33","author":"M. Shub","year":"1996","unstructured":"Shub, M., & Smale, S. (1996). Complexity of B\u00e9zout\u2019s theorem. IV: probability of success; extensions. SIAM Journal on Numerical Analysis, 33, 128\u2013148.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"5323_CR62","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2197\/ipsjtcva.3.1","volume":"3","author":"J. Simm","year":"2011","unstructured":"Simm, J., Sugiyama, M., & Kato, T. (2011). Computationally efficient multi-task learning with least-squares probabilistic classifiers. IPSJ Transactions on Computer Vision and Applications, 3, 1\u20138.","journal-title":"IPSJ Transactions on Computer Vision and Applications"},{"key":"5323_CR63","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","volume":"4","author":"S. Smale","year":"1981","unstructured":"Smale, S. (1981). The fundamental theorem of algebra and complexity theory. Bulletin of the American Mathematical Society, 4, 1\u201336.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"5323_CR64","first-page":"536","volume-title":"Twelfth international conference on artificial intelligence and statistics","author":"A. Smola","year":"2009","unstructured":"Smola, A., Song, L., & Teo, C. H. (2009). Relative novelty detection. In Twelfth international conference on artificial intelligence and statistics (pp. 536\u2013543)."},{"key":"5323_CR65","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D. A. Spielman","year":"2004","unstructured":"Spielman, D. A., & Teng, S.-H. (2004). Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51, 385\u2013463.","journal-title":"Journal of the ACM"},{"key":"5323_CR66","volume-title":"A comprehensive introduction to differential geometry","author":"M. Spivak","year":"1979","unstructured":"Spivak, M. (1979). A comprehensive introduction to differential geometry (Vol.\u00a0I) (2nd ed.). Berkley: Publish or Perish.","edition":"2"},{"key":"5323_CR67","first-page":"67","volume":"2","author":"I. Steinwart","year":"2001","unstructured":"Steinwart, I. (2001). On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research, 2, 67\u201393.","journal-title":"Journal of Machine Learning Research"},{"key":"5323_CR68","doi-asserted-by":"crossref","first-page":"2690","DOI":"10.1587\/transinf.E93.D.2690","volume":"E93-D","author":"M. Sugiyama","year":"2010","unstructured":"Sugiyama, M. (2010). Superfast-trainable multi-class probabilistic classifier by least-squares posterior fitting. IEICE Transactions on Information and Systems, E93-D, 2690\u20132701.","journal-title":"IEICE Transactions on Information and Systems"},{"key":"5323_CR69","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9780262017091.001.0001","volume-title":"Machine learning in non-stationary environments: Introduction to covariate shift adaptation","author":"M. Sugiyama","year":"2012","unstructured":"Sugiyama, M., & Kawanabe, M. (2012). Machine learning in non-stationary environments: Introduction to covariate shift adaptation. Cambridge: MIT Press."},{"key":"5323_CR70","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1524\/stnd.2005.23.4.249","volume":"23","author":"M. Sugiyama","year":"2005","unstructured":"Sugiyama, M., & M\u00fcller, K.-R. (2005). Input-dependent estimation of generalization error under covariate shift. Statistics & Decisions, 23, 249\u2013279.","journal-title":"Statistics & Decisions"},{"key":"5323_CR71","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1587\/transinf.E94.D.1333","volume":"E94-D","author":"M. Sugiyama","year":"2011","unstructured":"Sugiyama, M., & Suzuki, T. (2011). Least-squares independence test. IEICE Transactions on Information and Systems, E94-D, 1333\u20131336.","journal-title":"IEICE Transactions on Information and Systems"},{"key":"5323_CR72","first-page":"985","volume":"8","author":"M. Sugiyama","year":"2007","unstructured":"Sugiyama, M., Krauledat, M., & M\u00fcller, K.-R. (2007). Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8, 985\u20131005.","journal-title":"Journal of Machine Learning Research"},{"key":"5323_CR73","first-page":"1433","volume-title":"Advances in neural information processing systems","author":"M. Sugiyama","year":"2008","unstructured":"Sugiyama, M., Nakajima, S., Kashima, H., von B\u00fcnau, P., & Kawanabe, M. (2008a). Direct importance estimation with model selection and its application to covariate shift adaptation. In Advances in neural information processing systems (Vol.\u00a020, pp. 1433\u20131440). Cambridge: MIT Press."},{"key":"5323_CR74","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/s10463-008-0197-x","volume":"60","author":"M. Sugiyama","year":"2008","unstructured":"Sugiyama, M., Suzuki, T., Nakajima, S., Kashima, H., von B\u00fcnau, P., Kawanabe, M., & Nakajima, S. (2008b). Direct importance estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematics, 60, 699\u2013746.","journal-title":"Annals of the Institute of Statistical Mathematics"},{"key":"5323_CR75","doi-asserted-by":"crossref","first-page":"183","DOI":"10.2197\/ipsjtcva.1.183","volume":"1","author":"M. Sugiyama","year":"2009","unstructured":"Sugiyama, M., Kanamori, T., Suzuki, T., Hido, S., Sese, J., Takeuchi, I., & Wang, L. (2009). A density-ratio framework for statistical data processing. IPSJ Transactions on Computer Vision and Applications, 1, 183\u2013208.","journal-title":"IPSJ Transactions on Computer Vision and Applications"},{"key":"5323_CR76","first-page":"781","volume-title":"Proceedings of the thirteenth international conference on artificial intelligence and statistics (AISTATS2010)","author":"M. Sugiyama","year":"2010","unstructured":"Sugiyama, M., Takeuchi, I., Kanamori, T., Suzuki, T., Hachiya, H., & Okanohara, D. (2010a). Conditional density estimation via least-squares density ratio estimation. In Proceedings of the thirteenth international conference on artificial intelligence and statistics (AISTATS2010), Sardinia, Italy (pp. 781\u2013788)."},{"key":"5323_CR77","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1587\/transinf.E93.D.583","volume":"E93-D","author":"M. Sugiyama","year":"2010","unstructured":"Sugiyama, M., Takeuchi, I., Suzuki, T., Kanamori, T., Hachiya, H., & Okanohara, D. (2010b). Least-squares conditional density estimation. IEICE Transactions on Information and Systems, E93-D, 583\u2013594.","journal-title":"IEICE Transactions on Information and Systems"},{"key":"5323_CR78","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1016\/j.neunet.2011.04.003","volume":"24","author":"M. Sugiyama","year":"2011","unstructured":"Sugiyama, M., Suzuki, T., Itoh, Y., Kanamori, T., & Kimura, M. (2011). Least-squares two-sample test. Neural Networks, 24, 735\u2013751.","journal-title":"Neural Networks"},{"key":"5323_CR79","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1007\/s10463-011-0343-8","volume":"64","author":"M. Sugiyama","year":"2012","unstructured":"Sugiyama, M., Suzuki, T., & Kanamori, T. (2012a). Density ratio matching under the Bregman divergence: A unified framework of density ratio estimation. Annals of the Institute of Statistical Mathematics, 64, 1009\u20131044.","journal-title":"Annals of the Institute of Statistical Mathematics"},{"key":"5323_CR80","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139035613","volume-title":"Density ratio estimation in machine learning","author":"M. Sugiyama","year":"2012","unstructured":"Sugiyama, M., Suzuki, T., & Kanamori, T. (2012b). Density ratio estimation in machine learning. Cambridge: Cambridge University Press."},{"key":"5323_CR81","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1162\/NECO_a_00062","volume":"23","author":"T. Suzuki","year":"2011","unstructured":"Suzuki, T., & Sugiyama, M. (2011). Least-squares independent component analysis. Neural Computation, 23, 284\u2013301.","journal-title":"Neural Computation"},{"key":"5323_CR82","first-page":"5","volume-title":"JMLR workshop and conference proceedings","author":"T. Suzuki","year":"2008","unstructured":"Suzuki, T., Sugiyama, M., Sese, J., & Kanamori, T. (2008). Approximating mutual information by maximum likelihood density ratio estimation. In JMLR workshop and conference proceedings (pp. 5\u201320)."},{"key":"5323_CR83","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-10-167","volume":"10","author":"T. Suzuki","year":"2009","unstructured":"Suzuki, T., Sugiyama, M., Kanamori, T., & Sese, J. (2009a). Mutual information estimation reveals global associations between stimuli and biological processes. BMC Bioinformatics, 10, S52.","journal-title":"BMC Bioinformatics"},{"key":"5323_CR84","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1109\/ISIT.2009.5205712","volume-title":"Proceedings of 2009 IEEE international symposium on information theory (ISIT2009)","author":"T. Suzuki","year":"2009","unstructured":"Suzuki, T., Sugiyama, M., & Tanaka, T. (2009b). Mutual information approximation via maximum likelihood estimation of density ratio. In Proceedings of 2009 IEEE international symposium on information theory (ISIT2009), Seoul, Korea (pp. 463\u2013467)."},{"key":"5323_CR85","first-page":"248","volume-title":"Proceedings of the thirty-ninth annual ACM symposium on theory of computing","author":"T. Tao","year":"2007","unstructured":"Tao, T., & Vu, V. H. (2007). The condition number of a randomly perturbed matrix. In Proceedings of the thirty-ninth annual ACM symposium on theory of computing (pp. 248\u2013255). New York: ACM."},{"key":"5323_CR86","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/PL00011420","volume":"90","author":"M. J. Todd","year":"2001","unstructured":"Todd, M. J., Tun\u00e7el, L., & Ye, Y. (2001). Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems. Mathematical Programming, 90, 59\u201369.","journal-title":"Mathematical Programming"},{"key":"5323_CR87","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","volume":"1","author":"A. M. Turing","year":"1948","unstructured":"Turing, A. M. (1948). Rounding-off errors in matrix processes. Quarterly Journal of Mechanics and Applied Mathematics, 1, 287\u2013308.","journal-title":"Quarterly Journal of Mechanics and Applied Mathematics"},{"key":"5323_CR88","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1109\/FOCS.2006.19","volume-title":"FOCS 2006 (47th annual symposium on foundations of computer science","author":"R. Vershynin","year":"2006","unstructured":"Vershynin, R. (2006). Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. In FOCS 2006 (47th annual symposium on foundations of computer science (pp.\u00a0133\u2013142)."},{"key":"5323_CR89","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1090\/S0002-9904-1947-08909-6","volume":"53","author":"J. Neumann von","year":"1947","unstructured":"von Neumann, J., & Goldstine, H. (1947). Numerical inverting of matrices of high order. Bulletin of the American Mathematical Society, 53, 1021\u20131099.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"5323_CR90","first-page":"643","volume-title":"Proceedings of the twenty-fourth AAAI conference on artificial intelligence (AAAI2010)","author":"M. Yamada","year":"2010","unstructured":"Yamada, M., & Sugiyama, M. (2010). Dependence minimizing regression with model selection for non-linear causal inference under non-Gaussian noise. In Proceedings of the twenty-fourth AAAI conference on artificial intelligence (AAAI2010) (pp. 643\u2013648). Atlanta: AAAI Press."},{"key":"5323_CR91","first-page":"807","volume-title":"Proceedings of the fourteenth international conference on artificial intelligence and statistics (AISTATS2011)","author":"M. Yamada","year":"2011","unstructured":"Yamada, M., & Sugiyama, M. (2011). Cross-domain object matching with model selection. In Proceedings of the fourteenth international conference on artificial intelligence and statistics (AISTATS2011), Fort Lauderdale, Florida, USA (pp. 807\u2013815)."},{"key":"5323_CR92","volume-title":"Proceedings of the Twenty-First international conference on machine learning","author":"B. Zadrozny","year":"2004","unstructured":"Zadrozny, B. (2004). Learning and evaluating classifiers under sample selection bias. In Proceedings of the Twenty-First international conference on machine learning. New York: ACM."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-012-5323-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-012-5323-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-012-5323-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T04:51:04Z","timestamp":1714711864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-012-5323-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,12]]},"references-count":92,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["5323"],"URL":"https:\/\/doi.org\/10.1007\/s10994-012-5323-6","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,12]]}}}