Study on stable torsion length in groups, showing it vanishes in crystallographic groups and providing algorithms for computation.
problem Understanding the stable torsion length in groups, especially in crystallographic and free products of groups.
method Developed linear programming and exact algorithms to compute stable torsion length in free products of groups and finite groups.
result Showed that stable torsion length vanishes in crystallographic groups and provided exact computations for nontrivial examples.
Algorithm calculates stable multiplicities in cohomology of configuration spaces.
problem Computing stable multiplicities of irreducible representations in cohomology.
method Developed an algorithm to compute stable multiplicities of families of irreducible representations.
result Computed stable multiplicities for all Young diagrams with 23 boxes up to degree 50.
Algorithm identifies optimal stable matching in uncertain two-sided markets.
problem Sequential learning in two-sided markets with unknown preferences.
method Pure exploration approach with elimination-based algorithms exploiting partial preference information.
result Identification of pervasive stable matching for optimal stable matching identification.
New algorithms improve policy evaluation in reinforcement learning.
problem Off-policy stability and on-policy efficiency issues in policy evaluation.
method Introduced novel algorithms using oblique projection method.
result Demonstrated both off-policy stability and on-policy efficiency.
The paper verifies stable handleslide triviality of some R-links and shows many are stably equivalent.
problem Stable handleslide triviality of R-links as potential counterexamples to the generalized property R conjecture.
method Implemented an algorithm to construct all R-links explicitly and verified their stable handleslide triviality.
result Many R-links are stably handleslide equivalent.
Algorithm learns dynamics from past observations.
problem Learning a nonlinear dynamical system.
method Spectral filtering, online convex optimization.
result Vanishing prediction error for marginally stable systems.
The paper proposes a method to stabilize predictions by identifying causal variables using a seed variable.
problem Stable prediction across unknown test data with potential spurious correlations.
method Conditional independence test based algorithm using a seed variable to separate causal from non-causal variables.
result The algorithm precisely separates causal and non-causal variables for stable prediction across test data.
We give an algorithm to compute stable commutator length in free products of cyclic groups which is polynomial time in the length of the input, the number of factors, and the orders of the finite factors. We also describe some experimental and theoretical applications of this algorithm.
Heavy-tailed distributions are widely used in robust mixture modelling due to possessing thick tails. As a computationally tractable subclass of the stable distributions, sub-Gaussian α-stable distribution received much interest in the literature. Here, we introduce a type of expectation maximization algorithm that e…
Model selection on validation data is an essential step in machine learning. While the mixing of data between training and validation is considered taboo, practitioners often violate it to increase performance. Here, we offer a simple, practical method for using the validation set for training, which allows for a conti…
Develops a Monte Carlo algorithm for tempered stable process extrema.
problem Calculating the extrema of exponentially tempered Lévy processes.
method Novel Monte Carlo algorithm based on increments of the process.
result Geometrically fast convergence and optimal computational complexity.
For any group, there is a natural (pseudo-)norm on the vector space B1 of real (group) 1-boundaries, called the stable commutator length norm. This norm is closely related to, and can be thought of as a relative version of, the Gromov (pseudo)-norm on (ordinary) homology. We show that for a free group, the unit ball of…
New algorithm learns stable LDSs with lower error and better control performance.
problem Learning stable LDSs from data with minimal reconstruction error and stability constraints.
method Proposes an optimization method using a recent characterization of stable matrices, iteratively improving reconstruction error and ensuring stability.
result Achieves orders-of-magnitude improvement in reconstruction error compared to existing methods.
New algorithm reduces RL policy optimization gap.
problem Insufficient theoretical understanding of policy optimization methods.
method Reference-based Policy Optimization with Stable at Any Time guarantee (RPO-SAT)
result Achieves nearly minimax optimal policy-based algorithm for tabular RL.
To understand the empirical success of approximate MAP inference, recent work (Lang et al., 2018) has shown that some popular approximation algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise pote…
New method turns optimization algorithms into uniformly stable learning algorithms for non-Euclidean norms.
problem Non-Euclidean norms in binary classification problems.
method Black-box reduction method using uniformly convex regularizers.
result Achieves optimal statistical risk bounds on excess risk for non-Euclidean norms.
Proposes a stable classifier using inflated argmax for multiclass classification.
problem Inherent instability of taking the maximizer in multiclass classification.
method Bagging for stable continuous scores, inflated argmax for stable labels.
result Inflated argmax provides necessary protection against unstable classifiers without loss of accuracy.
Collaborative filtering (CF) is a popular technique in today's recommender systems, and matrix approximation-based CF methods have achieved great success in both rating prediction and top-N recommendation tasks. However, real-world user-item rating matrices are typically sparse, incomplete and noisy, which introduce ch…
Proposes a new model for clustering with heavier tails.
problem Clustering with heavy-tailed data.
method Finite mixture of skewed sub-Gaussian stable distributions, maximum likelihood estimation, EM algorithm.
result The proposed model can robustly handle heavy-tailed data.
We show that stable commutator length is rational on free products of free Abelian groups amalgamated over Zk, a class of groups containing the fundamental groups of all torus knot complements. We consider a geometric model for these groups and parameterize all surfaces with specified boundary mapping to th…
Stable random variables are motivated by the central limit theorem for densities with (potentially) unbounded variance and can be thought of as natural generalizations of the Gaussian distribution to skewed and heavy-tailed phenomenon. In this paper, we introduce stable graphical (SG) models, a class of multivariate st…
New LP method recovers MAP solution from noisy stable instances.
problem MAP inference on noisy stable instances.
method Designing an algorithm to find nearby perturbation stable instances and using LP relaxation.
result LP approximately recovers the MAP solution from noisy stable instances.
In many important machine learning applications, the training distribution used to learn a probabilistic classifier differs from the testing distribution on which the classifier will be used to make predictions. Traditional methods correct the distribution shift by reweighting the training data with the ratio of the de…
Clustering is a crucial component of many data mining systems involving the analysis and exploration of various data. Data diversity calls for clustering algorithms to be accurate while providing stable (i.e., deterministic and robust) results on arbitrary input networks. Moreover, modern systems often operate with lar…
New algorithms learn stable matchings from uncertain user preferences.
problem Learning stable matchings from uncertain user preferences.
method Stochastic multi-armed bandit problem, incentive-aware learning objective, primal-dual formulation.
result Near-optimal regret bounds for learning stable matchings.
NROWAN-DQN improves stability and exploration in noisy networks.
problem Noisy networks struggle with stable exploration in complex tasks.
method Noise reduction and online weight adjustment for stable actions.
result NROWAN-DQN outperforms prior algorithms in stability and exploration.
MAFLA improves sampling from heavy-tailed distributions using MH-inspired corrections.
problem Sampling from heavy-tailed and multimodal distributions when neither target nor proposal densities can be evaluated.
method Metropolis-Adjusted Fractional Langevin Algorithm (MAFLA) with Score Balance Matching.
result MAFLA significantly improves finite-time sampling accuracy over unadjusted fractional Langevin dynamics.
Overparameterized models generalize well in offline contextual bandits, but policy-based algorithms struggle.
problem The performance gap between value-based and policy-based algorithms in offline contextual bandits with overparameterized models.
method Analysis of action-stability in objectives and formal proofs of regret bounds.
result The performance gap is due to action-stability of objectives, with value-based objectives being stable and policy-based objectives unstable.
Thompson Sampling provides an efficient technique to introduce prior knowledge in the multi-armed bandit problem, along with providing remarkable empirical performance. In this paper, we revisit the Thompson Sampling algorithm under rewards drawn from symmetric α-stable distributions, which are a class of heavy-taile…
Stable density-based clustering via multiparameter persistence.
problem Density-based clustering stability to data perturbations.
method Degree-Rips construction, correspondence-interleaving distance, multiparameter stability analysis.
result Persistable pipeline yields stable, consistent density-based clustering.
I-SPEC learns stable models from data without full causal knowledge.
problem Learning models that generalize well across shifts in environment.
method End-to-end framework using partial ancestral graph to learn stable interventional distribution.
result I-SPEC can learn robust models without full causal knowledge.
No algorithm outperforms uniform sampling in A/B testing.
problem Identifying the best arm in A/B testing with fixed budget.
method Introducing consistent and stable algorithms, deriving lower bounds, and proving optimality of uniform sampling.
result No algorithm performs better than uniform sampling in A/B testing.
In this paper we consider the problem of finding stable maxima of expensive (to evaluate) functions. We are motivated by the optimisation of physical and industrial processes where, for some input ranges, small and unavoidable variations in inputs lead to unacceptably large variation in outputs. Our approach uses multi…
We propose a new blind source separation algorithm based on mixtures of alpha-stable distributions. Complex symmetric alpha-stable distributions have been recently showed to better model audio signals in the time-frequency domain than classical Gaussian distributions thanks to their larger dynamic range. However, infer…
SFB uses stable features to adapt unstable ones for better performance.
problem Improving classifier performance on out-of-distribution data by leveraging stable features.
method SFB learns a predictor that separates stable and unstable features, then adapts unstable predictions using stable predictions.
result SFB can learn an asymptotically-optimal predictor without test-domain labels.
Leveraging algorithmic stability to derive sharp generalization bounds is a classic and powerful approach in learning theory. Since Vapnik and Chervonenkis [1974] first formalized the idea for analyzing SVMs, it has been utilized to study many fundamental learning algorithms (e.g., k-nearest neighbors [Rogers and Wag…
This paper applies Thompson Sampling to asymmetric α-stable bandits for financial and wireless data.
problem Optimizing exploration-exploitation in multi-armed bandits with asymmetric α-stable distributions. method Thompson Sampling applied to unknown asymmetric α-stable reward distributions. result Demonstrates effectiveness of Thompson Sampling for asymmetric α-stable bandits. New method identifies optimal subset of stable information to transfer for better model generalization.
problem Non-reliability of machine learning models to dataset shifts.
method Causal minimax learning approach to identify optimal subset of stable information.
result Proposed algorithm efficiently searches for optimal subset with minimal worst-case risk.
Fair classification has been a topic of intense study in machine learning, and several algorithms have been proposed towards this important task. However, in a recent study, Friedler et al. observed that fair classification algorithms may not be stable with respect to variations in the training dataset -- a crucial con…
Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generalization bounds is that they hold only in expectation. Generalization with high probability has been established in a landmark paper of Bousque…
Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss function with range bounded in [0,1], the generalization error of a γ-uniformly stable learning a…
New algorithms help machines forget old data efficiently.
problem Machine learning models can retain old data, hindering new learning.
method Developed TV-stable algorithms based on noisy SGD for convex and non-convex functions.
result Achieved efficient unlearning with upper and lower bounds on risk.
SIRUS creates interpretable rules from random forests for regression.
problem Lack of interpretability in complex machine learning models.
method Random forest with rule extraction for stability and simplicity.
result SIRUS produces stable and interpretable rule sets.
Study normal tempered stable processes for energy derivative pricing.
problem Pricing energy derivatives with spot price models.
method Specified statistical properties, derived non-arbitrage conditions, developed efficient algorithm for trajectory generation.
result Validated pricing models for various energy contracts.
Characterizes Lévy-driven Ornstein-Uhlenbeck processes linked to tempered stable distributions.
problem Understanding Lévy-driven Ornstein-Uhlenbeck processes and their properties.
method Characterizes the Lévy triplet and deduces transition laws for finite variation Ornstein-Uhlenbeck processes associated with tempered stable distributions.
result Provides algorithms for generating skeleton of Ornstein-Uhlenbeck processes related to exponentially-modulated tempered stable laws.
Log-Normal Multiplicative Dynamics improves low-precision training of neural networks.
problem Training large neural networks with low precision is unstable.
method Derive a Bayesian learning rule with log-normal posterior distributions and multiplicative updates.
result LMD achieves stable and accurate training for Vision Transformer and GPT-2.
MLE and CVE are equivalent under exponential families, leading to faster and more stable EM algorithms.
problem Finding maximum likelihood estimators (MLE) efficiently and stably.
method Proved equivalence between MLE and CVE under exponential families, leading to an EM algorithm.
result EM algorithm achieves the same asymptotic variance as MLE and is faster and more stable.
Math proves deep learning unstable, despite stable neural networks existing.
problem Unstable neural networks in deep learning despite stable ones existing.
method Mathematical proof showing instability of current training procedures.
result Proven existence of stable and accurate neural networks with variable dimensions, but current algorithms cannot compute them.