--- _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' ...