An important open problem is the theoretically feasible acceleration of mini-batch SGD-type algorithms on quadratic problems with power-law spectrum. In the non-stochastic setting, the optimal exponent $\xi$ in the loss convergence $L_t\sim C_Lt^{-\xi}$ is double that in plain GD and is achievable using Heavy Ball (HB) with a suitable schedule; this no longer works in the presence of mini-batch noise. We address this challenge by considering first-order methods with an arbitrary fixed number $M$ of auxiliary velocity vectors (*memory-$M$ algorithms*). We first prove an equivalence between two forms of such algorithms and describe them in terms of suitable characteristic polynomials. Then we develop a general expansion of the loss in terms of *signal and noise propagators*. Using it, we show that losses of stationary stable memory-$M$ algorithms always retain the exponent $\xi$ of plain GD, but can have different constants $C_L$ depending on their *effective learning rate* that generalizes that of HB. We prove that in memory-1 algorithms we can make $C_L$ arbitrarily small while maintaining stability. As a consequence, we propose a memory-1 algorithm with a time-dependent schedule that we show heuristically and experimentally to improve the exponent $\xi$ of plain SGD.

The asymptotically precise estimation of the generalization of kernel methods has recently received attention due to the parallels between neural networks and their associated kernels. However, prior works derive such estimates for training by kernel ridge regression (KRR), whereas neural networks are typically trained with gradient descent (GD). In the present work, we consider the training of kernels with a family of \emph{spectral algorithms} specified by profile $h(\lambda)$, and including KRR and GD as special cases. Then, we derive the generalization error as a functional of learning profile $h(\lambda)$ for two data models: high-dimensional Gaussian and low-dimensional translation-invariant model. Under power-law assumptions on the spectrum of the kernel and target, we use our framework to (i) give full loss asymptotics for both noisy and noiseless observations (ii) show that the loss localizes on certain spectral scales, giving a new perspective on the KRR saturation phenomenon (iii) conjecture, and demonstrate for the considered data models, the universality of the loss w.r.t. non-spectral details of the problem, but only in case of noisy observation.

We explore the theoretical possibility of learning $d$-dimensional targets with $W$-parameter models by gradient flow (GF) when $W<d$. Our main result shows that if the targets are described by a particular $d$-dimensional probability distribution, then there exist models with as few as two parameters that can learn the targets with arbitrarily high success probability. On the other hand, we show that for $W<d$ there is necessarily a large subset of GF-non-learnable targets. In particular, the set of learnable targets is not dense in $\mathbb R^d$, and any subset of $\mathbb R^d$ homeomorphic to the $W$-dimensional sphere contains non-learnable targets. Finally, we observe that the model in our main theorem on almost guaranteed two-parameter learning is constructed using a hierarchical procedure and as a result is not expressible by a single elementary function. We show that this limitation is essential in the sense that most models written in terms of elementary functions cannot achieve the learnability demonstrated in this theorem.

Performance of optimization on quadratic problems sensitively depends on the low-lying part of the spectrum. For large (effectively infinite-dimensional) problems, this part of the spectrum can often be naturally represented or approximated by power law distributions, resulting in power law convergence rates for iterative solutions of these problems by gradient-based algorithms. In this paper, we propose a new spectral condition providing tighter upper bounds for problems with power law optimization trajectories. We use this condition to build a complete picture of upper and lower bounds for a wide range of optimization algorithms - Gradient Descent, Steepest Descent, Heavy Ball, and Conjugate Gradients - with an emphasis on the underlying schedules of learning rate and momentum. In particular, we demonstrate how an optimally accelerated method, its schedule, and convergence upper bound can be obtained in a unified manner for a given shape of the spectrum. Also, we provide first proofs of tight lower bounds for convergence rates of Steepest Descent and Conjugate Gradients under spectral power laws with general exponents. Our experiments show that the obtained convergence bounds and acceleration strategies are not only relevant for exactly quadratic optimization problems, but also fairly accurate when applied to the training of neural networks.

By universal formulas we understand parameterized analytic expressions that have a fixed complexity, but nevertheless can approximate any continuous function on a compact set. There exist various examples of such formulas, including some in the form of neural networks. In this paper we analyze the essential structural elements of these highly expressive models. We introduce a hierarchy of expressiveness classes connecting the global approximability property to the weaker property of infinite VC dimension, and prove a series of classification results for several increasingly complex functional families. In particular, we introduce a general family of polynomially-exponentially-algebraic functions that, as we prove, is subject to polynomial constraints. As a consequence, we show that fixed-size neural networks with not more than one layer of neurons having transcendental activations (e.g., sine or standard sigmoid) cannot in general approximate functions on arbitrary finite sets. On the other hand, we give examples of functional families, including two-hidden-layer neural networks, that approximate functions on arbitrary finite sets, but fail to do that on the whole domain of definition.

