{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T18:40:08Z","timestamp":1775155208471,"version":"3.50.1"},"reference-count":83,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10208-021-09499-8","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T20:10:31Z","timestamp":1616184631000},"page":"35-76","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Zeroth-Order Nonconvex Stochastic Optimization: Handling Constraints, High Dimensionality, and Saddle Points"],"prefix":"10.1007","volume":"22","author":[{"given":"Krishnakumar","family":"Balasubramanian","sequence":"first","affiliation":[]},{"given":"Saeed","family":"Ghadimi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,19]]},"reference":[{"key":"9499_CR1","unstructured":"Agarwal, A., Dekel, O., Xiao, L.: Optimal algorithms for online convex optimization with multi-point bandit feedback. In: Proceedings of The 23rd Conference on Learning Theory, pp. 28\u201340 (2010)"},{"key":"9499_CR2","unstructured":"Akhavan, A., Pontil, M., Tsybakov, A.: Exploiting higher order smoothness in derivative-free optimization and continuous bandits. In: Advances in Neural Information Processing Systems, vol.\u00a033 (2020)"},{"key":"9499_CR3","unstructured":"Allen-Zhu, Z.: Natasha 2: Faster non-convex optimization than SGD. In: Advances in Neural Information Processing Systems, pp. 2680\u20132691 (2018)"},{"key":"9499_CR4","unstructured":"Bach, F., Perchet, V.: Highly-smooth zero-th order online optimization. In: V.\u00a0Feldman, A.\u00a0Rakhlin, O.\u00a0Shamir (eds.) 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, vol.\u00a049, pp. 257\u2013283. PMLR (2016)"},{"key":"9499_CR5","doi-asserted-by":"crossref","unstructured":"Beck, A.: First-Order Methods in Optimization, vol.\u00a025. Society for Industrial and Applied Mathematics (SIAM) (2017)","DOI":"10.1137\/1.9781611974997"},{"key":"9499_CR6","unstructured":"Belloni, A., Liang, T., Narayanan, H., Rakhlin, A.: Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In: P.\u00a0Grunwald, E.\u00a0Hazan, S.\u00a0Kale (eds.) Proceedings of The 28th Conference on Learning Theory, Proceedings of Machine Learning Research, vol.\u00a040, pp. 240\u2013265. PMLR (2015)"},{"key":"9499_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications, vol.\u00a02. Society for Industrial and Applied Mathematics (SIAM) (2001)","DOI":"10.1137\/1.9780898718829"},{"key":"9499_CR8","unstructured":"Bertsekas, D.P.: Nonlinear programming. Athena scientific Belmont (2016)"},{"key":"9499_CR9","unstructured":"Bertsekas, D.P., Scientific, A.: Convex optimization algorithms. Athena Scientific Belmont (2015)"},{"key":"9499_CR10","unstructured":"Bhojanapalli, S., Neyshabur, B., Srebro, N.: Global optimality of local search for low rank matrix recovery. In: Advances in Neural Information Processing Systems, pp. 3873\u20133881 (2016)"},{"key":"9499_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press (2004)"},{"key":"9499_CR12","doi-asserted-by":"crossref","unstructured":"Bubeck, S., Cesa-Bianchi, N.: Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends\u00ae in Machine Learning 5(1), 1\u2013122 (2012)","DOI":"10.1561\/2200000024"},{"key":"9499_CR13","doi-asserted-by":"crossref","unstructured":"Bubeck, S., Lee, Y.T., Eldan, R.: Kernel-based methods for bandit convex optimization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 72\u201385 (2017)","DOI":"10.1145\/3055399.3055403"},{"key":"9499_CR14","unstructured":"Cai, H., Mckenzie, D., Yin, W., Zhang, Z.: Zeroth-order regularized optimization (ZORO): Approximately sparse gradients and adaptive sampling (2020)"},{"issue":"2","key":"9499_CR15","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.1137\/17M1114296","volume":"28","author":"Y Carmon","year":"2018","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Accelerated methods for nonconvex optimization. SIAM Journal on Optimization 28(2), 1751\u20131772 (2018)","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"9499_CR16","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10107-009-0286-5","volume":"127","author":"C Cartis","year":"2011","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization, Part I: Motivation, convergence and numerical results. Mathematical Programming 127(2), 245\u2013295 (2011)","journal-title":"Mathematical Programming"},{"issue":"2","key":"9499_CR17","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10107-009-0337-y","volume":"130","author":"C Cartis","year":"2011","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization, Part II: Worst-case function-and derivative-evaluation complexity. Mathematical programming 130(2), 295\u2013319 (2011)","journal-title":"Mathematical Programming"},{"issue":"5","key":"9499_CR18","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1007\/s10208-017-9363-y","volume":"18","author":"C Cartis","year":"2018","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: Second-order optimality and beyond: Characterization and evaluation complexity in convexly constrained nonlinear optimization. Foundations of Computational Mathematics 18(5), 1073\u20131107 (2018)","journal-title":"Foundations of Computational Mathematics"},{"key":"9499_CR19","unstructured":"Chen, L., Zhang, M., Hassani, H., Karbasi, A.: Black box submodular maximization: Discrete and continuous settings. In: S.\u00a0Chiappa, R.\u00a0Calandra (eds.) Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 108, pp. 1058\u20131070 (2020)"},{"key":"9499_CR20","doi-asserted-by":"crossref","unstructured":"Chen, P.Y., Zhang, H., Sharma, Y., Yi, J., Hsieh, C.J.: ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In: Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15\u201326. ACM (2017)","DOI":"10.1145\/3128572.3140448"},{"key":"9499_CR21","unstructured":"Choromanski, K., Rowland, M., Sindhwani, V., Turner, R., Weller, A.: Structured evolution with compact architectures for scalable policy optimization. In: Proceedings of the 35th International Conference on Machine Learning. PMLR (2018)"},{"key":"9499_CR22","doi-asserted-by":"crossref","unstructured":"Conn, A., Scheinberg, K., Vicente, L.: Introduction to derivative-free optimization, vol.\u00a08. Society of Industrial and Applied Mathematics (SIAM) (2009)","DOI":"10.1137\/1.9780898718768"},{"key":"9499_CR23","unstructured":"Dani, V., Kakade, S.M., Hayes, T.P.: The price of bandit information for online optimization. In: Advances in Neural Information Processing Systems, pp. 345\u2013352 (2008)"},{"key":"9499_CR24","unstructured":"Demyanov, V., Rubinov, A.: Approximate methods in optimization problems. American Elsevier Publishing (1970)"},{"issue":"1","key":"9499_CR25","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00365-010-9105-8","volume":"33","author":"R DeVore","year":"2011","unstructured":"DeVore, R., Petrova, G., Wojtaszczyk, P.: Approximation of functions of few variables in high dimensions. Constructive Approximation 33(1), 125\u2013143 (2011)","journal-title":"Constructive Approximation"},{"issue":"4","key":"9499_CR26","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Transactions on information theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Transactions on information theory"},{"issue":"5","key":"9499_CR27","doi-asserted-by":"publisher","first-page":"2788","DOI":"10.1109\/TIT.2015.2409256","volume":"61","author":"J Duchi","year":"2015","unstructured":"Duchi, J., Jordan, M., Wainwright, M., Wibisono, A.: Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory 61(5), 2788\u20132806 (2015)","journal-title":"IEEE Transactions on Information Theory"},{"key":"9499_CR28","unstructured":"Elibol, M., Lei, L., Jordan, M.I.: Variance reduction with sparse gradients. In: Proceedings of the 8th International Conference on Learning Representations (ICLR), pp. 1058\u20131070 (2020)"},{"issue":"1","key":"9499_CR29","first-page":"7565","volume":"17","author":"MA Erdogdu","year":"2016","unstructured":"Erdogdu, M.A.: Newton-Stein method: an optimization method for GLMs via Stein\u2019s lemma. The Journal of Machine Learning Research 17(1), 7565\u20137616 (2016)","journal-title":"The Journal of Machine Learning Research"},{"key":"9499_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 95\u2013110 (1956)","journal-title":"Naval Research Logistics Quarterly"},{"key":"9499_CR31","doi-asserted-by":"crossref","unstructured":"Gasnikov, A.V., Krymova, E.A., Lagunovskaya, A.A., Usmanova, I.N., Fedorenko, F.A.: Stochastic online optimization. single-point and multi-point non-linear multi-armed bandits. convex and strongly-convex case. Automation and remote control 78(2), 224\u2013234 (2017)","DOI":"10.1134\/S0005117917020035"},{"key":"9499_CR32","unstructured":"Ge, R., Huang, F., Jin, C., Yuan, Y.: Escaping from saddle points: Online stochastic gradient for tensor decomposition. In: Conference on Learning Theory, pp. 797\u2013842 (2015)"},{"key":"9499_CR33","unstructured":"Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. In: Advances in Neural Information Processing Systems, pp. 2973\u20132981 (2016)"},{"key":"9499_CR34","doi-asserted-by":"publisher","unstructured":"Ghadimi, S.: Conditional gradient type methods for composite nonlinear and stochastic optimization. Mathematical Programming (2018). https:\/\/doi.org\/10.1007\/s10107-017-1225-5","DOI":"10.1007\/s10107-017-1225-5"},{"issue":"4","key":"9499_CR35","doi-asserted-by":"publisher","first-page":"2341","DOI":"10.1137\/120880811","volume":"23","author":"S Ghadimi","year":"2013","unstructured":"Ghadimi, S., Lan, G.: Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization 23(4), 2341\u20132368 (2013)","journal-title":"SIAM Journal on Optimization"},{"key":"9499_CR36","doi-asserted-by":"publisher","first-page":"101443","DOI":"10.1016\/j.jco.2019.101443","volume":"57","author":"C Han","year":"2020","unstructured":"Han, C., Yuan, M.: Information based complexity for high dimensional sparse functions. Journal of Complexity 57, 101443 (2020)","journal-title":"Journal of Complexity"},{"key":"9499_CR37","unstructured":"Hazan, E., Kale, S.: Projection-free online learning. In: Proceedings of the 29th International Conference on International Conference on Machine Learning, pp. 1843\u20131850 (2012)"},{"key":"9499_CR38","unstructured":"Hazan, E., Levy, K.: Bandit convex optimization: Towards tight bounds. In: Advances in Neural Information Processing Systems, pp. 784\u2013792 (2014)"},{"key":"9499_CR39","unstructured":"Hazan, E., Luo, H.: Variance-reduced and projection-free stochastic optimization. In: International Conference on Machine Learning, pp. 1263\u20131271 (2016)"},{"key":"9499_CR40","first-page":"95","volume":"2","author":"D Hearn","year":"1982","unstructured":"Hearn, D.: The gap function of a convex program. Operations Research Letters 2, 95\u2013110 (1982)","journal-title":"Operations Research Letters"},{"key":"9499_CR41","unstructured":"Hu, X., Prashanth, L.A., Gy\u00f6rgy, A., Szepesvari, C.: (Bandit) Convex Optimization with Biased Noisy Gradient Oracles. In: The 19th International Conference on Artificial Intelligence and Statistics, pp. 3420\u20133428 (2016)"},{"key":"9499_CR42","unstructured":"Jaggi, M.: Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. In: Proceedings of the 30th International Conference on International Conference on Machine Learning, pp. 427\u2013435 (2013)"},{"key":"9499_CR43","doi-asserted-by":"crossref","unstructured":"Jain, P., Kar, P.: Non-convex optimization for machine learning.Foundations and Trends\u00ae in Machine Learning 10(3-4), 142\u2013336 (2017)","DOI":"10.1561\/2200000058"},{"key":"9499_CR44","unstructured":"Jain, P., Tewari, A., Kar, P.: On iterative hard thresholding methods for high-dimensional m-estimation. In: Advances in Neural Information Processing Systems, pp. 685\u2013693 (2014)"},{"key":"9499_CR45","unstructured":"Jamieson, K., Nowak, R., Recht, B.: Query complexity of derivative-free optimization. In: Advances in Neural Information Processing Systems, pp. 2672\u20132680 (2012)"},{"key":"9499_CR46","unstructured":"Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. In: International Conference on Machine Learning, pp. 1724\u20131732 (2017)"},{"key":"9499_CR47","unstructured":"Kawaguchi, K., Kaelbling, L.P.: Elimination of all bad local minima in deep learning. arXiv:1901.00279"},{"issue":"2","key":"9499_CR48","doi-asserted-by":"publisher","first-page":"1379","DOI":"10.1137\/140992382","volume":"26","author":"G Lan","year":"2016","unstructured":"Lan, G., Zhou, Y.: Conditional gradient sliding for convex optimization. SIAM Journal on Optimization 26(2), 1379\u20131409 (2016)","journal-title":"SIAM Journal on Optimization"},{"key":"9499_CR49","unstructured":"Lattimore, T.: Improved regret for zeroth-order adversarial bandit convex optimisation. arXiv:2006.00475"},{"key":"9499_CR50","unstructured":"Li, J., Balasubramanian, K., Ma, S.: Stochastic zeroth-order riemannian derivative estimation and optimization. arXiv:2003.11238 (2020)"},{"key":"9499_CR51","unstructured":"Mania, H., Guy, A., Recht, B.: Simple random search provides a competitive approach to reinforcement learning. In: Advances in Neural Information Processing Systems (2018)"},{"issue":"6A","key":"9499_CR52","doi-asserted-by":"publisher","first-page":"2871","DOI":"10.1214\/17-AOS1642","volume":"46","author":"S Minsker","year":"2018","unstructured":"Minsker, S.: Sub-gaussian estimators of the mean of a random matrix with heavy-tailed entries. The Annals of Statistics 46(6A), 2871\u20132903 (2018)","journal-title":"The Annals of Statistics"},{"key":"9499_CR53","unstructured":"Mockus, J.: Bayesian approach to global optimization: theory and applications, vol.\u00a037. Springer Science & Business Media (2012)"},{"key":"9499_CR54","unstructured":"Mokhtari, A., Hassani, H., Karbasi, A.: Conditional gradient method for stochastic submodular maximization: Closing the gap. In: International Conference on Artificial Intelligence and Statistics, pp. 1886\u20131895 (2018)"},{"key":"9499_CR55","first-page":"1","volume":"21","author":"A Mokhtari","year":"2020","unstructured":"Mokhtari, A., Hassani, H., Karbasi, A.: Stochastic conditional gradient methods: From convex minimization to submodular maximization. Journal of Machine Learning Research 21, 1\u201349 (2020)","journal-title":"Journal of Machine Learning Research"},{"issue":"2","key":"9499_CR56","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Mathematical programming 39(2), 117\u2013129 (1987)","journal-title":"Mathematical Programming"},{"key":"9499_CR57","volume-title":"Problem complexity and method efficiency in optimization","author":"AS Nemirovski","year":"1983","unstructured":"Nemirovski, A.S., Yudin, D.: Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV (1983)"},{"key":"9499_CR58","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: a basic course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: a basic course. Kluwer Academic Publishers, Massachusetts (2004)"},{"key":"9499_CR59","unstructured":"Nesterov, Y.: Introductory lectures on convex optimization: A basic course, vol.\u00a087. Springer Science & Business Media (2013)"},{"issue":"1","key":"9499_CR60","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Y Nesterov","year":"2006","unstructured":"Nesterov, Y., Polyak, B.: Cubic regularization of newton method and its global performance. Mathematical Programming 108(1), 177\u2013205 (2006)","journal-title":"Mathematical Programming"},{"key":"9499_CR61","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s10208-015-9296-2","volume":"17","author":"Y Nesterov","year":"2017","unstructured":"Nesterov, Y., Spokoiny, V.: Random gradient-free minimization of convex functions. Foundations of Computational Mathematics 17, 527\u2013566 (2017)","journal-title":"Foundations of Computational Mathematics"},{"key":"9499_CR62","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s10107-019-01449-1","volume":"186","author":"Y Nestrov","year":"2021","unstructured":"Nestrov, Y.: Implementable tensor methods in unconstrained convex optimization. Mathematical Programming 186, 157\u2013183 (2021)","journal-title":"Mathematical Programming"},{"key":"9499_CR63","unstructured":"Nocedal, J., Wright, S.J.: Numerical optimization. Springer Science & Business Media (2006)"},{"issue":"1","key":"9499_CR64","first-page":"389","volume":"13","author":"G Raskutti","year":"2012","unstructured":"Raskutti, G., Wainwright, M.J., Yu, B.: Minimax-optimal rates for sparse additive models over kernel classes via convex programming. The Journal of Machine Learning Research 13(1), 389\u2013427 (2012)","journal-title":"The Journal of Machine Learning Research"},{"key":"9499_CR65","doi-asserted-by":"crossref","unstructured":"Reddi, S., Sra, S., P\u00f3czos, B., Smola, A.: Stochastic Frank-Wolfe Methods for Nonconvex Optimization. In: Proceedings of the 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1244\u20131251 (2016)","DOI":"10.1109\/ALLERTON.2016.7852377"},{"key":"9499_CR66","unstructured":"Reddi, S., Zaheer, M., Sra, S., Poczos, B., Bach, F., Salakhutdinov, R., Smola, A.: A generic approach for escaping saddle points. In: International Conference on Artificial Intelligence and Statistics, pp. 1233\u20131242 (2018)"},{"issue":"1","key":"9499_CR67","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/s10959-008-0155-9","volume":"22","author":"E Rio","year":"2009","unstructured":"Rio, E.: Moment inequalities for sums of dependent random variables under projective conditions. Journal of Theoretical Probability 22(1), 146\u2013163 (2009)","journal-title":"Journal of Theoretical Probability"},{"key":"9499_CR68","doi-asserted-by":"publisher","DOI":"10.1002\/9781118631980","volume-title":"Simulation and the Monte Carlo method","author":"R Rubinstein","year":"2016","unstructured":"Rubinstein, R., Kroese, D.: Simulation and the Monte Carlo method, vol.\u00a010. John Wiley & Sons, New Jersey (2016)"},{"key":"9499_CR69","unstructured":"Saha, A., Tewari, A.: Improved regret guarantees for online smooth convex optimization with bandit feedback. In: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 636\u2013642 (2011)"},{"key":"9499_CR70","unstructured":"Salimans, T., Ho, J., Chen, X., Sidor, S., Sutskever, I.: Evolution strategies as a scalable alternative to reinforcement learning. arXiv:1703.03864"},{"key":"9499_CR71","unstructured":"Shamir, O.: On the complexity of bandit and derivative-free stochastic convex optimization. In: Conference on Learning Theory, pp. 3\u201324 (2013)"},{"key":"9499_CR72","unstructured":"Snoek, J., Larochelle, H., Adams, R.: Practical bayesian optimization of machine learning algorithms. In: Advances in neural information processing systems, pp. 2951\u20132959 (2012)"},{"key":"9499_CR73","volume-title":"Introduction to stochastic search and optimization: estimation, simulation, and control","author":"J Spall","year":"2005","unstructured":"Spall, J.: Introduction to stochastic search and optimization: estimation, simulation, and control, vol.\u00a065. John Wiley & Sons, New Jersey (2005)"},{"key":"9499_CR74","unstructured":"Stein, C.: A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory. The Regents of the University of California (1972)"},{"key":"9499_CR75","doi-asserted-by":"crossref","unstructured":"Stein, C.M.: Estimation of the mean of a multivariate normal distribution. The annals of Statistics pp. 1135\u20131151 (1981)","DOI":"10.1214\/aos\/1176345632"},{"key":"9499_CR76","unstructured":"Sun, J., Qu, Q., Wright, J.: When are nonconvex problems not scary? arXiv:1510.06096"},{"issue":"5","key":"9499_CR77","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1007\/s10208-017-9365-9","volume":"18","author":"J Sun","year":"2018","unstructured":"Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. Foundations of Computational Mathematics 18(5), 1131\u20131198 (2018)","journal-title":"Foundations of Computational Mathematics"},{"key":"9499_CR78","unstructured":"Tripuraneni, N., Stern, M., Jin, C., Regier, J., Jordan, M.: Stochastic cubic regularization for fast nonconvex optimization. In: Advances in Neural Information Processing Systems, pp. 2899\u20132908 (2018)"},{"key":"9499_CR79","doi-asserted-by":"crossref","unstructured":"Tropp, J.A.: The expected norm of a sum of independent random matrices: An elementary approach. In: High Dimensional Probability VII, pp. 173\u2013202. Springer (2016)","DOI":"10.1007\/978-3-319-40519-3_8"},{"issue":"2","key":"9499_CR80","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1093\/imaiai\/iax008","volume":"7","author":"H Tyagi","year":"2018","unstructured":"Tyagi, H., Kyrillidis, A., G\u00e4rtner, B., Krause, A.: Algorithms for learning sparse additive models with interactions in high dimensions. Information and Inference: A Journal of the IMA 7(2), 183\u2013249 (2018)","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"9499_CR81","unstructured":"Wang, Y., Du, S., Balakrishnan, S., Singh, A.: Stochastic zeroth-order optimization in high dimensions. In: A.\u00a0Storkey, F.\u00a0Perez-Cruz (eds.) Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol.\u00a084, pp. 1356\u20131365 (2018)"},{"issue":"2","key":"9499_CR82","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.jco.2011.01.004","volume":"27","author":"P Wojtaszczyk","year":"2011","unstructured":"Wojtaszczyk, P.: Complexity of approximation of functions of few variables in high dimensions. Journal of Complexity 27(2), 141\u2013150 (2011)","journal-title":"Journal of Complexity"},{"key":"9499_CR83","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10107-019-01405-z","volume":"184","author":"P Xu","year":"2020","unstructured":"Xu, P., Roosta-Khorasani, F., Mahoney, M.W.: Newton-type methods for non-convex optimization under inexact hessian information. Mathematical Programming 184, 35\u201370 (2020)","journal-title":"Mathematical Programming"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09499-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09499-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09499-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T23:19:41Z","timestamp":1644016781000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09499-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,19]]},"references-count":83,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["9499"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09499-8","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,19]]},"assertion":[{"value":"16 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}