On sparse mirror descent

Parsimony is a general guiding principle in science and philosophy which suggests that if one has multiple theories fitting the data equally well, one should choose the ``simplest" theory. In the field of machine learning and artificial intelligence, the sparsity of a model is used as a measure of parsimony. Algorithms which produce an optimal set of sparse parameters for a given model have been notoriously difficult to construct due to the non-convex and combinatorial nature of sparsity constraints. In this thesis we begin by giving an overview of popular algorithms for sparse and convex optimization. We then show how they can be combined with classical tools from the theory of approximation algorithms to compute approximate projections onto the sparsity constraints, which ultimately leads to a novel algorithm for sparse optimization.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Guha, Shovik

Contributors dc:contributor

• Koyejo, Oluwasanmi

• Machine Learning
• Optimization
• Algorithms
• Mirror Descent
• Sparse Optimization

Statement dc:rights

• Copyright 2022 Shovik Guha

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/115797

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115797