# Questions tagged [randomized-algorithms]

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

8 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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 \...
1 vote
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 ...
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 ...
1 vote
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 ...
1 vote
### 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 ...