Intelligent software has the potential to transform our society. It is becoming the building block for many systems in the real world. However, despite the excellent performance of machine learning models on benchmarks, state-of-the-art methods like neural networks often fail once they encounter realistic settings. Since neural networks often learn correlations without reasoning with the right signals and knowledge, they fail when facing shifting distributions, unforeseen corruptions, and worst-case scenarios. Since neural networks are black-box models, they are not interpretable or trusted by the user. We need to build robust models for machine learning to be confidently and responsibly deployed in the most critical applications and systems. In this dissertation, I introduce our robust machine learning systems advancements by tightly integrating context into algorithms. The context has two aspects: the intrinsic structure of natural data, and the extrinsic structure from domain knowledge. Both are crucial: By capitalizing on the intrinsic structure in natural data, my work has shown that we can create robust machine learning systems, even in the worst case, an analytical result that also enjoys strong empirical gains. Through integrating external knowledge, such as the association between tasks and causal structure, my framework can instruct models to use the right signals for inference, enabling new opportunities for controllable and interpretable models. This thesis consists of three parts. In the first part, I aim to cover three works that use the intrinsic structure as a constraint to achieve robust inference. I present our framework that performs test-time optimization to respect the natural constraint, which is captured by self-supervised tasks. I illustrate that test-time optimization improves out-of-distribution generalization and adversarial robustness. Besides the inference algorithm, I show that intrinsic structure through discrete representations also improves out-of-distribution robustness. In the second part of the thesis, I then detail my work using external domain knowledge. I first introduce using causal structure from external domain knowledge to improve domain generalization robustness. I then show how the association of multiple tasks and regularization objectives helps robustness. In the final part of this dissertation, I show three works on trustworthy and reliable foundation models, a general-purpose model that will be the foundation for many AI applications. I show a framework that uses context to secure, interpret, and control foundation models.

No description available.

Federated learning (FL), a novel distributed learning paradigm, has attracted significant attention in the past few years. Federated algorithms take a client/server computation model, and provide scope to train large-scale machine learning models over an edge-based distributed computing architecture. In the paradigm of FL, models are trained collaboratively under the coordination of a central server while storing data locally on the edge/clients. This thesis addresses critical challenges in FL, focusing on supervised learning, reinforcement learning (RL), control systems, and personalized system identification. By developing robust, efficient algorithms, our research enhances FL’s applicability across diverse, real-world environments characterized by data heterogeneity and communication constraints. In the first part, we introduce an algorithm for supervised FL to address the challenges posed by heterogeneous client data, ensuring stable convergence and effective learning, even with partial client participation. In the federated reinforcement learning (FRL) part, we develop algorithms that leverage similarities across heterogeneous environments to improve sample efficiency and accelerate policy learning. Our setup involves 𝑁 agents interacting with environments that share the same state and action space but differ in their reward functions and state transition kernels. Through rigorous theoretical analysis, we show that information exchange via FL can expedite both policy evaluation and optimization in decentralized, multi-agent settings, enabling faster, more efficient, and robust learning. Extending FL into control systems, we propose the 𝙵𝚎𝚍𝙻𝚀𝚁 algorithm, which enables agents with unknown but similar dynamics to collaboratively learn stabilizing policies, addressing the unique demands of closed-loop stability in federated control. Our method overcomes numerous technical challenges, such as heterogeneity in the agents’dynamics, multiple local updates, and stability concerns. We show that our proposed algorithm 𝙵𝚎𝚍𝙻𝚀𝚁 produces a common policy that, at each iteration, is stabilizing for all agents. We provide bounds on the distance between the common policy and each agent’s local optimal policy. Furthermore, we prove that when learning each agent’s optimal policy, 𝙵𝚎𝚍𝙻𝚀𝚁 achieves a sample complexity reduction proportional to the number of agents 𝑀 in a low-heterogeneity regime, compared to the single-agent setting. In the last part, we explore techniques for personalized system identification in FL, allowing clients to obtain customized models suited to their individual environments. We consider the problem of learning linear system models by observing multiple trajectories from systems with differing dynamics. This framework encompasses a collaborative scenario where several systems seeking to estimate their dynamics are partitioned into clusters according to system similarity. Thus, the systems within the same cluster can benefit from the observations made by the others. Considering this framework, we present an algorithm where each system alternately estimates its cluster identity and performs an estimation of its dynamics. This is then aggregated to update the model of each cluster. We show that under mild assumptions, our algorithm correctly estimates the cluster identities and achieves an 𝜀-approximate solution with a sample complexity that scales inversely with the number of systems in the cluster, thus facilitating a more efficient and personalized system identification.