A memory efficient approach to ensembling neural networks is to share most weights among the ensembled models by means of a single reference network. We refer to this strategy as Embedded Ensembling (EE); its particular examples are BatchEnsembles and Monte-Carlo dropout ensembles. In this paper we perform a systematic theoretical and empirical analysis of embedded ensembles with different number of models. Theoretically, we use a Neural-Tangent-Kernel-based approach to derive the wide network limit of the gradient descent dynamics. In this limit, we identify two ensemble regimes - independent and collective - depending on the architecture and initialization strategy of ensemble models. We prove that in the independent regime the embedded ensemble behaves as an ensemble of independent models. We confirm our theoretical prediction with a wide range of experiments with finite networks, and further study empirically various effects such as transition between the two regimes, scaling of ensemble performance with the network width and number of models, and dependence of performance on a number of architecture and hyperparameter choices.

We call a finite family of activation functions \emph{superexpressive} if any multivariate continuous function can be approximated by a neural network that uses these activations and has a fixed architecture only depending on the number of input variables (i.e., to achieve any accuracy we only need to adjust the weights, without increasing the number of neurons). Previously, it was known that superexpressive activations exist, but their form was quite complex. We give examples of very simple superexpressive families: for example, we prove that the family $\{sin, arcsin\}$ is superexpressive. We also show that most practical activations (not involving periodic functions) are not superexpressive.

Current theoretical results on optimization trajectories of neural networks trained by gradient descent typically have the form of rigorous but potentially loose bounds on the loss values. In the present work we take a different approach and show that the learning trajectory of a wide network in a lazy training regime can be characterized by an explicit asymptotic at large training times. Specifically, the leading term in the asymptotic expansion of the loss behaves as a power law $L(t) \sim C t^{-\xi}$ with exponent $\xi$ expressed only through the data dimension, the smoothness of the activation function, and the class of function being approximated. Our results are based on spectral analysis of the integral operator representing the linearized evolution of a large network trained on the expected loss. Importantly, the techniques we employ do not require a specific form of the data distribution, for example Gaussian, thus making our findings sufficiently universal.

In this paper, we present a new beam selection approach for the beamspace channel estimation (CE) in 64 antennas Massive Multiple-Input Multiple-Output (MIMO) receiver. Usually, the beamspace CE is implemented via digital transformation of antenna signal to a priori selected sub-space of discrete Fourier transform (DFT) directed towards propagation channel taps. This results in less complexity of CE and MIMO detector units. We propose a new data-based sub-space selection method, which outperforms the DFT-based beam selection thanks to employing prior knowledge of channel tap distribution in the spatial domain. Simulation results are presented for the non-line-of-sight models of the 5G QuaDRiGa 2.0 channel.

In this paper, we present a new sparse channel estimation (CE) for phase-synchronized sub-6G Massive Multiple-Input Multiple-Output (MIMO) receivers. The algorithm employs an iterative search for propagation channel taps, spatial filtration, and denoising. For that, we split each channel tap signal into tap-aligned and orthogonal parts and train their weighting coefficients in non-line-of-sight channel realizations generated in the QuaDRiGa 2.0 software. Simulation results are presented and compared with the beamspace CE implemented by the digital transformation of the antenna signal to a priori selected subspace directed towards channel taps.

In this paper, we propose a new channel interpolation algorithm for Massive Multiple Input, Multiple Output (MIMO) receivers. The algorithm employs adaptive linear interpolation for each channel tap separately in the time domain. It outperforms a common spline or linear interpolation due to considering more statistics (noise power and channel sparsity). The method is validated with a practical sparse channel estimation algorithm in both antenna and beam domains of 64 antennas receiver. Simulation results are presented for users, moving with a speed of up to 160km/h in line-of-sight scenarios (car in highway, fast train, quadcopter, and many others) of 5G QuaDRiGa 2.0 channel.

We propose a new Machine Learning (ML) approach to channel estimation (CE) in Massive Multiple Input Multiple Output (MIMO) receivers. The algorithm employs a recurrent neural network (RNN) for iterative channel tap search and nonlinear de-noising of their amplitudes in the time domain. Our method outperforms the sparse minimum mean square error (MMSE) CE that is based on time-domain windowing and a further linear denoising of channel taps within the window. Simulation results are presented for user speed of 5km/h in non-line-of-sight scenarios of the 5G QuaDRiGa 2.0 channel. The results are provided in both antenna and beamspace domains of the 64 antennas receiver.

