Rong Ge

Journal article Mathematical Programming · June 1, 2022 Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gra ... Full text Cite

On the optimization landscape of tensor decompositions

Journal article Mathematical Programming · June 1, 2022 Non-convex optimization with local search heuristics has been widely used in machine learning, achieving many state-of-art results. It becomes increasingly important to understand why they can work for these NP-hard problems on typical data. The landscape ... Full text Cite

On Nonconvex Optimization for Machine Learning

Journal article Journal of the ACM · March 1, 2021 Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in convex optimization problems, the most notable successes in mach ... Full text Cite

Estimating normalizing constants for log-concave distributions: Algorithms and lower bounds

Journal article Proceedings of the Annual ACM Symposium on Theory of Computing · June 8, 2020 Estimating the normalizing constant of an unnormalized probability distribution has important applications in computer science, statistical physics, machine learning, and statistics. In this work, we consider the problem of estimating the normalizing const ... Full text Cite

Beyond lazy training for over-parameterized tensor decomposition

Journal article Advances in Neural Information Processing Systems · January 1, 2020 Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decom ... Cite

Learning two-layer neural networks with symmetric inputs

Journal article 7th International Conference on Learning Representations, ICLR 2019 · January 1, 2019 © 7th International Conference on Learning Representations, ICLR 2019. All Rights Reserved. We give a new algorithm for learning a two-layer neural network under a general class of input distributions. Assuming there is a ground-truth two-layer network y = ... Cite

Explaining landscape connectivity of low-cost solutions for multilayer nets

Journal article Advances in Neural Information Processing Systems · January 1, 2019 Mode connectivity (Garipov et al., 2018; Draxler et al., 2018) is a surprising phenomenon in the loss landscape of deep nets. Optima'at least those discovered by gradient-based optimization'turn out to be connected by simple paths on which the loss functio ... Cite

Spectral learning on matrices and tensors

Journal article Foundations and Trends in Machine Learning · January 1, 2019 Spectral methods have been the mainstay in several domains such as machine learning, applied mathematics and scientific computing. They involve finding a certain kind of spectral decomposition to obtain basis functions that can capture important structures ... Full text Cite

Learning topic models — Provably and efficiently

Journal article Communications of the ACM · April 1, 2018 Full text Cite

Analyzing tensor power method dynamics in overcomplete regime

Journal article Journal of Machine Learning Research · April 1, 2017 We present a novel analysis of the dynamics of tensor power iterations in the overcomplete regime where the tensor CP rank is larger than the input dimension. Finding the CP decomposition of an overcomplete tensor is NP-hard in general. We consider the cas ... Cite

Minimal Realization Problems for Hidden Markov Models

Journal article IEEE Transactions on Signal Processing · April 1, 2016 This paper addresses two fundamental problems in the context of hidden Markov models (HMMs). The first problem is concerned with the characterization and computation of a minimal order HMM that realizes the exact joint densities of an output process based ... Full text Cite

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders

Journal article Algorithmica · May 1, 2015 We present a new algorithm for independent component analysis which has provable performance guarantees. In particular, suppose we are given samples of the form y=Ax+η where A is an unknown but non-singular n×n matrix, x is a random variable whose coordina ... Full text Cite

Tensor decompositions for learning latent variable models

Journal article Journal of Machine Learning Research · August 1, 2014 This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models-including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation-which exploits a certain tenso ... Cite

Minimal realization problem for Hidden Markov Models

Journal article 2014 52nd Annual Allerton Conference on Communication Control and Computing Allerton 2014 · January 30, 2014 In this paper, we study the problem of finding a minimal order (quasi-) Hidden Markov Model for a random process, which is the output process of an unknown stationary HMM of finite order. In the main theorem, we show that excluding a measure zero set in th ... Full text Cite

A tensor approach to learning mixed membership community models

Journal article Journal of Machine Learning Research · January 1, 2014 Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remov ... Cite

New algorithms for learning incoherent and overcomplete dictionaries

Journal article Journal of Machine Learning Research · January 1, 2014 In sparse recovery we are given a matrix A ∈ Rnxm ("the dictionary") and a vector of the form AX where X is sparse, and the goal is to recover X. This is a central notion in signal processing, statistics and machine learning. But in applications ... Cite

Provable bounds for learning some deep representations

Journal article 31st International Conference on Machine Learning Icml 2014 · January 1, 2014 2014 We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an n node multilayer network that has degree at most nγ for some γ < 1 and each edge has ... Cite

A practical algorithm for topic modeling with provable guarantees

Journal article 30th International Conference on Machine Learning Icml 2013 · January 1, 2013 Topic models provide a useful method for dimensionality reduction and exploratory data analysis in large text corpora. Most approaches to topic model learning have been based on a maximum likelihood objective. Efficient algorithms exist that attempt to app ... Cite

Towards a better approximation for SPARSEST CUT?

Journal article Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs · January 1, 2013 We give a new (1 + ε)-approximation for SPARSEST CUT problem on graphs where small sets expand significantly more than the sparsest cut (expansion of sets of size n/r exceeds that of the sparsest cut by a factor √ log n log r, for some small r; this condit ... Full text Cite

A tensor spectral approach to learning mixed membership community models

Journal article Journal of Machine Learning Research · January 1, 2013 Detecting hidden communities from observed interactions is a classical problem. Theoretical analysis of community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we prov ... Cite

Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders

Journal article Advances in Neural Information Processing Systems · December 1, 2012 We present a new algorithm for Independent Component Analysis (ICA) which has provable performance guarantees. In particular, suppose we are given samples of the form y = Ax +η where A is an unknown n × n matrix and x is a random variable whose components ... Cite

Finding overlapping communities in social networks: Toward a rigorous approach

Journal article Proceedings of the ACM Conference on Electronic Commerce · June 4, 2012 A community in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concept in most domains where networks arise: social, technological, biological, etc ... Full text Cite

Computing a nonnegative matrix factorization - Provably

Journal article Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2012 The Nonnegative Matrix Factorization (NMF) problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormo ... Full text Cite

Learning topic models - Going beyond SVD

Journal article Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs · January 1, 2012 Topic Modeling is an approach used for automatic comprehension and classification of data in a variety of settings, and perhaps the canonical application is in uncovering thematic structure in a corpus of documents. A number of foundational works both in m ... Full text Cite

Another sub-exponential algorithm for the simple stochastic game

Journal article Algorithmica New York · December 1, 2011 We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can ... Full text Cite

New tools for graph coloring

Journal article Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · September 8, 2011 How to color 3 colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses n 0.2072 colors. There are no indications that coloring using say O(log n) colors is hard. It has been suggested that ... Full text Cite

Computational complexity and information asymmetry in financial products

Journal article Communications of the ACM · May 1, 2011 Computational complexity studies intractable problems like NP-complete problems, which are conjectured to require more computational resources than can be provided by the fastest computers. The intractability of this problem leads to a concrete realization ... Full text Cite

New algorithms for learning in presence of errors

Journal article Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2011 We give new algorithms for a variety of randomly-generated instances of computational problems using a linearization technique that reduces to solving a system of linear equations. These algorithms are derived in the context of learning with structured noi ... Full text Cite

New results on simple stochastic games

Journal article Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · December 1, 2009 We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can ... Full text Cite