---
_id: '14198'
abstract:
- lang: eng
text: "High-dimensional time series are common in many domains. Since human\r\ncognition
is not optimized to work well in high-dimensional spaces, these areas\r\ncould
benefit from interpretable low-dimensional representations. However, most\r\nrepresentation
learning algorithms for time series data are difficult to\r\ninterpret. This is
due to non-intuitive mappings from data features to salient\r\nproperties of the
representation and non-smoothness over time. To address this\r\nproblem, we propose
a new representation learning framework building on ideas\r\nfrom interpretable
discrete dimensionality reduction and deep generative\r\nmodeling. This framework
allows us to learn discrete representations of time\r\nseries, which give rise
to smooth and interpretable embeddings with superior\r\nclustering performance.
We introduce a new way to overcome the\r\nnon-differentiability in discrete representation
learning and present a\r\ngradient-based version of the traditional self-organizing
map algorithm that is\r\nmore performant than the original. Furthermore, to allow
for a probabilistic\r\ninterpretation of our method, we integrate a Markov model
in the representation\r\nspace. This model uncovers the temporal transition structure,
improves\r\nclustering performance even further and provides additional explanatory\r\ninsights
as well as a natural representation of uncertainty. We evaluate our\r\nmodel in
terms of clustering performance and interpretability on static\r\n(Fashion-)MNIST
data, a time series of linearly interpolated (Fashion-)MNIST\r\nimages, a chaotic
Lorenz attractor system with two macro states, as well as on\r\na challenging
real world medical time series application on the eICU data set.\r\nOur learned
representations compare favorably with competitor methods and\r\nfacilitate downstream
tasks on the real world data."
article_processing_charge: No
author:
- first_name: Vincent
full_name: Fortuin, Vincent
last_name: Fortuin
- first_name: Matthias
full_name: Hüser, Matthias
last_name: Hüser
- first_name: Francesco
full_name: Locatello, Francesco
id: 26cfd52f-2483-11ee-8040-88983bcc06d4
last_name: Locatello
orcid: 0000-0002-4850-0683
- first_name: Heiko
full_name: Strathmann, Heiko
last_name: Strathmann
- first_name: Gunnar
full_name: Rätsch, Gunnar
last_name: Rätsch
citation:
ama: 'Fortuin V, Hüser M, Locatello F, Strathmann H, Rätsch G. SOM-VAE: Interpretable
discrete representation learning on time series. In: International Conference
on Learning Representations. ; 2018.'
apa: 'Fortuin, V., Hüser, M., Locatello, F., Strathmann, H., & Rätsch, G. (2018).
SOM-VAE: Interpretable discrete representation learning on time series. In International
Conference on Learning Representations. New Orleans, LA, United States.'
chicago: 'Fortuin, Vincent, Matthias Hüser, Francesco Locatello, Heiko Strathmann,
and Gunnar Rätsch. “SOM-VAE: Interpretable Discrete Representation Learning on
Time Series.” In International Conference on Learning Representations,
2018.'
ieee: 'V. Fortuin, M. Hüser, F. Locatello, H. Strathmann, and G. Rätsch, “SOM-VAE:
Interpretable discrete representation learning on time series,” in International
Conference on Learning Representations, New Orleans, LA, United States, 2018.'
ista: 'Fortuin V, Hüser M, Locatello F, Strathmann H, Rätsch G. 2018. SOM-VAE: Interpretable
discrete representation learning on time series. International Conference on Learning
Representations. ICLR: International Conference on Learning Representations.'
mla: 'Fortuin, Vincent, et al. “SOM-VAE: Interpretable Discrete Representation Learning
on Time Series.” International Conference on Learning Representations,
2018.'
short: V. Fortuin, M. Hüser, F. Locatello, H. Strathmann, G. Rätsch, in:, International
Conference on Learning Representations, 2018.
conference:
end_date: 2019-05-09
location: New Orleans, LA, United States
name: 'ICLR: International Conference on Learning Representations'
start_date: 2019-05-06
date_created: 2023-08-22T14:12:48Z
date_published: 2018-06-06T00:00:00Z
date_updated: 2023-09-13T06:35:12Z
day: '06'
department:
- _id: FrLo
extern: '1'
external_id:
arxiv:
- '1806.02199'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1806.02199
month: '06'
oa: 1
oa_version: Preprint
publication: International Conference on Learning Representations
publication_status: published
quality_controlled: '1'
status: public
title: 'SOM-VAE: Interpretable discrete representation learning on time series'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '14203'
abstract:
- lang: eng
text: We propose a conditional gradient framework for a composite convex minimization
template with broad applications. Our approach combines smoothing and homotopy
techniques under the CGM framework, and provably achieves the optimal O(1/k−−√)
convergence rate. We demonstrate that the same rate holds if the linear subproblems
are solved approximately with additive or multiplicative error. In contrast with
the relevant work, we are able to characterize the convergence when the non-smooth
term is an indicator function. Specific applications of our framework include
the non-smooth minimization, semidefinite programming, and minimization with linear
inclusion constraints over a compact domain. Numerical evidence demonstrates the
benefits of our framework.
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Alp
full_name: Yurtsever, Alp
last_name: Yurtsever
- first_name: Olivier
full_name: Fercoq, Olivier
last_name: Fercoq
- first_name: Francesco
full_name: Locatello, Francesco
id: 26cfd52f-2483-11ee-8040-88983bcc06d4
last_name: Locatello
orcid: 0000-0002-4850-0683
- first_name: Volkan
full_name: Cevher, Volkan
last_name: Cevher
citation:
ama: 'Yurtsever A, Fercoq O, Locatello F, Cevher V. A conditional gradient framework
for composite convex minimization with applications to semidefinite programming.
In: Proceedings of the 35th International Conference on Machine Learning.
Vol 80. ML Research Press; 2018:5727-5736.'
apa: 'Yurtsever, A., Fercoq, O., Locatello, F., & Cevher, V. (2018). A conditional
gradient framework for composite convex minimization with applications to semidefinite
programming. In Proceedings of the 35th International Conference on Machine
Learning (Vol. 80, pp. 5727–5736). Stockholm, Sweden: ML Research Press.'
chicago: Yurtsever, Alp, Olivier Fercoq, Francesco Locatello, and Volkan Cevher.
“A Conditional Gradient Framework for Composite Convex Minimization with Applications
to Semidefinite Programming.” In Proceedings of the 35th International Conference
on Machine Learning, 80:5727–36. ML Research Press, 2018.
ieee: A. Yurtsever, O. Fercoq, F. Locatello, and V. Cevher, “A conditional gradient
framework for composite convex minimization with applications to semidefinite
programming,” in Proceedings of the 35th International Conference on Machine
Learning, Stockholm, Sweden, 2018, vol. 80, pp. 5727–5736.
ista: 'Yurtsever A, Fercoq O, Locatello F, Cevher V. 2018. A conditional gradient
framework for composite convex minimization with applications to semidefinite
programming. Proceedings of the 35th International Conference on Machine Learning.
ICML: International Conference on Machine Learning, PMLR, vol. 80, 5727–5736.'
mla: Yurtsever, Alp, et al. “A Conditional Gradient Framework for Composite Convex
Minimization with Applications to Semidefinite Programming.” Proceedings of
the 35th International Conference on Machine Learning, vol. 80, ML Research
Press, 2018, pp. 5727–36.
short: A. Yurtsever, O. Fercoq, F. Locatello, V. Cevher, in:, Proceedings of the
35th International Conference on Machine Learning, ML Research Press, 2018, pp.
5727–5736.
conference:
end_date: 2018-07-15
location: Stockholm, Sweden
name: 'ICML: International Conference on Machine Learning'
start_date: 2018-07-10
date_created: 2023-08-22T14:16:01Z
date_published: 2018-07-15T00:00:00Z
date_updated: 2023-09-13T08:13:39Z
day: '15'
department:
- _id: FrLo
extern: '1'
external_id:
arxiv:
- '1804.08544'
intvolume: ' 80'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1804.08544
month: '07'
oa: 1
oa_version: Preprint
page: 5727-5736
publication: Proceedings of the 35th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: A conditional gradient framework for composite convex minimization with applications
to semidefinite programming
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 80
year: '2018'
...
---
_id: '282'
abstract:
- lang: eng
text: Adaptive introgression is common in nature and can be driven by selection
acting on multiple, linked genes. We explore the effects of polygenic selection
on introgression under the infinitesimal model with linkage. This model assumes
that the introgressing block has an effectively infinite number of genes, each
with an infinitesimal effect on the trait under selection. The block is assumed
to introgress under directional selection within a native population that is genetically
homogeneous. We use individual-based simulations and a branching process approximation
to compute various statistics of the introgressing block, and explore how these
depend on parameters such as the map length and initial trait value associated
with the introgressing block, the genetic variability along the block, and the
strength of selection. Our results show that the introgression dynamics of a block
under infinitesimal selection is qualitatively different from the dynamics of
neutral introgression. We also find that in the long run, surviving descendant
blocks are likely to have intermediate lengths, and clarify how the length is
shaped by the interplay between linkage and infinitesimal selection. Our results
suggest that it may be difficult to distinguish introgression of single loci from
that of genomic blocks with multiple, tightly linked and weakly selected loci.
article_processing_charge: No
author:
- first_name: Himani
full_name: Sachdeva, Himani
id: 42377A0A-F248-11E8-B48F-1D18A9856A87
last_name: Sachdeva
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Sachdeva H, Barton NH. Introgression of a block of genome under infinitesimal
selection. Genetics. 2018;209(4):1279-1303. doi:10.1534/genetics.118.301018
apa: Sachdeva, H., & Barton, N. H. (2018). Introgression of a block of genome
under infinitesimal selection. Genetics. Genetics Society of America. https://doi.org/10.1534/genetics.118.301018
chicago: Sachdeva, Himani, and Nicholas H Barton. “Introgression of a Block of Genome
under Infinitesimal Selection.” Genetics. Genetics Society of America,
2018. https://doi.org/10.1534/genetics.118.301018.
ieee: H. Sachdeva and N. H. Barton, “Introgression of a block of genome under infinitesimal
selection,” Genetics, vol. 209, no. 4. Genetics Society of America, pp.
1279–1303, 2018.
ista: Sachdeva H, Barton NH. 2018. Introgression of a block of genome under infinitesimal
selection. Genetics. 209(4), 1279–1303.
mla: Sachdeva, Himani, and Nicholas H. Barton. “Introgression of a Block of Genome
under Infinitesimal Selection.” Genetics, vol. 209, no. 4, Genetics Society
of America, 2018, pp. 1279–303, doi:10.1534/genetics.118.301018.
short: H. Sachdeva, N.H. Barton, Genetics 209 (2018) 1279–1303.
date_created: 2018-12-11T11:45:36Z
date_published: 2018-08-01T00:00:00Z
date_updated: 2023-09-13T08:22:32Z
day: '01'
department:
- _id: NiBa
doi: 10.1534/genetics.118.301018
external_id:
isi:
- '000440014100020'
intvolume: ' 209'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.biorxiv.org/content/early/2017/11/30/227082
month: '08'
oa: 1
oa_version: Submitted Version
page: 1279 - 1303
publication: Genetics
publication_status: published
publisher: Genetics Society of America
publist_id: '7617'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Introgression of a block of genome under infinitesimal selection
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 209
year: '2018'
...
---
_id: '108'
abstract:
- lang: eng
text: Universal hashing found a lot of applications in computer science. In cryptography
the most important fact about universal families is the so called Leftover Hash
Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography
it states that almost universal families are good extractors. In this work we
provide a somewhat surprising characterization in the opposite direction. Namely,
every extractor with sufficiently good parameters yields a universal family on
a noticeable fraction of its inputs. Our proof technique is based on tools from
extremal graph theory applied to the \'collision graph\' induced by the extractor,
and may be of independent interest. We discuss possible applications to the theory
of randomness extractors and non-malleable codes.
alternative_title:
- ISIT Proceedings
article_processing_charge: No
author:
- first_name: Marciej
full_name: Obremski, Marciej
last_name: Obremski
- first_name: Maciej
full_name: Skorski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skorski
citation:
ama: 'Obremski M, Skórski M. Inverted leftover hash lemma. In: Vol 2018. IEEE; 2018.
doi:10.1109/ISIT.2018.8437654'
apa: 'Obremski, M., & Skórski, M. (2018). Inverted leftover hash lemma (Vol.
2018). Presented at the ISIT: International Symposium on Information Theory, Vail,
CO, USA: IEEE. https://doi.org/10.1109/ISIT.2018.8437654'
chicago: Obremski, Marciej, and Maciej Skórski. “Inverted Leftover Hash Lemma,”
Vol. 2018. IEEE, 2018. https://doi.org/10.1109/ISIT.2018.8437654.
ieee: 'M. Obremski and M. Skórski, “Inverted leftover hash lemma,” presented at
the ISIT: International Symposium on Information Theory, Vail, CO, USA, 2018,
vol. 2018.'
ista: 'Obremski M, Skórski M. 2018. Inverted leftover hash lemma. ISIT: International
Symposium on Information Theory, ISIT Proceedings, vol. 2018.'
mla: Obremski, Marciej, and Maciej Skórski. Inverted Leftover Hash Lemma.
Vol. 2018, IEEE, 2018, doi:10.1109/ISIT.2018.8437654.
short: M. Obremski, M. Skórski, in:, IEEE, 2018.
conference:
end_date: 2018-06-22
location: Vail, CO, USA
name: 'ISIT: International Symposium on Information Theory'
start_date: '2018-06-17 '
date_created: 2018-12-11T11:44:40Z
date_published: 2018-08-16T00:00:00Z
date_updated: 2023-09-13T08:23:18Z
day: '16'
department:
- _id: KrPi
doi: 10.1109/ISIT.2018.8437654
external_id:
isi:
- '000448139300368'
intvolume: ' 2018'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/507
month: '08'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: IEEE
publist_id: '7946'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inverted leftover hash lemma
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2018
year: '2018'
...
---
_id: '14204'
abstract:
- lang: eng
text: Two popular examples of first-order optimization methods over linear spaces
are coordinate descent and matching pursuit algorithms, with their randomized
variants. While the former targets the optimization by moving along coordinates,
the latter considers a generalized notion of directions. Exploiting the connection
between the two algorithms, we present a unified analysis of both, providing affine
invariant sublinear O(1/t) rates on smooth objectives and linear convergence on
strongly convex objectives. As a byproduct of our affine invariant analysis of
matching pursuit, our rates for steepest coordinate descent are the tightest known.
Furthermore, we show the first accelerated convergence rate O(1/t2) for matching
pursuit and steepest coordinate descent on convex objectives.
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Francesco
full_name: Locatello, Francesco
id: 26cfd52f-2483-11ee-8040-88983bcc06d4
last_name: Locatello
orcid: 0000-0002-4850-0683
- first_name: Anant
full_name: Raj, Anant
last_name: Raj
- first_name: Sai Praneeth
full_name: Karimireddy, Sai Praneeth
last_name: Karimireddy
- first_name: Gunnar
full_name: Rätsch, Gunnar
last_name: Rätsch
- first_name: Bernhard
full_name: Schölkopf, Bernhard
last_name: Schölkopf
- first_name: Sebastian U.
full_name: Stich, Sebastian U.
last_name: Stich
- first_name: Martin
full_name: Jaggi, Martin
last_name: Jaggi
citation:
ama: 'Locatello F, Raj A, Karimireddy SP, et al. On matching pursuit and coordinate
descent. In: Proceedings of the 35th International Conference on Machine Learning.
Vol 80. ML Research Press; 2018:3198-3207.'
apa: Locatello, F., Raj, A., Karimireddy, S. P., Rätsch, G., Schölkopf, B., Stich,
S. U., & Jaggi, M. (2018). On matching pursuit and coordinate descent. In
Proceedings of the 35th International Conference on Machine Learning (Vol.
80, pp. 3198–3207). ML Research Press.
chicago: Locatello, Francesco, Anant Raj, Sai Praneeth Karimireddy, Gunnar Rätsch,
Bernhard Schölkopf, Sebastian U. Stich, and Martin Jaggi. “On Matching Pursuit
and Coordinate Descent.” In Proceedings of the 35th International Conference
on Machine Learning, 80:3198–3207. ML Research Press, 2018.
ieee: F. Locatello et al., “On matching pursuit and coordinate descent,”
in Proceedings of the 35th International Conference on Machine Learning,
2018, vol. 80, pp. 3198–3207.
ista: Locatello F, Raj A, Karimireddy SP, Rätsch G, Schölkopf B, Stich SU, Jaggi
M. 2018. On matching pursuit and coordinate descent. Proceedings of the 35th International
Conference on Machine Learning. , PMLR, vol. 80, 3198–3207.
mla: Locatello, Francesco, et al. “On Matching Pursuit and Coordinate Descent.”
Proceedings of the 35th International Conference on Machine Learning, vol.
80, ML Research Press, 2018, pp. 3198–207.
short: F. Locatello, A. Raj, S.P. Karimireddy, G. Rätsch, B. Schölkopf, S.U. Stich,
M. Jaggi, in:, Proceedings of the 35th International Conference on Machine Learning,
ML Research Press, 2018, pp. 3198–3207.
date_created: 2023-08-22T14:16:25Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2023-09-13T08:19:05Z
day: '01'
department:
- _id: FrLo
extern: '1'
external_id:
arxiv:
- '1803.09539'
intvolume: ' 80'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.09539
month: '07'
oa: 1
oa_version: Preprint
page: 3198-3207
publication: Proceedings of the 35th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: On matching pursuit and coordinate descent
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 80
year: '2018'
...