In this paper, we present a new performance bound for uplink channel estimation (CE) accuracy in the Massive Multiple Input Multiple Output (MIMO) system. The proposed approach is based on noise power calculation after the CE unit in a multi-antenna receiver. We decompose a non-line of sight (NLOS) channel into separate taps and calculate the cross-covariance matrix between them. Then a linear minimum mean squared error (MMSE) method is applied with these taps to estimate residual CE error value for each unique scenario, assuming Gaussian distribution of tap amplitudes and antenna noise. An artificial CE is calculated as a sum of the ideal noiseless channel (pre-defined Quadriga model) and the leftover noise after the optimal estimate. The artificial CE is then utilized in the MIMO detector and decoder units to calculate performance bound. Our method outperforms the accuracy of a well-known Cramer-Rao lower bound (CRLB) due to considering more statistics (number of taps and correlation between them) since performance strongly depends on several channel taps and their power ratio. Additionally, we show that our bound can be obtained from the generalized Bayesian CRLB. Simulation results are presented for the 5G QuaDRiGa 2.0 NLOS channel.

In this paper, we present a new performance bound for uplink channel estimation (CE) accuracy in the Massive Multiple Input Multiple Output (MIMO) system. The proposed approach is based on noise power prediction after the CE unit. Our method outperforms the accuracy of a well-known Cramer-Rao lower bound (CRLB) due to considering more statistics since performance strongly depends on a number of channel taps and power ratio between them. Simulation results are presented for the non-line of sight (NLOS) 3D-UMa model of 5G QuaDRiGa 2.0 channel and compared with CRLB and state-of-the-art CE algorithms.

Recent research shows that sublevel sets of the loss surfaces of overparameterized networks are connected, exactly or approximately. We describe and compare experimentally a panel of methods used to connect two low-loss points by a low-loss curve on this surface. Our methods vary in accuracy and complexity. Most of our methods are based on ”macroscopic” distributional assumptions and are insensitive to the detailed properties of the points to be connected. Some methods require a prior training of a ”global connection model” which can then be applied to any pair of points. The accuracy of the method generally correlates with its complexity and sensitivity to the endpoint detail.

We explore the phase diagram of approximation rates for deep neural networks and prove several new theoretical results. In particular, we generalize the existing result on the existence of deep discontinuous phase in ReLU networks to functional classes of arbitrary positive smoothness, and identify the boundary between the feasible and infeasible rates. Moreover, we show that all networks with a piecewise polynomial activation function have the same phase diagram. Next, we demonstrate that standard fully-connected architectures with a fixed width independent of smoothness can adapt to smoothness and achieve almost optimal rates. Finally, we consider deep networks with periodic activations ("deep Fourier expansion") and prove that they have very fast, nearly exponential approximation rates, thanks to the emerging capability of the network to implement efficient lookup operations.

In this paper, we propose a new nonlinear detector with improved interference suppression in Multi-User Multiple Input, Multiple Output (MU-MIMO) system. The proposed detector is a combination of the following parts: QR decomposition (QRD), low complexity users sorting before QRD, sorting-reduced (SR) K-best method and minimum mean square error (MMSE) preprocessing. Our method outperforms a linear interference rejection combining (IRC, i.e. MMSE naturally) method significantly in both strong interference and additive white noise scenarios with both ideal and real channel estimations. This result has wide application importance for scenarios with strong interference, i.e. when co-located users utilize the internet in stadium, highway, shopping center, etc. Simulation results are presented for the non-line of sight 3D-UMa model of 5G QuaDRiGa 2.0 channel for 16 highly correlated single-antenna users with QAM16 modulation in 64 antennas of Massive MIMO system. The performance was compared with MMSE and other detection approaches.

In this paper, we propose a new algorithm of iterative least squared (LS) channel estimation for 64 antennas Massive Multiple Input, Multiple Output (MIMO) turbo-receiver. The algorithm employs log-likelihood ratios (LLR) of low-density parity-check (LDPC) decoder and minimum mean square error (MMSE) estimator to achieve soft data symbols. These soft data symbols are further MMSE-weighted again and combined with pilot symbols to achieve a modified LS channel estimate. The modified LS estimate is employed by the same channel estimation unit to enhance turbo-receiver performance via channel re-estimation, as a result, the proposed approach has low complexity and fits any channel estimation solution, which is quite valuable in practice. We analyze both hard and soft algorithm versions and present simulation results of 5G turbo-receiver in the 3D-UMa model of the QuaDRiGa 2.0 channel. Simulation results demonstrate up to 0. 3dB performance gain compared to the unweighted hard data symbols utilization in the LS channel re-calculation.

