61 citations · 152 across the 22 of their papers we have counts for
26 papers
Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities
Lingqing Shen, Fatma Kılınç-Karzan
Monotone variational inequalities (VIs) provide a unifying framework for convex minimization, equilibrium computation, and convex-concave saddle-point problems. Extragradient-type…
Efficient Online Large-Margin Classification via Dual Certificates
Nam Ho-Nguyen, Fatma Kılınç-Karzan, Ellie Nguyen +1
Online classification is a central problem in optimization, statistical learning and data science. Classical algorithms such as the perceptron offer efficient updates and finite mi…
Mistake, Manipulation and Margin Guarantees in Online Strategic Classification
Lingqing Shen, Nam Ho-Nguyen, Khanh-Hung Giang-Tran +1
We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label, while incurring a co…
On semidefinite descriptions for convex hulls of quadratic programs
Alex L. Wang, Fatma Kilinc-Karzan
Quadratically constrained quadratic programs (QCQPs) are a highly expressive class of nonconvex optimization problems. While QCQPs are NP-hard in general, they admit a natural conv…
Constrained Optimization of Rank-One Functions with Indicator Variables
Soroosh Shafiee, Fatma Kılınç-Karzan
Optimization problems involving minimization of a rank-one convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine…
Accelerated first-order methods for a class of semidefinite programs
Alex L. Wang, Fatma Kilinc-Karzan
This paper introduces a new storage-optimal first-order method (FOM), CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that…
Implicit regularity and linear convergence rates for the generalized trust-region subproblem
Alex L. Wang, Yunlei Lu, Fatma Kilinc-Karzan
In this paper we develop efficient first-order algorithms for the generalized trust-region subproblem (GTRS), which has applications in signal processing, compressed sensing, and e…
Risk Guarantees for End-to-End Prediction and Optimization Processes
Nam Ho-Nguyen, Fatma Kılınç-Karzan
Prediction models are often employed in estimating parameters of optimization models. Despite the fact that in an end-to-end view, the real goal is to achieve good optimization per…
A Geometric View of SDP Exactness in QCQPs and its Applications
Alex L. Wang, Fatma Kilinc-Karzan
Quadratically constrained quadratic programs (QCQPs) are a highly expressive class of nonconvex optimization problems. While QCQPs are NP-hard in general, they admit a natural conv…
Rebounding Bandits for Modeling Satiation Effects
Liu Leqi, Fatma Kilinc-Karzan, Zachary C. Lipton +1
Psychological research shows that enjoyment of many goods is subject to satiation, with short-term satisfaction declining after repeated exposures to the same item. Nevertheless, p…
Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences
Violet Xinying Chen, Fatma Kılınç-Karzan
We study the problem of online learning (OL) from revealed preferences: a learner wishes to learn a non-strategic agent's private utility function through observing the agent's uti…
Necessary and sufficient conditions for rank-one generated cones
C. J. Argue, Fatma Kılınç-Karzan, Alex L. Wang
A closed convex conic subset of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The RO…
Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty under Wasserstein Ambiguity
Nam Ho-Nguyen, Fatma Kılınç-Karzan, Simge Küçükyavuz +1
Distributionally robust chance-constrained programs (DR-CCP) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big--based mixed-integer prog…
Distributionally Robust Chance-Constrained Programs with Right-Hand Side Uncertainty under Wasserstein Ambiguity
Nam Ho-Nguyen, Fatma Kılınç-Karzan, Simge Küçükyavuz +1
We consider exact deterministic mixed-integer programming (MIP) reformulations of distributionally robust chance-constrained programs (DR-CCP) with random right-hand sides over Was…
On convex hulls of epigraphs of QCQPs
Alex L. Wang, Fatma Kilinc-Karzan
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditi…
On the tightness of SDP relaxations of QCQPs
Alex L. Wang, Fatma Kilinc-Karzan
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under w…
Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
Fatma Kılınç-Karzan, Simge Küçükyavuz, Dabeen Lee
A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets w…
The Generalized Trust Region Subproblem: solution complexity and convex hull results
Alex L. Wang, Fatma Kilinc-Karzan
We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts th…
Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization
Nam Ho-Nguyen, Fatma Kilinc-Karzan
In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We…
Dynamic Data-Driven Estimation of Non-Parametric Choice Models
Nam Ho-Nguyen, Fatma Kilinc-Karzan
We study non-parametric estimation of choice models, which were introduced to alleviate unreasonable assumptions in traditional parametric models, and are prevalent in several appl…
Theoretical and Practical Advances on Smoothing for Extensive-Form Games
Christian Kroer, Kevin Waugh, Fatma Kilinc-Karzan +1
Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergen…
Online First-Order Framework for Robust Convex Optimization
Nam Ho-Nguyen, Fatma Kilinc-Karzan
Robust optimization (RO) has emerged as one of the leading paradigms to efficiently model parameter uncertainty. The recent connections between RO and problems in statistics and ma…
A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants
Nam Ho-Nguyen, Fatma Kilinc-Karzan
We study the trust-region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective,…
How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic
Sam Burer, Fatma Kilinc-Karzan
A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown---by sever…