MARC

 008260126s2025        us                              c    eng  d
■001000017358458
■00520260202104705
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798286499458
■035    ▼a(MiAaPQ)AAI32116890
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a310
■1001  ▼aOu,  Tingting.
■24510▼aDifferentially  Private  Algorithmic  Design:  Private  Bandits,  Counting  and  Histograms
■260    ▼a[Sl]▼bColumbia  University▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a141  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-01,  Section:  B.
■500    ▼aAdvisor:  Cummings,  Rachel;Avella  Medina,  Marco.
■5021  ▼aThesis  (Ph.D.)--Columbia  University,  2025.
■520    ▼aAs  concerns  around  data  privacy  continue  to  grow,  designing  differentially  private  (DP)  algorithms  has  become  a  central  topic  of  interest,  particularly  for  statistical  and  machine  learning  methods  used  in  practice.  This  thesis  contributes  to  this  line  of  work  by  presenting  new  results  in  private  algorithm  design  and  analysis  for  multi-armed  bandits,  counting,  and  histogram  estimation.The  thesis  begins  by  showing  that  the  classical  Thompson  Sampling  algorithm  with  a  Gaussian  prior  for  multi-armed  bandits  is  inherently  differentially  private  without  any  modification.  We  further  propose  simple  modifications  that  yield  improved  privacy  guarantees,  and  analyze  how  these  adjustments  affect  regret.  Next,  we  study  distinct  count  estimation  under  differential  privacy  in  the  turnstile  streaming  model.  We  present  the  first  differentially  private  algorithms  using  sublinear  space  in  the  stream  length  T.  Our  method  achieves  an  error  and  space  complexity  of  \uD835\uDC42˜(\uD835\uDC47  1/3  ),  significantly  improving  over  prior  linear-space  approaches.  Lastly,  we  address  locally  private  succinct  histogram  estimation  in  the  federated  setting.  Building  on  the  sample-and-threshold  paradigm  which  is  only  centrally  private,  we  develop  a  locally  private  algorithm  that  incorporates  an  additional  local  randomization  step.  This  new  method  achieves  stronger  privacy  guarantees  without  significantly  compromising  the  accuracy.
■590    ▼aSchool  code:  0054.
■650  4▼aStatistics
■650  4▼aApplied  mathematics
■650  4▼aComputer  science
■653    ▼aHistograms
■653    ▼aThompson  Sampling  algorithm
■653    ▼aDifferentially  private  algorithms
■653    ▼aDifferential  privacy
■653    ▼aTurnstile  streaming  model
■690    ▼a0796
■690    ▼a0984
■690    ▼a0463
■690    ▼a0364
■71020▼aColumbia  University▼bOperations  Research.
■7730  ▼tDissertations  Abstracts  International▼g87-01B.
■790    ▼a0054
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358458▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서