Back to search

Cornell University

Stochastic Optimization and Learning: An Adaptive and Resource-Efficient Approach

Abstract

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 \ell1 distance to the uniform distribution, allowing quicker identification of more anomalous (non-uniform) distributions.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Electrical and Computer Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Salgia, Sudeep
Chair dc:contributor.chair
  • Zhao, Qing
Committee members dc:contributor.committeemember
  • Wegkamp, Marten
  • Acharya, Jayadev
  • Krishnamurthy, Vikram

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16219448
Dc Identifier Other
ProQuest Submission ID: 13730
ProQuest Publication ID: 30528911

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Salgia, Sudeep. Stochastic Optimization and Learning: An Adaptive and Resource-Efficient Approach. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114753