The Nonconvex Geometry of Linear Inverse Problems
- URL: http://arxiv.org/abs/2101.02776v1
- Date: Thu, 7 Jan 2021 21:55:08 GMT
- Title: The Nonconvex Geometry of Linear Inverse Problems
- Authors: Armin Eftekhari and Peyman Mohajerin Esfahani
- Abstract summary: The gauge function measures the complexity of a statistical model.
We introduce a new notion of statistical complexity, gauge$_p$ function, which overcomes the limitations of the gauge function.
We propose a new learning machine, with the building block of gauge$_p$ function, and arm this machine with a number of statistical guarantees.
- Score: 26.049281826055797
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The gauge function, closely related to the atomic norm, measures the
complexity of a statistical model, and has found broad applications in machine
learning and statistical signal processing. In a high-dimensional learning
problem, the gauge function attempts to safeguard against overfitting by
promoting a sparse (concise) representation within the learning alphabet.
In this work, within the context of linear inverse problems, we pinpoint the
source of its success, but also argue that the applicability of the gauge
function is inherently limited by its convexity, and showcase several learning
problems where the classical gauge function theory fails. We then introduce a
new notion of statistical complexity, gauge$_p$ function, which overcomes the
limitations of the gauge function. The gauge$_p$ function is a simple
generalization of the gauge function that can tightly control the sparsity of a
statistical model within the learning alphabet and, perhaps surprisingly, draws
further inspiration from the Burer-Monteiro factorization in computational
mathematics.
We also propose a new learning machine, with the building block of gauge$_p$
function, and arm this machine with a number of statistical guarantees. The
potential of the proposed gauge$_p$ function theory is then studied for two
stylized applications. Finally, we discuss the computational aspects and, in
particular, suggest a tractable numerical algorithm for implementing the new
learning machine.
Related papers
- Tractable and Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation [8.378137704007038]
We present a regret analysis for distributional reinforcement learning with general value function approximation.
Our theoretical results show that approximating the infinite-dimensional return distribution with a finite number of moment functionals is the only method to learn the statistical information unbiasedly.
arXiv Detail & Related papers (2024-07-31T00:43:51Z) - Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic [8.813846754606898]
We present a mathematical analysis of limitations and challenges associated with using gradient-based learning techniques.
We highlight that the variance of the gradient is negligibly small in both cases when either a frequency or the prime base $p$ is large.
arXiv Detail & Related papers (2023-10-19T11:33:33Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation.
Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions.
We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
arXiv Detail & Related papers (2023-07-08T15:41:48Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
We study optimal procedures for estimating a linear functional based on observational data.
For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
arXiv Detail & Related papers (2023-01-16T02:57:37Z) - Provable General Function Class Representation Learning in Multitask
Bandits and MDPs [58.624124220900306]
multitask representation learning is a popular approach in reinforcement learning to boost the sample efficiency.
In this work, we extend the analysis to general function class representations.
We theoretically validate the benefit of multitask representation learning within general function class for bandits and linear MDP.
arXiv Detail & Related papers (2022-05-31T11:36:42Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability.
We study SM approximation for two function classes: circuits and Turing machines.
arXiv Detail & Related papers (2021-07-28T04:28:55Z) - A Simple and General Debiased Machine Learning Theorem with Finite
Sample Guarantees [4.55274575362193]
We provide a nonasymptotic debiased machine learning theorem that encompasses any global or local functional of any machine learning algorithm.
Our results culminate in a simple set of conditions that an analyst can use to translate modern learning theory rates into traditional statistical inference.
arXiv Detail & Related papers (2021-05-31T17:57:02Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
We study the exploration-exploitation tradeoff at the core of reinforcement learning.
In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function.
Our regret bounds are independent of the number of episodes.
arXiv Detail & Related papers (2020-11-09T18:32:22Z) - Batch Value-function Approximation with Only Realizability [17.692408242465763]
We make progress in a long-standing problem of batch reinforcement learning (RL): learning $Qstar$ from an exploratory dataset.
Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure.
We also discuss how BVFT can be applied to model selection among other extensions and open problems.
arXiv Detail & Related papers (2020-08-11T20:09:37Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
We establish a provably efficient reinforcement learning algorithm with general value function approximation.
We show that our algorithm achieves a regret bound of $widetildeO(mathrmpoly(dH)sqrtT)$ where $d$ is a complexity measure.
Our theory generalizes recent progress on RL with linear value function approximation and does not make explicit assumptions on the model of the environment.
arXiv Detail & Related papers (2020-05-21T17:36:09Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.