Serdar Kadioglu

TMLR Journal 2022 Journal Article

Non-Deterministic Behavior of Thompson Sampling with Linear Payoffs and How to Avoid It

• Doruk Kilitcioglu
• Serdar Kadioglu

Thompson Sampling with Linear Payoffs (LinTS) is popular contextual bandit algorithm for solving sequential decision making problem. While LinTS has been studied extensively in the academic literature, surprisingly, its behavior in terms of reproducibility did not receive the same attention. In this paper, we show that a standard and seemingly correct LinTS implementation leads to non-deterministic behavior. This might go unnoticed easily, yet impact results adversely. This calls the reproducibility of papers that use LinTS into question. Further, it forbids using this particular implementation in any industrial application where reproducibility is critical not only for debugging purposes but also for the trustworthiness of machine learning models. We first study the root cause of the non-deterministic behavior. We then conduct experiments on recommendation system benchmarks to demonstrate the impact of non-deterministic behavior in terms of reproducibility and downstream metrics. Finally, as a remedy, we show how to avoid the issue to ensure reproducible results and share general advice for practitioners.

AAAI Conference 2014 Conference Paper

Parallel Restarted Search

• Andre Cire
• Serdar Kadioglu
• Meinolf Sellmann

We consider the problem of parallelizing restarted backtrack search. With few notable exceptions, most commercial and academic constraint programming solvers do not learn no-goods during search. Depending on the branching heuristics used, this means that there are little to no side-effects between restarts, making them an excellent target for parallelization. We develop a simple technique for parallelizing restarted search deterministically and demonstrate experimentally that we can achieve near-linear speed-ups in practice.

AAAI Conference 2012 Conference Paper

Non-Model-Based Search Guidance for Set Partitioning Problems

• Serdar Kadioglu
• Yuri Malitsky
• Meinolf Sellmann

ECAI Conference 2010 Conference Paper

ISAC - Instance-Specific Algorithm Configuration

• Serdar Kadioglu
• Yuri Malitsky
• Meinolf Sellmann
• Kevin Tierney

We present a new method for instance-specific algorithm configuration (ISAC). It is based on the integration of the algorithm configuration system GGA and the recently proposed stochastic offline programming paradigm. ISAC is provided a solver with categorical, ordinal, and/or continuous parameters, a training benchmark set of input instances for that solver, and an algorithm that computes a feature vector that characterizes any given instance. ISAC then provides high quality parameter settings for any new input instance. Experiments on a variety of different constrained optimization and constraint satisfaction solvers show that automatic algorithm configuration vastly outperforms manual tuning. Moreover, we show that instance-specific tuning frequently leads to significant speed-ups over instance-oblivious configurations.

AAAI Conference 2008 Conference Paper

Efficient Context-Free Grammar Constraints

• Serdar Kadioglu

With the introduction of constraints based on finite automata a new line of research has opened where constraints are based on formal languages. Recently, constraints based on grammars higher up in the Chomsky hierarchy were introduced. We devise a time- and space-efficient incremental arc-consistency algorithm for context-free grammars. Particularly, we show how to filter a sequence of monotonically tightening problems in cubic time and quadratic space. Experiments on a scheduling problem show orders of magnitude improvements in time and space consumption.