Alexander Shevchenko

Hey there, I am Alex and this is my personal webpage 🦊

I am PhD student at IST Austria. I am extremely lucky to be co-advised by Marco Mondelli and Dan Alistarh. I am broadly interested in theoretical foundations of machine learning leaning towards

analysis of training dynamics of over-parameterized models
non-convex optimization in high dimensions in general

Before joining IST Austria, I got my bachelor’s degree at CS HSE and was a master student in Statistical Learning Theory at a joint programme at HSE and Skoltech. During my undergrad and master’s I was part of Bayesian Methods research group supervised by Anton Osokin and Dmitry Vetrov. I was also a research assistant at Samsung-HSE laboratory affiliated with the group.

Outside my research activities, I enjoy (😅 sometimes unhealthy amount of) anime and manga, hitting the gym and failing my bulking plans, waiting for the next Hidetaka Miyazaki’s masterpiece, and making sure that my music library and guitar do not collect too much dust.

Here is quokka so that you’ll definetily get something from visiting this webpage 🙃

"Selected" 🤔 Papers

2024

arXiv

Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth

Kevin Kögler*, Alexander Shevchenko*, Hamed Hassani, and Marco Mondelli

Preprint, 2024

Abs PDF

Autoencoders are a prominent model in many empirical branches of machine learning and lossy data compression. However, basic theoretical questions remain unanswered even in a shallow two-layer setting. In particular, to what degree does a shallow autoencoder capture the structure of the underlying data distribution? For the prototypical case of the 1-bit compression of sparse Gaussian data, we prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. Namely, the performance of the algorithm is the same as if it was compressing a Gaussian source - with no sparsity. For general data distributions, we give evidence of a phase transition phenomenon in the shape of the gradient descent minimizer, as a function of the data sparsity: below the critical sparsity level, the minimizer is a rotation taken uniformly at random (just like in the compression of non-sparse data); above the critical sparsity, the minimizer is the identity (up to a permutation). Finally, by exploiting a connection with approximate message passing algorithms, we show how to improve upon Gaussian performance for the compression of sparse data: adding a denoising function to a shallow architecture already reduces the loss provably, and a suitable multi-layer decoder leads to a further improvement. We validate our findings on image datasets, such as CIFAR-10 and MNIST.

2023

ICML

Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods

Alexander Shevchenko*, Kevin Kögler*, Hamed Hassani, and Marco Mondelli

International Conference on Machine Learning, 2023

Abs PDF

Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.

2022

JMLR

Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks

Alexander Shevchenko, Vyacheslav Kungurtsev, and Marco Mondelli

Journal of Machine Learning Research, 2022

Abs PDF

Understanding the properties of neural networks trained via stochastic gradient descent (SGD) is at the heart of the theory of deep learning. In this work, we take a meanfield view, and consider a two-layer ReLU network trained via noisy-SGD for a univariate regularized regression problem. Our main result is that SGD with vanishingly small noise injected in the gradients is biased towards a simple solution: at convergence, the ReLU network implements a piecewise linear map of the inputs, and the number of “knot” points–ie, points where the tangent of the ReLU network estimator changes–between two consecutive training inputs is at most three. In particular, as the number of neurons of the network grows, the SGD dynamics is captured by the solution of a gradient flow and, at convergence, the distribution of the weights approaches the unique minimizer of a related free energy, which has a Gibbs form. Our key technical contribution consists in the analysis of the estimator resulting from this minimizer: we show that its second derivative vanishes everywhere, except at some specific locations which represent the “knot” points. We also provide empirical evidence that knots at locations distinct from the data points might occur, as predicted by our theory.

2020

ICML

Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks

Alexander Shevchenko, and Marco Mondelli

International Conference on Machine Learning, 2020

Abs PDF Supp

The optimization of multilayer neural networks typically leads to a solution with zero training error, yet the landscape can exhibit spurious local minima and the minima can be disconnected. In this paper, we shed light on this phenomenon: we show that the combination of stochastic gradient descent (SGD) and over-parameterization makes the landscape of multilayer neural networks approximately connected and thus more favorable to optimization. More specifically, we prove that SGD solutions are connected via a piecewise linear path, and the increase in loss along this path vanishes as the number of neurons grows large. This result is a consequence of the fact that the parameters found by SGD are increasingly dropout stable as the network becomes wider. We show that, if we remove part of the neurons (and suitably rescale the remaining ones), the change in loss is independent of the total number of neurons, and it depends only on how many neurons are left. Our results exhibit a mild dependence on the input dimension: they are dimension-free for two-layer networks and require the number of neurons to scale linearly with the dimension for multilayer networks. We validate our theoretical findings with numerical experiments for different architectures and classification tasks.