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 |