The mean-squared-error criterion is widely used in the literature. However, there are applications where the squared-error is not the primary parameter affecting the performance of a system. In many communication systems, for instance, the information bits are carried over the phase of the transmitted signal. In this letter, we introduce a cost function that is based on both the error magnitude and the phase error. The criterion is useful for applications where the performance depends primarily on the phase of the estimated (recovered) signal. An adaptive filter is then developed using the proposed criterion with essentially the same complexity as the standard least mean squared (LMS) algorithm. The filter outperforms LMS specially in situations with fast channel variations. Bit error rate (BER) simulations for two communication systems using the proposed algorithm support the claims.

Orthogonal frequency division multiplexing (OFDM) is a widely recognized modulation scheme for high data rate communications. However, the implementation of OFDM-based systems suffers from in-phase and quadrature-phase (IQ) imbalances in the front-end analog processing. Such imbalances are caused by the analog processing of the received radio frequency (RF) signal, and they cannot be efficiently or entirely eliminated in the analog domain. The resulting IQ distortion limits the achievable operating SNR at the receiver and, consequently, the achievable data rates. The issue of IQ imbalances is even more severe at higher SNR and higher carrier frequencies. In this paper, the effect of IQ imbalances on multi-input multioutput (MIMO) OFDM systems is studied, and a framework for combating such distortions through digital signal processing is developed. An input-output relation governing MINIO OFDM systems is derived. The framework is used to design receiver algorithms with compensation for IQ imbalances. It is shown that the complexity of the system at the receiver grows from dimension (n(R) x n(T)) for ideal IQ branches to (2n(R) X 2n(T)) in the presence of IQ imbalances. However, by exploiting the structure of space-time block codes along with the distortion models, one can obtain efficient receivers that are robust to IQ imbalances. Simulation results show significant improvement in the achievable BER of the proposed MINIO receivers for space-time block-coded OFDM systems in the presence of IQ imbalances.

The first part of this dissertation considers distributed learning problems over networked agents. The general objective of distributed adaptation and learning is the solution of global, stochastic optimization problems through localized interactions and without information about the statistical properties of the data.

Regularization is a useful technique to encourage or enforce structural properties on the resulting solution, such as sparsity or constraints. A substantial number of regularizers are inherently non-smooth, while many cost functions are differentiable. We propose distributed and adaptive strategies that are able to minimize aggregate sums of objectives. In doing so, we exploit the structure of the individual objectives as sums of differentiable costs and non-differentiable regularizers. The resulting algorithms are adaptive in nature and able to continuously track drifts in the problem; their recursions, however, are subject to persistent perturbations arising from the stochastic nature of the gradient approximations and from disagreement across agents in the network. The presence of non-smooth, and potentially unbounded, regularizers enriches the dynamics of these recursions. We quantify the impact of this interplay and draw implications for steady-state performance as well as algorithm design and present applications in distributed machine learning and image reconstruction.

There has also been increasing interest in understanding the behavior of gradient-descent algorithms in non-convex environments. In this work, we consider stochastic cost functions, where exact gradients are replaced by stochastic approximations and the resulting gradient noise persistently seeps into the dynamics of the algorithm. We establish that the diffusion learning algorithm continues to yield meaningful estimates in these more challenging, non-convex environments, in the sense that (a) despite the distributed implementation, individual agents cluster in a small region around the weighted network centroid in the mean-fourth sense, and (b) the network centroid inherits many properties of the centralized, stochastic gradient descent recursion, including the escape from strict saddle-points in time inversely proportional to the step-size and return of approximately second-order stationary points in a polynomial number of iterations.

In the second part of the dissertation, we consider centralized learning problems over networked feature spaces. Rapidly growing capabilities to observe, collect and process ever increasing quantities of information, necessitate methods for identifying and exploiting structure in high-dimensional feature spaces. Networks, frequently referred to as graphs in this context, have emerged as a useful tool for modeling interrelations among different parts of a data set. We consider graph signals that evolve dynamically according to a heat diffusion process and are subject to persistent perturbations. The model is not limited to heat diffusion but can be applied to modeling other processes such as the evolution of interest over social networks and the movement of people in cities. We develop an online algorithm that is able to learn the underlying graph structure from observations of the signal evolution and derive expressions for its performance. The algorithm is adaptive in nature and able to respond to changes in the graph structure and the perturbation statistics. Furthermore, in order to incorporate prior structural knowledge to improve classification performance, we propose a BRAIN strategy for learning, which enhances the performance of traditional algorithms, such as logistic regression and SVM learners, by incorporating a graphical layer that tracks and learns in real-time the underlying correlation structure among feature subspaces. In this way, the algorithm is able to identify salient subspaces and their correlations, while simultaneously dampening the effect of irrelevant features.