In this paper, we propose a new candidates list re-calculating to improve performance of iterative nonlinear detection and decoding in Multi-User (MU) Massive Multiple Input, Multiple Output (MIMO) system. The proposed nonlinear iterative detector includes a new algorithm of users (UEs) sorting before QR decomposition (QRD) and a new sorting-reduced (SR) K-best method. If MIMO detector is based on a candidates list updates, the performance can be improved by the candidates list re-calculating or using a priori information in the list generation. This is natural, because the quality of the candidates list is likely to be improved by using the decoder output as a priori information. We analyze the convergence of combining the detection algorithms with the soft low-density parity-check (LDPC) decoder. Simulation results are presented in 5G QuaDRiGa channel with QAM64 modulation in 48 × 64 MIMO system and compared with other state-of-art approaches.

We consider approximations of general continuous functions on finite-dimensional cubes by general deep ReLU neural networks and study the approximation rates with respect to the modulus of continuity of the function and the total number of weights $W$ in the network. We establish the complete phase diagram of feasible approximation rates and show that it includes two distinct phases. One phase corresponds to slower approximations that can be achieved with constant-depth networks and continuous weight assignments. The other phase provides faster approximations at the cost of depths necessarily growing as a power law $L\sim W^{\alpha}, 0<\alpha\le 1,$ and with necessarily discontinuous weight assignments. In particular, we prove that constant-width fully-connected networks of depth $L\sim W$ provide the fastest possible approximation rate $\|f-\widetilde f\|_\infty = O(\omega_f(O(W^{-2/\nu})))$ that cannot be achieved with less deep networks.

In this paper a new unused beam reservation (UBR) algorithm is proposed to reduce peak-to-average power ratio (PAPR) of orthogonal frequency division multiplexing (OFDM) signal in the downlink channel of Massive Multiple Input Multiple Output (MIMO) system. The main challenge with PAPR reduction in coming 5G system is the selection of a method, which has an ultra-low latency and ability to reduce PAPR without performance degradation of high order modulation users (QAM256, QAM1024). This paper reviews some conventional PAPR reduction techniques with respect to selective tone reservation algorithm (STR, [1]) and finally we propose the UBR algorithm, which provides an extra gain in multi-user (MU) MIMO application scenarios. UBR is a non-iterative algorithm compared with a well-known tones reservation, constellation extension and clipping & filtering methods. It is based on a non-iterative modulation of unused beams amplitudes in the downlink channel of MU-MIMO so that target users are not degraded while PAPR is reduced on each TX antenna. Also UBR is fully consistent with 5G standard requirements and has a low latency. Advantages and disadvantages of this technique are discussed in details, simulation results are presented for 64 antennas of virtual Massive MIMO cell.

In this paper, we proposed a discrete sorting optimization approach for uplink channel of Massive Multiple Input, Multiple Output (MIMO) system. The algorithm includes users (UEs) sorting before QR decomposition (QRD) and sorting-reduced (SR) K-best detector for 48x64 MIMO uncoded systems. Simulation results show that detector losses is about 1dB to a Maximum Likelihood (ML) detection in low detector complexity.The UEs sorting is required to sort diagonal elements of the R matrix in ascending order to avoid error propagation in multi-user (MU) scenario. Fast and low complexity method of online discrete optimization is used to find the loss function minimum. Sorting tracking is proposed, so that the pre-sorted interpolated R matrix is used for further sorting optimization, resulting in low sorting complexity. The proposed sorting demonstrates huge performance gain compare to a common power-based one. Simulation results in 5G QuaDRiGa channel are presented.SR-K-best detector is a variant of K-best detector. The SR-K-best with (K,S,p) parameters results in significant losses in scenarios with high correlated users, therefore we proposed a new structure (K,S,p,v,q) of the SR-K-best algorithm and a new discrete optimization method to increase performance. Discrete stochastic optimization was done offline in QuaDRiGa channel to find optimal (K,S,p,v,q) parameters for fixed detector structure.

Modern railway networks include thousands of failure registration devices, and prompt response to detected failures is critical to normal network operation. However, a large share of produced alerts may be formed by false alarms associated with maintenance or faulty diagnostics, thus hindering the processing of actual failures. It is therefore very desirable to perform fast automated intelligent ranking of incidents before they are analyzed by human operators. In this paper we describe a machine-learning-based incident ranking model that we have developed and deployed at the Moscow Railway network (a large network with 500+ stations). The model estimates the probability of failure using multiple features of the incident at hand. The model was constructed using the XGBoost library and a database of 5 million historical incidents. The model shows high accuracy (AUC 0.901) in the deployment environment.