{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T08:08:08Z","timestamp":1791446888242,"version":"4.3.3"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-14-1-0313 P00003"],"award-info":[{"award-number":["N00014-14-1-0313 P00003"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1620070"],"award-info":[{"award-number":["DMS-1620070"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-0810213"],"award-info":[{"award-number":["DMS-0810213"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FG02-87ER25047"],"award-info":[{"award-number":["DE-FG02-87ER25047"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper, we propose a stochastic optimization method that adaptively controls the sample size used in the computation of gradient approximations. Unlike other variance reduction techniques that either require additional storage or the regular computation of full gradients, the proposed method reduces variance by increasing the sample size as needed. The decision to increase the sample size is governed by an inner product test that ensures that search directions are descent directions with high probability. We show that the inner product test improves upon the well-known norm test, and can be used as a basis for an algorithm that is globally convergent on nonconvex functions and enjoys a global linear rate of convergence on strongly convex functions. Numerical experiments on logistic regression and nonlinear least squares problems illustrate the performance of the algorithm.<\/jats:p>","DOI":"10.1137\/17m1154679","type":"journal-article","created":{"date-parts":[[2018,12,13]],"date-time":"2018-12-13T10:52:51Z","timestamp":1544698371000},"page":"3312-3343","source":"Crossref","is-referenced-by-count":90,"title":["Adaptive Sampling Strategies for Stochastic Optimization"],"prefix":"10.1137","volume":"28","author":[{"given":"Raghu","family":"Bollapragada","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Byrd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorge","family":"Nocedal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,12,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.016"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb3","unstructured":"D. P. Bertsekas,\n                      Convex Optimization Algorithms\n                      , Athena Scientific, Belmont, MA, 2015."},{"key":"atypb4","unstructured":"D. P. Bertsekas, A. Nedi\u0107, and A. E. Ozdaglar,\n                      Convex Analysis and Optimization\n                      , Athena Scientific, Belmont, MA, 2003."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-1699(99)00046-0"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"R. Bollapragada, R. H. Byrd, and J. Nocedal,\n                      Exact and inexact subsampled Newton methods for optimization\n                      , IMA J. Numer. Anal. (2018),https:\/\/doi.org\/10.1093\/imanum\/dry009.","DOI":"10.1093\/imanum\/dry009"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080173"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0572-5"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0728014"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1137-4"},{"key":"atypb11","first-page":"1504","volume":"54","author":"De S.","year":"2017","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb12","first-page":"1646","author":"Defazio A.","year":"2014","journal-title":"NY"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/110830629"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/120880811"},{"key":"atypb15","first-page":"545","author":"Guyon I.","year":"2004","journal-title":"NY"},{"key":"atypb16","first-page":"3959","author":"Hashemi F. S.","year":"2014","journal-title":"NJ"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/858481.858483"},{"key":"atypb18","first-page":"315","author":"Johnson R.","year":"2013","journal-title":"NY"},{"key":"atypb19","unstructured":"Y. LeCun, C. Cortes, and C. J. Burges,\n                      The MNIST Database of Handwritten Digits\n                      ,http:\/\/yann.lecun.com\/exdb\/mnist, 2010."},{"key":"atypb20","unstructured":"M. Lichman,\n                      UCI Machine Learning Repository\n                      ,http:\/\/archive.ics.uci.edu\/ml, 2013."},{"key":"atypb21","first-page":"17","author":"Mukherjee I.","year":"2013","journal-title":"Berlin"},{"key":"atypb22","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Appl. Optim. 87, Springer, New York, 2013."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/140951679"},{"key":"atypb24","unstructured":"F. Roosta-Khorasani and M. W. Mahoney,\n                      Sub-Sampled Newton Methods \u016dshape I: Globally Convergent Algorithms\n                      , preprint,https:\/\/arxiv.org\/abs\/1601.04737, 2016."},{"key":"atypb25","unstructured":"F. Roosta-Khorasani and M. W. Mahoney,\n                      Sub-Sampled Newton Methods \u016dshape II: Local Convergence Rates\n                      , preprint,https:\/\/arxiv.org\/abs\/1601.04738, 2016."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1163"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1030-6"},{"key":"atypb28","unstructured":"P. Xu, F. Roosta-Khorasan, and M. W. Mahoney,\n                      Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study\n                      , preprint,https:\/\/arxiv.org\/abs\/1708.07827, 2017."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1154679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:56Z","timestamp":1787338376000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1154679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1154679"],"URL":"https:\/\/doi.org\/10.1137\/17m1154679","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}