This paper shows that Nesterov's accelerated gradient descent algorithms can be interpreted as computing a saddle point via online optimization algorithms. A convex optimization problem is transformed to be a minmax problem by the Fenchel dual, the solution of which is then approximated via online optimization algorithms. This paper can be a significant contribution to the optimization community. I would say that this is one of the most natural interpretations of Nesterov's accelerated gradient methods. The use of weighted regrets and (optimistic) FollowTheLeader (instead of follow the regularized leader) are a little bit artificial but acceptable.

Thank you for the thoughtful response. I have read the other reviews and the rebuttal, and after discussing the work I am electing to keep my score the same. I am somewhat unsatisfied by the author response; for papers where gradient estimator efficiency (in terms of variance) is in service of the optimization problem, comparing ELBO traces by iteration can be very misleading. If the machinery you introduce to efficiently use an ensemble of control variates is not very costly, then it should be measured or shown in your experiments. My comments below weren't about optimal tuning, they were more about exploring/understanding the sensitivity of their method on the parameters they introduce.

It provides problem-related (asymptotic) lower and upper bounds on the regret, the latter for an algorithm presented in the paper that builds on Burnetas and Katehakis (1997) and a recent bandit paper by Combes et al (NIPS 2017). The setting assumes that an "MDP structure" \Phi (i.e. a set of possible MDP models) is given. The regret bounds (after T steps) are shown to be of the form K_Phi*log T, where the parameter K_\Phi is the solution to a particular optimization problem. It is shown that if \Phi is the set of all MDPs ("the unstructured case") then K_\Phi is bounded by HSA/\delta, where H is the bias span and \delta the minimal action sub-optimality gap. The second particular class that is considered is the Lipschitz structure that considers embeddings of finite MDPs in Euclidian space such that transition probabilities and rewards are Lipschitz. In this case, the regret bounds are shown to not to depend on the size of state and action space anymore.

This paper seems a continuation of last year: Bayesian optimization with a finite budget... where the authors have added new elements to deal with inequality constraints. The method uses a approximation of a lookahead strategy by dynamic programming. For the constrained case, the authors propose an heuristic that combines the EIc criterion for all the steps except for the last one were the mean function is used. The authors claim that the mean function has an exploitative behaviour, although it has been previously shown that it might be misleading [A]. A considerably amount of the text, including Figure 1, can be mostly found in [16]. Although it is nice to have an self-contained paper as much as possible, that space could be used to explain better the selection of the acquisition heuristic and present alternatives.

This paper presents a sharp asymptotic analysis of the regularized phase-max estimator for structured phase retrieval (PR) problems. The phase-max algorithm is a recently proposed Linear Programming based estimator for PR. The finite sample as well as the sharp asymptotic performance of phase-max for unstructured phase retrieval was well understood from prior work. The authors propose a natural modification by penalizing the usual phase-max objective with a regularizer f . For structured PR, prior work showed that for a k -sparse signal vector, L1-penalized phase-max recovers the signal with m O(klog(n/k)) samples given a good enough initialization.

The aim of this paper is to extend results in online combinatorial optimization to new combinatorial objects such as k -multipaths and binary search trees. Specifically, the authors are interested in extending Expanded-Hedge (EH) and Component Hedge (CH) to online combinatorial games, for which the offline problem can be solved in a bottom-up way using Dynamic Programming. Though the results about online optimization with k -multipaths are interesting, the overall paper could benefit from more polishing: some definitions and notations are not clearly defined, and some assertions look incorrect. Namely: In Section 4, the set (of subsets) \mathcal H_v is not clearly defined, so it is very difficult for the reader to capture the family of DP tasks defined according to the recurrence relation (3). In this section, some concrete examples of online optimization problems characterized by this DP family would be helpful.

This paper proposes a new method for the clustering of persistence diagrams using recent techniques in optimal transport. The problem is quite important; clustering provides a sensible way to group data according to their topological characterizations. It is also very challenging due to the Wasserstein distance between the persistence diagrams. This paper proposes to (1) approximate the Wasserstein distance between diagrams using the regularized optimal transport, and (2) treat the computation of the Frechet means as another optimal transport problem, and find the optimal solution using gradient descent. Several major technical challenges are addressed, include: 1) the Wasserstein distance may involve matching points with the a diagonal line. The proposed method is compared with the state-of-the-art (Hera) and is shown to be more efficient.

This paper proposes safe active learning algorithm for learning time-series models with piecewise trajectory sections. The basic model for the trajectory section is Gaussian Process, and the safety criterion is modeled as probability of certain safe value, which is modeled as a continuous function of inputs, being in the right region is greater than some threshold. The active learner explores the input space by generating trajectories that maximizes certain criterion in system identification. The paper also provides theoretical analysis in the safety perspective, as well as in the predictive variance reduction perspective. In the evaluation, besides simulated examples on predefined continuous functions and low dimensional models, this paper provides a specific use case for learning surrogate model of the high-pressure fluid system.

In Reinforcement Learning (RL), multi-armed Bandit (MAB) problems have found applications across diverse domains such as recommender systems, healthcare, and finance. Traditional MAB algorithms typically assume stationary reward distributions, which limits their effectiveness in real-world scenarios characterized by non-stationary dynamics. This paper addresses this limitation by introducing and evaluating novel Bandit algorithms designed for non-stationary environments. First, we present the Adaptive Discounted Thompson Sampling (ADTS) algorithm, which enhances adaptability through relaxed discounting and sliding window mechanisms to better respond to changes in reward distributions. We then extend this approach to the Portfolio Optimization problem by introducing the Combinatorial Adaptive Discounted Thompson Sampling (CADTS) algorithm, which addresses computational challenges within Combinatorial Bandits and improves dynamic asset allocation. Additionally, we propose a novel architecture called Bandit Networks, which integrates the outputs of ADTS and CADTS, thereby mitigating computational limitations in stock selection. Through extensive experiments using real financial market data, we demonstrate the potential of these algorithms and architectures in adapting to dynamic environments and optimizing decision-making processes. For instance, the proposed bandit network instances present superior performance when compared to classic portfolio optimization approaches, such as capital asset pricing model, equal weights, risk parity, and Markovitz, with the best network presenting an out-of-sample Sharpe Ratio 20% higher than the best performing classical model.

Batched Bayesian optimization (BO) can accelerate molecular design by efficiently identifying top-performing compounds from a large chemical library. Existing acquisition strategies for batch design in BO aim to balance exploration and exploitation. This often involves optimizing non-additive batch acquisition functions, necessitating approximation via myopic construction and/or diversity heuristics. In this work, we propose an acquisition strategy for discrete optimization that is motivated by pure exploitation, qPO (multipoint Probability of Optimality). qPO maximizes the probability that the batch includes the true optimum, which is expressible as the sum over individual acquisition scores and thereby circumvents the combinatorial challenge of optimizing a batch acquisition function. We differentiate the proposed strategy from parallel Thompson sampling and discuss how it implicitly captures diversity. Finally, we apply our method to the model-guided exploration of large chemical libraries and provide empirical evidence that it performs better than or on par with state-of-the-art methods in batched Bayesian optimization.