KCRL learns stable policies for nonlinear systems with formal guarantees.
problem Lack of stabilization guarantees in RL methods for safety-critical systems.
method KCRL uses Krasovskii's Lyapunov functions as a stability constraint and a primal-dual approach to learn stabilizing policies.
result KCRL guarantees learning a stabilizing policy in a finite number of interactions.
Bagging stabilizes models without distributional assumptions.
problem Stability of machine learning models without distributional assumptions.
method Derives a finite-sample guarantee on bagging stability for any model.
result Guarantee applies to many bagging variants and is optimal.
Enhanced stability improves privacy in machine learning.
problem Improving privacy in machine learning training while maintaining accuracy.
method Study of stability in private empirical risk minimization, focusing on strongly-convex loss functions and uniform stability.
result An algorithm with uniform stability of β implies a bound of O(√β) on the scale of noise required for differential privacy.
The paper guarantees global stability for stochastic subgradient methods in nonsmooth nonconvex optimization.
problem Minimizing nonsmooth nonconvex functions with convergence guarantees.
method Developed a framework for stochastic subgradient methods with global stability guarantees.
result Iterates are uniformly bounded and asymptotically stabilize around the stable set of the differential inclusion.
AUASE embeds dynamic networks with stability guarantees for node comparison.
problem Stability in dynamic network embeddings for comparing nodes across time.
method Attributed unfolded adjacency spectral embedding (AUASE) for stable unsupervised learning.
result AUASE provides significant improvements in link prediction and node classification.
Boosting framework for vector-valued prediction with geometric stability.
problem Lack of a general theoretical understanding of aggregation for structured prediction.
method Identifies (α,β)-stability property and proposes a boosting framework based on exponential reweighting and geometric-median aggregation. result Obtains exponential decay of empirical divergence error under weak learner condition and (α,β)-stability. A stability-based method selects the most desirable conformal prediction set.
problem Selecting the most desirable conformal prediction set from multiple valid sets invalidates coverage guarantees.
method A stability-based approach that ensures coverage for the selected prediction set.
result The stability-based approach maintains coverage guarantees for the selected prediction set.
Paper proposes an unsupervised feature selection algorithm with stability guarantees.
problem Feature selection for dimension reduction and interpretability.
method Proposes a novel unsupervised feature selection algorithm with stability guarantees.
result The algorithm has superior generalization performance and stable selected features.
The paper develops a convex parameterization for robust RNNs ensuring stability and robustness.
problem Lack of stability and robustness guarantees in RNNs for sequence-to-sequence mapping applications.
method Formulated convex sets of RNNs with stability and robustness guarantees using incremental quadratic constraints.
result The proposed model structure ensures global exponential stability and bounds on incremental ℓ2 gain. Design of reliable systems must guarantee stability against input perturbations. In machine learning, such guarantee entails preventing overfitting and ensuring robustness of models against corruption of input data. In order to maximize stability, we analyze and develop a computationally efficient implementation of Jac…
Efficient inference for adaptive data with directional stability condition.
problem Efficient inference on scalar targets after adaptive data collection.
method Introduces directional stability, a weaker condition than i.i.d. data, and shows asymptotic normality and efficiency of estimators.
result Estimators remain asymptotically normal and semiparametrically efficient under directional stability.
Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as t…
New stability framework relaxes boundedness assumptions for generalization bounds.
problem Overly restrictive assumptions for modern learning settings with heavy-tailed or unbounded losses.
method Develops a stability-based framework requiring only finite Lp moment conditions. result Sharp generalization bounds derived for various learning paradigms.
New method embeds dynamic networks with stability for node behavior.
problem Embed time-evolving node representations with stability.
method Unfolded adjacency spectral embedding for dynamic networks.
result Method satisfies cross-sectional and longitudinal stability.
New risk control method for non-monotonic losses in complex parameters.
problem Controlling risk for non-monotonic losses with multidimensional parameters.
method Stability-based guarantees for generic algorithms applied to non-monotonic losses.
result Guarantees depend on algorithm stability, with looser guarantees for unstable algorithms.
Cluster stability selection improves feature selection in correlated data.
problem Feature selection stability in correlated data.
method Cluster stability selection exploiting known cluster structure.
result Better predictive performance than lasso alone and stability selection.
Dealing with high variance is a significant challenge in model-free reinforcement learning (RL). Existing methods are unreliable, exhibiting high variance in performance from run to run using different initializations/seeds. Focusing on problems arising in continuous control, we propose a functional regularization appr…
New algorithms learn stability certificates from data, avoiding complex dynamics.
problem Synthesizing stability certificates from complex dynamical systems.
method Developed algorithms to learn certificate functions from trajectory data, establishing generalization error bounds.
result Efficiently learned certificates can be used for adaptive control.
New credit attribution methods for machine learning models using relaxed stability guarantees.
problem Ensuring proper attribution in generative models trained on existing works.
method Proposed new definitions of stability that allow for non-stable processing of a subset of datapoints with permission.
result Extended well-studied stability notions and provided a comprehensive characterization of learnability.
ULES embeds dynamic networks with stability guarantees.
problem Stability of time-varying node embeddings in evolving networks.
method Unfolded Laplacian Spectral Embedding (ULSE) using normalized Laplacian operators.
result ULES satisfies cross-sectional and longitudinal stability under dynamic stochastic block model.
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…
Study examines stability of image-reconstruction algorithms using variational regularization.
problem Stability and robustness of image-reconstruction algorithms in medical imaging.
method Review and novel stability results for ℓp-regularized linear inverse problems, focusing on p∈(1,∞). result Guarantees Lipschitz continuity for small p and Hölder continuity for larger p in Lp(Ω) function spaces. The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in…
The paper provides theoretical guarantees for behavior cloning using generative models.
problem Behavior cloning of complex expert demonstrations using generative models.
method The paper proposes a theoretical framework invoking low-level controllers to stabilize imitation around expert demonstrations. It shows that with suitable low-level stability guarantees and powerful generative models, pure supervised behavior cloning can match expert trajectories.
result The paper proves that with a suitable low-level stability guarantee and a powerful enough generative model, pure supervised behavior cloning can generate trajectories matching the per-time step distribution of essentially arbitrary expert trajectories in an optimal transport cost.
Efficient algorithm reduces control system regret to sqrt(t).
problem Control of linear quadratic systems with guaranteed anytime performance.
method Combines SDP-based framework with regularization and perturbation mechanisms.
result Achieves anytime regret of order sqrt(t) with explicit dependence on system dimensions.
A new Bayesian approach to linear system identification has been proposed in a series of recent papers. The main idea is to frame linear system identification as predictor estimation in an infinite dimensional space, with the aid of regularization/Bayesian techniques. This approach guarantees the identification of stab…
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.
New research shows Byzantine failures hurt generalization more than data poisoning in robust distributed learning.
problem Generalization in robust distributed learning algorithms under Byzantine failures vs. data poisoning.
method Algorithmic stability analysis of robust distributed learning algorithms.
result Byzantine failures yield strictly worse generalization rates than data poisoning.
New neural methods for stable control with provable guarantees.
problem Designing stable control policies for nonlinear systems.
method Neural network Lyapunov functions and a falsifier to guide learning.
result Provable stability of controlled nonlinear systems.
Reinforcement learning is a powerful paradigm for learning optimal policies from experimental data. However, to find optimal policies, most reinforcement learning algorithms explore all possible actions, which may be harmful for real-world systems. As a consequence, learning algorithms are rarely applied on safety-crit…
New method stabilizes machine learning predictions across random seeds.
problem Machine learning predictions vary across random seeds, causing instability.
method Introduces adaptive cross-bagging to eliminate seed dependence.
result Adaptive cross-bagging achieves targeted stability in debiased machine learning.
New bounds improve generalization in learning scenarios.
problem Limitations of existing information-theoretic bounds in SCO problems.
method Sample-conditioned hypothesis stability and neighboring-hypothesis matrix.
result Sharper generalization guarantees in various learning scenarios.
The present paper provides a new generic strategy leading to non-asymptotic theoretical guarantees on the Leave-one-Out procedure applied to a broad class of learning algorithms. This strategy relies on two main ingredients: the new notion of Lq stability, and the strong use of moment inequalities. Lq stability e…
Study shows how competition affects learning in matching markets, proving it's possible to balance stability, fairness, and regret.
problem How competition affects learning in matching markets and the impossibility of simultaneously guaranteeing stability and low optimal regret.
method Modeling a two-sided matching market with bandit learners and adding components of costs and transfers.
result It is possible to simultaneously guarantee stability, low optimal regret, fairness in the distribution of regret, and high social welfare.
New method stabilizes saddle-point optimization with unbounded gradients.
problem Stochastic saddle-point optimization faces instability due to large gradients.
method Proposes a regularization technique to stabilize iterates.
result Yields meaningful performance guarantees even with unbounded gradients.
Polynomial-time private algorithm for robust estimation of mean and covariance in the presence of outliers.
problem Estimating mean and covariance in the presence of adversarial outliers.
method Stabilizing convex relaxations using a new estimate-dependent noise injection mechanism.
result First efficient private robust estimation algorithm for covariance without condition-number assumptions.
New method stabilizes model selection with theoretical guarantees.
problem Stability of model selection methods in the face of noisy or incomplete data.
method Combines bagging with an 'inflated' argmax operation to select a stable set of models.
result Stable model selection with high probability of overlap after removing any data point.
A new stable similarity measure for time series using persistent homology.
problem Constructing a robust measure of time series similarity.
method Persistent homology for stability, bi-conditional periodicity score for similarity.
result Stability of the bi-conditional periodicity score under perturbations and dimension reduction.
OMD and DA perform similarly in static settings but OMD is inferior under dynamic learning rates.
problem Proving and understanding the performance difference between OMD and DA under dynamic learning rates.
method Introducing stabilization to OMD and modifying its convergence analysis.
result OMD with stabilization and DA have the same performance guarantees under dynamic learning rates.
Stabilizing black-box algorithms through task-oriented randomization
problem Ensuring stability of black-box models
method Task-oriented randomization
result Established rigorous theoretical foundations and demonstrated effectiveness through simulations and real-world applications
New Transformers maintain Lipschitz continuity for robustness.
problem Ensuring robustness in Transformers for safety-sensitive applications.
method Introducing gradient-descent-type in-context Transformers with explicit Euler steps of negative gradient flows.
result Universal approximation theorem for Lipschitz continuous Transformers.
Wiatowski and Bölcskei, 2015, proved that deformation stability and vertical translation invariance of deep convolutional neural network-based feature extractors are guaranteed by the network structure per se rather than the specific convolution kernels and non-linearities. While the translation invariance result appli…
The paper provides guarantees for clustering validity without distributional assumptions.
problem Validating clustering results without distributional assumptions.
method Generic method to obtain post-inference guarantees of near-optimality and stability for clustering.
result The guarantees do not depend on distributional assumptions but depend on the data set admitting a stable clustering.
Convolutional neural networks (CNNs) often perform well, but their stability is poorly understood. To address this problem, we consider the simple prototypical problem of signal denoising, where classical approaches such as nonlinear diffusion, wavelet-based methods and regularisation offer provable stability guarantee…
Gradient filters track moving parameters under noisy data and misspecification.
problem Tracking multidimensional time-varying parameters under noisy observations and model misspecification.
method Gradient-based filters update parameters using the gradient of a postulated objective function, evaluated at either the predicted or updated parameters.
result Novel sufficient conditions for exponential stability of the filtered parameter path, and finite-sample and asymptotic mean squared error bounds.
Improved MLE for Hawkes Processes stabilizes unstable optimization.
problem Unstable Maximum Likelihood Estimation (MLE) for Hawkes Processes.
method Simple stabilization procedure to improve MLE without restrictive assumptions.
result Stabilized MLE outperforms traditional methods over various sequence lengths.
We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is a generalization bound for data-dependent hypothesis sets expressed in terms of a notion of hypothe…
CLIP controls neural network stability by bounding Lipschitz constants.
problem Neural networks lack mathematical guarantees of stability, especially to adversarial examples.
method Develops a variational regularization method (CLIP) to control the Lipschitz constant of neural networks.
result CLIP provides a tighter bound on the actual Lipschitz constant compared to layer-wise methods.