Optimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator

Optimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Optimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator Chris Junchi Li This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5000467/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract In this paper, we tackle the optimization of nonconvex functions prevalent in large-scale statistical learning tasks. We introduce the Stochastic Path-Integrated Differential EstimatoR (SPIDER), a novel method for efficiently tracking deterministic quantities with significantly lower sampling costs. Utilizing SPIDER, we develop the SPIDER-SFO algorithm, which enhances Normalized Gradient Descent (NGD) and achieves faster convergence rates for nonconvex optimization problems in both finite-sum and online cases. Our rigorous analysis shows that SPIDER-SFO achieves a gradient computational cost of $\mathcal{O}\left(\epsilon^{-3} \wedge\left(n+n^{1 / 2} \epsilon^{-2}\right)\right)$ for finding an $\epsilon$-approximate first-order stationary point. Additionally, we extend our method to find approximate second-order stationary points with the SPIDER-SFO ${ }^{+}$algorithm, which combines SPIDER-SFO with efficient Negative-CurvatureSearch techniques. This algorithm attains an $(\epsilon, \delta)$-approximate second-order stationary point at the gradient cost $\tilde{\mathcal{O}}\left(\left(\epsilon^{-3}+\delta^{-2} \epsilon^{-2}+\delta^{-5}\right) \wedge\left(n^{1 / 2} \epsilon^{-2}+n^{1 / 2} \delta^{-2} \epsilon^{-1}+\delta^{-3} \epsilon^{-1}+\delta^{-5}+n\right)\right)$. We demonstrate that our algorithms achieve the best-known optimal convergence guarantees and optimality across a wide range of $\epsilon$ and $\delta$ values, providing superior performance under specific smoothness and Hessian-Lipschitz conditions. This work sets a new benchmark in nonconvex optimization, offering robust and scalable solutions for complex stochastic optimization tasks. Non-Convex Stochastic Optimization First-Order Methods SPIDER Algorithm Normalized Gradient Descent (NGD) Variance Reduction Negative-Curvature-Search Full Text Additional Declarations The authors declare no competing interests. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-5000467","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":347067923,"identity":"e8a7f088-c6b4-44b4-b641-7a1bbaf0bdf6","order_by":0,"name":"Chris Junchi Li","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABBElEQVRIiWNgGAWjYBACxgYGBmYGAwsefgYQg4HBgIEdLMFMSIsEj2QDTAszAS1QWQkGgwPEamGekXvwc0GBhIzx8eMPmAsq7hnzMzMfk2CosE5swOWwGXnJ0jOADjM7k2PAPONMsZlkM1uaBMOZdDxacsyYeUBabvAwMPO2JdgYHOYxk2BsO0xYi/EM9gfMvP8SbOwP83+TYPxHhBYDYAgw8zYkmBkw87BJMDbg0dLzxlgapEUC6JfDM44lGEscZjO2SDiWboxLi2F7juFnnj829vztxx8+LqhJMOxvb35440ONtSxOLcgSB6A0i0QCDuUgII9NkPkDHh2jYBSMglEw8gAAwlxKO7d2kLsAAAAASUVORK5CYII=","orcid":"","institution":"","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"Chris","middleName":"Junchi","lastName":"Li","suffix":""}],"badges":[],"createdAt":"2024-08-30 01:51:24","currentVersionCode":1,"declarations":{"humanSubjects":false,"vertebrateSubjects":false,"conflictsOfInterestStatement":false,"humanSubjectEthicalGuidelines":false,"humanSubjectConsent":false,"humanSubjectClinicalTrial":false,"humanSubjectCaseReport":false,"vertebrateSubjectEthicalGuidelines":false,"coiExplicitlySet":false},"doi":"10.21203/rs.3.rs-5000467/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5000467/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":63776750,"identity":"30443871-a36b-4be7-a6cb-f8a17242cb21","added_by":"auto","created_at":"2024-09-02 09:00:05","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":852961,"visible":true,"origin":"","legend":"","description":"","filename":"main.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5000467/v1_covered_5871ebb2-0723-462b-a93f-644ce20af80c.pdf"}],"financialInterests":"The authors declare no competing interests.","formattedTitle":"\u003cp\u003eOptimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Non-Convex Stochastic Optimization, First-Order Methods, SPIDER Algorithm, Normalized Gradient Descent (NGD), Variance Reduction, Negative-Curvature-Search","lastPublishedDoi":"10.21203/rs.3.rs-5000467/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5000467/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eIn this paper, we tackle the optimization of nonconvex functions prevalent in large-scale statistical learning tasks. We introduce the Stochastic Path-Integrated Differential EstimatoR (SPIDER), a novel method for efficiently tracking deterministic quantities with significantly lower sampling costs. Utilizing SPIDER, we develop the SPIDER-SFO algorithm, which enhances Normalized Gradient Descent (NGD) and achieves faster convergence rates for nonconvex optimization problems in both finite-sum and online cases. Our rigorous analysis shows that SPIDER-SFO achieves a gradient computational cost of $\\mathcal{O}\\left(\\epsilon^{-3} \\wedge\\left(n+n^{1 / 2} \\epsilon^{-2}\\right)\\right)$ for finding an $\\epsilon$-approximate first-order stationary point. Additionally, we extend our method to find approximate second-order stationary points with the SPIDER-SFO ${ }^{+}$algorithm, which combines SPIDER-SFO with efficient Negative-CurvatureSearch techniques. This algorithm attains an $(\\epsilon, \\delta)$-approximate second-order stationary point at the gradient cost $\\tilde{\\mathcal{O}}\\left(\\left(\\epsilon^{-3}+\\delta^{-2} \\epsilon^{-2}+\\delta^{-5}\\right) \\wedge\\left(n^{1 / 2} \\epsilon^{-2}+n^{1 / 2} \\delta^{-2} \\epsilon^{-1}+\\delta^{-3} \\epsilon^{-1}+\\delta^{-5}+n\\right)\\right)$. We demonstrate that our algorithms achieve the best-known optimal convergence guarantees and optimality across a wide range of $\\epsilon$ and $\\delta$ values, providing superior performance under specific smoothness and Hessian-Lipschitz conditions. This work sets a new benchmark in nonconvex optimization, offering robust and scalable solutions for complex stochastic optimization tasks.\u003c/p\u003e","manuscriptTitle":"Optimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-09-02 08:51:54","doi":"10.21203/rs.3.rs-5000467/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"6c7fb96e-6d5f-4413-98cf-e8a05230121c","owner":[],"postedDate":"September 2nd, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-09-02T08:51:54+00:00","versionOfRecord":[],"versionCreatedAt":"2024-09-02 08:51:54","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-5000467","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5000467","identity":"rs-5000467","version":["v1"]},"buildId":"FbvkV6FR0MCFSLy54lSbu","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}