DLDabeen Lee

Dabeen Lee

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Dabeen Lee has a total of 34 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Neural Logistic Bandits

    by Seoungbin Bae, Dabeen Lee

    We study the problem of neural logistic bandits, where the main task is to learn an unknown reward function within a logistic link function using a neural network. Existing approaches either exhibit unfavorable dependencies on $κ$, where $1/κ$ represents the minimum variance of reward distributions, or suffer from direct dependence on the feature dimension $d$, which can be huge in neural network-based settings. In this work, we introduce a novel Bernstein-type inequality for self-normalized vector-valued martingales that is designed to bypass a direct dependence on the ambient dimension. This lets us deduce a regret upper bound that grows with the effective dimension $\widetilde{d}$, not the feature dimension, while keeping a minimal dependence on $κ$. Based on the concentration inequality, we propose two algorithms, NeuralLog-UCB-1 and NeuralLog-UCB-2, that guarantee regret upper bounds of order $\widetilde{O}(\widetilde{d}\sqrt{κT})$ and $\widetilde{O}(\widetilde{d}\sqrt{T/κ})$, respectively, improving on the existing results. Lastly, we report numerical results on both synthetic and real datasets to validate our theoretical findings.

  • Technical Note—Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

    by Fatma Kılınç-Karzan, Simge Küçükyavuz, Dabeen Lee, Soroosh Shafieezadeh-Abadeh

    A Unifying Framework for the Convexification of Mixed-Integer Conic Binary Sets The paper “Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications,” by Fatma Kilinc-Karzan, Simge Kucukyavuz, Dabeen Lee, and Soroosh Shafieezadeh-Abadeh, develops a unifying framework for convexifying mixed-integer conic binary sets. Many applications in machine-learning and operations research give rise to integer programming models with nonlinear structures and binary variables. The paper develops general methods for generating strong valid inequalities that take into account multiple conic constraints at the same time. The authors demonstrate that their framework applies to conic quadratic programming with binary variables, fractional programming, best subset selection, distributionally robust optimization, and sparse approximation of positive semidefinite matrices.


  • Open Access

    From coordinate subspaces over finite fields to ideal multipartite uniform clutters

    by Ahmad Abdi, Dabeen Lee

    Take a prime power q, an integer $$n\ge 2$$ n ≥ 2 , and a coordinate subspace $$S\subseteq GF(q)^n$$ S ⊆ G F ( q ) n over the Galois field GF(q). One can associate with S an n-partite n-uniform clutter $$\mathcal {C}$$ C , where every part has size q and there is a bijection between the vectors in S and the members of $$\mathcal {C}$$ C . In this paper, we determine when the clutter $$\mathcal {C}$$ C is ideal, a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly, the characterization differs depending on whether q is 2, 4, a higher power of 2, or otherwise. Each characterization uses crucially that idealness is a minor-closed property: first the list of excluded minors is identified, and only then is the global structure determined. A key insight is that idealness of $$\mathcal {C}$$ C depends solely on the underlying matroid of S. Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence, we prove the Replication and $$\tau =2$$ τ = 2 Conjectures for this class of clutters.

  • Open Access

    A projection-free method for solving convex bilevel optimization problems

    by Khanh-Hung Giang-Tran, Nam Ho-Nguyen, Dabeen Lee

    When faced with multiple minima of an inner-level convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary outer-level convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free conditional gradient method for convex bilevel optimization which requires only a linear optimization oracle over the base domain. We establish $$O(t^{-1/2})$$ O ( t - 1 / 2 ) convergence rate guarantees for our method in terms of both inner- and outer-level objectives, and demonstrate how additional assumptions such as quadratic growth and strong convexity result in accelerated rates of up to $$O(t^{-1})$$ O ( t - 1 ) and $$O(t^{-2/3})$$ O ( t - 2 / 3 ) for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.


  • Open Access

    Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span

    by Woojin Chae, Kihyuk Hong, Yufan Zhang, Ambuj Tewari, Dabeen Lee

    This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) under the Bellman optimality condition. Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of $\widetilde{\mathcal{O}}(d\sqrt{\mathrm{sp}(v^*)T})$ over $T$ time steps where $\mathrm{sp}(v^*)$ is the span of the optimal bias function $v^*$ and $d$ is the dimension of the feature mapping. Our algorithm applies the recently developed technique of running value iteration on a discounted-reward MDP approximation with clipping by the span. We prove that the value iteration procedure, even with the clipping operation, converges. Moreover, we show that the associated variance term due to random transitions can be bounded even under clipping. Combined with the weighted ridge regression-based parameter estimation scheme, this leads to the nearly minimax optimal regret guarantee.

  • Open Access

    Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism

    by Kihyun Yu, Duksang Lee, William Overman, Dabeen Lee

    This paper studies the safe reinforcement learning problem formulated as an episodic finite-horizon tabular constrained Markov decision process with an unknown transition kernel and stochastic reward and cost functions. We propose a model-based algorithm based on novel cost and reward function estimators that provide tighter cost pessimism and reward optimism. While guaranteeing no constraint violation in every episode, our algorithm achieves a regret upper bound of $\widetilde{\mathcal{O}}((\bar C - \bar C_b)^{-1}H^{2.5} S\sqrt{AK})$ where $\bar C$ is the cost budget for an episode, $\bar C_b$ is the expected cost under a safe baseline policy over an episode, $H$ is the horizon, and $S$, $A$ and $K$ are the number of states, actions, and episodes, respectively. This improves upon the best-known regret upper bound, and when $\bar C- \bar C_b=Ω(H)$, it nearly matches the regret lower bound of $Ω(H^{1.5}\sqrt{SAK})$. We deduce our cost and reward function estimators via a Bellman-type law of total variance to obtain tight bounds on the expected sum of the variances of value function estimates. This leads to a tighter dependence on the horizon in the function estimators. We also present numerical results to demonstrate the computational effectiveness of our proposed framework.

  • Open Access

    Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions

    by Sungwoo Park, Junyeop Kwon, Byeongnoh Kim, Suhyun Chae, Jeeyong Lee, Dabeen Lee

    This paper studies performative risk minimization, a formulation of stochastic optimization under decision-dependent distributions. We consider the general case where the performative risk can be non-convex, for which we develop efficient parameter-free optimistic optimization-based methods. Our algorithms significantly improve upon the existing Lipschitz bandit-based method in many aspects. In particular, our framework does not require knowledge about the sensitivity parameter of the distribution map and the Lipshitz constant of the loss function. This makes our framework practically favorable, together with the efficient optimistic optimization-based tree-search mechanism. We provide experimental results that demonstrate the numerical superiority of our algorithms over the existing method and other black-box optimistic optimization methods.

  • Open Access

    Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

    by Fatma Kılınç-Karzan, Simge Küçükyavuz, Dabeen Lee, Soroosh Shafieezadeh-Abadeh

    We consider a general conic mixed-binary set where each homogeneous conic constraint $j$ involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, $f_j$, of common binary variables. Sets of this form naturally arise as substructures in a number of applications including mean-risk optimization, chance-constrained problems, portfolio optimization, lot-sizing and scheduling, fractional programming, variants of the best subset selection problem, a class of sparse semidefinite programs, and distributionally robust chance-constrained programs. We give a convex hull description of this set that relies on simultaneous characterization of the epigraphs of $f_j$'s, which is easy to do when all functions $f_j$'s are submodular. Our result unifies and generalizes an existing result in two important directions. First, it considers \emph{multiple general convex cone} constraints instead of a single second-order cone type constraint. Second, it takes \emph{arbitrary nonnegative functions} instead of a specific submodular function obtained from the square root of an affine function. We close by demonstrating the applicability of our results in the context of a number of problem classes.

  • Open Access

    Stochastic-Constrained Stochastic Optimization with Markovian Data

    by Yeongjong Kim, Dabeen Lee

    This paper considers stochastic-constrained stochastic optimization where the stochastic constraint is to satisfy that the expectation of a random function is below a certain threshold. In particular, we study the setting where data samples are drawn from a Markov chain and thus are not independent and identically distributed. We generalize the drift-plus-penalty framework, a primal-dual stochastic gradient method developed for the i.i.d. case, to the Markov chain sampling setting. We propose two variants of drift-plus-penalty; one is for the case when the mixing time of the underlying Markov chain is known while the other is for the case of unknown mixing time. In fact, our algorithms apply to a more general setting of constrained online convex optimization where the sequence of constraint functions follows a Markov chain. Both algorithms are adaptive in that the first works without knowledge of the time horizon while the second uses AdaGrad-style algorithm parameters, which is of independent interest. We demonstrate the effectiveness of our proposed methods through numerical experiments on classification with fairness constraints.

  • Open Access

    Online Resource Allocation in Episodic Markov Decision Processes

    by Duksang Lee, William Overman, Dabeen Lee

    This paper studies a long-term resource allocation problem over multiple periods where each period requires a multi-stage decision-making process. We formulate the problem as an online allocation problem in an episodic finite-horizon constrained Markov decision process with an unknown non-stationary transition function and stochastic non-stationary reward and resource consumption functions. We propose the observe-then-decide regime and improve the existing decide-then-observe regime, while the two settings differ in how the observations and feedback about the reward and resource consumption functions are given to the decision-maker. We develop an online dual mirror descent algorithm that achieves near-optimal regret bounds for both settings. For the observe-then-decide regime, we prove that the expected regret against the dynamic clairvoyant optimal policy is bounded by $\tilde O(ρ^{-1}{H^{3/2}}S\sqrt{AT})$ where $ρ\in(0,1)$ is the budget parameter, $H$ is the length of the horizon, $S$ and $A$ are the numbers of states and actions, and $T$ is the number of episodes. For the decide-then-observe regime, we show that the regret against the static optimal policy that has access to the mean reward and mean resource consumption functions is bounded by $\tilde O(ρ^{-1}{H^{3/2}}S\sqrt{AT})$ with high probability. We test the numerical efficiency of our method for a variant of the resource-constrained inventory management problem.