The paper is very interesting as it provides the first known lower bounds for the minimax rate of estimation of the MMD distance between two distributions based on finite random samples, considering general radial kernels, which match with the known upper bounds up to constants. Theses bounds lead to a classical parametric rate of estimation, not depending on the dimension of the data. The text could however be more fluent, and easier to read for nonspecialists of the minimax estimation theory. For instance, the results are all expressed with respect to the minimax probabilities. Could the link with the more classical minimax risk be clearly written?

The paper solves an open problem presented at COLT 2015 [Koolen et. It defines OSCO problems as online combinatorial optimization problems in sleeping setting in which in each trial a subset of actions become unavailable due to unavailability of a subset of elements. Basically, the paper shows that OSCO problems are as hard as PAC-Learning of DNF expressions -- which is a long standing open problem. In a nutshell, the hardness result is shown as follows: the paper reduces the problem of "Online Agnostic Learnign of Disjuction" into "Hard Instances" of OSCO problems with per-action regret via a proof that has similarities to a proof in [Kanade and Steinke, 2014]. Interestingly enough, because of the online-to-batch conversion argument in [Kanade and Steinke, 2014], the hardness results seem to be also true for a benign form of adversary namely stochastic availabilities and loss (i.e. they are drawn from an unknown but fixed joint distribution). After proving the general hardness results, the paper provides "Hard Instances" of various well-known OSCO problems to establish their hardness in particularv -- including Online Sabotaged Shortest Path.

This paper includes several results regarding the problem of function denoising over a grid of dimension 1. In particular, demonstrating that simple linear methods are not sufficient for denoising functions of bounded variation and that TV denoisers are minimax optimal (up to a log factor). Overall, I feel these are solid contributions which should be of interest to the mathematical statistics, machine learning and signal processing communities. My main criticism is that the simulations shown in Figure 3 of the main text and Figure 1 of the supplementary use rather artificial signals. The paper would be much stronger if simulations on real data sets would be performed (such as 2D images, 3D volumetric scans, etc.) and see real-world performance of TV denoising vs. Laplacian smoothing and Laplacian eigenmaps.

Major comments -------------- * An obvious major issue with this paper is the lack of experiments. How does the algorithm compare to gradient-based local search algorithms? I would be curious to see if it works better on i) Gaussian distributed data and ii) real data. Even if the results turn out to be similar, perhaps the authors can find some advantages to their algorithm such as, e.g., robustness to initialization. Recent works [1, 2] have called this variant "polynomial network" so the authors might want to use this name instead of "factorization machine".

The paper is well written and clearly organized, especially where it motivates the problem and the goals of the paper. It is a novel point of view to aim to find all feature subsets for which a statistical association test rejects the null hypothesis, and thus allowing to correct for a confounding categorical covariate. The authors results in the scope of the paper demonstrates that FACS keeps the computational efficiency, statistical power and the ability to correct for multiple hypothesis testing of existing method. The introduction of the branch-and-bound algorithm for conditional statistical association tests is novel and well-explained. Along with the results, the authors provide good intuition behind the methods and the key aspects, such as the appropriate testability criterion for the CMH test and the pruning criterion for the CMH test.

Monte-Carlo Tree Search (MCTS) methods, such as Upper Confidence Bound applied to Trees (UCT), are instrumental to automated planning techniques. However, UCT can be slow to explore an optimal action when it initially appears inferior to other actions. Maximum ENtropy Tree-Search (MENTS) incorporates the maximum entropy principle into an MCTS approach, utilising Boltzmann policies to sample actions, naturally encouraging more exploration. In this paper, we highlight a major limitation of MENTS: optimal actions for the maximum entropy objective do not necessarily correspond to optimal actions for the original objective. We introduce two algorithms, Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS), that address these limitations and preserve the benefits of Boltzmann policies, such as allowing actions to be sampled faster by using the Alias method. Our empirical analysis shows that our algorithms show consistent high performance across several benchmark domains, including the game of Go.

Despite the success of neural-based combinatorial optimization methods for end-to-end heuristic learning, out-of-distribution generalization remains a challenge. In this paper, we present a novel formulation of Combinatorial Optimization Problems (COPs) as Markov Decision Processes (MDPs) that effectively leverages common symmetries of COPs to improve out-of-distribution robustness. Starting from a direct MDP formulation of a constructive method, we introduce a generic way to reduce the state space, based on Bisimulation Quotienting (BQ) in MDPs. Then, for COPs with a recursive nature, we specialize the bisimulation and show how the reduced state exploits the symmetries of these problems and facilitates MDP solving. Our approach is principled and we prove that an optimal policy for the proposed BQ-MDP actually solves the associated COPs.

In clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. We propose a new initialization scheme for the k -median problem in the general metric space (e.g., discrete space induced by graphs), based on the construction of metric embedding tree structure of the data. We propose a novel and efficient search algorithm, for good initial centers that can be used subsequently for the local search algorithm. The so-called HST initialization method can produce initial centers achieving lower error than those from another popular method k -median, also with higher efficiency when k is not too small. Our HST initialization can also be easily extended to the setting of differential privacy (DP) to generate private initial centers.

Knowledge distillation (KD) has emerged as an effective technique for compressing models that can enhance the lightweight model. Conventional KD methods propose various designs to allow student model to imitate the teacher better. However, these handcrafted KD designs heavily rely on expert knowledge and may be sub-optimal for various teacher-student pairs. In this paper, we present a novel framework, KD-Zero, which utilizes evolutionary search to automatically discover promising distiller from scratch for any teacher-student architectures. Then, we construct our distiller search space by selecting advanced operations for these three components.

This work introduces JPS4, a novel pathfinding algorithm for 4-connected grid maps. JPS4 builds upon the Jump Point Search (JPS8) algorithm, originally designed for 8-connected environments. To achieve efficient pathfinding on 4-connected grids, JPS4 employs a canonical ordering and a successor function that enable online graph pruning. This reduces the search space by minimizing unnecessary node expansions. The core concept of JPS4 as well as JPS8 lies in the utilization of jump points. Strategically placed at obstacle corners, jump points prevent the search from overlooking crucial sections of the state space. They essentially reinitialize the canonical ordering, allowing exploration beyond obstacles. This mechanism ensures JPS4 finds optimal paths even in complex environments. The paper further explores the optimality of JPS4 and compares its performance against the established A* algorithm on various grid maps. Benchmarking results demonstrate that JPS4 significantly outperforms A* in scenarios with high obstacle density. However, A* remains more efficient on open maps. Overall, JPS4 presents itself as a promising alternative to A* for pathfinding on 4-connected grids, particularly applicable in video game development.