We develop efficient algorithms to estimate the stability of Ordinary Least Squares regression results.
problem Measuring the stability of regression conclusions in low dimensions.
method Efficient algorithms for estimating the minimum number of samples that need to be removed to change a regression conclusion.
result We can estimate stability up to a factor of 3 better than the greedy heuristic and certify stability even for dropping a majority of samples.
Heuristic weighting improves denoising score matching without requiring noise distribution assumptions.
problem Improving denoising score matching without assuming noise distribution.
method Demonstrated heteroskedasticity, derived optimal weighting functions, and provided theoretical and empirical comparisons.
result Heuristical weighting function can achieve lower variance than optimal weighting, facilitating more stable and efficient training.
Paper uses TDA to assess cryptocurrency risk by measuring phase space instability.
problem Traditional risk measures fail to capture market dynamics' geometric structure.
method Applied Takens' Delay Embedding Theorem to generate point cloud, computed persistent homology groups, defined Topological Persistence Norm.
result Proposed leverage calibration heuristic based on persistence of 1-dimensional cycles.
AdamQLR optimizes Adam with K-FAC heuristics, achieving comparable performance to tuned benchmarks.
problem Improving the performance of Adam optimizers with stabilizing heuristics.
method Combining Adam's update directions with K-FAC's heuristics (damping and learning rate selection).
result Untuned AdamQLR can achieve comparable performance to tuned benchmarks.
Improved decision tree learning guarantees for complex functions.
problem Achieving provable guarantees for decision tree induction with complex target functions.
method Introduces a new splitting criterion that considers correlations between target function and subsets of attributes.
result Proves provable guarantees for all target functions with respect to the uniform distribution, circumventing previous impossibility results.
Weight decay stabilizes training dynamics by slowing progressive sharpening.
problem Understanding how weight decay affects training stability in deep learning models.
method Analyzing weight decay effects at the Edge of Stability, developing a mathematical framework.
result Weight decay dampens oscillations and stabilizes sharpness in CNNs, causing a phase transition in MLPs.
New approach to concentration inequalities for unbounded state space dynamical systems.
problem Concentration inequalities for unbounded state space dynamical systems.
method Functional analytic framework, transport-entropy inequality.
result Exponential concentration inequalities for sampling from stationary distribution.
Market activity scales near a constant of 0.632 in intrinsic time.
problem Understanding the stability of market scaling laws.
method Modeling market directional changes as a memoryless exponential hazard process and identifying the intrinsic time scaling constant.
result The intrinsic time scaling constant is 1−1/e=0.632. New stability analysis improves generalization of multipass SGD.
problem Improper preconditioning affects generalization in multipass SGD.
method Developed on-average stability analysis for multipass SGD.
result Proper preconditioning yields optimal effective dimension dependence.
AEN-SAEs address feature starvation in sparse autoencoders by stabilizing the geometric alignment of sparse coding.
problem Feature starvation in sparse autoencoders, leading to unstable and misaligned representations.
method Adaptive Elastic Net SAEs (AEN-SAEs) combine ℓ2 and ℓ1 terms to stabilize the sparse coding map and control feature interactions. result AEN-SAEs mitigate feature starvation without heuristic resampling, maintaining competitive reconstruction abilities.
Fair k-means algorithm ensures equitable costs for different groups.
problem K-means clustering can result in biased outcomes for subgroups of data.
method Presented a fair k-means objective and algorithm (Fair-Lloyd) to choose cluster centers that provide equitable costs for different groups.
result Fair-Lloyd algorithm ensures all groups have equal costs in the output k-clustering, with negligible increase in running time.
Proposes proactive bed requests to reduce ED boarding and patient wait times.
problem Reduces ED boarding and patient wait times by proactively requesting inpatient beds.
method Formulates as a Markov decision process, uses predictions of admission probability and time to disposition to guide bed requests.
result Proactive aggregate bed requests can reduce boarding times by 30-70% and length of stay by 6-15%.
We consider the numerical stability of the parameter recovery problem in Linear Structural Equation Model ($\LSEM$) of causal inference. A long line of work starting from Wright (1920) has focused on understanding which sub-classes of $\LSEM$ allow for efficient parameter recovery. Despite decades of study, this questi…
This paper analyzes GANs using Fourier modes to stabilize training.
problem Stability and convergence issues in GAN training.
method Decompose GAN objective function into Fourier series and study dynamics.
result Convergent orbits in GANs are small perturbations of periodic orbits, justifying slow training.
Style Miner generates stable and significant style factors for time series analysis.
problem Finding significant and stable explanatory factors in high-dimensional time series data.
method Proposes a reinforcement learning method to balance explanatory power and stability constraints.
result Outperforms existing methods by a large margin and achieves a 10% gain in R-squared explanatory power.
This text is the rejoinder following the discussion of a survey paper about minimal penalties and the slope heuristics (Arlot, 2019. Minimal penalties and the slope heuristics: a survey. Journal de la SFDS). While commenting on the remarks made by the discussants, it provides two new results about the slope heuristics …
Proposes a method to imitate active learning heuristics for better performance.
problem The performance of active learning heuristics depends on the classifier model and data structure.
method Imitates the selection of the best active learning heuristic using DAGGER.
result Outperforms state-of-the-art imitation learners and heuristics on well-known datasets.
The first step to realize automatic experimental data analysis for fusion plasma experiments is fitting noisy data of temperature and density spatial profiles, which are obtained routinely. However, it has been difficult to construct algorithms that fit all the data without over- and under-fitting. In this paper, we sh…
This research evaluates and introduces new heuristics for clustering Bitcoin blockchain entities.
problem Efficiently analyzing the vast number of Bitcoin blockchain entities.
method Examined and introduced four new heuristics for clustering Bitcoin blockchain entities.
result Introduced clustering ratio to measure heuristic effectiveness.
Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, ev…
Nemo improves WS learning pipeline by 20%.
problem Creating effective labeling heuristics for weak supervision.
method Interactive procedure for designing heuristics, strategic data selection, contextualization of heuristics.
result Improves WS learning pipeline by 20%.
This paper evaluates heuristics and hyperparameters in weight-sharing NAS methods.
problem Improving the performance of weight-sharing NAS methods.
method Systematic evaluation of heuristics and hyperparameters in weight-sharing NAS algorithms.
result Some heuristics negatively impact super-net and stand-alone performance correlation.
Interactive weak supervision learns useful heuristics from user feedback.
problem Creating useful heuristics for large labeled datasets is tedious and subjective.
method Develops an interactive framework for learning heuristics from user feedback.
result Only a few feedback iterations are needed to train models without ground truth labels.
We propose a general approach to modeling semi-supervised learning (SSL) algorithms. Specifically, we present a declarative language for modeling both traditional supervised classification tasks and many SSL heuristics, including both well-known heuristics such as co-training and novel domain-specific heuristics. In ad…
Unified framework for stable RL learning with theoretical guarantees.
problem Lack of systematic theoretical principles guiding RL post-training methods.
method Unified theoretical framework for policy-gradient estimators and optimization algorithms.
result Establishes unbiasedness, variance expressions, and convergence guarantees.
We implement a market microstructure model including informed, uninformed and heuristic-driven investors, which latter behave in line with loss-aversion and mental accounting. We show that the probability of informed trading (PIN) varies significantly during 2008. In contrast, the probability of heuristic-driven tradin…
The report evaluates heuristics for learning timescale graphical event models.
problem Lack of heuristics for determining hyper-parameters in timescale graphical event models.
method Proposed and evaluated different heuristics for hyper-parameter determination and refined an existing distance measure.
result Conclusions about the applicability of different heuristics on synthetic data.
In this paper, we tackle the problem of online semi-supervised learning (SSL). When data arrive in a stream, the dual problems of computation and data storage arise for any SSL method. We propose a fast approximate online SSL algorithm that solves for the harmonic solution on an approximate graph. We show, both empiric…
New heuristics for predicting links in multiplex networks.
problem Link prediction in networks with multiple types of connections.
method Proposed a general framework and three families of heuristics.
result Significantly outperformed baseline heuristics for ordinary networks.
Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents in…
Finding the optimal k-means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the k-means objective. We first show how to extend Lloyd's batched relocation heuristic and Hartigan's single-point relocation heuristic to take into account empty-cluster and single-poin…
Study of spacelike singularities in spherical spacetimes with scalar matter.
problem Characterize spacelike singularities in spherically symmetric spacetimes with scalar matter.
method Analyzes the properties of spacelike singularities in spherically symmetric spacetimes with scalar matter, proving inverse polynomial blow-up rates and providing a BKL-type expansion.
result Provides a rigorous description of Kasner-like singularities in spherically symmetric gravitational collapse.
Heuristic algorithms such as simulated annealing, Concorde, and METIS are effective and widely used approaches to find solutions to combinatorial optimization problems. However, they are limited by the high sample complexity required to reach a reasonable solution from a cold-start. In this paper, we introduce a novel …
Bayesian symbolic regression automates model discovery from data.
problem Learning closed-form mathematical models from data using heuristic methods.
method Probabilistic approach to symbolic regression, connecting to information theory and statistical physics.
result Probabilistic approach provides model plausibility and performance guarantees.
Training deep belief networks (DBNs) requires optimizing a non-convex function with an extremely large number of parameters. Naturally, existing gradient descent (GD) based methods are prone to arbitrarily poor local minima. In this paper, we rigorously show that such local minima can be avoided (upto an approximation …
This work explores the non-convex optimization in compressive learning and the performance of heuristics.
problem The challenge of learning from compressed representations in compressive learning.
method Numerical simulations of the non-convex optimization landscape and heuristic performance.
result Properties of the non-convex optimization landscape and heuristic performance are explored.
PiNGDA learns beneficial noise for graph augmentation stability.
problem Challenges in generating effective and stable graph augmentations.
method PiNGDA uses positive-incentive noise to scientifically analyze and generate beneficial graph augmentations.
result PiNGDA improves GCL performance by learning beneficial noise on graph topology and attributes.
In kernel methods, the median heuristic has been widely used as a way of setting the bandwidth of RBF kernels. While its empirical performances make it a safe choice under many circumstances, there is little theoretical understanding of why this is the case. Our aim in this paper is to advance our understanding of the …
The learning rate warmup heuristic achieves remarkable success in stabilizing training, accelerating convergence and improving generalization for adaptive stochastic optimization algorithms like RMSprop and Adam. Here, we study its mechanism in details. Pursuing the theory behind warmup, we identify a problem of the ad…
Redundancy improves learning stability and generalization in structured systems.
problem Understanding redundancy in structured systems for learning and generalization.
method Developed a theoretical framework that redefines redundancy as a geometric principle unifying various measures.
result Redundancy balances structure and coupling, leading to optimal stability and generalization.
Partially performative prediction studies how predictive models influence future data.
problem Distribution shift in predictive models due to endogenous and exogenous factors.
method Generalizing performative prediction to capture both endogenous and exogenous sources of distribution shift.
result Developed online analogues of performative stability and optimality for partially performative environments.
We propose a technique for declaratively specifying strategies for semi-supervised learning (SSL). The proposed method can be used to specify ensembles of semi-supervised learning, as well as agreement constraints and entropic regularization constraints between these learners, and can be used to model both well-known h…
Study models opaque financial markets using multi-agent simulation.
problem Challenges in financial markets with obscured data availability.
method Multi-agent simulation with small-scale meta-heuristic methods.
result Captures bilateral market dynamics of OTC trading.
Two heuristics solve dynamic multiple travelling salesmen problems.
problem Dynamic routing with unknown customers.
method Balanced dynamic closest vehicle heuristic and balanced dynamic assignment vehicle heuristic.
result Continuous approximation models for strategic dynamic routing.
A* is a popular path-finding algorithm, but it can only be applied to those domains where a good heuristic function is known. Inspired by recent methods combining Deep Neural Networks (DNNs) and trees, this study demonstrates how to train a heuristic represented by a DNN and combine it with A*. This new algorithm which…
Deep RL learns 2-opt heuristics to improve TSP solutions.
problem Improving TSP solutions beyond initial heuristics.
method Deep reinforcement learning to learn 2-opt operations.
result Learned policies improve solutions faster than previous methods.
Clustering algorithms have regained momentum with recent popularity of data mining and knowledge discovery approaches. To obtain good clustering in reasonable amount of time, various meta-heuristic approaches and their hybridization, sometimes with K-Means technique, have been employed. A Kalman Filtering based heurist…
RL improves combinatorial optimization by automating heuristic search.
problem Hard combinatorial optimization problems with suboptimal solutions.
method Training RL agents to solve these problems.
result RL can outperform traditional algorithms in solving complex problems.