This dissertation focuses on stochastic gradient learning for problems involving large data sets or large feature spaces. One of the main advantages of the stochastic gradient technique is its simplicity and low computational complexity, especially for large datasets. This is because it selects, at each iteration, one data point at random from the training set, updates the weight iterate using this data point, and continuously repeats the procedure until sufficient convergence is attained. Two popular mechanisms for sampling the training data is to sample with or without replacement. In the first case, some samples may be repeated during the learning process, while in the second case the training data is first reshuffled randomly and the algorithm is run over the reshuffled data one sample at a time.

It has been observed in the literature through experimentation that learning under random reshuffling leads to enhanced performance, not only for the traditional stochastic gradient algorithms but also for variance-reduced implementations. However, no theoretical analysis exists that explains the phenomenon well under constant step-size adaptation. The first part of this dissertation resolves this issue and establishes analytically that, under random reshuffling, convergence is guaranteed to a small neighborhood of the optimizer at a linear rate. The analysis further shows that random reshuffling outperforms uniform sampling by showing that the iterates approach a smaller neighborhood of size $O(\mu^2)$ around the minimizer as opposed to $O(\mu)$. An analytical expression for the steady-state mean-square-error under random reshuffling is derived, which helps clarify in greater detail the differences between sampling with and without replacement. The dissertation also provides an explanation for the periodic behavior that is observed in random reshuffling implementations.

In addition, the dissertation examines the effect of random reshuffling on variance-reduced techniques, which are known to converge to the exact minimizers of empirical risks at linear convergence rates. The existing convergence results assume uniform data sampling with replacement and no proofs or guarantees of convergence exist under random reshuffling. The dissertation provides a theoretical guarantee of linear convergence under random reshuffling for the SAGA algorithm in the mean-square sense by using an argument that is also applicable to other variance-reduced algorithms. A new amortized variance-reduced gradient (AVRG) algorithm is also proposed, which has constant storage requirements compared to SAGA and balanced gradient computations compared to SVRG.

In the second part of the dissertation, we examine learning under large feature spaces, where the feature information is assumed to be spread across agents in a network. In this setting, each agent is assumed to observe part of the feature space. Through local cooperation, the agents are supposed to interact with each other to solve an inference problem and converge towards the global minimizer of the empirical risk. The dissertation proposes two solution methods: one operates in the dual domain and another operates in the primal domain. The dual domain solution builds on gradient boosting techniques, where each agent maintains a local dual variable. By sharing the dual variable with their immediate neighbors through a diffusion learning protocol, all agents are able to match the performance of centralized boosting solutions even when the individual agents only have access to partial information about the feature space. In comparison, the primal domain solution is achieved by combining a dynamic diffusion construction, a pipeline strategy, and variance-reduced techniques. One of the main advantages of the primal solution is that it does not require separate timescales and convergence towards the exact minimizer occurs at a linear rate.

Distributed learning deals with the problem of optimizing aggregate cost functions by networked agents from streaming data. This scenario arises in many contexts including distributed estimation, machine learning, resource allocation, and in the modeling of flocking and swarming behavior by biological networks. Among several available solutions such as consensus and incremental strategies, the class of diffusion strategies has proven to be particularly attractive because these techniques are scalable, robust, fully-distributed, and endow networks with real-time adaptation and learning abilities.

One key challenge in real applications is that networked agents generally face many types of asynchronous imperfections, such as random link failures, random data arrival times, noisy links, random topology changes, agents turning on and off randomly, and even drifting objectives. This dissertation provides a detailed analysis of the stability and performance of asynchronous diffusion strategies for solving distributed optimization and adaptation problems over networks in the presence of such imperfections. Conditions are developed to ensure the stability of the mean-square and mean-fourth-order moments of the network error vectors; closed-form expressions are derived to reveal how the network parameters influence the learning behavior; and the performance of the asynchronous networks is then compared against centralized solutions and synchronous networks. One notable conclusion is that the mean-square performance of asynchronous networks degrades only in the order of &mu, which is a small step-size parameter, while the convergence rate remains largely unaltered. A second notable conclusion is that even under the influence of asynchronous events, all agents in the adaptive network can still reach an O(&mu^{1+&gamma<\super>)$ near-agreement with some constant &gamma > 0, while approaching the desired solution within O(&mu) accuracy. These theoretical results provide a solid justification for the remarkable resilience of cooperative networks in the face of random imperfections at multiple levels: agents, links, data arrivals, and topology.}

The dissertation also examines a second challenging form of uncertainty arising from agents in a network pursuing different objectives or observing data arising from different unknown models. In these cases, indiscriminate cooperation will lead to undesired results. A useful adaptive clustering and learning strategy is developed in order to allow agents to learn which neighbors should be trusted and which other neighbors should be ignored. The resulting procedure enables agents to identify their grouping and to attain improved learning performance.

In this dissertation, we study optimization, adaptation, and learning problems over connected networks. In these problems, each agent $k$ collects and learns from its own local data and is able to communicate with its local neighbors. While each single node in the network may not be capable of sophisticated behavior on its own, the agents collaborate to solve large-scale and challenging learning problems.

