Questions tagged [optimal-stopping]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
17 views

Cross validation and early stoping

I'm kinda new to this, so excuse me if I sound a bit silly. I have a set of data that proves to be really unstable while training, with ups and downs on accuracy and evaluation loss, and i haven't ...
user avatar
0 votes
1 answer
34 views

Paper that proposes an algorithm for a optimal stoping rule based on an empirical distribution

Can you suggest me a paper that proposes an optimal stoping rule based on an empirical distribution? I am looking for some like this: I observe a random variable $x$ for a given time (this is usually ...
user avatar
1 vote
0 answers
127 views

When to stop episode during reinforcement learning

I have a reinforcement learning environment where the agent has to reach a certain target position by moving its limbs. At the moment, I stop each episode after 2000 simulation steps. During the first ...
user avatar
3 votes
1 answer
51 views

When to stop enumerating a fixed set of unknown cardinality via random sampling?

DNS resolution can sometimes return one of multiple IP addresses, for load balancing. I would like to enumerate a list of IPs for a service so I can whitelist traffic to a domain without performing an ...
user avatar
  • 141
1 vote
0 answers
19 views

Early stopping in wilcoxon signed rank test?

I have decided to acquire N joint samples of variables X and Y (for example, N=200), and test whether their means are different using the signed-rank test. I will repeat this procedure many times, ...
user avatar
2 votes
1 answer
1k views

When is EarlyStopping really neccessary?

I have trained a CNN with EarlyStopping and I wonder if I should not use EarlyStopping and waste 20% of Trainingsdata for Validation, because it looks like as that the validation loss doesn't increase ...
user avatar
  • 145
1 vote
0 answers
136 views

Tensorboard: Why does validation loss get evaluated after training loss stops?

When I monitor my model through Tensorboard, I notice that Tensorboard stops plotting the training loss but not the validation loss. Since the early stopping module, as I set it up below, is ...
user avatar
0 votes
0 answers
110 views

grid search with early stopping - influence of validation data to grid search results?

I would like to combine grid search with early stopping by passing a separate validation data set (used for early stopping) to grid search. However, I wonder when I use during the entire grid search ...
user avatar
  • 145
2 votes
0 answers
42 views

State the overall alpha after interium analyses

Suppose a trial investigator wants to analyse the primary outcome (morning peak flow at 6 months) after the trial has been running for 1 year, 18 months and 2 years using alpha=0.05 each time, and ...
user avatar
  • 67
0 votes
0 answers
979 views

Expectation Maximization (EM) stopping criterion

In several EM description (e.g., Theory and Use of the EM Algorithm By Maya R. Gupta and Yihua Chen) I read that two tipical stopping criterions for EM are defined on the difference between log-...
user avatar
1 vote
0 answers
26 views

Early loss stop and strategies to select best model

Run config: ...
user avatar
4 votes
1 answer
68 views

Problem of accepting a prize versus trying to get a better one

I don't know how to better formulate the general problem I am thinking about, let me try formulate an example. Assume you are playing a game with N rounds, and at each round the following happens: ...
user avatar
2 votes
1 answer
245 views

ABC: Population Monte Carlo (PMC) convergence statistics?

I'm using the abcpmc code: Approximate Bayesian Computing (ABC) Population Monte Carlo (PMC) implementation based on Sequential Monte Carlo (SMC) with Particle Filtering techniques. described in ...
user avatar
  • 3,124
11 votes
1 answer
539 views

The Fishing Problem

Suppose you want to go fishing at the nearby lake from 8AM-8PM. Due to overfishing, a law has been instated that says you may only catch one fish per day. When you catch a fish, you can choose to ...
user avatar
  • 219
2 votes
0 answers
141 views

Neural network training: going backward to go forward?

I am working on CNN models which are intended to predict a protein's structure from its amino acid sequence. I have a decently large data set, 750 protein structures containing over 100,000 amino ...
user avatar
  • 218
2 votes
0 answers
48 views

At which rank should I reasonably stop selecting interview candidates?

It seems that my problem could be classified as an "optimal stopping" problem, but I am unable to make much of this information. It is an important problem for my organisation (an NGO), in order to ...
user avatar
0 votes
0 answers
24 views

loss function for stopping problem

I want to test different algorithms for predicting when a person stops an activity. The information available to the person (and the algorithms) consists of different performance criteria and other ...
user avatar
  • 101
4 votes
0 answers
52 views

"Approved" switch criterion for the Secretary problem

The secretary problem ( 1, 2, 3, 4, 5 ) optimal stopping, says "stop and keep the best" in a randomized sequence of known length "k" where you can't select previously elements of the sequence. One ...
user avatar
  • 8,280
2 votes
1 answer
160 views

Simulation of Secretary problem: optimal pool size given k=2?

Question: Is it incorrect to think there is a "sweet spot" where more samples slightly decreases the likelihood of a "Best pick" in the Secretary Problem? Details: The "Secretary Problem" from "...
user avatar
  • 8,280
14 votes
2 answers
4k views

Why is it wrong to stop an A/B test before optimal sample size is reached?

I am in charge of presenting the results of A/B tests (run on website variations) at my company. We run the test for a month and then check the p-values at regular intervals until we reach ...
user avatar
  • 195
3 votes
2 answers
181 views

Optimal decision process to estimate Markov chain limiting distribution

Suppose there is a irreducible, reversible Markov chain with known states $1,\ldots,N$ and unknown transition matrix $T_{ij}$ and unknown limiting distribution $\pi_i$. I am able to repeatedly ...
user avatar
4 votes
1 answer
137 views

Prove $Z_n = X_n1_{n \le T} + Y_n1_{n+1\ge T}$ is a martingale

Given a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}, \mathbb P)$, let $X = (X_n)_{n \in \mathbb N}$ and $Y = (Y_n)_{n \in \mathbb N}$ be $(\{\mathscr F_n\}, \mathbb P)-$...
user avatar
  • 2,176
