From coordinate subspaces over finite fields to ideal multipartite uniform clutters
Ahmad Abdi, Dabeen Lee
IF 2.5
Mathematical Programming
Abstract Take a prime power q , an integer $$n\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , and a coordinate subspace $$S\subseteq GF(q)^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>G</mml:mi> <mml:mi>F</mml:mi> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> over the Galois field GF ( q ). One can associate with S an n -partite n -uniform clutter $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> , where every part has size q and there is a bijection between the vectors in S and the members of $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> . In this paper, we determine when the clutter $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>τ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> Conjectures for this class of clutters.
A projection-free method for solving convex bilevel optimization problems
Khanh-Hung Giang-Tran, Nam Ho-Nguyen, Dabeen Lee
IF 2.5
Mathematical Programming
Abstract 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(t^{-2/3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.
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.
From coordinate subspaces over finite fields to ideal multipartite uniform clutters
Ahmad Abdi, Dabeen Lee
IF 2.5
Mathematical Programming
Abstract Take a prime power q , an integer $$n\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , and a coordinate subspace $$S\subseteq GF(q)^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>G</mml:mi> <mml:mi>F</mml:mi> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> over the Galois field GF ( q ). One can associate with S an n -partite n -uniform clutter $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> , where every part has size q and there is a bijection between the vectors in S and the members of $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> . In this paper, we determine when the clutter $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>τ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> Conjectures for this class of clutters.
A projection-free method for solving convex bilevel optimization problems
Khanh-Hung Giang-Tran, Nam Ho-Nguyen, Dabeen Lee
IF 2.5
Mathematical Programming
Abstract 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(t^{-2/3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.
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.
Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions
Sungwoo Park, Junyeop Kwon, B.H. Kim, Suhyun Chae, Jeeyong Lee, Dabeen Lee
arXiv (Cornell University)
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.
Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback
Yeongjong Kim, Dabeen Lee
arXiv (Cornell University)
This paper studies online convex optimization with stochastic constraints. We propose a variant of the drift-plus-penalty algorithm that guarantees $O(\sqrt{T})$ expected regret and zero constraint violation, after a fixed number of iterations, which improves the vanilla drift-plus-penalty method with $O(\sqrt{T})$ constraint violation. Our algorithm is oblivious to the length of the time horizon $T$, in contrast to the vanilla drift-plus-penalty method. This is based on our novel drift lemma that provides time-varying bounds on the virtual queue drift and, as a result, leads to time-varying bounds on the expected virtual queue length. Moreover, we extend our framework to stochastic-constrained online convex optimization under two-point bandit feedback. We show that by adapting our algorithmic framework to the bandit feedback setting, we may still achieve $O(\sqrt{T})$ expected regret and zero constraint violation, improving upon the previous work for the case of identical constraint functions. Numerical results demonstrate our theoretical results.
From coordinate subspaces over finite fields to ideal multipartite uniform clutters
Ahmad Abdi, Dabeen Lee
arXiv (Cornell University)
Take a prime power $q$, an integer $n\geq 2$, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper, we determine when the clutter $\mathcal{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}$ 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 $τ=2$ Conjectures for this class of clutters.
Test Score Algorithms for Budgeted Stochastic Utility Maximization
Dabeen Lee, Milan Vojnović, Se-Young Yun
INFORMS Journal on Optimization
Motivated by recent developments in designing algorithms based on individual item scores for solving utility maximization problems, we study the framework of using test scores, defined as a statistic of observed individual item performance data, for solving the budgeted stochastic utility maximization problem. We extend an existing scoring mechanism, namely, the replication test scores, to incorporate heterogeneous item costs as well as item values. We show that a natural greedy algorithm that selects items solely based on their replication test scores outputs solutions within a constant factor of the optimum for the class of functions satisfying an extended diminishing returns property. Our algorithms and approximation guarantees assume that test scores are noisy estimates of certain expected values with respect to marginal distributions of individual item values, thus making our algorithms practical and extending previous work that assumes noiseless estimates. Moreover, we show how our algorithm can be adapted to the setting in which items arrive in a streaming fashion while maintaining the same approximation guarantee. We present numerical results, using synthetic data and data sets from the Academia.StackExchange Q&A forum, which show that our test score algorithm can achieve competitiveness and in some cases better performance than a benchmark algorithm that requires access to a value oracle to evaluate function values. Funding: This research was supported, in part, by the Institute for Basic Science [Grants IBS-R029-C1, IBS-R029-Y2].
