We study the problem of global optimization, where we analyze the performance of the Piyavskii--Shubert algorithm and its variants. For any given time duration T, instead of the extensively studied simple regret (which is the difference of the losses between the best estimate up to T and the global minimum), we study the cumulative regret up to time T. For L-Lipschitz continuous functions, we show that the cumulative regret is O(L logT). For H-Lipschitz smooth functions, we show that the cumulative regret is O(H). We analytically extend our results for functions with Hölder continuous derivatives, which cover both the Lipschitz continuous and the Lipschitz smooth functions, individually. We further show that a simpler variant of the Piyavskii-Shubert algorithm performs just as well as the traditional variants for the Lipschitz continuous or the Lipschitz smooth functions. We further extend our results to broader classes of functions, and show that, our algorithm efficiently determines its queries; and achieves nearly minimax optimal (up to log factors) cumulative regret, for general convex or even concave regularity conditions on the extrema of the objective (which encompasses many preceding regularities). We consider further extensions by investigating the performance of the Piyavskii-Shubert variants in the scenarios with unknown regularity, noisy evaluation and multivariate domain.

Video streaming accounts for the most of the global Internet traffic and providing a high user Quality of Experience (QoE) is considered an essential target for mobile network operators (MNOs). QoE strongly depends on network Quality of Service (QoS) parameters. In this work, we use real-world network traces obtained from a major cellular operator in Turkey to establish a mapping from network side parameters to the user QoE. To this end, we use a model-aided deep learning method for first predicting channel path loss, and then, employ this prediction for predicting video streaming MOS. The experimental results demonstrate that the proposed model-aided deep learning model can guarantee higher prediction accuracy compared to predictions only relying on mathematical models. We also demonstrate that even though a trained model cannot be directly transferred from one geographical area to another, they significantly reduce the volume of required training when used for prediction in a new area.

In this article, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when scheduling problems can be represented by claw-free conflict graphs where we consider a wireless broadcast medium. It is possible to formulate a scheduling problem of broadcast transmissions as finding the maximum weighted independent set (MWIS) in the conflict graph of the network. Finding the MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. In a claw-free conflict graph, MWIS may be found in polynomial time leading to a throughput-optimal scheduling. We show that the conflict graphs of certain wireless ad hoc networks are claw-free. In order to obtain claw-free conflict graphs in general networks, we suggest introducing additional conflicts (edges) with the aim of keeping the decrease in MWIS size minimal. To this end, we introduce an iterative optimization problem to decide where to introduce edges and investigate its efficient implementation. We conclude that the claw breaking method by adding extra edges can perform very close to optimal scenario and better than the polynomial time maximal independent set scheduling benchmark under the necessary assumptions.

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data-driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithm based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (with respect to the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state of the art. Our experimental work extensively covers various scenarios ranging from bandit settings to multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability.