Deep learning models are dominating almost all artificial intelligence tasks such as vision, text, and speech processing.Stochastic Gradient Descent (SGD) is the main tool for training such models, where the computations are usually performed in single-precision floating-point number format.The convergence of single-precision SGD is normally aligned with the theoretical results of real numbers since they exhibit negligible error.However, the numerical error increases when the computations are performed in low-precision number formats.This provides compelling reasons to study the SGD convergence adapted for low-precision computations.We present both deterministic and stochastic analysis of the SGD algorithm, obtaining bounds that show the effect of number format.Such bounds can provide guidelines as to how SGD convergence is affected when constraints render the possibility of performing high-precision computations remote.

Since the seminal work by Shannon, theoreticians have focused on designing compressors targeted at minimizing the output size without sacrificing much of the compression/decompression efficiency. On the other hand, software engineers have deployed several heuristics to implement compressors aimed at trading compressed space versus compression/decompression efficiency in order to match their application needs. In this paper we fill this gap by introducing the bicriteria data-compression problem that seeks to determine the shortest compressed file that can be decompressed in a given time bound. Then, inspired by modern data-storage applications, we instantiate the problem onto the family of Lempel--Ziv-based compressors (such as Snappy and LZ4) and solve it by combining in a novel and efficient way optimization techniques, string-matching data structures, and shortest path algorithms over properly (bi-)weighted graphs derived from the data-compression problem at hand. An extensive set of experiments complements our theoretical achievements by showing that the proposed algorithmic solution is very competitive with respect to state-of-the-art highly engineered compressors.

Cellular network nodes should be dynamically switched on/off based on the load requirements of the network, to save power and minimize inter-cell interference. This should be done keeping into account global interference effects, which requires a centralized approach. In this paper, we present an architecture, realized within the Flex5GWare EU project, that manages a large-scale cellular network, switching on and off nodes based on load requirements and context data. We describe the architectural framework and the optimization model that is used to decide the activity state of the nodes. We present simulation results showing that the framework adapts to the minimum power level based on the cell loads.

Computing network paths under worst-case delay constraints has been the subject of abundant literature in the past two decades. Assuming weighted fair queueing scheduling at the nodes, this translates to computing paths and reserving rates at each link. The problem is 𝒩𝒫-hard in general, even for a single path; hence polynomial-time heuristics have been proposed in the past that either assume equal rates at each node, or compute the path heuristically and then allocate the rates optimally on the given path. In this paper we show that the above heuristics, albeit finding optimal solutions quite often, can lead to failing of paths at very low loads, and that this could be avoided by solving the problem, i.e. path computation and rate allocation, jointly at optimality. This is possible by modeling the problem as a mixed-integer second-order cone program and solving it optimally in split-second times for relatively large networks on commodity hardware; this approach can also be easily turned into a heuristic one, trading a negligible increase in blocking probability for one order of magnitude of computation time. Extensive simulations show that these methods are feasible in today's Internet service provider networks and they significantly outperform the existing schemes in terms of blocking probability.

In this paper we address the problem of trading optimally, and in a principled way, the compressed size/decompression time of LZ77 parsings by introducing what we call the Bicriteria LZ77-Parsing problem. The goal is to determine an LZ77 parsing which minimizes the space occupancy in bits of the compressed file, provided that the decompression time is bounded by T. Symmetrically, we can exchange the role of the two resources and thus ask for minimizing the decompression time provided that the compressed space is bounded by a fixed amount given in advance. We address this goal in three stages: (i) we introduce the novel Bicriteria LZ77-Parsing problem which formalizes in a principled way what data-compressors have traditionally approached by means of heuristics; (ii) we solve this problem efficiently, up to a negligible additive constant, in O(nlog2 n) time and optimal O(n) words of working space, by proving and deploying some specific structural properties of a weighted graph derived from the possible LZ77-parsings of the input file; (iii) we execute a preliminary set of experiments which show that our novel compressor is very competitive to all the highly engineered competitors (such as Snappy, lzma, bzip2), hence offering a win-win situation in theory&practice.

A graph G=(V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n=7, …, 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any PCG admits a full binary tree as witness tree T.

In the last two decades, a number of algorithms for the linear single-commodity min-cost flow (MCF) problem have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving “from-scratch” instances of MCF, of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of MCF have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one that minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for MCF under cost reoptimization in the context of decomposition algorithms for the multicommodity min-cost flow (MMCF) problem, showing that for some classes of instances the relative performances of the codes doing “from-scratch” optimization do not accurately predict the relative performances when reoptimization is used. Because the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for MCF problem solvers that we have proposed and implemented.

We study the coarse-grained parallelization of an efficient bundle-based cost-decomposition algorithm for the solution of multicommodity min-cost flow (MMCF) problems. We show that a code exploiting only the natural parallelism inherent in the cost-decomposition approach, i.e., solving the min-cost flow subproblems in parallel, obtains satisfactory efficiencies even with many processors on large, difficult MMCF problems with many commodities. This is exactly the class of instances where the decomposition approach attains its best results in sequential. The parallel code we developed is highly portable and flexible, and it can be used on different machines. We also show how to exploit a common characteristic of current supercomputer facilities, i.e., the side-to-side availability of massively parallel and vector supercomputers, to implement an asymmetric decomposition algorithm where each architecture is used for the tasks for which it is best suited.

We present a Cost Decomposition approach for the linear Multicommodity Min-Cost Flow problem, where the mutual capacity constraints are dualized and the resulting Lagrangean Dual is solved with a dual-ascent algorithm belonging to the class of Bundle methods. Although decomposition approaches to block-structured Linear Programs have been reported not to be competitive with general-purpose software, our extensive computational comparison shows that, when carefully implemented, a decomposition algorithm can outperform several other approaches, especially on problems where the number of commodities is “large” with respect to the size of the graph. Our specialized Bundle algorithm is characterized by a new heuristic for the trust region parameter handling, and embeds a specialized Quadratic Program solver that allows the efficient implementation of strategies for reducing the number of active Lagrangean variables. We also exploit the structural properties of the single-commodity Min-Cost Flow subproblems to reduce the overall computational cost. The proposed approach can be easily extended to handle variants of the problem.