{"id":{"repo_id":"buffalo","oai_identifier":"oai:ubir.buffalo.edu:10477/86795"},"canonical_url":"https://search.dev.ndltd.org/etd/buffalo/oai:ubir.buffalo.edu:10477/86795","repository":{"repo_id":"buffalo","name":"Buffalo","base_url":"https://ubir.buffalo.edu/oai/request"},"display":{"title":"Some Fundamental Machine Learning Problems in the Differential Privacy Model","abstract":"Ph.D.","abstract_html":"Ph.D.","abstract_has_math":false,"creators":["Wang, Di; 0000-0003-4908-0243"],"institution":"State University of New York at Buffalo","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Xu, Jinhui","Computer Science and Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-02-25T23:22:50Z","date_published":"2025-02-25T23:22:50Z","updated_at":"2026-07-27T19:05:37Z","subjects":["computer science"],"languages":["eng"],"rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10477/86795","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Xu, Jinhui","Computer Science and Engineering"]},{"key":"dc:creator","label":"Author","values":["Wang, Di; 0000-0003-4908-0243"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-02-25T23:22:50Z","2020","2020-08-06 16:47:39"]},{"key":"dc:publisher","label":"Institution","values":["State University of New York at Buffalo"]},{"key":"dc:type","label":"Dc Type","values":["Text","Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/10477/86795"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ph.D.","Machine Learning has emerged as one of the most powerful tools for us to learn and extract useful information from big data. It plays a vital role in many applications, especially in those from social sciences, finance, medical sciences and genomics research. However, due to the existence of sensitive information, we cannot implement machine learning algorithms directly on such data. Traditional ad hoc approaches like anonymization have suffered from numerous high-profile failures. Thus, approaches with more privacy preserving ability are urgently needed. For this purpose, we focus our studies on differential privacy (DP), which is a strong mathematical scheme for privacy preserving rooted in cryptography. It allows for rich statistical and machine learning analysis, and is now becoming a standard for private data analysis. Despite the rapid development of differential privacy in theory, its adoption to machine learning community remains slow. This dissertation summarizes our contributions to the sub-field of differentially private machine learning and presents a number of novel algorithms, new results and limitations for a number of fundamental machine learning problems. In part one of this dissertation, we consider the Empirical Risk Minimization (ERM) problem in the differential privacy model. Firstly, we investigate the behaviors of Convex ERM in the central DP model. For this problem, we propose several algorithms with tighter utility upper bound and less running time in different settings, such as general convex, strongly convex and high dimensional settings. We also study the problem in the case where the underlying distribution of data is heavy-tailed, and the case where the loss function of ERM is pairwise. Secondly, we investigate the behaviors of ERM with non-convex loss functions in the central DP model. Specifically, we first generalize the expected excess empirical risk from convex to Polyak-Lojasiewicz condition. Then, we study ERM with general non-convex loss functions by considering the error measurements from the first order stationary, second order stationary and global view, respectively. Thirdly, we consider ERM in the Non-interactive Local DP (NLDP) model and show how to reduce the exponential sample complexity given by previous studies for some special loss functions. We also show that if the server is allowed to have some public but unlabeled data, the sample complexity can be further reduced to polynomial size for smooth Generalized Linear Model. Fourthly, we try to understand the limitations of high dimensional ERM in the LDP model. Particularly, we study the sparse linear regression problem and show the lower bound of its estimation error. We also show some positive results under a relaxation of the problem. In part two of this dissertation, we consider some matrix estimation problems. Firstly, we study the problem of Principal Component Analysis (PCA) in the LDP model and show its lower bound and near optimal upper bound for both low dimension and high dimensional sparse cases. Secondly, we study the sparse covariance matrix estimation problem and show its optimal upper bound and algorithm. Finally, we provide the first study of sparse inverse covariance matrix estimation problem in the DP model. In part three of this dissertation, we consider some other machine learning related problems. Firstly, we study the the problem of inferring ground truth in the Local Attribute Differential Privacy model and provide the first theoretical result for the problem. Secondly, we focus on developing DP versions of the Expectation Maximization algorithm. Specifically, we propose the first DP version of (Gradient) EM algorithm with statistical guarantees.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Some Fundamental Machine Learning Problems in the Differential Privacy Model"]}]}],"canonical_facts":{"dc:contributor":["Xu, Jinhui","Computer Science and Engineering"],"dc:creator":["Wang, Di; 0000-0003-4908-0243"],"dc:date":["2025-02-25T23:22:50Z","2020","2020-08-06 16:47:39"],"dc:description":["Ph.D.","Machine Learning has emerged as one of the most powerful tools for us to learn and extract useful information from big data. It plays a vital role in many applications, especially in those from social sciences, finance, medical sciences and genomics research. However, due to the existence of sensitive information, we cannot implement machine learning algorithms directly on such data. Traditional ad hoc approaches like anonymization have suffered from numerous high-profile failures. Thus, approaches with more privacy preserving ability are urgently needed. For this purpose, we focus our studies on differential privacy (DP), which is a strong mathematical scheme for privacy preserving rooted in cryptography. It allows for rich statistical and machine learning analysis, and is now becoming a standard for private data analysis. Despite the rapid development of differential privacy in theory, its adoption to machine learning community remains slow. This dissertation summarizes our contributions to the sub-field of differentially private machine learning and presents a number of novel algorithms, new results and limitations for a number of fundamental machine learning problems. In part one of this dissertation, we consider the Empirical Risk Minimization (ERM) problem in the differential privacy model. Firstly, we investigate the behaviors of Convex ERM in the central DP model. For this problem, we propose several algorithms with tighter utility upper bound and less running time in different settings, such as general convex, strongly convex and high dimensional settings. We also study the problem in the case where the underlying distribution of data is heavy-tailed, and the case where the loss function of ERM is pairwise. Secondly, we investigate the behaviors of ERM with non-convex loss functions in the central DP model. Specifically, we first generalize the expected excess empirical risk from convex to Polyak-Lojasiewicz condition. Then, we study ERM with general non-convex loss functions by considering the error measurements from the first order stationary, second order stationary and global view, respectively. Thirdly, we consider ERM in the Non-interactive Local DP (NLDP) model and show how to reduce the exponential sample complexity given by previous studies for some special loss functions. We also show that if the server is allowed to have some public but unlabeled data, the sample complexity can be further reduced to polynomial size for smooth Generalized Linear Model. Fourthly, we try to understand the limitations of high dimensional ERM in the LDP model. Particularly, we study the sparse linear regression problem and show the lower bound of its estimation error. We also show some positive results under a relaxation of the problem. In part two of this dissertation, we consider some matrix estimation problems. Firstly, we study the problem of Principal Component Analysis (PCA) in the LDP model and show its lower bound and near optimal upper bound for both low dimension and high dimensional sparse cases. Secondly, we study the sparse covariance matrix estimation problem and show its optimal upper bound and algorithm. Finally, we provide the first study of sparse inverse covariance matrix estimation problem in the DP model. In part three of this dissertation, we consider some other machine learning related problems. Firstly, we study the the problem of inferring ground truth in the Local Attribute Differential Privacy model and provide the first theoretical result for the problem. Secondly, we focus on developing DP versions of the Expectation Maximization algorithm. Specifically, we propose the first DP version of (Gradient) EM algorithm with statistical guarantees.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/10477/86795"],"dc:language":["eng"],"dc:publisher":["State University of New York at Buffalo"],"dc:rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"dc:subject":["computer science"],"dc:title":["Some Fundamental Machine Learning Problems in the Differential Privacy Model"],"dc:type":["Text","Dissertation"]},"updated_at":"2026-07-27T19:05:37Z"}