University of Minnesota
Information-Theoretic Foundations Of Machine Learning: Fundamental Limits And Optimal Algorithms
Abstract
dc:description.abstractCharacterizing the fundamental limits of machine learning problems is essential for determining what levels of performance are achievable and for guiding the development of methods that operate near these boundaries. This dissertation analyzes fundamental limits in three machine learning problems through a unifying framework grounded in information theory. The information-theoretic approach enables rigorous characterization of performance thresholds and theoretical guarantees while providing principled guidance for designing computationally efficient algorithms that approach these fundamental boundaries. The first part addresses the active rank aggregation problem, where the objective is to identify the top-K items from noisy pairwise comparisons while minimizing the number of queries. A unified noise modeling framework, termed the Sorted-by-Probabilities model, generalizes several established noise models, including Bradley-Terry-Luce, Strong Stochastic Transitivity, and uniform noise models, enabling systematic analysis across diverse comparison settings. Upper bounds on sample complexity are derived for two ranking tasks: recovering the sorted top-K items and identifying the top-K items as an unordered set. The theoretical analysis reveals that sample complexity depends critically on how distinguishable items are from one another, with harder-to-separate items requiring substantially more comparisons, and demonstrates that adaptive query selection achieves multiplicative efficiency gains over passive sampling strategies. A computationally efficient algorithm achieving these theoretical limits is developed, combining tournament-based selection with heap data structures to attain near-linear runtime. Extensive experiments validate the theoretical predictions and demonstrate that the proposed algorithm significantly outperforms state-of-the-art active and passive ranking methods across different noise models and problem configurations. The second part focuses on the data shuffling problem in distributed learning systems comprising a master node and multiple worker nodes connected through a shared link. In each shuffling iteration, workers process new data subsets while maintaining local caches to reduce communication overhead. The fundamental trade-off between communication load and storage capacity is exactly characterized through a two-stage analysis. First, for the canonical case where the number of files equals the number of workers, a novel deterministic coded shuffling scheme based on interference alignment and elimination techniques is developed and proven universally optimal over all possible shuffling scenarios through matching achievability and converse bounds. The proposed scheme integrates file partitioning, strategic cache placement, encoding, decoding, and cache updating phases, with the uncoded cache placement proven optimal among all possible placement strategies. Second, the canonical setting is leveraged as a building block to address the general case where the number of files exceeds the number of workers. A graph decomposition approach based on perfect matchings in bipartite file transition graphs reduces the general problem into multiple canonical subproblems, enabling exact characterization of the optimal load-memory trade-off for worst-case shuffling. These results establish the minimum communication requirements and develop computationally efficient algorithms that achieve these fundamental limits. The third part addresses the matrix completion problem with hierarchical graph side information, motivated by recommender systems where structured social relationships exist among users. We consider a hierarchical stochastic block model in which users are organized hierarchically into communities, consisting of clusters and groups within clusters. The rating vectors of these groups follow a low-rank structure governed by Maximum Distance Separable code relationships, allowing the algorithm to leverage both graph connectivity patterns and underlying algebraic dependencies. We characterize the exact information-theoretic limit on the minimal number of observed matrix entries required for reliable completion by establishing sharp matching upper and lower bounds. This analysis reveals three distinct operational regimes determined by graph quality parameters, each exhibiting different sample complexity scaling behaviors. Leveraging the hierarchical structure yields substantial gains in sample complexity compared with methods that do not employ the relational structure among groups. A computationally efficient four-phase algorithm achieving these fundamental limits is developed through cluster recovery via community detection, group recovery using spectral methods, maximum likelihood decoding using the code structure, and iterative refinement. Extensive experiments demonstrate sharp phase transitions at the predicted theoretical thresholds, validating the theoretical characterization and showing significant performance improvements over prior methods when hierarchical graph information is reliable. These contributions establish exact fundamental performance limits for three important machine learning problems, develop computationally efficient algorithms that provably achieve these limits, and validate the theoretical predictions through extensive experiments. The results demonstrate that information theory provides a mathematically rigorous framework for analyzing fundamental trade-offs in machine learning, enabling the design of algorithms that approach theoretical optimality while maintaining computational efficiency. Across all three problems, the proposed algorithms significantly outperform existing methods, confirming the value of information-theoretic analysis in guiding practical algorithm design.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Elmahdy, Adel
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Citation
- Elmahdy, Adel. (2025). Information-Theoretic Foundations Of Machine Learning: Fundamental Limits And Optimal Algorithms. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/279232.