One aspect of the algorithmic lens in theoretical computer science is a view on other scientific disciplines that focuses on satisfactory solutions that adhere to real-world constraints, as opposed to solutions that would be optimal ignoring such constraints. The algorithmic lens has provided a unique and important perspective on many academic fields, including molecular biology, ecology, neuroscience, quantum physics, economics, and social science. This thesis applies the algorithmic lens to Bayesian epistemology. Traditional Bayesian epistemology provides a comprehensive framework for how an individual's beliefs should evolve upon receiving new information. However, these methods typically assume an exhaustive model of such information, including the correlation structure between different pieces of evidence. In reality, individuals might lack such an exhaustive model, while still needing to form beliefs. Beyond such informational constraints, an individual may be bounded by limited computation, or by limited communication with agents that have access to information, or by the strategic behavior of such agents. Even when these restrictions prevent the formation of a *perfectly* accurate belief, arriving at a *reasonably* accurate belief remains crucial. In this thesis, we establish fundamental possibility and impossibility results about belief formation under a variety of restrictions, and lay the groundwork for further exploration.

This dissertation considers the problem of scheduling deadline-constrained packets in networks, an increasingly relevant problem, which due to the rise of time-sensitive applications such as teleconferencing and video streaming, has recently received renewed attention. To accommodate a diverse range of environments and scenarios, our work investigates single-hop and multi-hop networks, across various traffic models and network conditions, including wired and wireless settings. We propose algorithms in each setting, with their performance evaluated by considering commonly used benchmarks in the related literature, such as the attained fraction of the real-time capacity region achieved in single-hop networks and the maximization of the cumulative weight of packets reaching their destinations within their deadlines in multi-hop networks. We explore traffic which is either worst-case, or stochastic, and provide different performance guarantees in each case. The first part of our study focuses on scheduling real-time traffic in single-hop wireless networks with conflict-graph interference models. We propose randomized policies that achieve higher real-time efficiency ratios, compared to state-of-the-art existing algorithms, such as the Largest-Deficit-First algorithm. The research then extends to single-hop wireless networks with unreliable links due to channel fading, designing randomized algorithms that achieve efficiency ratios strictly higher than traditional scheduling algorithms, such as Maximum-Weight Scheduling. The dissertation proceeds to examine online admission, routing, and scheduling algorithms for multi-hop wireless networks under a general interference graph model. It presents online algorithms that are competitive with the optimal offline algorithms and provides upper bounds on performance which demonstrate the asymptotic optimality of these results. Simulation results illustrate significant improvements over prior approaches. Furthermore, the research addresses the problem of scheduling packets with end-to-end deadline constraints in both wired and wireless multi-hop networks, in the case of stochastic traffic. It illustrates the first near-optimal approximation algorithms under nontrivial assumptions on traffic and link capacity, showcasing significant improvements over worst-case algorithms in practical settings. In conclusion, this dissertation contributes scheduling algorithms for deadline-constrained packet delivery in single and multi-hop networks, under various traffic and interference models, and in both wired and wireless settings. The proposed algorithms materially improve the state-of-the-art performance guarantees in each case.

The potential is vast for the enhancement of graphic images that are used for human interpretation and/or image display. Sensor noise, blur due to camera misfocus, relative object-camera motion, and random atmospheric turbulence may contribute to photographic image deterioration. Image enhancement and restoration methods are useful for improving the quality and for augmenting specific characteristics of an image. Often, complex filtering of the image data is required. This paper presents a technique for enhancement of images using multistage filtering techniques which take advantage of a priori knowledge as to the images' content. Algorithms are designed and implemented which enhance edges as well as gray level contrast. In addition, the source images are passed through a sequence of controllable filter stages to provide varying degrees and types of enhancements. Image enhancement techniques do not increase the inherent information content in the data, but the techniques do accentuate distinct image features which result in an improved image display. The effects of the different filters and filter stages will be analyzed with regard to image enhancement and picture quality. Numerical results and graphic image results are included in the analysis. Further applications of the techniques analyzed are discussed as well.

