Stochastic Optimization and Learning: An Adaptive and Resource-Efficient Approach
| dc.contributor.author | Salgia, Sudeep | |
| dc.contributor.chair | Zhao, Qing | en_US |
| dc.contributor.committeeMember | Wegkamp, Marten | en_US |
| dc.contributor.committeeMember | Acharya, Jayadev | en_US |
| dc.contributor.committeeMember | Krishnamurthy, Vikram | en_US |
| dc.date.accessioned | 2024-04-05T18:47:50Z | |
| dc.date.available | 2024-04-05T18:47:50Z | |
| dc.date.issued | 2023-08 | |
| dc.description | 501 pages | en_US |
| dc.description.abstract | This dissertation focuses on stochastic optimization and learning where the underlying probabilistic models are unknown and the decision maker optimizes their actions over time through sequential interactions with the unknown environment. The first part of this dissertation is on stochastic optimization where the learner aims at optimizing an unknown random loss function in expectation --- the fundamental building block of training any machine learning model today. In the centralized setting, we study three different classes of stochastic optimization problems, categorized based on the structural assumptions of the unknown function. For stochastic convex optimization, we propose the first extension of the coordinate minimization (CM) approach to stochastic optimization. The proposed approach provides a universal framework for extending low-dimensional optimization routines to high-dimensional problems and inherits the scalability and parallelizability properties of CM. For kernel-based optimization, we propose the first algorithm with order-optimal regret guarantees thereby closing the existing gap between upper and lower bounds. Thirdly, for neural net based optimization for contextual bandits, we explore the setting where neural nets are equipped with a smooth activation function, in contrast to the existing work which primarily focuses on ReLU neural nets. In the second part of this dissertation, we focus on challenges unique to distributed stochastic optimization. For the problem of distributed linear bandits, we investigate the regret-communication trade-off by establishing the information-theoretic lower bounds on the required communications (in terms of bits) for achieving a sublinear regret order. We also develop an efficient algorithm that is the first to achieve both order-optimal regret and optimal order of communication cost (in bits). We also extend our algorithm for stochastic convex optimization where it continues to enjoy order-optimal regret and communication performance. Secondly, we study the impact of statistical heterogeneity among clients in a distributed kernel-based bandit framework. We adopt a personalization approach to tackle the heterogeneity among users propose an algorithm that achieves order-optimal regret through a novel design that carefully balances personalized exploration with collaborative exploration. The third part of the dissertation focuses on problems arising in Active Learning and Active Hypothesis Testing. For the problem of online active learning for classifying streaming instances, we develop a disagreement-based learning algorithm for a general hypothesis space and noise model that incurs a bounded regret and has an order-optimal label complexity. We also study the problem of noisy group testing under unknown noise models, which is contrast to the existing studies that assume perfect knowledge of probabilistic model of the noise. We propose a novel algorithm that is agnostic to the noise distribution and offers a sample complexity that adapts to the noise level and is order-optimal in both the population size and the error rate. In the last chapter, we consider the problem of uniformity testing of Lipschitz continuous distributions with bounded support. We propose a sequential test that offers adaptivity to the unknown $\ell_1$ distance to the uniform distribution, allowing quicker identification of more anomalous (non-uniform) distributions. | en_US |
| dc.identifier.doi | https://doi.org/10.7298/a3gx-wr09 | |
| dc.identifier.other | Salgia_cornellgrad_0058F_13730 | |
| dc.identifier.other | http://dissertations.umi.com/cornellgrad:13730 | |
| dc.identifier.uri | https://hdl.handle.net/1813/114753 | |
| dc.language.iso | en | |
| dc.rights | Attribution 4.0 International | * |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | * |
| dc.subject | Adaptive | en_US |
| dc.subject | Bandits | en_US |
| dc.subject | Communication Efficient | en_US |
| dc.subject | Computationally Efficient | en_US |
| dc.subject | Machine Learning | en_US |
| dc.subject | Stochastic Optimization | en_US |
| dc.title | Stochastic Optimization and Learning: An Adaptive and Resource-Efficient Approach | en_US |
| dc.type | dissertation or thesis | en_US |
| dcterms.license | https://hdl.handle.net/1813/59810.2 | |
| thesis.degree.discipline | Electrical and Computer Engineering | |
| thesis.degree.grantor | Cornell University | |
| thesis.degree.level | Doctor of Philosophy | |
| thesis.degree.name | Ph. D., Electrical and Computer Engineering |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Salgia_cornellgrad_0058F_13730.pdf
- Size:
- 5.41 MB
- Format:
- Adobe Portable Document Format