[{"type":"conference","extern":"1","abstract":[{"lang":"eng","text":"We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈ℝd, r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable 𝔼(y), when d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting. "}],"status":"public","publication_status":"published","title":"On the connection between learning two-layers neural networks and tensor decomposition","publisher":"Proceedings of Machine Learning Research","intvolume":" 89","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6747","year":"2019","date_updated":"2021-01-12T08:08:49Z","date_created":"2019-07-31T09:31:26Z","oa_version":"Preprint","volume":89,"author":[{"orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco"},{"full_name":"Montanari, Andrea","first_name":"Andrea","last_name":"Montanari"}],"day":"01","month":"04","article_processing_charge":"No","quality_controlled":"1","page":"1051-1060","publication":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics","external_id":{"arxiv":["1802.07301"]},"citation":{"mla":"Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor Decomposition.” Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, vol. 89, Proceedings of Machine Learning Research, 2019, pp. 1051–60.","short":"M. Mondelli, A. Montanari, in:, Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, 2019, pp. 1051–1060.","chicago":"Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor Decomposition.” In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 89:1051–60. Proceedings of Machine Learning Research, 2019.","ama":"Mondelli M, Montanari A. On the connection between learning two-layers neural networks and tensor decomposition. In: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. Vol 89. Proceedings of Machine Learning Research; 2019:1051-1060.","ista":"Mondelli M, Montanari A. 2019. On the connection between learning two-layers neural networks and tensor decomposition. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence and Statistics vol. 89, 1051–1060.","ieee":"M. Mondelli and A. Montanari, “On the connection between learning two-layers neural networks and tensor decomposition,” in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Naha, Okinawa, Japan, 2019, vol. 89, pp. 1051–1060.","apa":"Mondelli, M., & Montanari, A. (2019). On the connection between learning two-layers neural networks and tensor decomposition. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (Vol. 89, pp. 1051–1060). Naha, Okinawa, Japan: Proceedings of Machine Learning Research."},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1802.07301","open_access":"1"}],"language":[{"iso":"eng"}],"conference":{"name":"AISTATS: Artificial Intelligence and Statistics","start_date":"2019-04-16","location":"Naha, Okinawa, Japan","end_date":"2019-04-18"},"date_published":"2019-04-01T00:00:00Z"},{"volume":67,"date_created":"2019-07-31T09:51:14Z","date_updated":"2021-01-12T08:08:51Z","author":[{"last_name":"Hashemi","first_name":"Seyyed Ali","full_name":"Hashemi, Seyyed Ali"},{"full_name":"Condo, Carlo","first_name":"Carlo","last_name":"Condo"},{"full_name":"Mondelli, Marco","last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Gross, Warren J","last_name":"Gross","first_name":"Warren J"}],"department":[{"_id":"MaMo"}],"publisher":"IEEE","publication_status":"published","year":"2019","article_number":"8854897","language":[{"iso":"eng"}],"doi":"10.1109/TSP.2019.2944738","quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1903.09203","open_access":"1"}],"external_id":{"arxiv":["1903.09203"]},"publication_identifier":{"issn":["1053587X"]},"month":"11","oa_version":"Preprint","intvolume":" 67","status":"public","title":"Rate-flexible fast polar decoders","_id":"6750","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","issue":"22","abstract":[{"lang":"eng","text":"Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. "}],"type":"journal_article","date_published":"2019-11-15T00:00:00Z","article_type":"original","citation":{"apa":"Hashemi, S. A., Condo, C., Mondelli, M., & Gross, W. J. (2019). Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. IEEE. https://doi.org/10.1109/TSP.2019.2944738","ieee":"S. A. Hashemi, C. Condo, M. Mondelli, and W. J. Gross, “Rate-flexible fast polar decoders,” IEEE Transactions on Signal Processing, vol. 67, no. 22. IEEE, 2019.","ista":"Hashemi SA, Condo C, Mondelli M, Gross WJ. 2019. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 67(22), 8854897.","ama":"Hashemi SA, Condo C, Mondelli M, Gross WJ. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 2019;67(22). doi:10.1109/TSP.2019.2944738","chicago":"Hashemi, Seyyed Ali, Carlo Condo, Marco Mondelli, and Warren J Gross. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions on Signal Processing. IEEE, 2019. https://doi.org/10.1109/TSP.2019.2944738.","short":"S.A. Hashemi, C. Condo, M. Mondelli, W.J. Gross, IEEE Transactions on Signal Processing 67 (2019).","mla":"Hashemi, Seyyed Ali, et al. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions on Signal Processing, vol. 67, no. 22, 8854897, IEEE, 2019, doi:10.1109/TSP.2019.2944738."},"publication":"IEEE Transactions on Signal Processing","article_processing_charge":"No","day":"15","scopus_import":1},{"language":[{"iso":"eng"}],"doi":"10.37236/8096","project":[{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program"}],"quality_controlled":"1","external_id":{"arxiv":["1808.04148"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"publication_identifier":{"eissn":["10778926"]},"month":"07","volume":26,"date_created":"2019-08-04T21:59:20Z","date_updated":"2022-03-18T12:32:02Z","author":[{"first_name":"Vít","last_name":"Jelínek","full_name":"Jelínek, Vít"},{"id":"4B865388-F248-11E8-B48F-1D18A9856A87","last_name":"Töpfer","first_name":"Martin","full_name":"Töpfer, Martin"}],"department":[{"_id":"DaAl"}],"publisher":"Electronic Journal of Combinatorics","publication_status":"published","year":"2019","ec_funded":1,"file_date_updated":"2020-07-14T12:47:39Z","article_number":"P3.17","date_published":"2019-07-19T00:00:00Z","article_type":"original","citation":{"chicago":"Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2019. https://doi.org/10.37236/8096.","short":"V. Jelínek, M. Töpfer, Electronic Journal of Combinatorics 26 (2019).","mla":"Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics, vol. 26, no. 3, P3.17, Electronic Journal of Combinatorics, 2019, doi:10.37236/8096.","apa":"Jelínek, V., & Töpfer, M. (2019). On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/8096","ieee":"V. Jelínek and M. Töpfer, “On grounded L-graphs and their relatives,” Electronic Journal of Combinatorics, vol. 26, no. 3. Electronic Journal of Combinatorics, 2019.","ista":"Jelínek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 26(3), P3.17.","ama":"Jelínek V, Töpfer M. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 2019;26(3). doi:10.37236/8096"},"publication":"Electronic Journal of Combinatorics","article_processing_charge":"No","has_accepted_license":"1","day":"19","scopus_import":"1","oa_version":"Published Version","file":[{"file_id":"6764","relation":"main_file","date_created":"2019-08-05T06:46:55Z","date_updated":"2020-07-14T12:47:39Z","checksum":"20fc366fc6683ef0b074a019b73a663a","file_name":"2019_eJourCombinatorics_Jelinek.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":533697}],"intvolume":" 26","ddc":["510"],"status":"public","title":"On grounded L-graphs and their relatives","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6759","issue":"3","abstract":[{"lang":"eng","text":"We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. \r\nWe also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions."}],"type":"journal_article"},{"publisher":"Springer","department":[{"_id":"ToHe"}],"publication_status":"published","year":"2019","volume":11674,"date_created":"2019-08-19T07:58:10Z","date_updated":"2021-01-12T08:09:12Z","author":[{"full_name":"Avni, Guy","last_name":"Avni","first_name":"Guy","orcid":"0000-0001-5588-8287","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Novotny, Petr","first_name":"Petr","last_name":"Novotny"}],"file_date_updated":"2020-07-14T12:47:41Z","project":[{"call_identifier":"FWF","name":"Formal Methods meets Algorithmic Game Theory","grant_number":"M02369","_id":"264B3912-B435-11E9-9278-68D0E5697425"},{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-30806-3_1","conference":{"start_date":"2019-09-11","location":"Brussels, Belgium","end_date":"2019-09-13","name":"RP: Reachability Problems"},"publication_identifier":{"isbn":["978-303030805-6"],"issn":["0302-9743"]},"month":"09","intvolume":" 11674","status":"public","ddc":["000"],"title":"Bidding games on Markov decision processes","_id":"6822","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"relation":"main_file","file_id":"6823","date_created":"2019-08-19T07:56:40Z","date_updated":"2020-07-14T12:47:41Z","checksum":"45ebbc709af2b247d28c7c293c01504b","file_name":"prob.pdf","access_level":"open_access","content_type":"application/pdf","file_size":436635,"creator":"gavni"}],"oa_version":"Submitted Version","alternative_title":["LNCS"],"type":"conference","abstract":[{"lang":"eng","text":"In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher\r\nbidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called \r\n randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one."}],"page":"1-12","citation":{"chicago":"Avni, Guy, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Petr Novotny. “Bidding Games on Markov Decision Processes.” In Proceedings of the 13th International Conference of Reachability Problems, 11674:1–12. Springer, 2019. https://doi.org/10.1007/978-3-030-30806-3_1.","short":"G. Avni, T.A. Henzinger, R. Ibsen-Jensen, P. Novotny, in:, Proceedings of the 13th International Conference of Reachability Problems, Springer, 2019, pp. 1–12.","mla":"Avni, Guy, et al. “Bidding Games on Markov Decision Processes.” Proceedings of the 13th International Conference of Reachability Problems, vol. 11674, Springer, 2019, pp. 1–12, doi:10.1007/978-3-030-30806-3_1.","apa":"Avni, G., Henzinger, T. A., Ibsen-Jensen, R., & Novotny, P. (2019). Bidding games on Markov decision processes. In Proceedings of the 13th International Conference of Reachability Problems (Vol. 11674, pp. 1–12). Brussels, Belgium: Springer. https://doi.org/10.1007/978-3-030-30806-3_1","ieee":"G. Avni, T. A. Henzinger, R. Ibsen-Jensen, and P. Novotny, “Bidding games on Markov decision processes,” in Proceedings of the 13th International Conference of Reachability Problems, Brussels, Belgium, 2019, vol. 11674, pp. 1–12.","ista":"Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. 2019. Bidding games on Markov decision processes. Proceedings of the 13th International Conference of Reachability Problems. RP: Reachability Problems, LNCS, vol. 11674, 1–12.","ama":"Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. Bidding games on Markov decision processes. In: Proceedings of the 13th International Conference of Reachability Problems. Vol 11674. Springer; 2019:1-12. doi:10.1007/978-3-030-30806-3_1"},"publication":" Proceedings of the 13th International Conference of Reachability Problems","date_published":"2019-09-06T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"06"},{"month":"08","language":[{"iso":"eng"}],"conference":{"location":"Amsterdam, Netherlands","start_date":"2019-08-27","end_date":"2019-08-30","name":"CONCUR: International Conference on Concurrency Theory"},"doi":"10.4230/LIPICS.CONCUR.2019.7","quality_controlled":"1","project":[{"name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"file_date_updated":"2020-07-14T12:47:43Z","ec_funded":1,"article_number":"7","date_created":"2019-09-18T08:07:58Z","date_updated":"2022-08-12T10:54:34Z","volume":140,"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Wolfgang","last_name":"Dvorák","full_name":"Dvorák, Wolfgang"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Svozil","first_name":"Alexander","full_name":"Svozil, Alexander"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"year":"2019","day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1","date_published":"2019-08-01T00:00:00Z","publication":"Leibniz International Proceedings in Informatics","citation":{"ama":"Chatterjee K, Dvorák W, Henzinger MH, Svozil A. Near-linear time algorithms for Streett objectives in graphs and MDPs. In: Leibniz International Proceedings in Informatics. Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.CONCUR.2019.7","ista":"Chatterjee K, Dvorák W, Henzinger MH, Svozil A. 2019. Near-linear time algorithms for Streett objectives in graphs and MDPs. Leibniz International Proceedings in Informatics. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 140, 7.","ieee":"K. Chatterjee, W. Dvorák, M. H. Henzinger, and A. Svozil, “Near-linear time algorithms for Streett objectives in graphs and MDPs,” in Leibniz International Proceedings in Informatics, Amsterdam, Netherlands, 2019, vol. 140.","apa":"Chatterjee, K., Dvorák, W., Henzinger, M. H., & Svozil, A. (2019). Near-linear time algorithms for Streett objectives in graphs and MDPs. In Leibniz International Proceedings in Informatics (Vol. 140). Amsterdam, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.CONCUR.2019.7","mla":"Chatterjee, Krishnendu, et al. “Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.” Leibniz International Proceedings in Informatics, vol. 140, 7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.CONCUR.2019.7.","short":"K. Chatterjee, W. Dvorák, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","chicago":"Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Alexander Svozil. “Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.” In Leibniz International Proceedings in Informatics, Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.7."},"abstract":[{"lang":"eng","text":"The fundamental model-checking problem, given as input a model and a specification, asks for the algorithmic verification of whether the model satisfies the specification. Two classical models for reactive systems are graphs and Markov decision processes (MDPs). A basic specification formalism in the verification of reactive systems is the strong fairness (aka Streett) objective, where given different types of requests and corresponding grants, the requirement is that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All omega-regular objectives can be expressed as Streett objectives and hence they are canonical in verification. Consider graphs/MDPs with n vertices, m edges, and a Streett objectives with k pairs, and let b denote the size of the description of the Streett objective for the sets of requests and grants. The current best-known algorithm for the problem requires time O(min(n^2, m sqrt{m log n}) + b log n). In this work we present randomized near-linear time algorithms, with expected running time O~(m + b), where the O~ notation hides poly-log factors. Our randomized algorithms are near-linear in the size of the input, and hence optimal up to poly-log factors. "}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"date_created":"2019-10-01T08:20:30Z","date_updated":"2020-07-14T12:47:43Z","checksum":"e1f0e4061212454574f34a1368d018ec","file_id":"6922","relation":"main_file","creator":"kschuh","file_size":730112,"content_type":"application/pdf","file_name":"2019_LIPIcs_Chatterjee.pdf","access_level":"open_access"}],"oa_version":"Published Version","status":"public","title":"Near-linear time algorithms for Streett objectives in graphs and MDPs","ddc":["000"],"intvolume":" 140","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","_id":"6887"}]