Questions tagged [randomized-algorithms]

an algorithm that employs a degree of randomness as part of its logic.

Filter by
Sorted by
Tagged with
1 vote
1 answer
30 views

How does randomized search cv algorithm work?

I am building a DNN, and I used Randomizedsearchcv from Scikit learn to optimise the hyper-parameters. Hence, I have one question about this: As I understood, the basic of random search is to try out ...
user avatar
  • 13
0 votes
1 answer
38 views

Evaluating randomized algorithms on randomized problem instances

Suppose we want to compare the performances of two algorithms — call them A and B — on a problem X. In particular, suppose that we want to evaluate the algorithms on random instances of X drawn from ...
user avatar
4 votes
2 answers
643 views

Why does Hutchinson's trace estimator reduce computation complexity?

Given a matrix $A$, we want to compute its trace, in which we can use a trick name Hutchinson's trace estimator \begin{align} tr(A) = tr(A\mathbb{E}[\epsilon \epsilon^T])=\mathbb{E}[tr(A \epsilon \...
user avatar
  • 137
1 vote
2 answers
382 views

Why is DP-SGD differentially private?

The paper 'Deep Learning with Differential Privacy' explains how to make a deep learning algorithm as differentially private. This explanation is implemented in Tensorflow Privacy My question is: we ...
user avatar
  • 11
2 votes
1 answer
35 views

Survey Analysis: Weighted Randomization to fill Missing Values

I am developing a Survey Analysis Application that works with Categorical Data and looking for a way to treat missing data fairly without losing the original data variance. Thus, I came up with a way ...
user avatar
  • 131
1 vote
0 answers
23 views

With high probability analysis

I am quite confused with 'with high probability analysis' in randomized algorithms. Perhaps it's helpful to illustrate with an example. What is the expected number of rounds to have at least one head ...
user avatar
1 vote
1 answer
64 views

Is it possible to to have more than 2 groups for biased coin randomization? If no, is there any modifications supporting multiple groups?

Is it possible to have more than 2 groups for biased coin randomization? If no, is there any modifications of biased coin randomization supporting multiple groups? This is my R code for generating ...
user avatar
  • 957
2 votes
1 answer
31 views

Why $Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}]$ for all $\lambda> 0$

I hope everyone is having a nice day. I don't know why this inequality holds. $$ Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}] $$ For $\lambda >0$. I guess it has something to do ...
user avatar