The paper explores using restart distributions to enhance exploration in reinforcement learning.
problem Enhancing exploration in reinforcement learning environments.
method Adapting a restart distribution to promote faster state-space coverage and diverse initial states.
result Performance gains can be achieved, especially in hard exploration problems, through the use of restart distributions.
RePS improves diffusion models for solving inverse problems efficiently.
problem Solving inverse problems with incomplete or noisy measurements.
method Restart for Posterior Sampling (RePS) using pre-trained diffusion models.
result RePS achieves faster convergence and superior reconstruction quality.
A new restart criterion for k-means++ improves clustering quality and adapts to data difficulty.
problem Arbitrary restart counts in k-means++ lead to inconsistent results and wasted computation.
method GTRC combines Good-Turing estimates, bounds, and user-specified tolerance to dynamically decide restarts.
result GTRC achieves clustering quality comparable to fixed restart counts, varying restarts based on data difficulty.
Paper adds a restart mechanism to a drawdown control policy for better trading performance.
problem Missed profitable opportunities when drawdown limit is close to reality.
method Integrates a data-driven restart mechanism into the drawdown modulation trading system.
result The restart mechanism improves trading performance even with transaction costs.
Study on improving the linear two-time-scale stochastic approximation method with a restarting scheme.
problem Characterizing and optimizing the finite-time complexity of linear two-time-scale stochastic approximation.
method Analysis of mean square errors, introduction of a restarting scheme to improve performance.
result The method achieves an exact convergence to the desired solution with improved complexity under time-varying step sizes.
A new sampling method called Restart improves both speed and quality of generative processes.
problem Balancing speed and quality in generative processes involving differential equations.
method Alternates between adding noise and following ODE, improving both speed and quality.
result Surpasses previous SDE and ODE samplers in both speed and accuracy.
Online distributional prediction with latent cluster geometry
problem Predicting the full data-generating distribution in non-stationary streams
method Representing candidate laws as latent cluster geometry and using Gibbs quasi-posterior
result Achieving sublinear cumulative Wasserstein regret under bounded support and stable latent geometry
New algorithms boost SAT solver performance by optimizing restart strategies.
problem Optimizing decision-making under time constraints with restarts.
method Developed online learning algorithms for a bandit problem with controlled restarts.
result Achieved O ( log ( τ ) ) O(\log(τ)) O ( log ( τ )) and O ( τ log ( τ ) ) O(\sqrt{τ\log(τ)}) O ( τ log ( τ ) ) regret bounds. New method samples from complex Bayesian posteriors efficiently.
problem Challenges in Bayesian inference for complex datasets.
method Bayesian nonparametric learning with posterior bootstrap.
result Scalable sampling from multimodal posteriors.
Master algorithm fails to detect non-stationarity in practical settings.
problem Non-Stationary Reinforcement Learning without prior knowledge.
method Master algorithm tested under various conditions, including piecewise stationary multi-armed bandits.
result Master's non-stationarity detection is ineffective for practical horizons, leading to performance similar to random restarting.
Study adapts combinatorial semi-bandit for piecewise stationary, causally related rewards.
problem Nonstationary environment with changing base arms' distributions and causal relationships.
method Upper Confidence Bound (UCB) algorithm with change-point detector and group restart strategy.
result Regret upper bound reflecting effects of structural and distribution changes.
Improved SEG method converges to Nash equilibrium in bilinear games.
problem Stochastic bilinear minimax optimization problem
method Stochastic ExtraGradient (SEG) method with constant step size, iteration averaging, and scheduled restarting.
result Provable convergence to Nash equilibrium under standard settings, optimal convergence rate in interpolation setting.
A distributed algorithm reduces communication complexity for non-convex optimization.
problem Efficiently solving non-convex optimization problems in a distributed setting.
method Parallel Restarted SPIDER algorithm, incorporating SPIDER gradient estimator.
result Achieves optimal communication complexity O ( ε − 1 ) O(ε^{-1}) O ( ε − 1 ) and optimal computation complexity. Recent studies have shown that proximal gradient (PG) method and accelerated gradient method (APG) with restarting can enjoy a linear convergence under a weaker condition than strong convexity, namely a quadratic growth condition (QGC). However, the faster convergence of restarting APG method relies on the potentially …
New method tracks significant arm switches to improve bandit algorithms.
problem Adaptive procedures for bandits with unknown changes in reward distribution.
method Proposes a new notion of significant shift to count severe changes.
result Achieves faster rates than previous methods, especially when few changes are severe.
WITCHcraft improves PGD attacks with random step size, enhancing efficiency.
problem Efficiently crafting adversarial attacks on neural networks.
method Variant of PGD using random step size.
result Superior performance to classical PGD without additional computational cost.
New RL algorithm tackles nonstationary MDPs with linear approximations and varying rewards.
problem Nonstationary reinforcement learning with evolving reward and state transition functions.
method Developed a new algorithm LSVI-UCB-Restart with periodic restart, and parameter-free Ada-LSVI-UCB-Restart for unknown variation budgets.
result First minimax dynamic regret lower bound for nonstationary linear MDPs and linear MDPs lower bound.
ParaMonte::Python streamlines Bayesian data analysis with fast Monte Carlo and MCMC routines.
problem Efficiently sampling posterior distributions in Bayesian modeling and data science.
method Serial and MPI-parallelized Markov Chain Monte Carlo (MCMC) routines.
result Automated model calibration and uncertainty quantification in Bayesian analysis.
Algorithm reduces decision-making errors in multi-agent bandit problems.
problem Minimizing decision errors in multi-agent multi-armed bandit problems.
method RBO-Coop-UCB algorithm with Bayesian change point detection.
result Expected group regret is upper bounded by O ( K N M log T + K M T log T ) \mathcal{O}(KNM\log T + K\sqrt{MT\log T}) O ( K N M log T + K M T log T ) . WARPd method solves inverse problems with approximate sharpness conditions.
problem Reconstruction of signals from undersampled and noisy measurements.
method First-order method based on primal-dual iterations with restart-reweight scheme.
result WARPd achieves stable linear convergence under generic approximate sharpness condition.
BRPC online Bayesian calibration handles gradual and abrupt system changes.
problem Aligning model outputs with field observations in evolving systems.
method Bayesian Recursive Projected Calibration (BRPC) for streaming data under simulator mismatch and nonstationarity.
result Improves calibration accuracy under gradual changes and robustness under abrupt regime shifts.
In this paper we develop a Morse theory for the uniform energy. We use the one-sided directional derivative of the distance function to study the minimizing properties of variations through closed geodesics. This derivative is then used to define a one-sided directional derivative for the uniform energy which allows us…
Dual training method for EBMs with overparametrized neural networks.
problem Training EBMs with non-convex energies is challenging.
method Derive variational principles and dual GDA algorithm for feature-learning regime.
result Dual GDA algorithm performs best with similar time scales for features and particles.
PER-ETD improves ETD by reducing variance to polynomial complexity.
problem Large variance in ETD leading to exponential sample complexity.
method Periodically restart and update the follow-on trace for a finite period.
result PER-ETD converges to the same fixed point as ETD but with improved sample complexity.
The paper optimizes dynamic scheduling for ring architectures in deep learning training.
problem Optimizing deep learning training times with ring architectures.
method Formulated a non-convex, non-linear, NP-hard integer programming problem and developed a doubling heuristic.
result Dynamic scheduling can significantly reduce job completion times in ring architectures.
Empirical analysis of deep learning heuristics like learning rate restarts and distillation.
problem Understanding the effectiveness and mechanisms of deep learning heuristics.
method Loss surface and representation analysis methods (mode connectivity and CCA) for empirical analysis.
result Learning rate warmup prevents training instability in deeper layers, and cosine annealing does not explain success.
Improved algorithm detects changes in RL environments with non-stationary MDPs.
problem Learning in non-stationary reinforcement learning environments.
method R-BOCPD-UCRL2 algorithm for MDPs with multinomial state transitions.
result Near-optimal theoretical guarantees in terms of false-alarm rate and detection delay.
LLMs optimize quantum circuits by iteratively improving proposals with feedback and memory traces.
problem Optimizing quantum circuits using large language models (LLMs) under black-box evaluation.
method Closed-loop, test-time optimization with LLMs, score-difference feedback, and restart-from-the-best sampling.
result The approach improves circuit synthesis performance and success rate, especially for larger qubit settings.
We consider the problem where an agent wants to find a hidden object that is randomly located in some vertex of a directed acyclic graph (DAG) according to a fixed but possibly unknown distribution. The agent can only examine vertices whose in-neighbors have already been examined. In this paper, we address a learning s…
Paper tackles non-stationary kernelized bandits with near-optimal algorithm.
problem Minimizing regret in a time-varying reward function.
method Near-optimal algorithm with a novel restarting phased elimination with random permutation (R-PERP).
result Regret upper bound matches the lower bound, making the algorithm near-optimal.
Continuous optimization is an important problem in many areas of AI, including vision, robotics, probabilistic inference, and machine learning. Unfortunately, most real-world optimization problems are nonconvex, causing standard convex techniques to find only local optima, even with extensions like random restarts and …
PROPO tackles non-stationary MDPs with efficient policy optimization.
problem Non-stationary MDPs with varying reward and transition kernels.
method PROPO, a periodic restarted optimistic policy optimization algorithm with sliding-window-based policy evaluation and improvement.
result PROPO achieves near-optimal performance in non-stationary MDPs.
One-pass optimisation for high-dimensional hyperparameters.
problem Efficient optimisation of hyperparameters in machine learning models.
method Approximate hypergradient-based optimisation for any continuous hyperparameter, requiring only one training episode.
result Competitive performance on various datasets without hyperparameter restarts.
A scalable framework preserves personalized higher-order network proximities.
problem Lack of expressive methods to preserve personalized higher-order network proximities.
method Incorporates random walk into a sound objective to preserve arbitrary higher-order proximities and introduces random walk with restart for personalized-weighted preservation.
result Consistently and substantially outperforms state-of-the-art methods on real-world networks.
Unified approach for non-stationary linear bandits with dynamic regret.
problem Non-stationary linear bandits with round-specific feasible actions and drifting reward models.
method Unified misspecification-reduction viewpoint, restarting algorithms with misspecification-dependent regret guarantees.
result Optimal \(T^{2/3}P_T^{1/3}\) dynamic-regret dependence for both linear bandits and contextual linear bandits.
The multi-armed bandit problem has been extensively studied under the stationary assumption. However in reality, this assumption often does not hold because the distributions of rewards themselves may change over time. In this paper, we propose a change-detection (CD) based framework for multi-armed bandit problems und…
Determinantal consensus clustering improves clustering robustness.
problem Robustness of clustering algorithms.
method Use of determinantal point processes (DPP) for random restart of clustering algorithms.
result Determinantal consensus clustering outperforms classical algorithms.
SRSGD improves DNN training speed and accuracy.
problem Training deep neural networks is computationally expensive and slow.
method Scheduled Restart SGD (SRSGD) combines NAG momentum with momentum reset.
result SRSGD achieves better error rates with fewer training epochs.
A new algorithm solves nonnegative least squares faster with nonnegative data.
problem Nonnegative least squares problems with nonnegative data.
method Primal-dual perspective accelerated algorithm with adaptive restart.
result Oracle complexity independent of matrix constants, solvable to multiplicative error.
Given a generic Lagrangian system, its Euler-Lagrange operator obeys Noether identities which need not be independent, but satisfy first-stage Noether identities, and so on. This construction is generalized to arbitrary differential operators on a smooth fiber bundle. Namely, if a certain necessary and sufficient condi…
Paper speeds up tensor factorization algorithms.
problem Improving convergence speed of tensor factorization algorithms.
method Proposes an extrapolation strategy between block updates.
result HER significantly accelerates convergence speed.
New method RECAST improves uncertainty calibration in neural networks.
problem Improving uncertainty estimation in neural networks for better predictions.
method Proposed RECAST method combining cosine annealing, warm restarts, and Stochastic Gradient Langevin Dynamics.
result RECAST offers the best calibrated measure of uncertainty compared to recent methods.
A good clustering can help a data analyst to explore and understand a data set, but what constitutes a good clustering may depend on domain-specific and application-specific criteria. These criteria can be difficult to formalize, even when it is easy for an analyst to know a good clustering when they see one. We presen…
New method uses entropy to improve policy gradient exploration.
problem Limited exploration in policy gradient methods.
method Entropy regularization with discounted future state distribution.
result Proves convergence to locally optimal policy.
New method finds near-optimal solutions for non-convex optimization problems.
problem Finding near-optimal solutions for non-convex optimization problems.
method Riemannian stochastic recursive momentum method
result Achieves a near-optimal complexity of i l d e O ( ε − 3 ) ilde{\mathcal{O}}(ε^{-3}) i l d e O ( ε − 3 ) . We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's schem…
Novel methods for accelerating optimization in complex bilevel and minimax problems.
problem Optimization challenges in bilevel and minimax problems, especially when strong convexity assumptions are not met.
method Accelerated fully first-order methods for Bilevel Optimization (BLO) and Minimax Optimization (NCSC).
result State-of-the-art complexity for finding approximate second-order stationary points in BLO and NCSC.
Efficiently samples posterior distributions using Langevin dynamics.
problem Challenges in generating diverse posterior samples in high-dimensional spaces.
method Simulates Langevin dynamics in the noise space of a pre-trained generative model.
result Noise-space Langevin dynamics approximates the posterior without restarting the full sampling chain.