The study of tail behaviour of \textbf{\texttt{SGD}}-induced processes has been attracting a lot of interest, due to offering strong guarantees with respect to individual runs of an algorithm. While many works provide high-probability guarantees, quantifying the error rate for a fixed probability threshold, there is a lack of work directly studying the probability of failure, i.e., quantifying the tail decay rate for a fixed error threshold. Moreover, existing results are of finite-time nature, limiting their ability to capture the true long-term tail decay which is more informative for modern learning models, typically trained for millions of iterations. Our work closes these gaps, by studying the long-term tail decay of \textbf{\texttt{SGD}}-based methods through the lens of large deviations theory, establishing several strong results in the process. First, we provide an upper bound on the tails of the gradient norm-squared of the best iterate produced by (vanilla) \textbf{\texttt{SGD}}, for non-convex costs and bounded noise, with long-term decay at rate $e^{-\frac{t}{\log(t)}}$. Next, we relax the noise assumption by considering clipped \textbf{\texttt{SGD}} (\textbf{\texttt{c-SGD}}) under heavy-tailed noise with bounded moment of order $p \in (1,2]$, showing an upper bound with long-term decay at rate $e^{-\frac{t^{\beta_p}}{\log(t)}}$, where $\beta_p = \frac{4(p-1)}{3p-2}$ for $p \in (1,2)$ and $e^{-\frac{t}{\log^2(t)}}$ for $p = 2$. Finally, we provide lower bounds on the tail decay, at rate $e^{-t}$, showing that our rates for both \textbf{\texttt{SGD}} and \textbf{\texttt{c-SGD}} are tight, up to poly-logarithmic factors. Notably, our results demonstrate \textit{an order of magnitude faster} long-term tail decay compared to existing work based on finite-time bounds, which show rates $e^{-\sqrt{t}}$ and $e^{-t^{\beta_p/2}}$, $p \in (1,2]$, for \textbf{\texttt{SGD}} and \textbf{\texttt{c-SGD}}, respectively. As such, we uncover regimes where the tails decay much faster than previously known, providing stronger long-term guarantees for individual runs.

We study high-probability convergence in online learning, in the presence of heavy-tailed noise. To combat the heavy tails, a general framework of nonlinear SGD methods is considered, subsuming several popular nonlinearities like sign, quantization, component-wise and joint clipping. In our work the nonlinearity is treated in a black-box manner, allowing us to establish unified guarantees for a broad range of nonlinear methods. For symmetric noise and non-convex costs we establish convergence of gradient norm-squared, at a rate $\widetilde{\mathcal{O}}(t^{-1/4})$, while for the last iterate of strongly convex costs we establish convergence to the population optima, at a rate $\mathcal{O}(t^{-\zeta})$, where $\zeta \in (0,1)$ depends on noise and problem parameters. Further, if the noise is a (biased) mixture of symmetric and non-symmetric components, we show convergence to a neighbourhood of stationarity, whose size depends on the mixture coefficient, nonlinearity and noise. Compared to state-of-the-art, who only consider clipping and require unbiased noise with bounded $p$-th moments, $p \in (1,2]$, we provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments. While the rate exponents in state-of-the-art depend on noise moments and vanish as $p \rightarrow 1$, our exponents are constant and strictly better whenever $p < 6/5$ for non-convex and $p < 8/7$ for strongly convex costs. Experiments validate our theory, showing that clipping is not always the optimal nonlinearity, further underlining the value of a general framework.

This paper studies probabilistic rates of convergence for consensus+innovations type of algorithms in random, generic networks. For each node, we find a lower and also a family of upper bounds on the large deviations rate function, thus enabling the computation of the exponential convergence rates for the events of interest on the iterates. Relevant applications include error exponents in distributed hypothesis testing, rates of convergence of beliefs in social learning, and inaccuracy rates in distributed estimation. The bounds on the rate function have a very particular form at each node: they are constructed as the convex envelope between the rate function of the hypothetical fusion center and the rate function corresponding to a certain topological mode of the node’s presence. We further show tightness of the discovered bounds for several cases, such as pendant nodes and regular networks, thus establishing the first proof of the large deviations principle for consensus+innovations and social learning in random networks.

