Most high-dimensional estimation and classification methods propose to minimize a loss function (empirical risk) that is the sum of losses associated with each observed data point. We consider the special case of binary classification problems, where the loss is a function of the inner product of the feature vectors and a weight vector. For this special class of classification tasks, the empirical risk minimization problem can be recast as a minimax optimization which has a unique saddle point when the losses are smooth functions. We propose a distributed proximal primal-dual method to solve the minimax problem. We also analyze the convergence of the proposed primal-dual method and show its convergence to the unique saddle point. To prove the convergence results, we present a novel analysis of the consensus terms that takes into account the non-Euclidean geometry of the parameter space. We also numerically verify the convergence of the proposed algorithm for the logistic regression on the Erdös-Réyni random graphs and lattices.

Power capping is a mechanism to ensure that the power consumption of clusters does not exceed the provisioned resources. A fast power capping method allows for a safe over-subscription of the rated power distribution devices, provides equipment protection, and enables large clusters to participate in demand-response programs. However, current methods have a slow response time with a large actuation latency when applied across a large number of servers as they rely on hierarchical management systems. We propose a fast decentralized power capping (DPC) technique that reduces the actuation latency by localizing power management at each server. The DPC method is based on a maximum throughput optimization formulation that takes into account the workloads priorities as well as the capacity of circuit breakers. Therefore, DPC significantly improves the cluster performance compared to alternative heuristics. We implement the proposed decentralized power management scheme on a real computing cluster. Compared to state-of-the-art hierarchical methods, DPC reduces the actuation latency by 72% up to 86% depending on the cluster size. In addition, DPC improves the system throughput performance by 16%, while using only 0.02% of the available network bandwidth. We describe how to minimize the overhead of each local DPC agent to a negligible amount. We also quantify the traffic and fault resilience of our decentralized power capping approach.

We study a stochastic primal-dual method for optimizing functions on elliptic (sub)manifolds- Riemannian (sub)manifolds with a positive bounded sectional curvature. In particular, we establish a convergence rate for geodesically convex functions that is related to the lower bound on the sectional curvature. The convergence analysis we present is based on Toponogov's comparison theorem, where geodesic triangles on the elliptic manifolds and a sphere are compared. We numerically demonstrate the performance of the proposed stochastic primal-dual algorithm on the sphere for non-negative principle component analysis (PCA), and on the Lie group SO(3) for the anchored localization from partial noisy measurements of relative rotations. In both applications, the proposed algorithm scales gracefully to high dimensions.

We study a continuous-time power policy to maximize the ergodic channel throughput of an energy harvesting transmitter over a Markov fading channel. In particular, we consider transmission power policies that are adapted to the fading process of the channel as well as the storage process of the battery. We obtain a set of equations that determine the probability density of the energy in the battery at each channel state. Specifically, for an ergodic battery storage process, these equations describe the relation between the probability density of stored energy and the transmission power at each channel state. From these equations, we derive an upper bound on the average transmission power and an upper bound on the average transmission rate. To compute a lower bound on the average transmission rate, we apply a calculus of variations technique to a non-linear throughput maximization problem. As a result, we obtain a system of coupled ordinary differential equations for locally optimal power policies. We then focus on the Gilbert-Elliot channel as a special case and derive some structural results for specific classes of fast and slow fading channels. Furthermore, we numerically find a locally optimal transmission power policy for the two channel state scenario.

Power management has become a central issue inlarge-scale computing clusters where a considerable amount ofenergy is consumed and a large operational cost is incurredannually. Traditional power management techniques have a centralizeddesign that creates challenges for scalability of computingclusters. In this work, we develop a framework for distributedpower budget allocation that maximizes the utility of computingnodes subject to a total power budget constraint. To eliminate the role of central coordinator in the primaldualtechnique, we propose a distributed power budget allocationalgorithm (DiBA) which maximizes the combined performanceof a cluster subject to a power budget constraint in a distributedfashion. Specifically, DiBA is a consensus-based algorithm inwhich each server determines its optimal power consumptionlocally by communicating its state with neighbors (connectednodes) in a cluster. We characterize a synchronous primal-dualtechnique to obtain a benchmark for comparison with thedistributed algorithm that we propose. We demonstrate numericallythat DiBA is a scalable algorithm that outperforms theconventional primal-dual method on large scale clusters in termsof convergence time. Further, DiBA eliminates the communicationbottleneck in the primal-dual method. We thoroughly evaluatethe characteristics of DiBA through simulations of large-scaleclusters. Furthermore, we provide results from a proof-of-conceptimplementation on a real experimental cluster.