In recent years, the collection of genomic data has skyrocketed and databases of genomic data are growing at a faster rate than ever before. Although many computational methods have been developed to interpret these data, they tend to struggle to process the ever increasing file sizes that are being produced and fail to take advantage of the advances in multi-core processors by using parallel processing. In some instances, loss of accuracy has been a necessary trade off to allow faster computation of the data. This thesis discusses one such algorithm that has been developed and how changes were made to allow larger input file sizes and reduce the time required to achieve a result without sacrificing accuracy. An information entropy based algorithm was used as a basis to demonstrate these techniques. The algorithm dissects the distinctive patterns underlying genomic data efficiently requiring no a priori knowledge, and thus is applicable in a variety of biological research applications. This research describes how parallel processing and object-oriented programming techniques were used to process larger files in less time and achieve a more accurate result from the algorithm. Through object oriented techniques, the maximum allowable input file size was significantly increased from 200 mb to 2000 mb. Using parallel processing techniques allowed the program to finish processing data in less than half the time of the sequential version. The accuracy of the algorithm was improved by reducing data loss throughout the algorithm. Finally, adding user-friendly options enabled the program to use requests more effectively and further customize the logic used within the algorithm.

The purpose of the thesis is to develop a parallel implementation of the General Block Min Max Criterion (GBMM). This thesis deals with two kinds of parallel overheads: Redundant Calculations Parallel Overhead (RCPO) and Communication Parallel Overhead (CPO).

