2026-08-03T15:20:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19553 2024-03-06T11:04:18Z ddc:004 open_access

Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning Chandra, Pritam Garg, Ankit Kayal, Neeraj Mittal, Kunal Sinha, Tanmay Arithmetic Circuits Robust Vector Space Decomposition Subspace Clustering Mixtures of Gaussians We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic formulas in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal and Saha (FOCS '20), who designed such a framework for learning arithmetic formulas without any noise. A key ingredient of our meta algorithm is an efficient algorithm for a novel problem called Robust Vector Space Decomposition. We show that our meta algorithm works well when certain matrices have sufficiently large smallest non-zero singular values. We conjecture that this condition holds for smoothed instances of our problems, and thus our framework would yield efficient algorithms for these problems in the smoothed setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pritam Chandra and Ankit Garg and Neeraj Kayal and Kunal Mittal and Tanmay Sinha 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.25 urn:nbn:de:0030-drops-195537 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.25 eng https://creativecommons.org/licenses/by/4.0/legalcode