Smoothed analysis of tensor decompositions

DOI10.1145/2591796.2591881zbMath1315.68203arXiv1311.3651OpenAlexW2057214765MaRDI QIDQ5259595

Aditya Bhaskara, Ankur Moitra, Aravindan Vijayaraghavan, Moses Charikar

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.3651

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Multilinear algebra, tensor calculus (15A69)

Related Items (19)

Smoothed analysis for tensor methods in unsupervised learning ⋮ On the optimization landscape of tensor decompositions ⋮ Overcomplete Order-3 Tensor Decomposition, Blind Deconvolution, and Gaussian Mixture Models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Effective Criteria for Specific Identifiability of Tensors and Forms ⋮ Complete decomposition of symmetric tensors in linear time and polylogarithmic precision ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond ⋮ Concentration inequalities for random tensors ⋮ Composition-aware spectroscopic tomography ⋮ Recovering Structured Probability Matrices ⋮ Planning and learning in partially observable systems via filter stability ⋮ Universality of the least singular value for the sum of random matrices ⋮ Homotopy techniques for tensor decomposition and perfect identifiability ⋮ An operator theoretic approach to nonparametric mixture models ⋮ Unnamed Item ⋮ Polynomial Learning of Distribution Families ⋮ Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Smoothed analysis of tensor decompositions