2 votes
1 answer
68 views

Prove Doob's using a certain Lemma

I am to prove Doob's (d) in the red box below: What I tried: Since $T < \infty$ a.s., we have $$E[X_T] = E[\lim X_{T \wedge n}].$$ By Fatou's Lemma, we have $$E\left[\lim X_{T \wedge n}\right] ...
user avatar
  • 2,176
3 votes
1 answer
152 views

How to show that $S \wedge T, S \vee T, S + T$ are stopping times?

From Williams (1991) Probability with Martingales: $$(S \wedge T \le n) = (S \le n) \cup (T \le n) \in \mathscr F_n$$ $$\because (S \le n), (T \le n) \in \mathscr F_n$$ $$(S \ \vee \ T \le n) = (S \...
user avatar
  • 2,176
2 votes
0 answers
147 views

Optimal stopping rule for sequential subsampling?

I have a set of ranking models added sequential one at a time. Where each model generate ranks for the sample. Finally the expected rank is done by taking the average rank from all models. scenario I ...
user avatar
  • 136
2 votes
1 answer
976 views

Secretary Problem (Optimal Stopping) When Interviews Are Costly

The Secretary problem is an optimal stopping problem. Imagine hiring one secretary out of $n$ applicants, who are interviewed in random order and either rejected or hired on the spot (as soon as one ...
user avatar
  • 161
5 votes
0 answers
337 views

Optimal Stopping for Bernoulli One-Armed Bandit with a Fixed, Known Payout

I'm very new to bandit problems (apologies if I've formatted my question incorrectly), but I have to solve the optimal stopping of what I think is a very simple case. Suppose I have two arms $k = {1, ...
user avatar
  • 51
0 votes
0 answers
51 views

How important is the quality of solutions to NP-hard problems arising in machine learning problems?

Machine learning and inference problems give rise to intractable problems. For instance the exact inference in Bayes nets is an NP-hard problem. At the same time there are polynomially tractable ...
user avatar
7 votes
0 answers
196 views

bias of an estimator when using stopping rules

Consider the setting where $X_1,X_2,...$ are i.i.d. real-valued random variables with $\mathbb{E}[X_i] = \theta$ and let the random variable $\tau$ be an associated stopping time. I'm wondering what ...
user avatar
  • 1,188
6 votes
1 answer
340 views

How are optional stopping rules based on e.g. sample confidence (width of confidence interval) biased?

Inspired by this: http://pss.sagepub.com/content/22/11/1359 In the context of open-ended data collection where the necessary sample size cannot be properly estimated, for the purpose of a ...
user avatar
  • 1,694
12 votes
0 answers
1k views

Understanding Sequential Probability Ratio Test (SPRT) Likelihood Ratio

I am a software developer looking to develop an alternative for the simple hypothesis testing scheme described here. In short, the test works as follows: Two URLs are compared for their ability to ...
user avatar
  • 653
19 votes
4 answers
2k views

How could one develop a stopping rule in a power analysis of two independent proportions?

I am a software developer working on A/B testing systems. I don't have a solid stats background but have been picking up knowledge over the past few months. A typical test scenario involves comparing ...
user avatar
  • 653
2 votes
0 answers
2k views

Determining Optimal Number of Cluster in Hierarchical Clustering in Consideration of Variance of Data

I'm applying a Hierarchical Agglomerative Clustering (HAC) for grouping my data and I need to determine the number of the cluster automatically. To determine the optimal number of cluster, I obtain ...
user avatar
  • 121
16 votes
3 answers
742 views

Optional stopping rules not in textbooks

Stopping rules affect the relationship between P-values and the error rates associated with decisions. A recent paper by Simmons et al. 2011 coins the term researcher degrees of freedom to describe a ...
user avatar
  • 11.2k
3 votes
1 answer
133 views

Thoughts on model self-penalization amidst difficult parameter estimation

It is well accepted that one should account for model complexity when performing model comparisons, and the general procedure is to penalize more complex models more strongly. While this makes sense ...
user avatar
0 votes
2 answers
219 views

Difference between the Stopping Criteria [closed]

I would like to know the difference between below mentioned stopping criteria used in various gradient descent algorithm $\frac{Prev\_fun\_value - curr\_fun\_value}{Pre\_fun\_value} \le tol$ $Prev\...
user avatar
  • 4,037
4 votes
0 answers
194 views

Stopping rule for chi-squared discretization algorithm

I developed an algorithm that uses the chi-squared test to perform supervised discretization of a continuous variable. I described it in the paper "ChiD-A Chi-Squared Discretization Algorithm" ...
user avatar
2 votes
0 answers
111 views

Optimal stopping under partially observable state

This problem is basically the classic asset selling problem but with imperfect state information. In the classical problem, we have an asset that we wish to sell, we receive offers w(0) to w(N-1). ...
user avatar
4 votes
2 answers
868 views

Optimal stopping from an unknown distribution

The Secretary problem has an algorithm for fixed N and immediate accept/reject (that is, reject reject ... accept one, stop). There are several variants; in mine, secretaries or samples come from a ...
user avatar
  • 3,197