Recent works have shown that high probability metrics with stochastic gradient descent (SGD) exhibit informativeness and in some cases advantage over the commonly adopted mean-square error-based ones. In this work we provide a formal framework for the study of general high probability bounds with SGD, based on the theory of large deviations. The framework allows for a generic (not-necessarily bounded) gradient noise satisfying mild technical assumptions, allowing for the dependence of the noise distribution on the current iterate. Under the preceding assumptions, we find an upper large deviations bound for SGD with strongly convex functions. The corresponding rate function captures analytical dependence on the noise distribution and other problem parameters. This is in contrast with conventional mean-square error analysis that captures only the noise dependence through the variance and does not capture the effect of higher order moments nor interplay between the noise geometry and the shape of the cost function. We also derive exact large deviation rates for the case when the objective function is quadratic and show that the obtained function matches the one from the general upper bound hence showing the tightness of the general upper bound. Numerical examples illustrate and corroborate theoretical findings.

Deploying deep neural networks (DNNs) on IoT and mobile devices is a challenging task due to their limited computational resources. Thus, demanding tasks are often entirely offloaded to edge servers which can accelerate inference, however, it also causes communication cost and evokes privacy concerns. In addition, this approach leaves the computational capacity of end devices unused. Split computing is a paradigm where a DNN is split into two sections; the first section is executed on the end device, and the output is transmitted to the edge server where the final section is executed. Here, we introduce dynamic split computing, where the optimal split location is dynamically selected based on the state of the communication channel. By using natural bottlenecks that already exist in modern DNN architectures, dynamic split computing avoids retraining and hyperparameter optimization, and does not have any negative impact on the final accuracy of DNNs. Through extensive experiments, we show that dynamic split computing achieves faster inference in edge computing environments where the data rate and server load vary over time.

We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality with respect to cluster assignments and cluster center positions. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions, satisfying some mild assumptions. The main advantage of the proposed approach is a simple and computationally cheap update rule. Unlike previous methods that specialize to a specific formulation of the clustering problem, our approach is applicable to a wide range of costs, including non-Bregman clustering methods based on the Huber loss. We analyze the convergence of the proposed algorithm, and show that it converges to the set of appropriately defined fixed points, under arbitrary center initialization. In the special case of Bregman cost functions, the algorithm converges to the set of centroidal Voronoi partitions, which is consistent with prior works. Numerical experiments on real data demonstrate the effectiveness of the proposed method.

The augmented Lagrangian method (ALM) is a classical optimization tool that solves a given “difficult” (constrained) problem via finding solutions of a sequence of “easier” (often unconstrained) subproblems with respect to the original (primal) variable, wherein constraints satisfaction is controlled via the so-called dual variables. ALM is highly flexible with respect to how primal subproblems can be solved, giving rise to a plethora of different primal-dual methods. The powerful ALM mechanism has recently proved to be very successful in various large-scale and distributed applications. In addition, several significant advances have appeared, primarily on precise complexity results with respect to computational and communication costs in the presence of inexact updates and design and analysis of novel optimal methods for distributed consensus optimization. We provide a tutorial-style introduction to ALM and its variants for solving convex optimization problems in large-scale and distributed settings. We describe control-theoretic tools for the algorithms' analysis and design, survey recent results, and provide novel insights into the context of two emerging applications: federated learning and distributed energy trading.

Smart Grid is expected to support a variety of services for energy prosumers - entities that are able both to produce and consume energy. Enabling cooperation among such prosumers in the form of energy trading may be highly beneficial for all actors in Smart Grid. However, in order to provide energy trading capabilities, a communication infrastructure that will be able to offer energy trading service to a massive number of energy traders dispersed over a large geographic area is needed. In this paper, we argue that a 4G/5G cellular network that offers cellular Internet of Things (IoT) services and provides mobile edge computing (MEC) capabilities is ideally suited for future widespread energy trading. We discuss architecture of such a system, identify and present analytic models for each of its parts that also account for stochastic aspects, and propose an overall energy trading system model. By doing so, we obtain a novel optimization problem formulation of the energy trading, that is capable of handling uncertainties in price changes. Our results and discussion provides initial insights towards the design of energy trading services via emerging IoT/MEC-enabled mobile cellular networks.

We consider the problem of detecting a random walk on a graph, based on observations of the graph nodes. When visited by the walk, each node of the graph observes a signal of elevated mean, which we assume can be different across different nodes. Outside of the path of the walk, and also in its absence, nodes measure only noise. Assuming the Neyman-Pearson setting, our goal then is to characterize detection performance by computing the error exponent for the probability of a miss, under a constraint on the probability of false alarm. Since the exact computation of the error exponent is known to be difficult, equivalent to the computation of the Lyapunov exponent, we approximate its value by finding a tractable lower bound. The bound reveals an interesting detectability condition: the walk is detectable whenever the entropy of the walk is smaller than one half of the expected signal-to-noise ratio. We derive the bound by extending the notion of Markov types to Gauss-Markov types. These are sequences of the state-observation pairs with a given number of node-to-node transition counts and the same average signal values across nodes, computed from the measurements made during the times the random walk visited each node's respective location. The lower bound has an intuitive interpretation: among all Gauss-Markov types that are asymptotically feasible in the absence of the walk, the bound finds the most typical one under the presence of the walk. Finally, we show by a sequence of judicious problem reformulations that computing the bound reduces to solving a convex optimization problem, which is a result of in its interest own right.

