---
OA_place: publisher
_id: '23072'
abstract:
- lang: eng
text: "Inferring signal from large quantities of data is one of the most important
problems in today’s\r\nworld, with neural networks emerging as the most powerful
solution. While there have been\r\nmassive breakthroughs in the ML space, there
are two main drawbacks. The first is that\r\nmost of these models are “black boxes”,
with very little understanding of why they work,\r\nwhich makes it hard to find
the correct architecture for a given problem. The architecture is\r\ncrucial,
as the widely used training algorithms are “local” and thus rely on the loss landscape\r\nbeing
benign enough to find a global optimum. This brings us to the second problem:
while\r\nthere is a lot of evidence that this can be overcome with large enough
data, this is less clear\r\nfor datasets which are noisy, do not have enough samples,
or have a non-standard structure.\r\nHistorically, on a smaller scale, the alternative
has been simple (Bayesian) statistical methods,\r\nwhich also have the advantage
of being interpretable and adaptable. However, many of the\r\nclassical results
cannot be easily extended to the high-dimensional regime in which modern\r\ndata
lives.\r\nIn this work we want to consider two different settings relating to
the above. The first is\r\napproximate message passing (AMP), an iterative algorithm
for high-dimensional (generalized)\r\nlinear models that easily lends itself to
Bayesian setups, and which in many cases is provably\r\nBayes-optimal. The second
is an autoencoder with a shallow encoder, for which we can\r\nanalyze the weights
along the training trajectory of gradient descent. Surprisingly, we will find\r\na
connection between the two, as we recover certain structures of AMP.\r\nWe will
first introduce the AMP framework by studying an extension that can be applied\r\nto
a wider variety of data: rotationally invariant generalized approximate message
passing\r\n(RI-GAMP). This shows that one can extend the AMP framework to a much
wider class of\r\nalgorithms, relevant to more practical settings. The results
are then also confirmed on real\r\ndata that go beyond the theoretical setting.\r\nWe
then move to the setup of an autoencoder with a shallow encoder and a Bayesian
prior in\r\nthe high-dimensional regime, in which the input and compression dimensions
are large and\r\nproportional; this is also a first step towards opening one of
the black boxes above, as we\r\ncan say precisely when and why the network works.
While autoencoders are widely used in\r\nmodern ML architectures, most fundamental
research in this direction has focused on extreme\r\nasymptotic regimes, where
the autoencoder is either severely over- or under-parameterized,\r\nand which
do not extend to the proportional high-dimensional regime. We show that for\r\nGaussian
priors the network finds the global optimum, and these theoretical findings extrapolate\r\nstrikingly
well to real image data. Next we extend this analysis to more structured priors
and\r\na deeper decoder. For sparse Gaussian inputs in the training regime studied
here, the shallow\r\ndecoder does not exploit sparsity and yields the same dynamics
as in the Gaussian setting.\r\nWe then show how a deeper decoder can break this
behavior, and interestingly, if we treat the\r\nproblem as an AMP problem, the
network eventually learns the same decoding as AMP. This\r\ntoo extrapolates to
real image data.\r\nLastly, we will show that the AMP setup has real practical
use, by using a practical variant,\r\ngenetic vector approximate message passing
(gVAMP), for predicting plasma protein levels\r\nfrom genetic information using
the UKB GWAS data. This is a perfect example of the problems\r\nin the high-dimensional
regime: approximately 8.4 million dimensions and 40,000 samples,\r\nwhere the
high noise, low sample count, and large size make it hard for ML methods to work.\r\nTo
get the optimal prediction accuracy we consider a two-step inference. We first
consider a\r\npre-processed version of the data, of about 880,000 dimensions,
on which we run the gVAMP\r\nalgorithm; this allows us to find predictive regions,
taking into account joint effects between\r\ndifferent regions, and for most proteins
we end up selecting only about 0.1% of the dimensions.\r\nWe then consider the
analogue of this small subset, on which we can now run a standard tree\r\nalgorithm
(XGB) that no longer suffers from the aforementioned problems. This pipeline yields\r\nbetter
prediction accuracy than recent nonlinear deep learning approaches applied to
this data,\r\nas we are able to handle the pre-processing in a principled Bayesian
way."
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "This project was partially supported by the 2019 Lopez-Loreta Prize
and\r\nthe ERC INF2 project (project number 101161364). Furthermore, the candidate
acknowledges\r\nthe support from the Scientific Service Units of the Institute of
Science and Technology Austria\r\nthrough resources provided by Scientific Computing."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
citation:
ama: 'Kögler K. Compression and inference in high dimensions: An approximate message
passing perspective. 2026. doi:10.15479/AT-ISTA-23072'
apa: 'Kögler, K. (2026). Compression and inference in high dimensions: An approximate
message passing perspective. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT-ISTA-23072'
chicago: 'Kögler, Kevin. “Compression and Inference in High Dimensions: An Approximate
Message Passing Perspective.” Institute of Science and Technology Austria, 2026.
https://doi.org/10.15479/AT-ISTA-23072.'
ieee: 'K. Kögler, “Compression and inference in high dimensions: An approximate
message passing perspective,” Institute of Science and Technology Austria, 2026.'
ista: 'Kögler K. 2026. Compression and inference in high dimensions: An approximate
message passing perspective. Institute of Science and Technology Austria.'
mla: 'Kögler, Kevin. Compression and Inference in High Dimensions: An Approximate
Message Passing Perspective. Institute of Science and Technology Austria,
2026, doi:10.15479/AT-ISTA-23072.'
short: 'K. Kögler, Compression and Inference in High Dimensions: An Approximate
Message Passing Perspective, Institute of Science and Technology Austria, 2026.'
corr_author: '1'
date_created: 2026-10-07T11:20:26Z
date_published: 2026-10-08T00:00:00Z
date_updated: 2026-10-12T13:04:49Z
day: '08'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: MaMo
- _id: GradSch
doi: 10.15479/AT-ISTA-23072
doi_confirm: '1'
file:
- access_level: closed
checksum: 5fb2ff02dc9d8c659b2fb5e0802b06ff
content_type: application/zip
creator: kkoegler
date_created: 2026-10-09T11:20:09Z
date_updated: 2026-10-09T12:22:55Z
file_id: '23084'
file_name: 2026_Koegler_Kevin_Thesis.zip
file_size: 8504109
relation: source_file
- access_level: open_access
checksum: a6df3b04c97628a1703f63356fb56f96
content_type: application/pdf
creator: kkoegler
date_created: 2026-10-09T13:25:49Z
date_updated: 2026-10-09T13:25:49Z
file_id: '23085'
file_name: 2026_Koegler_Kevin_Thesis.pdf
file_size: 6692605
relation: main_file
success: 1
file_date_updated: 2026-10-09T13:25:49Z
fulldoi: https://doi.org/10.15479/AT-ISTA-23072
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: '222'
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '14459'
relation: part_of_dissertation
status: public
- id: '12540'
relation: part_of_dissertation
status: public
- id: '17469'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
title: 'Compression and inference in high dimensions: An approximate message passing
perspective'
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
_id: '17469'
abstract:
- lang: eng
text: '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.'
acknowledgement: "Kevin Kogler, Alexander Shevchenko and Marco Mondelli are supported
by the 2019 Lopez-Loreta Prize. Hamed\r\nHassani acknowledges the support by the
NSF CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data
Science (EnCORE)."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Kögler K, Shevchenko A, Hassani H, Mondelli M. Compression of structured data
with autoencoders: Provable benefit of nonlinearities and depth. In: Proceedings
of the 41st International Conference on Machine Learning. Vol 235. ML Research
Press; 2024:24964-25015.'
apa: 'Kögler, K., Shevchenko, A., Hassani, H., & Mondelli, M. (2024). Compression
of structured data with autoencoders: Provable benefit of nonlinearities and depth.
In Proceedings of the 41st International Conference on Machine Learning
(Vol. 235, pp. 24964–25015). Vienna, Austria: ML Research Press.'
chicago: 'Kögler, Kevin, Alexander Shevchenko, Hamed Hassani, and Marco Mondelli.
“Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities
and Depth.” In Proceedings of the 41st International Conference on Machine
Learning, 235:24964–15. ML Research Press, 2024.'
ieee: 'K. Kögler, A. Shevchenko, H. Hassani, and M. Mondelli, “Compression of structured
data with autoencoders: Provable benefit of nonlinearities and depth,” in Proceedings
of the 41st International Conference on Machine Learning, Vienna, Austria,
2024, vol. 235, pp. 24964–25015.'
ista: 'Kögler K, Shevchenko A, Hassani H, Mondelli M. 2024. Compression of structured
data with autoencoders: Provable benefit of nonlinearities and depth. Proceedings
of the 41st International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 235, 24964–25015.'
mla: 'Kögler, Kevin, et al. “Compression of Structured Data with Autoencoders: Provable
Benefit of Nonlinearities and Depth.” Proceedings of the 41st International
Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 24964–5015.'
short: K. Kögler, A. Shevchenko, H. Hassani, M. Mondelli, in:, Proceedings of the
41st International Conference on Machine Learning, ML Research Press, 2024, pp.
24964–25015.
conference:
end_date: 2024-07-27
location: Vienna, Austria
name: 'ICML: International Conference on Machine Learning'
start_date: 2024-07-21
corr_author: '1'
das_tickbox: '0'
date_created: 2024-08-29T11:47:57Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2026-10-21T22:31:20Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
- _id: MaMo
external_id:
arxiv:
- '2402.05013'
intvolume: ' 235'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.mlr.press/v235/kogler24a.html
month: '07'
oa: 1
oa_version: Published Version
page: 24964-25015
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 41st International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '23072'
relation: dissertation_contains
status: public
- id: '17465'
relation: dissertation_contains
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Compression of structured data with autoencoders: Provable benefit of nonlinearities
and depth'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 235
year: '2024'
...
---
_id: '14459'
abstract:
- lang: eng
text: 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.
acknowledgement: Aleksandr Shevchenko, Kevin Kogler and Marco Mondelli are supported
by the 2019 Lopez-Loreta Prize. Hamed Hassani acknowledges the support by the NSF
CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science
(EnCORE).
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Shevchenko A, Kögler K, Hassani H, Mondelli M. Fundamental limits of two-layer
autoencoders, and achieving them with gradient methods. In: Proceedings of
the 40th International Conference on Machine Learning. Vol 202. ML Research
Press; 2023:31151-31209.'
apa: 'Shevchenko, A., Kögler, K., Hassani, H., & Mondelli, M. (2023). Fundamental
limits of two-layer autoencoders, and achieving them with gradient methods. In
Proceedings of the 40th International Conference on Machine Learning (Vol.
202, pp. 31151–31209). Honolulu, Hawaii, HI, United States: ML Research Press.'
chicago: Shevchenko, Alexander, Kevin Kögler, Hamed Hassani, and Marco Mondelli.
“Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient
Methods.” In Proceedings of the 40th International Conference on Machine Learning,
202:31151–209. ML Research Press, 2023.
ieee: A. Shevchenko, K. Kögler, H. Hassani, and M. Mondelli, “Fundamental limits
of two-layer autoencoders, and achieving them with gradient methods,” in Proceedings
of the 40th International Conference on Machine Learning, Honolulu, Hawaii,
HI, United States, 2023, vol. 202, pp. 31151–31209.
ista: 'Shevchenko A, Kögler K, Hassani H, Mondelli M. 2023. Fundamental limits of
two-layer autoencoders, and achieving them with gradient methods. Proceedings
of the 40th International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 202, 31151–31209.'
mla: Shevchenko, Alexander, et al. “Fundamental Limits of Two-Layer Autoencoders,
and Achieving Them with Gradient Methods.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 31151–209.
short: A. Shevchenko, K. Kögler, H. Hassani, M. Mondelli, in:, Proceedings of the
40th International Conference on Machine Learning, ML Research Press, 2023, pp.
31151–31209.
conference:
end_date: 2023-07-29
location: Honolulu, Hawaii, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
corr_author: '1'
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2026-10-21T22:31:20Z
day: '30'
department:
- _id: MaMo
- _id: DaAl
external_id:
arxiv:
- '2212.13468'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2212.13468
month: '07'
oa: 1
oa_version: Preprint
page: 31151-31209
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '23072'
relation: dissertation_contains
status: public
- id: '17465'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Fundamental limits of two-layer autoencoders, and achieving them with gradient
methods
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '12540'
abstract:
- lang: eng
text: We consider the problem of signal estimation in generalized linear models
defined via rotationally invariant design matrices. Since these matrices can have
an arbitrary spectral distribution, this model is well suited for capturing complex
correlation structures which often arise in applications. We propose a novel family
of approximate message passing (AMP) algorithms for signal estimation, and rigorously
characterize their performance in the high-dimensional limit via a state evolution
recursion. Our rotationally invariant AMP has complexity of the same order as
the existing AMP derived under the restrictive assumption of a Gaussian design;
our algorithm also recovers this existing AMP as a special case. Numerical results
showcase a performance close to Vector AMP (which is conjectured to be Bayes-optimal
in some settings), but obtained with a much lower complexity, as the proposed
algorithm does not require a computationally expensive singular value decomposition.
acknowledgement: The authors would like to thank the anonymous reviewers for their
helpful comments. KK and MM were partially supported by the 2019 Lopez-Loreta Prize.
article_number: '22'
article_processing_charge: No
author:
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Venkataramanan R, Kögler K, Mondelli M. Estimation in rotationally invariant
generalized linear models via approximate message passing. In: Proceedings
of the 39th International Conference on Machine Learning. Vol 162. ML Research
Press; 2022.'
apa: 'Venkataramanan, R., Kögler, K., & Mondelli, M. (2022). Estimation in rotationally
invariant generalized linear models via approximate message passing. In Proceedings
of the 39th International Conference on Machine Learning (Vol. 162). Baltimore,
MD, United States: ML Research Press.'
chicago: Venkataramanan, Ramji, Kevin Kögler, and Marco Mondelli. “Estimation in
Rotationally Invariant Generalized Linear Models via Approximate Message Passing.”
In Proceedings of the 39th International Conference on Machine Learning,
Vol. 162. ML Research Press, 2022.
ieee: R. Venkataramanan, K. Kögler, and M. Mondelli, “Estimation in rotationally
invariant generalized linear models via approximate message passing,” in Proceedings
of the 39th International Conference on Machine Learning, Baltimore, MD, United
States, 2022, vol. 162.
ista: 'Venkataramanan R, Kögler K, Mondelli M. 2022. Estimation in rotationally
invariant generalized linear models via approximate message passing. Proceedings
of the 39th International Conference on Machine Learning. ICML: International
Conference on Machine Learning vol. 162, 22.'
mla: Venkataramanan, Ramji, et al. “Estimation in Rotationally Invariant Generalized
Linear Models via Approximate Message Passing.” Proceedings of the 39th International
Conference on Machine Learning, vol. 162, 22, ML Research Press, 2022.
short: R. Venkataramanan, K. Kögler, M. Mondelli, in:, Proceedings of the 39th International
Conference on Machine Learning, ML Research Press, 2022.
conference:
end_date: 2022-07-23
location: Baltimore, MD, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2022-07-17
corr_author: '1'
date_created: 2023-02-10T13:49:04Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2026-10-12T13:04:49Z
ddc:
- '000'
department:
- _id: MaMo
file:
- access_level: open_access
checksum: 67436eb0a660789514cdf9db79e84683
content_type: application/pdf
creator: dernst
date_created: 2023-02-13T10:53:11Z
date_updated: 2023-02-13T10:53:11Z
file_id: '12547'
file_name: 2022_PMLR_Venkataramanan.pdf
file_size: 2341343
relation: main_file
success: 1
file_date_updated: 2023-02-13T10:53:11Z
has_accepted_license: '1'
intvolume: ' 162'
language:
- iso: eng
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 39th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '23072'
relation: dissertation_contains
status: public
status: public
title: Estimation in rotationally invariant generalized linear models via approximate
message passing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 162
year: '2022'
...