We study the transmission of a set of correlated sources (U1, . . . , UK) over a Gaussian multiple access relay channel with time asynchronism between the encoders. We assume that the maximum possible offset dmax(n) between the transmitters grows without bound as the block length n → ∞, while the relative ratio dmax(n)/n of the maximum possible offset to the block length asymptotically vanishes. For such a joint source-channel coding problem and under specific gain conditions, we derive necessary and sufficient conditions for reliable communications and show that separate source and channel coding achieves optimal performance. In particular, we first derive a general outer bound on the source entropy content for all channel gains as our main result. Then, using Slepian-Wolf source coding combined with the channel coding scheme on top of block Markov coding, we show that the thus achieved inner bound matches the outer bound. As a corollary, we also address the problem of sending a pair of correlated sources over a two-user interference channel in the same context.

We study the problem of lossy joint source-channel coding in a single-user energy harvesting communication system with causal energy arrivals and the energy storage unit may have leakage. In particular, we investigate the achievable distortion in the transmission of a single source via an energy harvesting transmitter over a point-to-point channel. We consider an adaptive joint source-channel coding system, where the length of channel codewords varies based on the available battery charge. We first establish a lower bound on the achievable distortion. Then, as necessary conditions for local optimality, we obtain two coupled equations that determine the mismatch ratio between channel symbols and source symbols as well as the transmission power, both as functions of the battery charge. As examples of continuous and discrete sources, we consider Gaussian and binary sources respectively. For the Gaussian case, we obtain a closed-form expression for the mismatch factor in terms of the LambertW function, and show that an increasing transmission power policy results in a decreasing mismatch factor policy and vice versa. Finally, we numerically compare the performance of the adaptive mismatch factor scheme to the case of a constant mismatch factor.

Continuous-time lossy source transmission in an Energy Harvesting (EH) communication system is studied. In particular, the distortion performance for the transmission of a Gaussian source and compound Poisson energy arrivals is considered. Based on the convexity of the distortion function and Jensen's inequality, a lower bound on the average distortion is established in terms of the capacity of the battery and parameters such as the distribution of energy arrivals and the variance of the source. Moreover, a calculus of variations technique is used to derive an adaptive transmission power policy as well as an adaptive mismatch factor. More specifically, the structure of a locally optimal achievable power policy is characterized as the solution to a first order non-linear ordinary differential equation (ODE). Also for the mismatch factor, a closed-form formula as a function of the battery charge via the LambertW function is derived.

We investigate performance limits of a multiple access communication system with energy harvesting nodes where the utility function is taken to be the long-term average sum-throughput. We assume a causal structure for energy arrivals and study the problem in the continuous time regime. For this setting, we first characterize a storage dam model that captures the dynamics of a battery with energy harvesting and variable transmission power. Using this model, we next establish an upper bound on the throughput problem as a function of battery capacity. We also formulate a nonlinear optimization problem to determine optimal achievable power policies for transmitters. Applying a calculus of variations technique, we then derive Euler-Lagrange equations as necessary conditions for optimum power policies in terms of a system of coupled partial integro-differential equations. Based on a Gauss-Seidel algorithm, we devise an iterative algorithm to solve these equations. We also propose a fixed-point algorithm for the symmetric multiple access setting in which the statistical descriptions of energy harvesters are identical. To further support our iterative algorithms, along with the analysis, comprehensive numerical results are also obtained.

We investigate fundamental limits of lossy communication in a bi-directional (two-way), half-duplex relay channel, where users wish to exchange correlated Gaussian sources and do so by sending their data according to a two-phase transmission protocol. We first establish a general distortion inner bound using the data processing inequality. Based on uncoded transmission schemes, separate source and channel coding schemes, and a lattice coding scheme, we then develop several cooperative joint source-channel coding (JSCC) approaches. Furthermore, we compare the corresponding achievable distortion performances in terms of the correlation coefficient between Gaussian sources. This comparison particularly shows that separate source and channel coding in combination with decode-and-forward relaying achieves the best distortion values of any joint source-channel coding scheme in this paper.

We investigate the problem of continuous-time energy harvesting in communication systems operating over fading wireless channels. We model the fading as a finite-state continuous-time Markov process, and the battery dynamics as a storage dam process with reflecting boundary conditions. We describe a set of necessary conditions for the ergodicity of the dam process. Followed by these conditions, we establish an upper bound on the ergodic channel throughput. We further determine some structure for good transmission power policies based on a throughput maximization problem. Specifically, using calculus of variations techniques, we derive Euler-Lagrange equations as a necessary condition for optimal power policies. In the case of a Markov channel with two channel states (i.e. Gilbert-Elliot channel), we characterize power policies by solving these equations numerically.

We study the lossy communication of a bivariate Gaussian source over an interference channel with the presence of a helping relay. We assume that the wireless links introduce random phase shifts which are unknown to the transmitters (including the relay) and call the channel a phase incoherent interference relay channel (PI-IRC). We derive inner and outer bounds for the achievable distortion region, where the inner bound is derived under specific strong interference conditions as well as strong gain conditions between transmitters and the relay. When the sources are correlated, we find an approximate achievable distortion region in the high SNR regime. In case of independent sources, the bounds are tight and by explicitly providing the achievable distortion region, we show that a separation theorem results for the PI-IRC under strong interference conditions. By removing the relay, the result also specializes to an interference channel.