Back to search

Georgia Institute of Technology

Theory and Algorithms for Nonconvex Learning and Optimization

Abstract

dc:description.abstract

This dissertation contributes to the field of mathematical programming on three fronts by developing: (i) a mixed-integer programming framework for fair classification; (ii) distributionally fair stochastic programming methods based on a Wasserstein fairness measure; and (iii) second-order conic and polyhedral approximations of the exponential cone. Fair classification aims to mitigate systematic disparities across protected groups in predictive decision-making. Although many widely used group fairness measures are inherently discrete and nonconvex, existing approaches typically rely on convex surrogates that approximate rather than enforce fairness exactly. We propose a unified mixed-integer optimization framework that models group fairness measures exactly while jointly optimizing predictive accuracy and regularization. The framework applies to a broad class of classifiers, including support vector machines, logistic regression, deep neural networks, and multiclass models. For support vector machines, we derive an exact mixed-integer conic formulation and establish Fisher consistency. A key structural insight is that fairness enforcement admits an interpretation as unbiased subdata selection. Leveraging this structure, we prove that the subdata selection subproblem is strongly polynomially solvable and develop an iterative reselection strategy with convergence and approximation guarantees. Computational experiments demonstrate that exact fairness modeling yields competitive and often superior fairness–accuracy trade-offs relative to reduction-based and post-processing approaches. The results also demonstrate the scalability of mixed-integer optimization as a computational framework for fair machine learning. A traditional stochastic program defined over a finite population typically focuses on efficiency, for example, by maximizing expected profit or minimizing expected cost subject to a set of constraints. However, decisions derived from such efficiency-driven formulations can affect individuals differently. In particular, when evaluated through individual utility functions, these effects may vary substantially across demographic groups characterized by sensitive attributes such as gender, race, age, and socioeconomic status. As each group comprises multiple individuals, a common approach is to impose group fairness, which requires quantifying disparities between the distributions of utilities across groups. This thesis introduces Distributionally Fair Stochastic Optimization (DFSO) based on a Wasserstein fairness measure. DFSO seeks to reduce distributional disparities among groups, as measured by the Wasserstein distance, while maintaining an acceptable level of inefficiency. We show that despite the biconvex structure of DFSO, the epigraph of the Wasserstein fairness measure can generally be represented as mixed-integer convex program. In addition, we introduce two valid lower bounds for the Wasserstein fairness measure: the Jensen bound, which applies to the general case, and the Gelbrich bound, which is specific to the type-2 Wasserstein fairness measure. We prove the tightness of the Gelbrich bound and characterize the theoretical gap between the Wasserstein fairness measure and the Gelbrich bound. Finally, the theoretical properties of the Wasserstein fairness measure motivate us to develop efficient algorithms for solving DFSO problems. Numerical experiments demonstrate the effectiveness of these algorithms and confirm their practical applicability for achieving distributional fairness in a range of societally relevant real-world stochastic optimization problems. Exponential and logarithmic functions arise in a broad range of applications, including logistic regression, maximum likelihood estimation, and relative entropy optimization. Since the exponential cone represents the epigraph of the perspective of the exponential function (or equivalently, the hypograph of the perspective of the logarithmic function), many mixed-integer convex programs involving exponential or logarithmic terms can be reformulated as mixed-integer exponential conic programs (MIECPs). In contrast to the substantial algorithmic and modeling advances for mixed-integer linear programs (MILPs) and mixed-integer second-order cone programs (MISOCPs), effective solution methodologies for MIECPs remain relatively underdeveloped. To leverage the extensive computational infrastructure developed for MILPs and MISOCPs, we propose second-order conic (SOC) and polyhedral approximation schemes for the exponential cone and apply those schemes to the solution of MIECPs. We first extend and generalize existing SOC approximation techniques in an extended space, introduce new scaling and shifting strategies, establish explicit approximation error bounds, and derive computable lower bounds on the resulting relaxations. We then develop a polyhedral outer-approximation framework in the original variable space based on gradient inequalities, analyze its approximation accuracy, and provide corresponding lower bounds. For practical implementations, we propose a data-driven strategy for constructing SOC approximation patterns by calibrating them on small instances and transferring them to larger-scale problems. For the polyhedral scheme, we integrate the approximation within a branch-and-cut framework for MIECPs. Numerical experiments demonstrate that the proposed methods can yield substantial computational improvements over state-of-the-art exponential cone solvers, including MOSEK, and that the scaling, shifting, and polyhedral outer-approximation techniques significantly enhance solution efficiency.

Degree

thesis:*
Name thesis:degree_name
Operations Research, PhD
Department thesis:degree_department
Industrial and Systems Engineering
Grantor
Georgia Institute of Technology
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ye, Qing
Advisors dc:contributor.advisor
  • Alexopoulos, Christos
  • Xie, Weijun
Committee members dc:contributor.committeemember
  • Romeijn, Edwin
  • Goldsman, David

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/82229

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ye, Qing. Theory and Algorithms for Nonconvex Learning and Optimization. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82229