New algorithm tackles non-convex matrix completion in semi-random settings.
problem Matrix completion in semi-random environments with varying observation probabilities.
method Proposes a pre-processing step to re-weight semi-random input, followed by a nearly-linear time algorithm.
result Recovering ground-truth matrix using non-convex local minima after pre-processing.
We propose semi-random features for nonlinear function approximation. The flexibility of semi-random feature lies between the fully adjustable units in deep learning and the random features used in kernel methods. For one hidden layer models with semi-random features, we prove with no unrealistic assumptions that the m…
New method robust to semi-random sparse recovery, nearly-linear time.
problem Brittleness of fast sparse recovery algorithms under generative model changes.
method Designing a new iterative method robust to semi-random model.
result Proves robustness of new method to semi-random generative models.
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
Spectral ranking methods are improved against semi-random graph sampling.
problem Improving spectral ranking methods in semi-random graph sampling.
method Investigating entry-wise error of spectral algorithms against a semi-random adversary.
result Asymptotic performance can be recovered by reweighting observed edges.
SDP relaxation for Sub-Gaussian Mixture Model achieves optimal error bound and robustness.
problem Estimating discrete clustering structures in Sub-Gaussian Mixture Model.
method Hidden integrality property of SDP relaxation and semi-random robustness analysis.
result SDP relaxation achieves optimal error bound and robustness in semi-random setting.
KSS method converges and recovers correct clustering under certain conditions.
problem Subspace clustering for semi-randomly sampled data.
method Local convergence analysis and recovery guarantee for KSS method.
result KSS method converges superlinearly and finds correct clustering within loglog N iterations.
Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a \textit{semi-ran…
Improved SGD for robust linear and ReLU regression with adversarial corruptions.
problem Robust regression with adversarial corruptions in streaming data.
method Stochastic gradient descent (SGD-exp) with exponentially decaying step size.
result Nearly linear convergence to true parameter with up to 50% Massart corruption rate.
Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model…
Study on ReLU regression with Massart noise, achieving exact parameter recovery.
problem Efficiently fitting ReLUs to data in the presence of Massart noise.
method Developed an efficient algorithm for exact parameter recovery under mild assumptions.
result Achieved exact parameter recovery in ReLU regression with Massart noise.
A fast, non-iterative method for missing value imputation using random trees.
problem Missing value imputation in large and high-dimensional datasets.
method Recursive semi-random hyperplane cuts to assign observations to buckets and calculate weighted averages as imputations.
result Significantly faster than chained equations and scales well to large datasets.
MAX uses ensemble models to efficiently explore novel situations in reinforcement learning.
problem Efficient exploration in reinforcement learning.
method Model-based active exploration using ensemble forward models and Bayesian disagreement.
result MAX is at least an order of magnitude more efficient than baselines in semi-random environments.
Efficient algorithm detects communities in noisy graphs with robustness.
problem Community detection in stochastic block models with adversarial corruptions.
method Efficient algorithm using semidefinite programming for robust clustering.
result Achieves error O(ε)+e−2C(1±o(1)) for ε-fraction of corruptions. Metric learning is a key problem for many data mining and machine learning applications, and has long been dominated by Mahalanobis methods. Recent advances in nonlinear metric learning have demonstrated the potential power of non-Mahalanobis distance functions, particularly tree-based functions. We propose a novel non…
New formula refutes random CSPs with fewer constraints.
problem Refuting random constraint satisfaction problems efficiently.
method Introduced a non-backtracking matrix and proved an Ihara-Bass formula.
result Efficiently refutes random CSPs with fewer constraints.
Paper improves ℓ0-SSC for noisy data by proving SDP and proposing Noisy-DR-ℓ0-SSC.
problem Noisy data and less restrictive subspace affinity in sparse subspace clustering.
method Proposes Noisy-DR-ℓ0-SSC, which projects data onto a lower dimensional space and then applies noisy ℓ0-SSC. result Theoretical guarantee on the correctness of noisy ℓ0-SSC in terms of SDP on noisy data. This paper improves linear system solving by optimizing matrix diagonal scaling.
problem Improving the condition number of a matrix for faster iterative methods.
method Left or right diagonal rescaling of the matrix A, with new bounds and algorithms.
result Jacobi preconditioning reduces A's condition number to within a quadratic factor of the best possible scaling.
Study shows Julia sets and gasket limit sets are quasiconformally different.
problem Quasiconformal non-equivalence of Julia sets and gasket limit sets.
method Proved quasiconformal non-equivalence of Julia sets and gasket limit sets.
result Julia sets and gasket limit sets are quasiconformally different.
New deep learning model for matching sets of items, preserving exchangeability.
problem Matching two different sets of items while preserving exchangeability.
method Exchangeable deep neural networks architecture and efficient training framework.
result Significant improvements in fashion set recommendation and group re-identification.
Study shows non-symmetric convex sets have full boundary limits.
problem Understanding boundaries of non-symmetric convex sets.
method Proved using proximal limit set analysis.
result Proximal limit set equals full projective boundary for non-symmetric irreducible divisible convex sets.
The paper analyzes set-to-set matching with neural networks, focusing on theoretical generalization.
problem Theoretical analysis of set-to-set matching with neural networks.
method Generalization error analysis of set-to-set matching with neural networks.
result Theoretical insights into the behavior of set-to-set matching models.
Generative model learns to autoencode and generate sets of images.
problem Learning to represent and generate sets of images with unknown number of sets.
method Set Distribution Networks (SDNs) learn set encoder, discriminator, generator, and prior.
result SDNs can reconstruct and generate sets of images with preserved attributes.
Study on cold and freezing sets in digital images.
problem Properties of cold sets in digital images.
method Analysis of properties and relationships between cold and freezing sets.
result Examined relationships between cold and freezing sets.
Paper solves whether zero sets are mapping degree sets.
problem Whether finite sets containing zero are mapping degree sets.
method Examined oriented closed connected manifolds of the same dimension.
result Affirmative answer given for both integer and rational settings.
Maps sets to probability distributions to minimize information loss.
problem Learning to map sets to probability distributions to preserve information.
method Relates set operations to probability distribution interpolations and demonstrates a preliminary solution.
result Experimental results show the effectiveness of the set embedding approach.
Unified framework for generating set-valued outputs.
problem Handling unordered set outputs with varying sizes.
method Sequential Set Generation (SSG) framework.
result SSG outperforms baseline methods in experiments.
New model predicts sets from feature vectors without discontinuity issues.
problem Discontinuity issues in predicting sets from feature vectors.
method General model that respects set structure, auto-encodes point sets, predicts bounding boxes, and attributes.
result Model successfully predicts sets from a single feature vector without discontinuity.
New set-valued star-shaped risk measures introduced for better risk assessment.
problem Improving risk assessment in financial contexts.
method Developed new set-valued star-shaped risk measures and proved their representation theorems.
result Set-valued star-shaped risk measures can be represented as unions of set-valued convex risk measures.
We introduce the concept of hereditarily non uniformly perfect sets, compact sets for which no compact subset is uniformly perfect, and compare them with the following: Hausdorff dimension zero sets, logarithmic capacity zero sets, Lebesgue 2-dimensional measure zero sets, and porous sets. In particular, we give an exa…
Study dynamics and topology of flows near non-saddle sets or W-sets.
problem Understanding the dynamics and topology of flows near specific invariant sets.
method Cohomological relations and global properties analysis.
result Dynamical classification of surfaces and robustness of non-saddle-sets.
Bayesian optimization for set inputs using approximate set kernels.
problem Permutation-invariant optimization over sets with black-box functions.
method Developed a Bayesian optimization method with set kernel, efficient approximate set kernel, and constrained acquisition function.
result Our method outperforms other methods in numerical experiments.
The study explores mapping degree sets and their properties for manifolds.
problem Understanding the structure and properties of mapping degree sets for manifolds.
method Analyzes the properties of mapping degree sets and their relationships with self-mapping degree sets.
result Not every multiplicative set containing 0,1 is a self-mapping degree set.
This paper studies the geometry of minimum-volume confidence sets for multinomial parameters.
problem Determining if minimum-volume confidence sets for multinomial outcomes are disjoint.
method Enumerating and covering the continuous regions of the exact p-value function to study the geometry of minimum-volume confidence sets.
result The geometry of minimum-volume confidence sets for multinomial parameters is studied, providing insights into their structure and properties.
Model learns set representations through optimized permutations.
problem Challenges in learning set representations due to permutation-invariance.
method Proposes a Permutation-Optimisation module to learn set permutations.
result Achieves state-of-the-art results on various set learning tasks.
Deep Sets approximates functions on sets with high-dimensional latent space.
problem Modeling functions of sets (permutation-invariant functions).
method Deep Sets, a method known to be a universal approximator for continuous set functions.
result Deep Sets' universal approximation property is only guaranteed with a sufficiently high-dimensional latent space.
Study online learning with set-valued feedback, showing differences between deterministic and randomized approaches.
problem Online learning with set-valued feedback, where labels are sets rather than single labels.
method Introduced new combinatorial dimensions (Set Littlestone and Measure Shattering) to characterize learnability.
result Characterized deterministic and randomized online learnability, and established bounds for various learning settings.
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.
The paper links set cuspidality to function regularity and flatness.
problem Linking set cuspidality to function regularity and flatness.
method Analyzes arc-smooth functions and their properties on various sets.
result Establishes a precise link between set cuspidality and function regularity.
This work establishes properties on diffeological structures for set-valued maps and measures.
problem Establish rigorous properties on diffeological structures for set-valued maps and measures.
method Using diffeologies, the authors link various structures including set-valued maps, relations, gradients, measures, and shape analysis.
result Established rigorous properties on sample diffeologies.
MAGIC generates image collages from set templates using attention and set representations.
problem Generating image collages from set templates is challenging for classical models.
method Memory Attentive Generation of Image Collages (MAGIC) using Set-Transformer layers and set-pooling.
result MAGIC can generate image collages from set templates in one forward pass.
Causal Set Theory's Hauptvermutung is resolved in two ways, one of which is true.
problem Formulating and resolving the Hauptvermutung in Causal Set Theory.
method Two mathematically well-defined formulations of the Hauptvermutung, one of which is true.
result The Hauptvermutung is true when finite sets are replaced by countable sets.
DMPS learns set data by connecting graph and set learning.
problem Lack of relational learning for set data.
method Deep Message Passing on Sets (DMPS) that connects graph and set learning.
result DMPS achieves competitive or superior results on synthetic and real-world datasets.
We adapted the Covertype data set for unsupervised learning.
problem Lack of suitable unsupervised learning data sets.
method Transformed the Covertype data set into the Wilderness Area data set.
result The Wilderness Area data set is more suitable for unsupervised learning.
Find limiting sets for digital cones and suspensions.
problem Digital topology cone and suspension constructions.
method Identify (m, n)-limiting sets, especially (0, 0)-freezing sets.
result Discover (0, 0)-limiting sets for digital cones and suspensions.
Analytic sets with unique infinite tangent cone are algebraic.
problem Characterizing analytic sets with unique infinite tangent cones.
method Analytic and algebraic set properties, degree of complex algebraic sets.
result Degree of Lipschitz normally embedded sets equals their infinite tangent cone degree.
Study freezing sets for digital images in a 2D grid.
problem Determine minimal freezing sets for digital images.
method Prove methods to obtain freezing sets for digital images (X, c_i) where X is a subset of Z^2.
result Examples show how methods can lead to the determination of minimal freezing sets.
Fuzzy prediction sets generalize binary predictions to include elements at varying confidence levels.
problem Binary prediction sets are limited; fuzzy prediction sets offer richer guarantees.
method Generalize prediction sets to fuzzy sets, showing they are e-values with merging properties.
result Optimal e-values lead to optimal fuzzy prediction sets, including optimal conformal prediction.