A Survey on concentration inequalities

The source code for the project can be found at: https://github.com/martinprad0/Thesis

Autores:
Prado Guerra, Martín
Tipo de recurso:
Trabajo de grado de pregrado
Fecha de publicación:
2024
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
eng
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/73881
Acceso en línea:
https://hdl.handle.net/1992/73881
Palabra clave:
Concentration
Inequality
Probability
Vapnik–Chervonenkis theory
Hoeffding inequality
Exponential inequality
Measure
Manifold sampling
Dimension estimation
Matemáticas
Rights
openAccess
License
Attribution 4.0 International
id UNIANDES2_9da3aa1b9ac40b1bc9f417bc9da38c3c
oai_identifier_str oai:repositorio.uniandes.edu.co:1992/73881
network_acronym_str UNIANDES2
network_name_str Séneca: repositorio Uniandes
repository_id_str
dc.title.eng.fl_str_mv A Survey on concentration inequalities
title A Survey on concentration inequalities
spellingShingle A Survey on concentration inequalities
Concentration
Inequality
Probability
Vapnik–Chervonenkis theory
Hoeffding inequality
Exponential inequality
Measure
Manifold sampling
Dimension estimation
Matemáticas
title_short A Survey on concentration inequalities
title_full A Survey on concentration inequalities
title_fullStr A Survey on concentration inequalities
title_full_unstemmed A Survey on concentration inequalities
title_sort A Survey on concentration inequalities
dc.creator.fl_str_mv Prado Guerra, Martín
dc.contributor.advisor.none.fl_str_mv Quiroz Salazar, Adolfo José
dc.contributor.author.none.fl_str_mv Prado Guerra, Martín
dc.contributor.jury.none.fl_str_mv Junca Peláez, Mauricio José
dc.subject.keyword.eng.fl_str_mv Concentration
Inequality
Probability
Vapnik–Chervonenkis theory
Hoeffding inequality
Exponential inequality
Measure
Manifold sampling
Dimension estimation
topic Concentration
Inequality
Probability
Vapnik–Chervonenkis theory
Hoeffding inequality
Exponential inequality
Measure
Manifold sampling
Dimension estimation
Matemáticas
dc.subject.themes.spa.fl_str_mv Matemáticas
description The source code for the project can be found at: https://github.com/martinprad0/Thesis
publishDate 2024
dc.date.accessioned.none.fl_str_mv 2024-02-05T13:07:17Z
dc.date.available.none.fl_str_mv 2024-02-05T13:07:17Z
dc.date.issued.none.fl_str_mv 2024-01-31
dc.type.none.fl_str_mv Trabajo de grado - Pregrado
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/bachelorThesis
dc.type.version.none.fl_str_mv info:eu-repo/semantics/acceptedVersion
dc.type.coar.none.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.content.none.fl_str_mv Text
dc.type.redcol.none.fl_str_mv http://purl.org/redcol/resource_type/TP
format http://purl.org/coar/resource_type/c_7a1f
status_str acceptedVersion
dc.identifier.uri.none.fl_str_mv https://hdl.handle.net/1992/73881
dc.identifier.instname.none.fl_str_mv instname:Universidad de los Andes
dc.identifier.reponame.none.fl_str_mv reponame:Repositorio Institucional Séneca
dc.identifier.repourl.none.fl_str_mv repourl:https://repositorio.uniandes.edu.co/
url https://hdl.handle.net/1992/73881
identifier_str_mv instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
repourl:https://repositorio.uniandes.edu.co/
dc.language.iso.none.fl_str_mv eng
language eng
dc.relation.references.none.fl_str_mv Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208–240. Springer, 2003.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
Mateo Dı́az, Adolfo J Quiroz, and Mauricio Velasco. Local angles and dimension estimation from data on manifolds. Journal of Multivariate Analysis, 173:229–247, 2019.
H Gzyl, R Jiménez, and AJ Quiroz. The physicist’s approach to the travelling salesman problem—ii. Mathematical and Computer Modelling, 13(7):45–48, 1990.
Svante Janson. On concentration of probability. Contemporary combinatorics, 10(3): 1–9, 2002.
David Pollard. Convergence of stochastic processes. David Pollard, 1984.
Loring W Tu. Manifolds. In An Introduction to Manifolds, pages 47–83. Springer, 2011.
dc.rights.en.fl_str_mv Attribution 4.0 International
dc.rights.uri.none.fl_str_mv http://creativecommons.org/licenses/by/4.0/
dc.rights.accessrights.none.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.none.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Attribution 4.0 International
http://creativecommons.org/licenses/by/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.none.fl_str_mv 45 páginas
dc.format.mimetype.none.fl_str_mv application/pdf
dc.publisher.none.fl_str_mv Universidad de los Andes
dc.publisher.program.none.fl_str_mv Matemáticas
dc.publisher.faculty.none.fl_str_mv Facultad de Ciencias
dc.publisher.department.none.fl_str_mv Departamento de Matemáticas
publisher.none.fl_str_mv Universidad de los Andes
institution Universidad de los Andes
bitstream.url.fl_str_mv https://repositorio.uniandes.edu.co/bitstreams/cb06060e-0911-4442-a5cd-922ce9a0768a/download
https://repositorio.uniandes.edu.co/bitstreams/08fbd987-43aa-4eb6-a3fb-4cea3c73aeaf/download
https://repositorio.uniandes.edu.co/bitstreams/cac94da6-ce02-473d-8695-efc69052d76a/download
https://repositorio.uniandes.edu.co/bitstreams/be78ed9d-0e8a-4aae-81de-239b7817575c/download
https://repositorio.uniandes.edu.co/bitstreams/da8d4569-d741-4c3a-a9d1-39f860dbc692/download
https://repositorio.uniandes.edu.co/bitstreams/4a2f5bcd-2dd3-49e3-bb1b-87dbb3f06587/download
https://repositorio.uniandes.edu.co/bitstreams/5ec2323f-a4f5-4054-b0f8-936ccdcfa757/download
https://repositorio.uniandes.edu.co/bitstreams/71d24f3e-1ac5-444f-bb34-7d4ff4f0edd4/download
bitstream.checksum.fl_str_mv ae9e573a68e7f92501b6913cc846c39f
95322499165bf2c53a298126d14f93ca
caaba4ba60a531de6c9c834d70ececc8
0175ea4a2d4caec4bbcc37e300941108
d6567d467250171e226fdc20226277a1
da50a7b8cf30733e29a7d7490d61de01
10ed871346b20f015f2d1e5068996faa
f21d7d217a13634eeb098eb5144c087b
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional Séneca
repository.mail.fl_str_mv adminrepositorio@uniandes.edu.co
_version_ 1812133923498491904
spelling Quiroz Salazar, Adolfo Josévirtual::377-1Prado Guerra, MartínJunca Peláez, Mauricio Josévirtual::378-12024-02-05T13:07:17Z2024-02-05T13:07:17Z2024-01-31https://hdl.handle.net/1992/73881instname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/The source code for the project can be found at: https://github.com/martinprad0/ThesisConcentration inequalities are formulas for the upper and lower bounds of the distribution of a random variable. The low computational cost of the inequality formulas, in comparison to the direct calculation of the distributions, make them viable for the estimation of distributions around the tails. In this survey, you will find the details, examples and applications of some of the most important concentration inequalities.MatemáticoPregrado45 páginasapplication/pdfengUniversidad de los AndesMatemáticasFacultad de CienciasDepartamento de MatemáticasAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2A Survey on concentration inequalitiesTrabajo de grado - Pregradoinfo:eu-repo/semantics/bachelorThesisinfo:eu-repo/semantics/acceptedVersionhttp://purl.org/coar/resource_type/c_7a1fTexthttp://purl.org/redcol/resource_type/TPConcentrationInequalityProbabilityVapnik–Chervonenkis theoryHoeffding inequalityExponential inequalityMeasureManifold samplingDimension estimationMatemáticasNoga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208–240. Springer, 2003.Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.Mateo Dı́az, Adolfo J Quiroz, and Mauricio Velasco. Local angles and dimension estimation from data on manifolds. Journal of Multivariate Analysis, 173:229–247, 2019.H Gzyl, R Jiménez, and AJ Quiroz. The physicist’s approach to the travelling salesman problem—ii. Mathematical and Computer Modelling, 13(7):45–48, 1990.Svante Janson. On concentration of probability. Contemporary combinatorics, 10(3): 1–9, 2002.David Pollard. Convergence of stochastic processes. David Pollard, 1984.Loring W Tu. Manifolds. In An Introduction to Manifolds, pages 47–83. Springer, 2011.201922940Publicationhttps://scholar.google.es/citations?user=qwMDh-4AAAAJvirtual::377-1https://scholar.google.es/citations?user=CoIlxH0AAAAJvirtual::378-10000-0003-4033-3400virtual::377-10000-0002-5541-0758virtual::378-1https://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0001497101virtual::377-1https://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0000155861virtual::378-11be19e5b-39c2-4d92-b44f-b9b4a48991cavirtual::377-11be19e5b-39c2-4d92-b44f-b9b4a48991cavirtual::377-11e5c3dc6-4d9c-406b-9f99-5c91523b7e49virtual::378-11e5c3dc6-4d9c-406b-9f99-5c91523b7e49virtual::378-1LICENSElicense.txtlicense.txttext/plain; charset=utf-82535https://repositorio.uniandes.edu.co/bitstreams/cb06060e-0911-4442-a5cd-922ce9a0768a/downloadae9e573a68e7f92501b6913cc846c39fMD52ORIGINALA survey on concentration inequalities.pdfA survey on concentration inequalities.pdfapplication/pdf503327https://repositorio.uniandes.edu.co/bitstreams/08fbd987-43aa-4eb6-a3fb-4cea3c73aeaf/download95322499165bf2c53a298126d14f93caMD54autorizacion tesis MP.pdfautorizacion tesis MP.pdfHIDEapplication/pdf277371https://repositorio.uniandes.edu.co/bitstreams/cac94da6-ce02-473d-8695-efc69052d76a/downloadcaaba4ba60a531de6c9c834d70ececc8MD55CC-LICENSElicense_rdflicense_rdfapplication/rdf+xml; charset=utf-8908https://repositorio.uniandes.edu.co/bitstreams/be78ed9d-0e8a-4aae-81de-239b7817575c/download0175ea4a2d4caec4bbcc37e300941108MD58TEXTA survey on concentration inequalities.pdf.txtA survey on concentration inequalities.pdf.txtExtracted texttext/plain65490https://repositorio.uniandes.edu.co/bitstreams/da8d4569-d741-4c3a-a9d1-39f860dbc692/downloadd6567d467250171e226fdc20226277a1MD59autorizacion tesis MP.pdf.txtautorizacion tesis MP.pdf.txtExtracted texttext/plain2069https://repositorio.uniandes.edu.co/bitstreams/4a2f5bcd-2dd3-49e3-bb1b-87dbb3f06587/downloadda50a7b8cf30733e29a7d7490d61de01MD511THUMBNAILA survey on concentration inequalities.pdf.jpgA survey on concentration inequalities.pdf.jpgGenerated Thumbnailimage/jpeg4562https://repositorio.uniandes.edu.co/bitstreams/5ec2323f-a4f5-4054-b0f8-936ccdcfa757/download10ed871346b20f015f2d1e5068996faaMD510autorizacion tesis MP.pdf.jpgautorizacion tesis MP.pdf.jpgGenerated Thumbnailimage/jpeg11058https://repositorio.uniandes.edu.co/bitstreams/71d24f3e-1ac5-444f-bb34-7d4ff4f0edd4/downloadf21d7d217a13634eeb098eb5144c087bMD5121992/73881oai:repositorio.uniandes.edu.co:1992/738812024-02-16 14:55:48.491http://creativecommons.org/licenses/by/4.0/Attribution 4.0 Internationalopen.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.coPGgzPjxzdHJvbmc+RGVzY2FyZ28gZGUgUmVzcG9uc2FiaWxpZGFkIC0gTGljZW5jaWEgZGUgQXV0b3JpemFjacOzbjwvc3Ryb25nPjwvaDM+CjxwPjxzdHJvbmc+UG9yIGZhdm9yIGxlZXIgYXRlbnRhbWVudGUgZXN0ZSBkb2N1bWVudG8gcXVlIHBlcm1pdGUgYWwgUmVwb3NpdG9yaW8gSW5zdGl0dWNpb25hbCBTw6luZWNhIHJlcHJvZHVjaXIgeSBkaXN0cmlidWlyIGxvcyByZWN1cnNvcyBkZSBpbmZvcm1hY2nDs24gZGVwb3NpdGFkb3MgbWVkaWFudGUgbGEgYXV0b3JpemFjacOzbiBkZSBsb3Mgc2lndWllbnRlcyB0w6lybWlub3M6PC9zdHJvbmc+PC9wPgo8cD5Db25jZWRhIGxhIGxpY2VuY2lhIGRlIGRlcMOzc2l0byBlc3TDoW5kYXIgc2VsZWNjaW9uYW5kbyBsYSBvcGNpw7NuIDxzdHJvbmc+J0FjZXB0YXIgbG9zIHTDqXJtaW5vcyBhbnRlcmlvcm1lbnRlIGRlc2NyaXRvcyc8L3N0cm9uZz4geSBjb250aW51YXIgZWwgcHJvY2VzbyBkZSBlbnbDrW8gbWVkaWFudGUgZWwgYm90w7NuIDxzdHJvbmc+J1NpZ3VpZW50ZScuPC9zdHJvbmc+PC9wPgo8aHI+CjxwPllvLCBlbiBtaSBjYWxpZGFkIGRlIGF1dG9yIGRlbCB0cmFiYWpvIGRlIHRlc2lzLCBtb25vZ3JhZsOtYSBvIHRyYWJham8gZGUgZ3JhZG8sIGhhZ28gZW50cmVnYSBkZWwgZWplbXBsYXIgcmVzcGVjdGl2byB5IGRlIHN1cyBhbmV4b3MgZGUgc2VyIGVsIGNhc28sIGVuIGZvcm1hdG8gZGlnaXRhbCB5L28gZWxlY3Ryw7NuaWNvIHkgYXV0b3Jpem8gYSBsYSBVbml2ZXJzaWRhZCBkZSBsb3MgQW5kZXMgcGFyYSBxdWUgcmVhbGljZSBsYSBwdWJsaWNhY2nDs24gZW4gZWwgU2lzdGVtYSBkZSBCaWJsaW90ZWNhcyBvIGVuIGN1YWxxdWllciBvdHJvIHNpc3RlbWEgbyBiYXNlIGRlIGRhdG9zIHByb3BpbyBvIGFqZW5vIGEgbGEgVW5pdmVyc2lkYWQgeSBwYXJhIHF1ZSBlbiBsb3MgdMOpcm1pbm9zIGVzdGFibGVjaWRvcyBlbiBsYSBMZXkgMjMgZGUgMTk4MiwgTGV5IDQ0IGRlIDE5OTMsIERlY2lzacOzbiBBbmRpbmEgMzUxIGRlIDE5OTMsIERlY3JldG8gNDYwIGRlIDE5OTUgeSBkZW3DoXMgbm9ybWFzIGdlbmVyYWxlcyBzb2JyZSBsYSBtYXRlcmlhLCB1dGlsaWNlIGVuIHRvZGFzIHN1cyBmb3JtYXMsIGxvcyBkZXJlY2hvcyBwYXRyaW1vbmlhbGVzIGRlIHJlcHJvZHVjY2nDs24sIGNvbXVuaWNhY2nDs24gcMO6YmxpY2EsIHRyYW5zZm9ybWFjacOzbiB5IGRpc3RyaWJ1Y2nDs24gKGFscXVpbGVyLCBwcsOpc3RhbW8gcMO6YmxpY28gZSBpbXBvcnRhY2nDs24pIHF1ZSBtZSBjb3JyZXNwb25kZW4gY29tbyBjcmVhZG9yIGRlIGxhIG9icmEgb2JqZXRvIGRlbCBwcmVzZW50ZSBkb2N1bWVudG8uPC9wPgo8cD5MYSBwcmVzZW50ZSBhdXRvcml6YWNpw7NuIHNlIGVtaXRlIGVuIGNhbGlkYWQgZGUgYXV0b3IgZGUgbGEgb2JyYSBvYmpldG8gZGVsIHByZXNlbnRlIGRvY3VtZW50byB5IG5vIGNvcnJlc3BvbmRlIGEgY2VzacOzbiBkZSBkZXJlY2hvcywgc2lubyBhIGxhIGF1dG9yaXphY2nDs24gZGUgdXNvIGFjYWTDqW1pY28gZGUgY29uZm9ybWlkYWQgY29uIGxvIGFudGVyaW9ybWVudGUgc2XDsWFsYWRvLiBMYSBwcmVzZW50ZSBhdXRvcml6YWNpw7NuIHNlIGhhY2UgZXh0ZW5zaXZhIG5vIHNvbG8gYSBsYXMgZmFjdWx0YWRlcyB5IGRlcmVjaG9zIGRlIHVzbyBzb2JyZSBsYSBvYnJhIGVuIGZvcm1hdG8gbyBzb3BvcnRlIG1hdGVyaWFsLCBzaW5vIHRhbWJpw6luIHBhcmEgZm9ybWF0byBlbGVjdHLDs25pY28sIHkgZW4gZ2VuZXJhbCBwYXJhIGN1YWxxdWllciBmb3JtYXRvIGNvbm9jaWRvIG8gcG9yIGNvbm9jZXIuPC9wPgo8cD5FbCBhdXRvciwgbWFuaWZpZXN0YSBxdWUgbGEgb2JyYSBvYmpldG8gZGUgbGEgcHJlc2VudGUgYXV0b3JpemFjacOzbiBlcyBvcmlnaW5hbCB5IGxhIHJlYWxpesOzIHNpbiB2aW9sYXIgbyB1c3VycGFyIGRlcmVjaG9zIGRlIGF1dG9yIGRlIHRlcmNlcm9zLCBwb3IgbG8gdGFudG8sIGxhIG9icmEgZXMgZGUgc3UgZXhjbHVzaXZhIGF1dG9yw61hIHkgdGllbmUgbGEgdGl0dWxhcmlkYWQgc29icmUgbGEgbWlzbWEuPC9wPgo8cD5FbiBjYXNvIGRlIHByZXNlbnRhcnNlIGN1YWxxdWllciByZWNsYW1hY2nDs24gbyBhY2Npw7NuIHBvciBwYXJ0ZSBkZSB1biB0ZXJjZXJvIGVuIGN1YW50byBhIGxvcyBkZXJlY2hvcyBkZSBhdXRvciBzb2JyZSBsYSBvYnJhIGVuIGN1ZXN0acOzbiwgZWwgYXV0b3IgYXN1bWlyw6EgdG9kYSBsYSByZXNwb25zYWJpbGlkYWQsIHkgc2FsZHLDoSBkZSBkZWZlbnNhIGRlIGxvcyBkZXJlY2hvcyBhcXXDrSBhdXRvcml6YWRvcywgcGFyYSB0b2RvcyBsb3MgZWZlY3RvcyBsYSBVbml2ZXJzaWRhZCBhY3TDumEgY29tbyB1biB0ZXJjZXJvIGRlIGJ1ZW5hIGZlLjwvcD4KPHA+U2kgdGllbmUgYWxndW5hIGR1ZGEgc29icmUgbGEgbGljZW5jaWEsIHBvciBmYXZvciwgY29udGFjdGUgY29uIGVsIDxhIGhyZWY9Im1haWx0bzpiaWJsaW90ZWNhQHVuaWFuZGVzLmVkdS5jbyIgdGFyZ2V0PSJfYmxhbmsiPkFkbWluaXN0cmFkb3IgZGVsIFNpc3RlbWEuPC9hPjwvcD4K