In this setting our objective is to provide low regret with respect to the sequence of losses as well as with respect to the constraints. This setting is useful when one would like to avoid projections which might be costly. Previous works focused on the regret with the respect to the cumulative constraints, where constraint violation may be compensated by constrained satisfaction. In this work the authors consider a more appropriate measure of regret which accounts only for constraints violation. In this case, the authors come up with a new algorithm (similar in spirit to previous approaches), which provides regret guarantees with respect to the sum of squared constrained violations. They also extend their approach to the strongly convex setting.

The paper considers online convex optimization with constraints revealed in an online manner. In an attempt to circumvent a linear regret lower bound by Mannor et al [17] for adaptively chosen constraints, the paper deals with the setting where constraints are themselves generated stochastically. As a side effect, superior results are obtained for related problems such as OCO with long-term constraints. The paper does a nice job of introducing previous work and putting the contribution in perspective. The main algorithm of the paper is a first order online algorithm that performs an optimization step using the instantaneous penalty and constraint functions.

The technique used for aggregation is the Bradley-Terry model with computational saving techniques. The pairs are queried with Expected Information Gain (from the Bradley-Terry model) and either choosing the most informative pairs or choosing a batch of pairs corresponding to a MST built on the graph with edges based on the most informative pairs. Questions: Something that I didn't quite understand is that this work claimed to run the preferences in batches, however, it doesn't appear that they are run in batches for the first standard trial number. Can the authors please clarify this? The runtime for small problems (n 10-20) show that the algorithm runs relatively slowly and quadratically.

The work proposes the use of streamlining in the context of survey inspired decimation algorithms---a main approach alongside stochastic local search---for effciiently finding solutions to large satisfiable random instances of the Boolean satisfiability (SAT) problem. The paper is well-written and easy to follow (although some hasty mistakes remain, see below). The proposed approach is shown to improve the state of the art (to some extent) in algorithms for solving random k-SAT instances, especially by showing that streamlining constraints allow for solving instances that a closer to the sat-unsat phase transition point than previously for different values of k. In terms of motivations, while I do find it of interest to develop algorithmic approach which allow for more efficiently finding solutions to the hardest random k-SAT instances, it would be beneficial if the authors would expand the introduction with more motivations for the work. In terms of contributions, the proposal consists essentially of combining previous proposed ideas to obtain further advances (which is of course ok, but slightly lowers the novelty aspects).

Model predictive control (MPC) is a powerful tool for controlling complex nonlinear systems under constraints, but often struggles with model uncertainties and the design of suitable cost functions. To address these challenges, we discuss an approach that integrates MPC with safe Bayesian optimization to optimize long-term closed-loop performance despite significant model-plant mismatches. By parameterizing the MPC stage cost function using a radial basis function network, we employ Bayesian optimization as a multi-episode learning strategy to tune the controller without relying on precise system models. This method mitigates conservativeness introduced by overly cautious soft constraints in the MPC cost function and provides probabilistic safety guarantees during learning, ensuring that safety-critical constraints are met with high probability. As a practical application, we apply our approach to fast charging of lithium-ion batteries, a challenging task due to the complicated battery dynamics and strict safety requirements, subject to the requirement to be implementable in real time. Simulation results demonstrate that, in the context of model-plant mismatch, our method reduces charging times compared to traditional MPC methods while maintaining safety. This work extends previous research by emphasizing closed-loop constraint satisfaction and offers a promising solution for enhancing performance in systems where model uncertainties and safety are critical concerns.

Object-level mapping [1, 2, 3, 4, 5, 6, 7, 8, 9] builds a 3D map of multiple object instances in a scene, which is critical for scene understanding [10] and has various applications in robotic manipulation [11], semantic navigation [12, 13] and long-term dynamic map maintenance [14]. It addresses two closely coupled tasks: 3D shape reconstruction [15, 16] and pose estimation [17]. Conventional methods [18, 19, 20] approach these tasks from a perspective of state estimation [21], solving an inverse problem where low-dimensional observations (RGB and Depth images) are used to recover high-dimensional unknown variables (3D poses and shapes) through a known observation process (e.g., projection, and differentiable rendering). However, these methods require dense observations (e.g., hundreds of views for NeRF [18]) to fully constrain the problem. In robotics or AR applications, obtaining such dense observations is challenging due to limitations in the robot's or user's observation angle and occlusions in clustered scenarios. Therefore, it is crucial to develop methods that can map from sparse (fewer than 10) or even single observations. Human vision can infer complete 3D objects from images despite occlusions by using prior knowledge of the objects, which represents the prior distributions of the shapes of specific categories, such as chairs, based on thousands of instances observed in daily life. We aim to introduce generative models [22] as providers of prior knowledge to constrain the 3D object mapping. Generative models have demonstrated impressive abilities to generate high-quality multi-modal data by learning distributions in large-scale datasets, including texts [23], images [24], videos [25], and 3D models [26, 27, 28, 29].

This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d.

In the last few years, the formulation of real-world optimization problems and their efficient solution via metaheuristic algorithms has been a catalyst for a myriad of research studies. In spite of decades of historical advancements on the design and use of metaheuristics, large difficulties still remain in regards to the understandability, algorithmic design uprightness, and performance verifiability of new technical achievements. A clear example stems from the scarce replicability of works dealing with metaheuristics used for optimization, which is often infeasible due to ambiguity and lack of detail in the presentation of the methods to be reproduced. Additionally, in many cases, there is a questionable statistical significance of their reported results. This work aims at providing the audience with a proposal of good practices which should be embraced when conducting studies about metaheuristics methods used for optimization in order to provide scientific rigor, value and transparency. To this end, we introduce a step by step methodology covering every research phase that should be followed when addressing this scientific field. Specifically, frequently overlooked yet crucial aspects and useful recommendations will be discussed in regards to the formulation of the problem, solution encoding, implementation of search operators, evaluation metrics, design of experiments, and considerations for real-world performance, among others. Finally, we will outline important considerations, challenges, and research directions for the success of newly developed optimization metaheuristics in their deployment and operation over real-world application environments.

We study the application of min-max propagation, a variation of belief propagation, for approximate min-max inference in factor graphs. We show that for "any" highorder function that can be minimized in O(ω), the min-max message update can be obtained using an efficient O(K(ω + log(K)) procedure, where K is the number of variables. We demonstrate how this generic procedure, in combination with efficient updates for a family of high-order constraints, enables the application of min-max propagation to efficiently approximate the NP-hard problem of makespan minimization, which seeks to distribute a set of tasks on machines, such that the worst case load is minimized.

We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or adversarial. In such settings, Stradi et al.(2024) proposed the first best-of-both-worlds algorithm able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and constraint violation bounds in both cases. This algorithm suffers from two major drawbacks. First, it only works under full feedback, which severely limits its applicability in practice. Moreover, it relies on optimizing over the space of occupancy measures, which requires solving convex optimization problems, an highly inefficient task. In this paper, we provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback. Specifically, when the constraints are stochastic, the algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation, while, when they are adversarial, it attains $\widetilde{\mathcal{O}}(\sqrt{T})$ constraint violation and a tight fraction of the optimal reward. Moreover, our algorithm is based on a policy optimization approach, which is much more efficient than occupancy-measure-based methods.