Algorithm estimates tensors from sparse observations with robust error bounds.
problem Estimating tensors from sparse noisy observations.
method Similarity-based collaborative filtering algorithm for tensor estimation.
result Achieves sample complexity nearly matching conjectured lower bound.
The paper provides entrywise bounds for Sparse PCA, improving upon previous results.
problem Sparse Principal Component Analysis (PCA) recovery error characterization in spectral or Frobenius norms.
method Entrywise ℓ2,∞ bounds for Sparse PCA under general high-dimensional subgaussian design, using sparsistent algorithms. result Improved entrywise bounds for Sparse PCA, finer characterization of estimation error.
The paper proposes methods for predicting missing values in mixed data matrices.
problem Matrix completion for mixed data types (continuous, binary, ordinal).
method Generalized latent factor models for low-rank matrix estimation with entrywise consistency.
result Tight probabilistic error bounds for the proposed estimators.
Proposes a new algorithm to estimate invariant subspaces across multilayer networks.
problem Estimating invariant subspaces across heterogeneous multiple networks.
method Bias-corrected joint spectral embedding algorithm that recursively calibrates diagonal bias and iteratively updates the subspace estimator.
result Established entrywise subspace perturbation bound and entrywise eigenvector central limit theorem for the algorithm.
We study the column subset selection problem with respect to the entrywise ℓ1-norm loss. It is known that in the worst case, to obtain a good rank-k approximation to a matrix, one needs an arbitrarily large nΩ(1) number of columns to obtain a (1+ε)-approximation to the best entrywise ℓ1-norm low ra…
This paper is concerned with the problem of top-K ranking from pairwise comparisons. Given a collection of n items and a few pairwise comparisons across them, one wishes to identify the set of K items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model --- the Bradley-Te…
We develop embeddings for nonlinear subspaces preserving vector norms.
problem Preserving vector norms in nonlinear subspaces.
method Low-distortion embeddings for subspaces under nonlinear transformations.
result First low-distortion embeddings for a wide class of nonlinear functions.
EPMF factorizes matrices by adjusting their entries to match a specified power.
problem Factorizing matrices with adjusted entries to match a specified power.
method Analyzes the computational complexity of exact and approximate EPMF problems.
result Exact EPMF is strongly NP-hard, but can be solved in polynomial time when rank is fixed.
Simple method for estimating missing panel data entries with confidence intervals.
problem Estimating missing values in panel data with staggered adoption.
method Simple matrix algebra and singular value decomposition for estimation, with data-driven confidence intervals.
result Confidence intervals match non-asymptotic lower bounds, proving instance optimality.
Max-rank improves multiple testing in conformal prediction.
problem Simultaneous testing of multiple hypotheses in scientific inquiries.
method Introduces max-rank, a novel correction for positive dependencies in simultaneous testing.
result Max-rank efficiently controls family-wise error rate and improves predictive uncertainty estimates.
We consider the weak detection problem in a rank-one spiked Wigner data matrix where the signal-to-noise ratio is small so that reliable detection is impossible. We propose a hypothesis test on the presence of the signal by utilizing the linear spectral statistics of the data matrix. The test is data-driven and does no…
Improves detection of low-rank signals from noisy data matrices.
problem Statistical detection of low-rank signals in noisy data matrices.
method Entrywise pre-transforming data matrix for non-Gaussian noise, sharp phase transition thresholds, central limit theorem for linear spectral statistics, hypothesis test.
result Improves detection of low-rank signals from noisy data matrices, generalizing known results.
Study shows fast rates for inverse reinforcement learning with linear rewards.
problem Entropy-regularized min-max inverse reinforcement learning in finite-horizon MDPs.
method Structural and statistical analysis of Min-Max-IRL with pseudo-self-concordance.
result Both trajectory-level KL divergence and parameter error decay at O(n−1). A new method for fair PCA ensures balanced error across groups.
problem Balancing approximation error across different groups in multi-group data.
method Iterative method to compute fair principal components minimizing max group-wise reconstruction error.
result Preserves the containment property of standard PCA and reduces to standard PCA for single-group data.
Study introduces statistical mechanics for min-max problems.
problem Understanding the properties of min-max problems in high dimensions.
method Statistical mechanical formalism for analyzing min-max problems.
result Derives the relationship between training data and generalization error.
Max-min margin Markov networks improve consistency in structured prediction.
problem Statistical inconsistency in max-margin methods for structured prediction.
method Defining a max-min margin formulation to overcome statistical inconsistency.
result Proves consistency and provides an explicit algorithm with finite sample generalization bounds.
Paper corrects Max-Margin loss for multi-label tasks.
problem Max-Margin loss inconsistency in multi-label classification.
method Introduced Restricted-Max-Margin loss.
result Consistent loss for multi-label tasks under milder conditions.
A new method for streaming PCA provides confidence intervals for eigenvector entries.
problem Uncertainty quantification for individual entries in streaming PCA.
method Oja's algorithm, Bernstein-type concentration bound, Central Limit Theorem, subsampling algorithm.
result Sharp concentration bound and Central Limit Theorem for streaming PCA entries.
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.
Max-margin classifiers can overfit without harming performance in high dimensions.
problem Understanding how max-margin classifiers generalize in high-dimensional settings.
method Stylized setting with Gaussian features and labels, proportional asymptotics, and random neural network features.
result Exact expressions for limiting generalization error and conditions for 'benign overfitting'.
Efficiently finds sparse solutions to max-plus equations for convex regression.
problem Finding sparse solutions to max-plus equations for convex multivariate regression.
method Polynomial-time algorithm for sparse approximate solutions.
result Optimal piecewise-linear fitting with minimum number of regions.
Max-margin classifiers' behavior is studied in high dimensions with non-Gaussian features.
problem Understanding the role of featurization maps and high-dimensional misclassification error.
method High-dimensional asymptotics, Gaussian model, support vector representation.
result Asymptotic behavior of max-margin classifiers is determined by feature covariance and label covariance.
AdaBoost improves binary classification in robust one-bit compressed sensing with adversarial errors.
problem Binary classification in robust one-bit compressed sensing with adversarial errors.
method AdaBoost and max-ℓ1-margin-classifier approach, with convergence rates improved under certain feature conditions. result Improved convergence rates and explanation for harmless interpolating adversarial noise.
A new method for constrained Bayesian optimization using Max-Value Entropy Search.
problem Optimizing expensive functions with unknown constraints.
method Constrained Max-value Entropy Search (cMES), a novel acquisition function.
result cMES outperforms prior work on constrained hyperparameter optimization problems.
Max-affine regression method converges linearly using GD and SGD.
problem Regression of max-affine models in signal processing and statistics.
method Gradient descent and mini-batch stochastic gradient descent analysis.
result GD and SGD converge linearly to a neighborhood of the ground truth under sub-Gaussian assumptions.
The Gumbel-max trick and its extensions simplify sampling from categorical distributions in machine learning.
problem Sampling from categorical distributions with unnormalized probabilities.
method Extensions of the Gumbel-max trick for various applications.
result Simplified and efficient methods for sampling and gradient estimation.
We reformulate LIPs as min-max problems for easier solution.
problem Recovering signals from few linear measurements.
method Proposed a min-max reformulation of LIPs.
result Saddle points characterize solutions to LIPs.
Bayesian optimization for function-valued responses, addressing worst case deviations.
problem Optimizing expensive functions with functional responses, focusing on worst case performance.
method Min-Max Functional Bayesian Optimization (MM-FBO) using Gaussian process surrogates and functional principal component analysis.
result MM-FBO consistently outperforms existing methods in synthetic and real-world applications.
Optimal test for detecting signal in noisy matrix model.
problem Signal detection in noisy matrix models with unknown rank.
method Hypothesis test based on linear spectral statistics, optimal under Gaussian noise.
result Optimal test under Gaussian noise, improved with non-Gaussian noise.
New method improves AI system's uncertainty estimation.
problem Precise uncertainty estimation in AI predictions.
method Information Aware Max-Norm Dirichlet Networks.
result Outperforms state-of-the-art neural networks for uncertainty estimation.
FLASH-MAX predicts electromagnetic fields from sparse data in seconds.
problem Predicting homogeneous electromagnetic fields from sparse pointwise observations.
method Exact-by-construction neural network architecture that satisfies Maxwell's equations symbolically.
result FLASH-MAX achieves sub-1% relative validation error from 1K sparse observations in seconds.
We develop an efficient algorithm for low-rank approximation with improved approximation guarantees.
problem Optimal low-rank approximation of matrices with ℓ1 norm constraints. method Polynomial time column subset selection-based algorithm achieving ildeO(k1/2)-approximation. result Improved approximation guarantees for ℓ1 low-rank approximation. Matrices of (approximate) low rank are pervasive in data science, appearing in recommender systems, movie preferences, topic models, medical records, and genomics. While there is a vast literature on how to exploit low rank structure in these datasets, there is less attention on explaining why the low rank structure ap…
Study on double descent behavior in two-layer neural networks for binary classification.
problem Understanding the double descent phenomenon in model test error.
method Two-layer neural network with ReLU activation for binary classification. Quantified model size by sample-to-dimension ratio. Empirical risk minimization using Convex Gaussian Min Max Theorem.
result Observed and investigated the double descent behavior of model test error.
Model reveals double descent in binary linear classification.
problem Investigating classification error in high-dimensional binary linear classification.
method Gradient descent on logistic loss, maximum-likelihood, max-margin (SVM) solutions, and convex Gaussian min-max theorem.
result Double descent phenomenon observed in classification error for varying overparameterization ratio.
Improved online learning for fuzzy min-max neural networks.
problem Classification performance issues due to expansion and contraction steps.
method Proposes an improved online learning algorithm without contraction for overlapping hyperboxes.
result Significant improvement in classification accuracy and stability.
New AMP algorithm estimates signals and latent variables in mixed regression models.
problem Estimating signals and latent variables in mixed regression models.
method Approximate Message Passing (AMP) algorithm for matrix GLM.
result State evolution recursion and optimal denoising functions for precise error minimization.
The Lloyd-Max algorithm is a classical approach to perform K-means clustering. Unfortunately, its cost becomes prohibitive as the training dataset grows large. We propose a compressive version of K-means (CKM), that estimates cluster centers from a sketch, i.e. from a drastically compressed representation of the traini…
Model-free approach to hedge path-dependent options using min-max optimization.
problem Hedging path-dependent options with maturity T using a static portfolio of vanilla options.
method Model-free approach based on primal-dual Martingale Optimal Transport (MOT) problem, solving a min-max optimization problem.
result Provides theoretical bounds on hedging error at maturity T.
New polynomial-time solutions found for training ReLU networks, mirroring Max-Cut complexity.
problem Training two-layer ReLU neural networks with weight decay regularization.
method Developed a convex formulation and randomized algorithm to find approximate global optimizers.
result First polynomial-time approximation guarantees and hardness of approximation results for regularized ReLU networks.
This paper presents a method to summarize directed graphs while preserving edge information.
problem Summarizing directed graphs while maintaining edge directionality.
method A model based on minimizing reconstruction error with non-negative constraints, related to Max-Cut criterion, using multiplicative update algorithms.
result The proposed method identifies compressed nodes and directed compressed relations, providing a more accurate representation of directed graphs.
The paper tackles dictionary learning with almost sure error constraints.
problem Achieving desirable features in data representation with almost sure error constraints.
method Imposes almost sure recovery constraints and reformulates the problem as a convex-concave min-max problem, solved using gradient descent-ascent.
result Demonstrates the effectiveness of the proposed method in achieving almost sure error constraints in dictionary learning.
The report studies ranking from pairwise comparisons in graphs, achieving optimal error bounds and proposing efficient algorithms.
problem Ranking items from pairwise comparisons in general graphs and graphs with locality.
method Maximum likelihood estimation (MLE) and preconditioned gradient descent for general graphs; divide-and-conquer algorithms for graphs with locality.
result MLE achieves optimal error bounds in general graphs and identifies conditions for locality.
We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are noisy realizations of a linear transformation X of the sum of an approximately) low rank matrix Θ⋆ with a second matrix Γ⋆ endowed with a complementary …
Optimal transfer learning for missing not-at-random matrix completion using source data.
problem Matrix completion in a Missing Not-at-Random setting with incomplete and noisy source data.
method Active sampling of rows and columns, feature shift in latent space, minimax lower bounds, computationally efficient estimation framework.
result Achieves minimax lower bound for active sampling setting, avoiding incoherence assumptions.
Optimal best arm identification for multi-objective bandits with fixed error probability.
problem Identifying the best arm for each of multiple objectives with fixed confidence.
method Surrogate proportions to sample arms at each time step, eliminating max-min optimisation.
result Asymptotically optimal algorithm for multi-objective best arm identification.
New algorithm identifies optimal subtrees in fixed-budget tree search.
problem Identifying optimal subtrees in fixed-budget Monte Carlo Tree Search.
method ε-agnostic algorithm for max-min action identification.
result Misidentification probability decays exponentially with sample size.
New algorithm for mean estimation in add-remove model achieves optimal error.
problem Mean estimation in add-remove model of differential privacy.
method Proposed new algorithm achieving min-max optimality.
result Achieves best possible constant in mean squared error for all ε.