Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
We improve the over-parametrization size over two beautiful results [Li and Liang' 2018] and [Du, Zhai, Poczos and Singh' 2019] in deep learning theory.
Code (0)
등록된 구현이 없습니다.
Tasks
Deep LearningLearning TheorySimilar Papers 제목 키워드 기반
A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Specially, consider a random walk on a regular Markov chain and a Hermitian…
Graph LearningGraph Representation LearningRepresentation LearningTraining Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
We consider the problem of training a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In the typical setting of over-parametrization, the network width $m$ is much …
On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix
This paper presents local asymptotic minimax regret lower bounds for adaptive Linear Quadratic Regulators (LQR). We consider affinely parametrized $B$-matrices and known $A$-matrices and aim to understand when logarithmi…
PAC-Bayesian Certificates for Quadratic Closed-Loop Control
PAC-Bayesian bounds provide finite-sample guarantees for data-dependent randomized predictors, but applying them to learning-based control is difficult because the natural objective is a quadratic trajectory cost. Such l…
Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points
This paper studies the role of over-parametrization in solving non-convex optimization problems. The focus is on the important class of low-rank matrix sensing, where we propose an infinite hierarchy of non-convex proble…