{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:56:53Z","timestamp":1760385413029},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,1,17]],"date-time":"2015-01-17T00:00:00Z","timestamp":1421452800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s10107-015-0860-y","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T04:20:28Z","timestamp":1421382028000},"page":"497-510","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A deterministic rescaled perceptron algorithm"],"prefix":"10.1007","volume":"155","author":[{"given":"Javier","family":"Pe\u00f1a","sequence":"first","affiliation":[]},{"given":"Negar","family":"Soheili","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,1,17]]},"reference":[{"issue":"3","key":"860_CR1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.4153\/CJM-1954-037-2","volume":"6","author":"S Agmon","year":"1954","unstructured":"Agmon, S.: The relaxation method for linear inequalities. Can. J. Math. 6(3), 382\u2013392 (1954)","journal-title":"Can. J. Math."},{"key":"860_CR2","doi-asserted-by":"crossref","unstructured":"Amaldi, E., Belotti, P., Hauser, R.: A randomized algorithm for the maxFS problem. In: IPCO, pp. 249\u2013264 (2005)","DOI":"10.1007\/11496915_19"},{"issue":"4","key":"860_CR3","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1287\/moor.1050.0164","volume":"30","author":"E Amaldi","year":"2005","unstructured":"Amaldi, E., Hauser, R.: Boundedness theorems for the relaxation method. Math. Oper. Res. 30(4), 939\u2013955 (2005)","journal-title":"Math. Oper. Res."},{"key":"860_CR4","unstructured":"Ball, K.: An Elementary Introduction to Modern Convex Geometry. Flavors of Geometry, vol. 31, pp. 1\u201358. Cambridge University Press, Cambridge (1997)"},{"key":"860_CR5","first-page":"27","volume":"4","author":"HH Bauschke","year":"1997","unstructured":"Bauschke, H.H., Borwein, J.M.: Legendre functions and the method of random Bregman projections. J. Convex Anal. 4, 27\u201367 (1997)","journal-title":"J. Convex Anal."},{"key":"860_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/204\/02620","volume":"204","author":"HH Bauschke","year":"1997","unstructured":"Bauschke, H.H., Borwein, J.M., Lewis, A.: The method of cyclic projections for closed convex sets in Hilbert space. Contemp. Math. 204, 1\u201338 (1997)","journal-title":"Contemp. Math."},{"issue":"3","key":"860_CR7","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1287\/moor.1090.0388","volume":"34","author":"A Belloni","year":"2009","unstructured":"Belloni, A., Freund, R., Vempala, S.: An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3), 621\u2013641 (2009)","journal-title":"Math. Oper. Res."},{"key":"860_CR8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00454-004-2878-4","volume":"32","author":"U Betke","year":"2004","unstructured":"Betke, U.: Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geom. 32, 317\u2013338 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"860_CR9","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1103\/RevModPhys.34.123","volume":"34","author":"HD Block","year":"1962","unstructured":"Block, H.D.: The perceptron: a model for brain functioning. Rev. Mod. Phys. 34, 123\u2013135 (1962)","journal-title":"Rev. Mod. Phys."},{"issue":"1\u20132","key":"860_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/PL00013833","volume":"22","author":"A Blum","year":"1998","unstructured":"Blum, A., Frieze, A., Kannan, R., Vempala, S.: A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica 22(1\u20132), 35\u201352 (1998)","journal-title":"Algorithmica"},{"key":"860_CR11","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/s10107-011-0445-3","volume":"134","author":"S Chubanov","year":"2012","unstructured":"Chubanov, S.: A strongly polynomial algorithm for linear systems having a binary solution. Math. Program. 134, 533\u2013570 (2012)","journal-title":"Math. Program."},{"issue":"1","key":"860_CR12","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s10107-007-0095-7","volume":"114","author":"J Dunagan","year":"2006","unstructured":"Dunagan, J., Vempala, S.: A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program. 114(1), 101\u2013114 (2006)","journal-title":"Math. Program."},{"key":"860_CR13","doi-asserted-by":"crossref","unstructured":"Fleming, W.: Functions of Several Variables. Springer, New York (1977)","DOI":"10.1007\/978-1-4684-9461-7"},{"key":"860_CR14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1023\/A:1007662407062","volume":"37","author":"Y Freund","year":"1999","unstructured":"Freund, Y., Schapire, R.: Large margin classification using the perceptron algorithm. Mach. Learn. 37, 277\u2013296 (1999)","journal-title":"Mach. Learn."},{"key":"860_CR15","doi-asserted-by":"crossref","unstructured":"Gilpin, A., Pe\u00f1a, J., Sandholm, T.: First-order algorithm with $${\\cal {O}}({\\ln }(1\/\\epsilon ))$$ O ( ln ( 1 \/ \u03f5 ) ) convergence for $$\\epsilon $$ \u03f5 -equilibrium in two-person zero-sum games. Math. Program. 133, 279\u2013298 (2012)","DOI":"10.1007\/s10107-010-0430-2"},{"key":"860_CR16","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/moor.5.3.388","volume":"5","author":"J Goffin","year":"1980","unstructured":"Goffin, J.: The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5, 388\u2013414 (1980)","journal-title":"Math. Oper. Res."},{"key":"860_CR17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01581028","volume":"22","author":"J Goffin","year":"1982","unstructured":"Goffin, J.: On the non-polynomiality of the relaxation method for systems of linear inequalities. Math. Program. 22, 93\u2013103 (1982)","journal-title":"Math. Program."},{"key":"860_CR18","doi-asserted-by":"crossref","first-page":"301","DOI":"10.2307\/2321716","volume":"89","author":"G Huber","year":"1982","unstructured":"Huber, G.: Gamma function derivation of $$n$$ n -sphere volumes. Am. Math. Mon. 89, 301\u2013302 (1982)","journal-title":"Am. Math. Mon."},{"issue":"3","key":"860_CR19","doi-asserted-by":"crossref","first-page":"393","DOI":"10.4153\/CJM-1954-038-x","volume":"6","author":"TS Motzkin","year":"1954","unstructured":"Motzkin, T.S., Schoenberg, I.J.: The relaxation method for linear inequalities. Can. J. Math. 6(3), 393\u2013404 (1954)","journal-title":"Can. J. Math."},{"key":"860_CR20","unstructured":"Novikoff, A.B.J.: On convergence proofs on perceptrons. In: Proceedings of the Symposium on the Mathematical Theory of Automata, vol. XII, pp. 615\u2013622 (1962)"},{"key":"860_CR21","doi-asserted-by":"crossref","unstructured":"O\u2019Donoghue, B., Cand\u00e8s, E.J.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. (2013) doi: 10.1007\/s10208-013-9150-3","DOI":"10.1007\/s10208-013-9150-3"},{"issue":"6","key":"860_CR22","first-page":"386","volume":"65","author":"F Rosenblatt","year":"1958","unstructured":"Rosenblatt, F.: The perceptron: a probabilistic model for information storage and organization in the brain. Cornell Aeronaut. Lab. Psychol. Rev. 65(6), 386\u2013408 (1958)","journal-title":"Cornell Aeronaut. Lab. Psychol. Rev."},{"key":"860_CR23","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-010-0420-4","volume":"127","author":"S Shalev-Shwartz","year":"2011","unstructured":"Shalev-Shwartz, S., Singer, Y., Srebro, N., Cotter, A.: Pegasos: primal estimated sub-gradient solver for SVM. Math. Program. 127, 3\u201330 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"860_CR24","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1137\/110848955","volume":"22","author":"N Soheili","year":"2012","unstructured":"Soheili, N., Pe\u00f1a, J.: A smooth perceptron algorithm. SIAM J. Optim. 22(2), 728\u2013737 (2012)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0860-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0860-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0860-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T19:29:17Z","timestamp":1566242957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0860-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,17]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["860"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0860-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,17]]}}}