We derive the large deviation rate for convergence in probability of products of independent but not identically distributed stochastic matrices arising in time-varying distributed consensus-type networks. More precisely, we consider the model in which there exists a baseline topology that describes all possible communications and nodes are activated sparsely. At any given time, a node is active with a certain time-dependent probability, and any two nodes communicate if they are both active at that time. Under this model, we compute the exact rate for exponential decay of probabilities that the matrix products stay bounded away from their limiting matrix. We show that the rate is given by the minimal vertex cut of the baseline topology, where the node costs are defined by their limiting activation probabilities. The computed rate has many potential applications in distributed inference with intermittent communications. We provide an application in the context of consensus+innovations distributed detection. Therein, we show that optimal error exponent is achievable under a very general model of sparsified activations, thus effectively constructing asymptotically optimal detectors with significant communications savings.

We introduce a neighborhood-based data access model for distributed coded storage allocation. Storage nodes are connected in a generic network and data is accessed locally: a user accesses a randomly chosen storage node, which subsequently queries its neighborhood to recover the data object. We aim at finding an optimal allocation that minimizes the overall storage budget while ensuring recovery with probability one. We show that the problem reduces to finding the fractional dominating set of the underlying network. Furthermore, we develop a fully distributed algorithm where each storage node communicates only with its neighborhood in order to find its optimal storage allocation. The proposed algorithm is based upon the recently proposed proximal center method-an efficient dual decomposition based on accelerated dual gradient method. We show that our algorithm achieves a (1 + ε)-approximation ratio in O(dmax3/2/ε) iterations and per-node communications, where dmaxis the maximal degree across nodes. Simulations demonstrate the effectiveness of the algorithm.

We introduce a framework to study slotted Aloha with cooperative base stations. Assuming a geographic-proximity communication model, we propose several decoding algorithms with different degrees of base stations' cooperation (noncooperative, spatial, temporal, and spatio-temporal). With spatial cooperation, neighboring base stations inform each other whenever they collect a user within their coverage overlap; temporal cooperation corresponds to (temporal) successive interference cancellation done locally at each station. We analyze the four decoding algorithms and establish several fundamental results. With all algorithms, the peak throughput (average number of decoded users per slot, across all base stations) increases linearly with the number of base stations. Further, temporal and spatio-temporal cooperations exhibit a threshold behavior with respect to the normalized load (number of users per station, per slot). There exists a positive load G*, such that, below G*, the decoding probability is asymptotically maximal possible, equal the probability that a user is heard by at least one base station; with non-cooperative decoding and spatial cooperation, we show that G* is zero. Finally, with spatio-temporal cooperation, we optimize the degree distribution according to which users transmit their packet replicas; the optimum is in general very different from the corresponding optimal distribution of the single-base station system.

We consider framed slotted Aloha where m base stations cooperate to decode messages from n users. Users and base stations are placed uniformly at random over an area. At each frame, each user sends multiple replicas of its packet according to a prescribed distribution, and it is heard by all base stations within the communication radius r. Base stations employ a decoding algorithm that utilizes the successive interference cancellation mechanism, both in space-across neighboring base stations, and in time-across different slots, locally at each base station. We show that there exists a threshold on the normalized load G = n/(τm), where τ is the number of slots per frame, below which decoding probability converges asymptotically (as n, m, τ → ∞, r → 0) to the maximal possible value-the probability that a user is heard by at least one base station, and we find a lower bound on the threshold. Further, we give a heuristic evaluation of the decoding probability based on the and-or-tree analysis. Finally, we show that the peak throughput increases linearly in the number of base stations.

We show that distributed detection over random networks, or using a random protocol, e.g., of the gossip type, is asymptotically optimal, if the rate of information flow across the random network is large enough. Asymptotic optimality is in the sense of Chernoff information; in other words, we determine when the exponential rate of decay of the error probability for distributed detection is the best possible and equal to the rate of decay of the best centralized detector. The rate of information flow is defined by |log r|, where r is the second largest eigenvalue of the second moment of the random, consensus weight matrix. We quantify interesting tradeoffs in distributed detection, between the rate of information flow and the achievable detection performance.