# Non-Convex Optimizations for Machine Learning with Theoretical Guarantee: Robust Matrix Completion and Neural Network Learning

arXiv: https://arxiv.org/abs/2306.16557 · HTML: https://mlsanity.com/paper/2306.16557/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 250 references that are in the map.
- First posted on arXiv 28 Jun 2023.

## Builds on (most cited first, 25 of 25)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [MixMatch: A Holistic Approach to Semi-Supervised Learning](https://mlsanity.com/paper/1905.02249/) (2019)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Temporal Ensembling for Semi-Supervised Learning](https://mlsanity.com/paper/1610.02242/) (2016)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Deep Domain Confusion: Maximizing for Domain Invariance](https://mlsanity.com/paper/1412.3474/) (2014)
- [The Lottery Ticket Hypothesis for Pre-trained BERT Networks](https://mlsanity.com/paper/2007.12223/) (2020)
- [Billion-scale semi-supervised learning for image classification](https://mlsanity.com/paper/1905.00546/) (2019)
- [Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures](https://mlsanity.com/paper/1607.03250/) (2016)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Data-free parameter pruning for Deep Neural Networks](https://mlsanity.com/paper/1507.06149/) (2015)
- [The Lottery Tickets Hypothesis for Supervised and Self-supervised Pre-training in Computer Vision Models](https://mlsanity.com/paper/2012.06908/) (2020)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization](https://mlsanity.com/paper/1604.03257/) (2016)
- [Stabilizing the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1903.01611/) (2019)
- [Consistent Feature Selection for Analytic Deep Neural Networks](https://mlsanity.com/paper/2010.08097/) (2020)
- [Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems](https://mlsanity.com/paper/1905.09870/) (2019)
- [Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning](https://mlsanity.com/paper/2007.08243/) (2020)
- [SiPPing Neural Networks: Sensitivity-informed Provable Pruning of Neural Networks](https://mlsanity.com/paper/1910.05422/) (2019)
- [Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels](https://mlsanity.com/paper/1711.03440/) (2017)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Nearly-optimal Robust Matrix Completion](https://mlsanity.com/paper/1606.07315/) (2016)
- [Statistical and Algorithmic Insights for Semi-supervised Learning with Self-training](https://mlsanity.com/paper/2006.11006/) (2020)

## Abstract (arXiv)

Despite the recent development in machine learning, most learning systems are still under the concept of "black box", where the performance cannot be understood and derived. With the rise of safety and privacy concerns in public, designing an explainable learning system has become a new trend in machine learning. In general, many machine learning problems are formulated as minimizing (or maximizing) some loss function. Since real data are most likely generated from non-linear models, the loss function is non-convex in general. Unlike the convex optimization problem, gradient descent algorithms will be trapped in spurious local minima in solving non-convex optimization. Therefore, it is challenging to provide explainable algorithms when studying non-convex optimization problems. In this thesis, two popular non-convex problems are studied: (1) low-rank matrix completion and (2) neural network learning.