Different approaches have been proposed in the literature to boost the learning capabilities of networked agents. Among these approaches, the class of diffusion strategies has been shown to be particularly well-suited due to their enhanced stability range over other methods and improved performance in adaptive scenarios. However, diffusion implementations suffer from a small inherent bias in the iterates. When a constant step-size is employed to solve deterministic optimization problems, the iterates generated by the diffusion strategy will converge to a small neighborhood around the desired global solution but not to the exact solution itself. This bias is not due to any gradient noise arising from stochastic approximation; it is instead due to the update structure in diffusion implementations. The existence of the bias leads to three questions: (1) What is the origin of this inherent bias? (2) Can it be eliminated? (3) Does the correction of the bias bring benefits to distributed optimization, distributed adaptation, or distributed learning?

This dissertation provides affirmative solutions to these questions. Specifically, we design a new {\em exact diffusion} approach that eliminates the inherent bias in diffusion. Exact diffusion has almost the same structure as diffusion, with the addition of a ``correction'' step between the adaptation and combination steps. Next, this dissertation studies the performance of exact diffusion for the scenarios of distributed optimization, distributed adaptation, and distributed learning, respectively. For distributed optimization, exact diffusion is proven to converge exponentially fast to the {\em exact} global solution under proper conditions. For distributed adaptation, exact diffusion is proven to have better steady-state mean-square-error than diffusion, and this superiority is analytically shown to be more evident for sparsely-connected networks such as line, cycle, grid, and other topologies. In distributed learning, exact diffusion can be integrated with the amortized variance-reduced gradient method (AVRG) so that it converges exponentially fast to the exact global solution while employing stochastic gradients per iteration. This dissertation also compares exact diffusion with other state-of-the-art methods in literature. Intensive numerical simulations are provided to illustrate the theoretical results derived in the dissertation.

This dissertation deals with the development of effective information processing strategies for distributed optimization and learning over graphs. The work considers initially global cost functions that can be expressed as the aggregate sum of individual costs (``sum-of-costs'') and proceeds to develop diffusion adaptation algorithms that enable distributed optimization through localized coordination among neighboring agents. The diffusion strategies allow the nodes to cooperate and diffuse information in real-time and they help alleviate the effects of stochastic approximations and gradient noise through a continuous learning process. Among other applications, the resulting strategies can be applied to large-scale machine learning problems, where a network of agents is used to learn a common model from big data sets that are distributed over the network.

The work also develops diffusion strategies for the solution of another class of problems where the global cost functions are expressed as regularized ``cost-of-sum'' forms. This situation arises when a large-scale model is stored and learned over a network of agents, with each agent being in charge of a portion of the model and it is not feasible to aggregate the entire model in one location due to communication and privacy considerations. It is shown that the ``cost-of-sum'' problem can be transformed into a ``sum-of-costs'' problem by using dual decompositions and the concept of conjugate functions. The collaborative inference step in the dual domain is shown to generate dual variables that can be used by the agents to update their model without the need to share these model parameters or the training data with the other agents. This is a powerful property that leads to an efficient distributed procedure for learning large-scale models over networks.

The dissertation carries out a detailed transient and steady-state analysis of the learning behavior of multi-agent networks, and reveals interesting results about the learning abilities of distributed strategies. Among other results, the analysis reveals how combination policies influence the learning process of networked agents, and how these policies can steer the convergence point towards any of many possible Pareto optimal solutions. The results also establish that the learning process of an adaptive network undergoes three well-defined stages of evolution with distinctive convergence rates during the first two stages, while attaining a finite mean-square-error (MSE) level in the last stage. The analysis reveals what aspects of the network topology influence performance directly and suggests design procedures that can optimize performance by adjusting the relevant topology parameters. Interestingly, it is further shown that, in the adaptation regime, each agent in a sparsely connected network is able to achieve the same performance level as that of a centralized stochastic approximation strategy even for left-stochastic combination strategies. These results lead to a deeper understanding and useful insights on the convergence behavior of coupled distributed learners. The results also lead to effective design mechanisms to help diffuse information more thoroughly over networks.

In this dissertation, we study diffusion social learning over weakly-connected graphs and reveal several interesting properties characterizing the flow of information over such networks. We discover that the asymmetric flow of information hinders the learning ability of certain agents regardless of their local observations. Under some circumstances that we clarify in this work, a scenario of total influence (or "mind-control") arises where a set of influential agents ends up shaping the beliefs of non-influential agents. We derive useful closed-form expressions that characterize this influence, and then analyze this control mechanism more closely to highlight some critical properties. In particular, we use the theoretical analysis to address two main questions: (a) First, how much freedom do influential agents have in controlling the beliefs of the receiving agents? That is, can influential agents drive receiving agents to arbitrary beliefs or does the network structure limit the scope of control by the influential agents? and (b) second, even if there is a limit to what influential agents can accomplish, how can they ensure that receiving agents will end up with particular beliefs? These questions raise interesting possibilities about belief control. Once addressed, we end up with design procedures that allow influential agents to drive other agents to endorse particular beliefs regardless of their convictions. We illustrate the theoretical findings and results by means of several examples and numerical simulations.