Questions tagged [proofs]
For questions that ask about or call for proofs for specific assertions, whether they be proofs of theorems or corollaries, proofs of concept through working implementation, counter proofs, or counter examples.
51
questions
2
votes
1answer
21 views
Equivalence between expected parameter increments in “Off-Policy Temporal-Difference Learning with Function Approximation”
I am having a hard time understanding the proof of theorem 1 presented in the "Off-Policy Temporal-Difference Learning with Function Approximation" paper.
Let $\Delta \theta$ and $\Delta \bar{\theta}...
2
votes
1answer
36 views
Is the derivative of the loss wrt a single scalar parameter proportional to the loss?
I am wondering about the correlation between the loss and the derivative of the loss wrt a single scalar parameter, with the same sample. That means: considering a machine learning model with ...
2
votes
0answers
50 views
Does Rice's theorem prove safe AI is undecidable?
According to Wikipedia
In computability theory, Rice's theorem states that all non-trivial,
semantic properties of programs are undecidable. A semantic property
is one about the program's ...
2
votes
1answer
62 views
How to prove $\mathcal H$ with VC dimension $d$ shatter all subsets with size less than $d-1$?
I was wondering that if a certain hypothesis class $H$ has a VC dimension $d$ over domain $X$ how to prove that $H$ will shatter all subsets of $X$ with size less than $d$ i.e $H$ will shatter $A \...
1
vote
3answers
81 views
How to prove that gradient descent doesn't necessarily find the global optimum?
How can I prove that gradient descent doesn't necessarily find the global optimum?
For example, consider the following function
$$f(x_1, x_2, x_3, x_4) = (x_1 + 10x_2)^2 + 5x_2^3 + (x_2 + 2x_3)^4 + ...
2
votes
0answers
59 views
Is an oracle that answers only with a “yes” or “no” dangerous?
I was thinking about the risks of Oracle AI and it doesn't seem as safe to me as Bostrom et al. suggest. From my point of view, even an AGI that only answers questions could have a catastrophic impact....
3
votes
1answer
56 views
Is the summation of consistent heuristic functions also consistent?
Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not?
Is there any proof ...
1
vote
0answers
18 views
Does SARSA(0) converge to the optimal policy in expectation if the Robbins-Monro conditions are removed?
The conditions of convergence of SARSA(0) to the optimal policy are :
The Robbins-Monro conditions above hold for $Ī±_t$.
Every state-action pair is visited infinitely often
The policy is greedy with ...
1
vote
2answers
31 views
What are the conditions for the convergence of SARSA to the optimal value function?
Is it correct that for SARSA to converge to the optimal value function (and policy)
The learning rate parameter $\alpha$ must satisfy the conditions:
$$\sum \alpha_{n^k(s,a)} =\infty \quad \text{and}...
1
vote
1answer
45 views
Does TD(0) prediction require Robbins-Monro conditions to converge to the value function?
Does the learning rate parameter $\alpha$ require the Robbins-Monro conditions below for the TD(0) algorithm to converge to the true value function of a policy?
$$\sum \alpha_t =\infty \quad \text{...
1
vote
1answer
140 views
Is there a simple proof of the convergence of TD(0)?
Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?
2
votes
1answer
79 views
Is there a mathematical theory behind why MLP can classify handwritten digits?
I'm trying to really understand how multi-layer perceptrons work. I want to prove mathematically that MLP's can classify handwritten digits. The only thing I really have is that each perceptron can ...
2
votes
1answer
55 views
Why does KL divergence not satisfy the triangle inequality?
$D_{KL}=\sum_i p(x_i)log(p(x_i)/q(x_i)$
Also can't you make it satisfy the triangle inequality by taking the absolute value of the information at every point?
2
votes
0answers
24 views
How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?
How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?
For this problem, I only try the case $n=2$ for 1. When $n=2$, consider 4 points $A,B,C,D$ and ...
2
votes
0answers
44 views
A problem about the relation between 1-oracle and 2-oracle PAC model
This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $\mathcal{D}_{+}$ and $\mathcal{D}_{-} .$ For an ...
2
votes
0answers
31 views
How can we prove this inequality, related to the generalization error, without using the Rademacher complexity?
This is an inequality on page 36 of the book Foundations of Machine Learning, but the author only states it without proof.
$$
\mathbb{P}\left[\left|R(h)-\widehat{R}_{S}(h)\right|>\epsilon\right] \...
2
votes
0answers
24 views
Convert a PAC-learning algorithm into another one which requires no knowledge of the parameter
This is part of the exercise 2.13 in the book Foundations of Machine Learning (page 28). You can refer to chapter 2 for the notations.
Consider a family of concept classes $\left\{\mathcal{C}_{s}\...
3
votes
1answer
51 views
Why is the stationary distribution independent of the initial state in the proof of the policy gradient theorem?
I was going through the proof of the policy gradient theorem here: https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#svpg
In the section "Proof of Policy Gradient ...
3
votes
1answer
62 views
Understanding proof of lemma 1 (policy improvement bound) of the “Trust Region Policy Optimization” paper
In the Trust Region Policy Optimization paper, in Lemma 1 of Appendix A, I did not quite understand the transition from (21) from (20). In going from (20) to (21), $A^\pi(s_t, a_t)$ is substituted ...
4
votes
2answers
447 views
If an heuristic is not admissible, can it be consistent?
I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
6
votes
1answer
64 views
Can two admissable heuristics not dominate each other?
I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am ...
10
votes
1answer
497 views
What are the implications of the “No Free Lunch” theorem for machine learning?
The No Free Lunch (NFL) theorem states (see the paper Coevolutionary Free Lunches by David H. Wolpert and William G. Macready)
any two algorithms are equivalent when their performance is averaged ...
4
votes
2answers
89 views
Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?
Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?
I came across this statement in the section 5.2 of the book "understanding machine learning: from theory to ...
2
votes
1answer
101 views
What happens to the optimal value function if the reward is multiplied by a constant?
What happens to the optimal action-value function, $q_*$ if the reward is multiplied by a constant $c$? Is the optimal action-value function also multiplied by such a constant?
2
votes
0answers
42 views
How to show Monte Carlo methods converge to an estimate which minimizes mean squared error?
In chapter six of Sutton and Barto (p.128), they claim Monte Carlo methods converge to an estimate minimizing the mean squared error. How can this be shown formally?
Bump
3
votes
1answer
142 views
How to show temporal difference methods converge to MLE?
In chapter 6 of Sutton and Barto (p. 128), they claim temporal difference converges to the maximum likelihood estimate (MLE). How can this be shown formally?
3
votes
1answer
59 views
Is unsupervised disentanglement really impossible?
In Locatello et al's Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations he claims to prove unsupervised disentanglement is impossible.
His entire claim is ...
1
vote
1answer
67 views
Is there a rigorous proof for finding Hopfield minima?
I am looking for a rigorous mathematical proof for finding the several local minima of the Hopfield networks. I am searching for something rigorous, a demonstration, not just let the network keep ...
8
votes
1answer
946 views
Where can I find the proof of the universal approximation theorem?
The Wikipedia article for the universal approximation theorem cites a version of the universal approximation theorem for Lebesgue-measurable functions from this conference paper. However, the paper ...
2
votes
1answer
87 views
Understanding the proof that A* search is optimal
I don't understand the proof that $A^*$ is optimal.
The proof is by contradiction:
Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
3
votes
1answer
121 views
How is G(z) related to x in GAN proof?
In the proofs for the original GAN paper, it is written:
$$ā«_x p_{data}(x) \log D(x)dx+ā«_zp(z)\log(1āD(G(z)))dz
=ā«_xp_{data}(x)\log D(x)+p_G(x) \log(1āD(x))dx$$
I've seen some explanations asserting ...
1
vote
0answers
44 views
Proof of Correctness of Monte Carlo Tree Search
I'm trying to write the proof of correctness of Monte Carlo Tree Search. Any help would be really appreciated.
3
votes
1answer
28 views
Proof Branch and Bound always finds optimal path in a graph?
I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others, but I haven't been able to find a proof on ...
2
votes
1answer
237 views
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}.
If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) ...
11
votes
2answers
527 views
Why doesn't Q-learning converge when using function approximation?
The tabular Q-learning algorithm is guaranteed to find the optimal $Q$ function, $Q^*$, provided the following conditions (the Robbins-Monro conditions) regarding the learning rate are satisfied
$\...
3
votes
1answer
185 views
How do I find whether this heuristic is or not admissible and consistent?
I was given the following problem to solve.
Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge ...
3
votes
2answers
60 views
Why is the max a non-expansive operator?
In certain reinforcement learning (RL) proofs, the operators involved are assumed to be non-expansive. For example, on page 6 of the paper Generalized Markov Decision Processes: Dynamic-programming ...
2
votes
1answer
219 views
Why Nilsson's Sequence Score isn't an admissible heuristic?
I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson heuristic isn't admissible.
4
votes
2answers
78 views
How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?
In this video, the lecturer states that $R(s)$, $R(s, a)$ and $R(s, a, s')$ are equivalent representations of the reward function. Intuitively, this is the case, according to the same lecturer, ...
6
votes
1answer
714 views
How do we prove the n-step return error reduction property?
In section 7.1 (about the n-step bootstrapping) of the book Reinforcement Learning: An Introduction (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-...
2
votes
1answer
108 views
Understanding lemma 2 of the “Trust Region Policy Optimization” paper
In the Trust Region Policy Optimization paper, in Lemma 2 of Appendix A, I did not quite understand deriving inequality (31) from (30), which is:
$$\bar{A}(s) = P(a \neq \tilde{a} | s) \mathbb{E}_{(a,...
4
votes
1answer
2k views
How do I show that uniform-cost search is a special case of A*?
How do I show that uniform-cost search is a special case of A*? How do I prove this?
1
vote
0answers
87 views
Why does Q-learning converges to optimal policy even if I am acting suboptimally?
In Q-learning, during training, it doesnāt matter how I select actions. The algorithm always converges to optimal optimal policy. Why does this happen?
2
votes
0answers
42 views
Understanding the proof of theorem 2.1 from the paper “Efficient reductions for imitation learning”
I am trying to understand the proof of theorem 2.1 from this paper:
Ross, StƩphane, and Drew Bagnell. "Efficient reductions for imitation learning." Proceedings of the thirteenth international ...
5
votes
1answer
68 views
Is there a limit of minimum error for a particular training dataset in artificial Neural Network?
In error-based learning using gradient descent, if I give you a training dataset, then can you find the minimum error after training? And the minimum error should be true for all architectures of a ...
7
votes
1answer
351 views
How can a neural network approximate all functions when the weights are not allowed to grow exponentially?
It has been proven in the paper "Approximation by Superpositions of a Sigmoidal Function" (by Cybenko, in 1989) that neural networks are universal function approximators. I have a related question.
...
2
votes
1answer
279 views
Why is exact inference in a Bayesian network both NP-hard and P-hard?
I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem.
So, I did formulate a 3-SAT problem by defining 3-CNF:
$$(x_1 \lor x_2) \land (\neg x_3 \...
8
votes
1answer
8k views
Why is A* optimal if the heuristic function is admissible?
A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
11
votes
8answers
3k views
Proof that Artificial General Intelligence is possible
It is assumed in computer science that the human mind can be replicated with a Turing machine, therefore Artificial General Intelligence (AGI) is possible. To assume otherwise is to believe in ...
2
votes
1answer
1k views
Understanding why the expectation is over the new policy $\pi'$ in the proof of the Policy Improvement Theorem
In reinforcement learning, policy improvement is a part of an algorithm called policy iteration, which attempts to find approximate solutions to the Bellman optimality equations.
Pages 84 and 85 in ...
