---
_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: <i>Proceedings
    of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research
    Press; 2024:24964-25015.'
  apa: 'Kögler, K., Shevchenko, A., Hassani, H., &#38; Mondelli, M. (2024). Compression
    of structured data with autoencoders: Provable benefit of nonlinearities and depth.
    In <i>Proceedings of the 41st International Conference on Machine Learning</i>
    (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 <i>Proceedings of the 41st International Conference on Machine
    Learning</i>, 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 <i>Proceedings
    of the 41st International Conference on Machine Learning</i>, 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.” <i>Proceedings of the 41st International
    Conference on Machine Learning</i>, 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-06T22:31:18Z
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: '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'
...