{"data":{"id":"10.48550/arxiv.2302.00316","type":"dois","attributes":{"doi":"10.48550/arxiv.2302.00316","prefix":"10.48550","suffix":"arxiv.2302.00316","identifiers":[{"identifier":"2302.00316","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2302.00316"}],"creators":[{"name":"Muehlebach, Michael","nameType":"Personal","givenName":"Michael","familyName":"Muehlebach","affiliation":[],"nameIdentifiers":[]},{"name":"Jordan, Michael I.","nameType":"Personal","givenName":"Michael I.","familyName":"Jordan","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Accelerated First-Order Optimization under Nonlinear Constraints"}],"publisher":"arXiv","container":{},"publicationYear":2023,"subjects":[{"lang":"en","subject":"Optimization and Control (math.OC)","subjectScheme":"arXiv"},{"lang":"en","subject":"Machine Learning (cs.LG)","subjectScheme":"arXiv"},{"lang":"en","subject":"Signal Processing (eess.SP)","subjectScheme":"arXiv"},{"lang":"en","subject":"Machine Learning (stat.ML)","subjectScheme":"arXiv"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Electrical engineering, electronic engineering, information engineering","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Electrical engineering, electronic engineering, information engineering","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2023-02-01T08:50:48Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2023-02-02T01:10:25Z","dateType":"Updated","dateInformation":"v1"},{"date":"2024-01-02T09:50:04Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2024-01-03T01:14:43Z","dateType":"Updated","dateInformation":"v2"},{"date":"2025-05-01T15:30:17Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2025-05-02T00:45:54Z","dateType":"Updated","dateInformation":"v3"},{"date":"2023-02","dateType":"Available","dateInformation":"v1"},{"date":"2023","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. We prove convergence to stationary points even in a nonconvex setting and we derive accelerated rates for the convex setting both in continuous time, as well as in discrete time. An important property of these algorithms is that constraints are expressed in terms of velocities instead of positions, which naturally leads to sparse, local and convex approximations of the feasible set (even if the feasible set is nonconvex). Thus, the complexity tends to grow mildly in the number of decision variables and in the number of constraints, which makes the algorithms suitable for machine learning applications. We apply our algorithms to a compressed sensing and a sparse regression problem, showing that we can treat nonconvex $\\ell^p$ constraints ($p\u0026lt;1$) efficiently, while recovering state-of-the-art performance for $p=1$.","descriptionType":"Abstract"},{"description":"44 pages, 6 figures","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMzAyLjAwMzE2PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjMwMi4wMDMxNjwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5NdWVobGViYWNoLCBNaWNoYWVsPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5NaWNoYWVsPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPk11ZWhsZWJhY2g8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Sm9yZGFuLCBNaWNoYWVsIEkuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5NaWNoYWVsIEkuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkpvcmRhbjwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+QWNjZWxlcmF0ZWQgRmlyc3QtT3JkZXIgT3B0aW1pemF0aW9uIHVuZGVyIE5vbmxpbmVhciBDb25zdHJhaW50czwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAyMzwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPk9wdGltaXphdGlvbiBhbmQgQ29udHJvbCAobWF0aC5PQyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChjcy5MRyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5TaWduYWwgUHJvY2Vzc2luZyAoZWVzcy5TUCk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChzdGF0Lk1MKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IE1hdGhlbWF0aWNzPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogRWxlY3RyaWNhbCBlbmdpbmVlcmluZywgZWxlY3Ryb25pYyBlbmdpbmVlcmluZywgaW5mb3JtYXRpb24gZW5naW5lZXJpbmc8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIzLTAyLTAxVDA4OjUwOjQ4WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIzLTAyLTAyVDAxOjEwOjI1WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMjQtMDEtMDJUMDk6NTA6MDRaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMjQtMDEtMDNUMDE6MTQ6NDNaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MyI+MjAyNS0wNS0wMVQxNTozMDoxN1o8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MyI+MjAyNS0wNS0wMlQwMDo0NTo1NFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIzLTAyPC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJQcmVwcmludCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDx2ZXJzaW9uPjM8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbGljZW5zZXMvYnkvNC4wLyIgcmlnaHRzSWRlbnRpZmllclNjaGVtZT0iU1BEWCIgcmlnaHRzSWRlbnRpZmllcj0iQ0MtQlktNC4wIj5DcmVhdGl2ZSBDb21tb25zIEF0dHJpYnV0aW9uIDQuMCBJbnRlcm5hdGlvbmFsPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+V2UgZXhwbG9pdCBhbmFsb2dpZXMgYmV0d2VlbiBmaXJzdC1vcmRlciBhbGdvcml0aG1zIGZvciBjb25zdHJhaW5lZCBvcHRpbWl6YXRpb24gYW5kIG5vbi1zbW9vdGggZHluYW1pY2FsIHN5c3RlbXMgdG8gZGVzaWduIGEgbmV3IGNsYXNzIG9mIGFjY2VsZXJhdGVkIGZpcnN0LW9yZGVyIGFsZ29yaXRobXMgZm9yIGNvbnN0cmFpbmVkIG9wdGltaXphdGlvbi4gVW5saWtlIEZyYW5rLVdvbGZlIG9yIHByb2plY3RlZCBncmFkaWVudHMsIHRoZXNlIGFsZ29yaXRobXMgYXZvaWQgb3B0aW1pemF0aW9uIG92ZXIgdGhlIGVudGlyZSBmZWFzaWJsZSBzZXQgYXQgZWFjaCBpdGVyYXRpb24uIFdlIHByb3ZlIGNvbnZlcmdlbmNlIHRvIHN0YXRpb25hcnkgcG9pbnRzIGV2ZW4gaW4gYSBub25jb252ZXggc2V0dGluZyBhbmQgd2UgZGVyaXZlIGFjY2VsZXJhdGVkIHJhdGVzIGZvciB0aGUgY29udmV4IHNldHRpbmcgYm90aCBpbiBjb250aW51b3VzIHRpbWUsIGFzIHdlbGwgYXMgaW4gZGlzY3JldGUgdGltZS4gQW4gaW1wb3J0YW50IHByb3BlcnR5IG9mIHRoZXNlIGFsZ29yaXRobXMgaXMgdGhhdCBjb25zdHJhaW50cyBhcmUgZXhwcmVzc2VkIGluIHRlcm1zIG9mIHZlbG9jaXRpZXMgaW5zdGVhZCBvZiBwb3NpdGlvbnMsIHdoaWNoIG5hdHVyYWxseSBsZWFkcyB0byBzcGFyc2UsIGxvY2FsIGFuZCBjb252ZXggYXBwcm94aW1hdGlvbnMgb2YgdGhlIGZlYXNpYmxlIHNldCAoZXZlbiBpZiB0aGUgZmVhc2libGUgc2V0IGlzIG5vbmNvbnZleCkuIFRodXMsIHRoZSBjb21wbGV4aXR5IHRlbmRzIHRvIGdyb3cgbWlsZGx5IGluIHRoZSBudW1iZXIgb2YgZGVjaXNpb24gdmFyaWFibGVzIGFuZCBpbiB0aGUgbnVtYmVyIG9mIGNvbnN0cmFpbnRzLCB3aGljaCBtYWtlcyB0aGUgYWxnb3JpdGhtcyBzdWl0YWJsZSBmb3IgbWFjaGluZSBsZWFybmluZyBhcHBsaWNhdGlvbnMuIFdlIGFwcGx5IG91ciBhbGdvcml0aG1zIHRvIGEgY29tcHJlc3NlZCBzZW5zaW5nIGFuZCBhIHNwYXJzZSByZWdyZXNzaW9uIHByb2JsZW0sIHNob3dpbmcgdGhhdCB3ZSBjYW4gdHJlYXQgbm9uY29udmV4ICRcZWxsXnAkIGNvbnN0cmFpbnRzICgkcCZsdDsxJCkgZWZmaWNpZW50bHksIHdoaWxlIHJlY292ZXJpbmcgc3RhdGUtb2YtdGhlLWFydCBwZXJmb3JtYW5jZSBmb3IgJHA9MSQuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj40NCBwYWdlcywgNiBmaWd1cmVzPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/2302.00316","contentUrl":null,"metadataVersion":2,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2023-02-02T01:54:54.000Z","registered":"2023-02-02T01:54:55.000Z","published":"2023","updated":"2025-05-02T01:47:15.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2302.00316","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}