MARC

 008260126s2024        us                              c    eng  d
■001000017360604
■00520260202105554
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798263398033
■035    ▼a(MiAaPQ)AAI32315845
■035    ▼a(MiAaPQ)GeorgiaTech75185
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a330
■1001  ▼aRutten,  Daan.
■24510▼aCompatibility,  Predictions  and  Optimization  in  Large-Scale  Online  Decision  Making
■260    ▼a[Sl]▼bGeorgia  Institute  of  Technology▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a290  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-05,  Section:  B.
■500    ▼aAdvisor:  Mukherjee,  Debankur.
■5021  ▼aThesis  (Ph.D.)--Georgia  Institute  of  Technology,  2024.
■520    ▼aThe  last  few  years  have  seen  a  shift  in  server  architecture  towards  large-scale,  dedicateddata  centers.  The  massive  scale  of  these  datacenters  has  highlighted  important,  unsolvedproblems  in  the  space  of  load  balancing,  speed  scaling  and  related  areas  in  the  optimizationof  such  large-scale  service  systems.  Many  of  the  mathematical  problems  abstracted  fromthese  challenges  form  fundamental  problems  in  the  field  of  online  decision  making  andrequire  a  combination  of  tools  from  probability,  stochastic  processes  and  online  algorithmstogether  with  completely  new  insights  to  be  solvable.  This  thesis  broadly  addresses  threeof  these  problems,  as  detailed  below.In  Chapter  2,  we  consider  a  large-scale,  parallel-server  system,  where  tasks  of  a  particular  type  can  only  be  routed  to  a  small  subset  of  servers.  The  task-server  constraints  arerepresented  by  a  bipartite  graph  where  vertices  represent  task  types  and  servers,  respectively.  The  analysis  of  these  systems  has  historically  relied  heavily  on  mean-field  analysis.A  pivotal  assumption  for  this  framework  is  that  servers  are  exchangeable.  However,  due  tothe  lack  of  exchangeability  in  the  constrained  system,  mean-field  techniques  fundamentallybreak  down.  In  this  chapter,  we  develop  a  novel  coupling-based  approach  to  establish  themean-field  approximation  for  a  large  class  of  sparse  graphs,  including  spatial  graphs.  Themethod  extends  the  scope  of  mean-field  analysis  far  beyond  the  classical  full-flexibilitysetup.In  Chapter  3,  we  consider  a  large-scale,  parallel-server  system  with  an  unknown  arrivalrate,  where  each  server  is  able  to  adjust  its  processing  speed.  The  objective  is  to  minimize  the  system  cost,  which  consists  of  a  power  cost  to  maintain  the  servers'  processingspeed  and  a  quality  of  service  cost  depending  on  the  tasks'  sojourn  times.  We  draw  onideas  from  stochastic  approximation  to  design  a  novel  speed  scaling  algorithm  and  provethat  the  server's  processing  speeds  converge  to  the  globally  asymptotically  optimum  value.Curiously,  the  algorithm  is  fully  distributed  and  does  not  require  any  communication  between  servers.  Apart  from  the  algorithm  design,  a  key  contribution  of  our  approach  lies  indemonstrating  how  concepts  from  the  stochastic  approximation  literature  can  be  leveragedto  effectively  tackle  learning  problems  in  large-scale,  distributed  systems.In  Chapter  4,  we  consider  learning-augmented  algorithms,  where  the  decision  makerhas  access  to  a  black-box  oracle,  such  as  a  machine  learning  model,  that  provides  untrustedand  potentially  inaccurate  predictions  of  future  inputs.  The  goal  of  the  decision  maker  isto  exploit  the  predictions  if  they  are  accurate,  while  guaranteeing  performance  that  is  notmuch  worse  than  the  hindsight  optimal  sequence  of  decisions,  even  when  predictions  areinaccurate.  We  consider  two  applications:  capacity  scaling  and  smoothed  online  optimization.  For  both  applications,  we  design  a  novel  algorithm  and  prove  a  competitive  ratioguarantee  as  a  function  of  the  predictions'  accuracy.  Interestingly,  we  identify  a  fundamental  trade-off  between  the  worst-case  (predictions  are  inaccurate)  and  best-case  (predictionsare  accurate).  In  fact,  we  prove  that  this  trade-off  is  necessary  for  any  algorithm.
■590    ▼aSchool  code:  0078.
■650  4▼aSparsity
■650  4▼aGraphs
■650  4▼aNeural  networks
■650  4▼aDecision  making
■650  4▼aStochastic  models
■650  4▼aOrdinary  differential  equations
■650  4▼aProcessing  speed
■650  4▼aMathematics
■690    ▼a0800
■690    ▼a0405
■71020▼aGeorgia  Institute  of  Technology.
■7730  ▼tDissertations  Abstracts  International▼g87-05B.
■790    ▼a0078
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360604▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서