Thesis (MSc)--Stellenbosch University, 2008. / ENGLISH ABSTRACT: Traffic Engineering (TE) is intended to be used in next generation IP networks to optimize the usage of network resources by effecting QoS agreements between the traffic offered to the network and the available network resources. TE is currently performed by the IP community using three methods including (1) IGP TE using connectionless routing optimization (2) MPLS TE using connection-oriented routing optimization and (3) Hybrid TE combining IGP TE with MPLS TE. MPLS has won the battle of the core of the Internet and is making its way into metro, access and even some private networks. However, emerging provider practices are revealing the relevance of using IGP TE in hybrid TE models where IGP TE is combined with MPLS TE to optimize IP routing. This is done by either optimizing IGP routing while setting a few number of MPLS tunnels in the network or optimizing the management of MPLS tunnels to allow growth for the IGP traffic or optimizing both IGP and MPLS routing in a hybrid IGP+MPLS setting. The focus of this thesis is on IGP TE using heuristic algorithms borrowed from the computational intelligence research field. We present four classes of algorithms for Maximum Link Utilization (MLU) minimization. These include Genetic Algorithm (GA), Gene Expression Programming (GEP), Ant Colony Optimization (ACO), and Simulated Annealing (SA). We use these algorithms to compute a set of optimal link weights to achieve IGP TE in different settings where a set of test networks representing Europe, USA, Africa and China are used. Using NS simulation, we compare the performance of these algorithms on the test networks with various traffic profiles. / AFRIKAANSE OPSOMMING: Verkeersingenieurswese (VI) is aangedui vir gebruik in volgende generasie IP netwerke vir die gebruiksoptimering van netwerkbronne deur die daarstelling van kwaliteit van diens ooreenkomste tussen die verkeersaanbod vir die netwerk en die beskikbare netwerkbronne. VI word huidiglik algemeen bewerkstellig deur drie metodes, insluitend (1) IGP VI gebruikmakend van verbindingslose roete-optimering, (2) MPLS VI gebruikmakend van verbindingsvaste roete-optimering en (3) hibriede VI wat IGP VI en MPLS VI kombineer. MPLS is die mees algemene, en word ook aangewend in metro, toegang en selfs sommige privaatnetwerke. Nuwe verskaffer-praktyke toon egter die relevansie van die gebruik van IGP VI in hibriede VI modelle, waar IGP VI gekombineer word met MPLS VI om IP roetering te optimeer. Dit word gedoen deur `of optimering van IGP roetering terwyl ’n paar MPLS tonnels in die netwerk gestel word, `of optimering van die bestuur van MPLS tonnels om toe te laat vir groei in die IGP verkeer `of die optimering van beide IGP en MPLS roetering in ’n hibriede IGP en MPLS situasie. Die fokus van hierdie tesis is op IGP VI gebruikmakend van heuristieke algoritmes wat ontleen word vanuit die berekeningsintelligensie navorsingsveld. Ons beskou vier klasse van algoritmes vir Maksimum Verbindingsgebruik (MVG) minimering. Dit sluit in genetiese algoritmes, geen-uitdrukkingsprogrammering, mierkoloniemaksimering and gesimuleerde temperoptimering. Ons gebruik hierdie algoritmes om ’n versameling optimale verbindingsgewigte te bereken om IGP VI te bereik in verskillende situasies, waar ’n versameling toetsnetwerke gebruik is wat Europa, VSA, Afrika en China verteenwoordig. Gebruikmakende van NS simulasie, vergelyk ons die werkverrigting van hierdie algoritmes op die toetsnetwerke, met verskillende verkeersprofiele.

Thesis (MSc)--University of Stellenbosch, 2007. / ENGLISH ABSTRACT: We use Evolutionary Multi-Objective Optimisation (EMOO) algorithms to optimise objective functions that reflect situations in communication networks. These include functions that optimise Network Engineering (NE) objective functions in core, metro and wireless sensor networks. The main contributions of this thesis are threefold. Routing and Wavelength Assignment (RWA) for IP backbone networks. Routing and Wavelength Assignment (RWA) is a problem that has been widely addressed by the optical research community. A recent interest in this problem has been raised by the need to achieve routing optimisation in the emerging generation multilayer networks where data networks are layered above a Dense Wavelength Division Multiplexing (DWDM) network. We formulate the RWA as both a single and a multi-objective optimisation problem which are solved using a two-step solution where (1) a set of paths are found using genetic optimisation and (2) a graph coloring approach is implemented to assign wavelengths to these paths. The experimental results from both optimisation scenarios reveal the impact of (1) the cost metric used which equivalently defines the fitness function (2) the algorithmic solution adopted and (3) the topology of the network on the performance achieved by the RWA procedure in terms of path quality and wavelength assignment. Optimisation of Arrayed Waveguide Grating (AWG) Metro Networks. An Arrayed Waveguide Grating (AWG) is a device that can be used as a multiplexer or demultiplexer in WDM systems. It can also be used as a drop-and-insert element or even a wavelength router. We take a closer look at how the hardware and software parameters of an AWG can be fine tuned in order to maximise throughput and minimise the delay. We adopt a multi-objective optimisation approach for multi-service AWG-based single hop metro WDM networks. Using a previously proposed multi-objective optimisation model as a benchmark, we propose several EMOO solutions and compare their efficiency by evaluating their impact on the performance achieved by the AWG optimisation process. Simulation reveals that (1) different EMOO algorithms can exhibit different performance patterns and (2) good network planning and operation solutions for a wide range of traffic scenarios can result from a well selected EMOO algorithm. Wireless Sensor Networks (WSNs) Topology (layout) Optimisation. WSNs have been used in a number of application areas to achieve vital functions in situations where humans cannot constantly be available for certain tasks such as in hostile areas like war zones, seismic sensing where continuous inspection and detection are needed, and many other applications such as environment monitoring, military operations and surveillance. Research and practice have shown that there is a need to optimise the topology (layout) of such sensors on the ground because the position on which they land may affect the sensing efficiency. We formulate the problem of layout optimisation as a multi-objective optimisation problem consisting of maximising both the coverage (area) and the lifetime of the wireless sensor network. We propose different algorithmic evolutionary multi-objective methods and compare their performance in terms of Pareto solutions. Simulations reveal that the Pareto solutions found lead to different performance patterns and types of layouts. / AFRIKAANSE OPSOMMING: Ons gebruik ”Evolutionary Multi-Objective Optimisation (EMOO)” algoritmes om teiken funksies, wat egte situasies in kommunikasie netwerke voorstel, te optimiseer. Hierdie sluit funksies in wat ”Network Engineering” teiken funksies in kern, metro en wireless sensor netwerke optimiseer. Die hoof doelwitte van hierdie tesis is dus drievuldig. RWA vir IP backbone netwerke ”Routing and Wavelength Assignment (RWA)” is ’n probleem wat al menigte kere in die optiese navorsings kringe aangespreek is. Belangstelling in hierdie veld het onlangs ontstaan a.g.v. die aanvraag na die optimisering van routering in die opkomende generasie van veelvuldige vlak netwerke waar data netwerke in ’n vlak ho¨er as ’n ”Dense Wavelength Division Multiplexing (DWDM)” netwerk gele is. Ons formuleer die RWA as beide ’n enkele and veelvuldige teiken optimiserings probleem wat opgelos word deur ’n 2-stap oplossing waar (1) ’n stel roetes gevind word deur genetiese optimisering te gebruik en (2) ’n grafiek kleuring benadering geimplementeer word om golflengtes aan hierdie roetes toe te ken. Die eksperimentele resultate van beide optimiserings gevalle vertoon die impak van (1) die koste on wat gebruik word wat die ekwalente fitness funksie definieer , (2) die algoritmiese oplossing wat gebruik word en (3) die topologie van die netwerk op die werkverrigting van die RWA prosedure i.t.v. roete kwaliteit en golflengte toekenning. Optimisering van AWG Metro netwerk ’n ”Arrayed Waveguide Grating (AWG)” is ’n toestel wat gebruik kan word as ’n multipleksor of demultipleksor in WDM sisteme. Dit kan ook gebruik word as ’n val-en-inplaas element of selfs ’n golflengte router. Kennis word ingestel na hoe die hardeware en sagteware parameters van ’n AWG ingestel kan word om die deurset tempo te maksimeer en vertragings te minimiseer. Ons neem ’n multi-teiken optimiserings benadering vir multi diens, AWG gebaseerde, enkel skakel, metro WDM netwerke aan. Deur ’n vooraf voorgestelde multi teiken optimiserings model as ”benchmark” te gebruik, stel ons ’n aantal EMOO oplossings voor en vergelyk ons hul effektiwiteit deur hul impak op die werkverrigting wat deur die AWG optimiserings proses bereik kan word, te vergelyk. Simulasie modelle wys dat (1) verskillende EMOO algoritmes verskillende werkverrigtings patrone kan vertoon en (2) dat goeie netwerk beplanning en werking oplossings vir ’n wye verskeidenheid van verkeer gevalle kan plaasvind a.g.v ’n EMOO algoritme wat reg gekies word. ”Wireless Sensor Network” Topologie Optimisering WSNs is al gebruik om belangrike funksies te verrig in ’n aantal toepassings waar menslike beheer nie konstant beskikbaar is nie, of kan wees nie. Voorbeelde van sulke gevalle is oorlog gebiede, seismiese metings waar aaneenlopende inspeksie en meting nodig is, omgewings meting, militˆere operasies en bewaking. Navorsing en praktiese toepassing het getoon dat daar ’n aanvraag na die optimisering van die topologie van sulke sensors is, gebaseer op gronde van die feit dat die posisie waar die sensor beland, die effektiwiteit van die sensor kan affekteer. Ons formuleer die probleem van uitleg optimisering as ’n veelvuldige vlak optimiserings probleem wat bestaan uit die maksimering van beide die bedekkings area en die leeftyd van die wireless sensor netwerk. Ons stel verskillende algoritmiese, evolutionˆere, veelvuldige vlak oplossings voor en vergelyk hul werkverrigting i.t.v Pareto oplossings. Simulasie modelle wys dat die Pareto oplossings wat gevind word lei na verskillende werkverrigtings patrone en uitleg tipes.