Online gradient descent can simulate complex computations.
problem Understanding the fine-grained behavior of online gradient descent is hard.
method Proving online gradient descent can encode arbitrary polynomial-space computations.
result It is impossible to reason efficiently about the fine-grained behavior of online gradient descent under weak complexity-theoretic assumptions.
In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite prog…
Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods. While there has been a large body of work on algorithms for various ERM problems, the exact computational complexity of ERM is still not understood. We address this issue for multiple popular ERM problems…
Topological quantum computers use hyperbolic knots for computations.
problem The difficulty of calculating quantum invariants of knots.
method Using hyperbolic knots to compute topological quantum computer invariants.
result The hyperbolic geometry of knots is unlikely to be useful for topological quantum computation.
Tyler's M-estimator's phase transition at DS-SNR = 1 is resolved.
problem Robust Subspace Recovery
method Tyler's M-estimator
result TME converges exactly to the true subspace for DS-SNR >= 1 under a new stability condition.
Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is importa…
Bayesian structure learning is the NP-hard problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computational worst-case complexity of exact Bayesian structure learning under graph theoretic restrictions on the super-structure. The super-structure …
Optimal trend-following strategy uses simple EMA, avoiding complex cherry-picked signals.
problem Cherry-picking signals for trend-following strategies.
method Simple EMA for trend capture, avoiding complex indicators.
result Simple EMA is optimal for capturing trend, complex indicators are risky.
We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈Rd, r hidden units with weights {wi}1≤i≤r and output y∈R, i.e., $y=\sum_{i=1}^r σ( \boldsymbol w_i…
New method reduces distributed non-convex optimization rounds and bits.
problem Efficiently optimizing non-convex models in distributed systems.
method Introduces permutation compressors to reduce communication complexity.
result PermK compressors lead to significant communication complexity improvements.
Proving that next-token prediction makes language models generate coherent long documents.
problem Understanding why language models generate coherent documents despite focusing on next-token prediction.
method Proving the power of next-token prediction in learning longer-range structure using Recurrent Neural Networks (RNN).
result Optimizing next-token prediction in RNNs yields a model that closely approximates the training distribution, even for long-range coherence.
Study shows memory needs grow with task sequence length in continual learning.
problem Challenges in retaining aptitude for multiple learning tasks sequentially.
method Complexity-theoretic study using communication complexity and multiplicative weights update.
result Memory needs grow linearly with task sequence length, suggesting intractability.
TQFT invariants are either easy or hard to compute, depending on the TQFT type.
problem Computing TQFT invariants on closed 3-manifolds.
method Application of a dichotomy result for weighted constraint satisfaction problems over C.
result TQFT invariants are either solvable in polynomial time or #P-hard. A new algorithm splits Gaussian processes for efficient streaming data.
problem Poor scaling of Gaussian processes in streaming data.
method Sequential partitioning of input space and localized Gaussian process fitting.
result The algorithm achieves linear memory complexity and superior time and space complexity.
This paper develops a general framework for metric learning in RKHS with theoretical guarantees.
problem Learning a metric in RKHS from triplet comparisons.
method Develops a general RKHS framework for metric learning with theoretical guarantees.
result Provides novel generalization guarantees and sample complexity bounds for metric learning in RKHS.
Theoretical analysis shows pretext-based self-supervised learning can be boosted by downstream data under certain conditions.
problem Theoretical analysis of pretext-based self-supervised learning and downstream data refinement.
method Theoretical analysis and experiments on synthetic and real-world datasets.
result Theoretical lower bounds and experiments show that downstream data refinement can boost or hurt performance depending on conditions.
Study on size and depth of neural networks for approximating benign functions, showing barriers and explicit results.
problem Understanding how size and depth of neural networks affect their ability to approximate benign functions.
method Analyzing ReLU networks for benign functions, proving barriers and explicit results.
result Explicit benign functions that cannot be approximated by networks of certain sizes or depths, showing barriers to size and depth separation.
This paper proves a generalization bound for complex-valued neural networks scaling with spectral complexity.
problem Ensuring the performance of complex-valued neural networks on unseen data.
method Theoretical derivation using Maurey Sparsification Lemma and Dudley Entropy Integral, empirical validation on various datasets.
result The spectral complexity of weight matrices is a significant factor in the generalization ability of complex-valued neural networks.
Study on SignGD optimization of two-layer transformer on noisy data.
problem Understanding how SignGD optimizes transformers and its generalization.
method Analysis of a two-layer transformer with SignGD on a linearly separable noisy dataset.
result SignGD converges fast but has poor generalization on noisy data.
New framework formalizes RLHF trilemma: improving safety, fairness, and robustness is computationally infeasible.
problem Aligning large language models with diverse human values while maintaining computational feasibility and robustness.
method Complexity-theoretic analysis integrating statistical learning theory and robust optimization.
result Achieving both representativeness (epsilon <= 0.01) and robustness (delta <= 0.001) for global-scale populations requires super-polynomial operations.
New algorithms learn robust policies from shifted distributions.
problem Learning robust policies in environments with distributional shifts.
method Two novel model-free algorithms: distributionally robust Q-learning and variance-reduced distributionally robust Q-learning.
result Achieves minimax sample complexity upper bound of ildeO(∣S∣∣A∣(1−γ)−4ε−2). Efficient tests achieve best error rates in high-dimensional hypothesis testing.
problem Achieving optimal error rates in computationally efficient hypothesis testing.
method Linear spectral statistics and low-degree likelihood ratio analysis.
result An efficient test achieves the best possible error rates among all computationally efficient tests.
New proof shows a link problem is hard without complex links.
problem Deciding if a link contains a trivial sublink is hard.
method Reduces from Independent Set Problem, avoiding Brunnian links.
result The Trivial Sublink Problem is NP-hard due to mod 2 linking.
Bayesian neural networks learn efficiently at infinite width, matching polynomial-width performance.
problem Understanding the inductive bias of infinite-width neural networks.
method Analyzing the reduced entropy and using subsampling techniques.
result The Bayesian mean-field learner generalizes exactly on polynomially-bounded targets.
Complexity of counting homomorphisms in 3-manifold invariants is hard.
problem Computational complexity of counting homomorphisms in 3-manifold invariants.
method Study the action of the mapping class group on homomorphisms, using combinatorial topological quantum field theory.
result Proving #P-completeness of counting homomorphisms for closed 3-manifolds and knot complements. Proposes a weaker faithfulness assumption for causal discovery.
problem Violation of the faithfulness assumption in causal discovery.
method Proposes a new assumption called 2-adjacency faithfulness and a modified Grow and Shrink algorithm.
result Proves the correctness of the modified algorithm under weaker assumptions.
Paper simplifies balancing weights by relaxing outcome assumptions.
problem Estimating missing outcomes in a target population.
method Relaxes outcome assumptions to simplify balancing weights.
result Balancing weights can be simplified with convex loss and minimum worst-case bias.
Directed graphical models provide a useful framework for modeling causal or directional relationships for multivariate data. Prior work has largely focused on identifiability and search algorithms for directed acyclic graphical (DAG) models. In many applications, feedback naturally arises and directed graphical models …
Study finds rigidity of biconservative hypersurfaces in space forms without curvature assumptions.
problem Investigating biconservative hypersurfaces in space forms without scalar curvature assumptions.
method Introduced a novel divergence-free tensor to derive results without curvature assumptions.
result Rigidity results for biconservative hypersurfaces in space forms without scalar curvature assumptions.
Paper relaxes independence assumption for non-centered data.
problem Failing to account for dependencies in data leads to model failures.
method Proposes 'Kronecker-sum-structured mean' assumption to relax zero-mean requirement.
result Models with nonconvex but unimodal log-likelihoods can be solved efficiently.
New algorithm estimates causal effects for non-Gaussian data.
problem Estimating causal effects in non-Gaussian distributions.
method Generalized k-Triangle Faithfulness Assumption and Edge Estimation Algorithm.
result Uniformly consistent estimates of causal effects.
New ITID assumption improves generalization in practical tasks.
problem Generalization theories fail to interpret many generalization phenomena and guide practical learning tasks due to the IID assumption.
method Proposes ITID assumption to consider task properties, derives a new generalization bound, and introduces an invariance enhancement algorithm.
result Demonstrates the effectiveness of the new generalization theory in improving practical generalization performance.
Proposes an EM method for learning from positive and unlabeled data with random selection assumption.
problem Learning from positive and unlabeled data with random selection assumption.
method Proposes an EM method to learn under the assumption that positive examples are selected at random, conditioned on some attributes.
result The proposed method outperforms state-of-the-art methods for learning under the selected completely at random assumption.
Improved k-NN active learning with local smoothness assumption.
problem Active learning convergence rates under smoothness assumptions.
method Designing an active learning algorithm with better convergence rate using local smoothness assumption for k-NN.
result Better convergence rate than in passive learning.
The paper clarifies the distinction between CATE and ITE under ignorability assumptions.
problem Confusion between CATE and ITE hinders personalized effect estimation.
method Clarifies the distinction between CATE and ITE under ignorability assumptions.
result CATE and ITE are not necessarily the same under ignorability assumptions.
New assumptions and algorithm solve offline two-player zero-sum Markov games.
problem Solving offline two-player zero-sum Markov games under insufficient assumptions.
method Proposed unilateral concentration assumption and pessimism-type algorithm.
result Algorithm efficiently learns Nash equilibrium under unilateral concentration.
The paper relaxes assumptions for analyzing stochastic optimization algorithms.
problem Analyzing the convergence of stochastic gradient algorithms under weaker variance assumptions.
method Building on and extending a connection to the Halpern iteration, the paper analyzes algorithms for convex nonsmooth optimization and min-max problems.
result Rates for optimality measures are obtained without requiring boundedness of the feasible set for problems beyond simple constrained optimization.
Unified parametric assumption improves convergence guarantees for nonconvex optimization.
problem Weak convergence guarantees for nonconvex optimization.
method Introducing a novel unified parametric assumption.
result Unified convergence theorem for gradient-based methods.
Revisits causal inference identifiability with positivity assumption.
problem General identifiability in causal inference without positivity assumption.
method Introduces new algorithm sound and complete under positivity assumption.
result New algorithm connects general identifiability to classical identifiability.
Emputation learns imputation models guided by missingness assumptions.
problem Learning imputation models for missing data given observed data.
method Guided by specific missingness assumptions, Emputation trains a deep generative model to learn the extrapolation distribution of missing variables.
result The population minimizer of the emputation risk recovers the target extrapolation distribution under various identification assumptions.
A new learning method uses data to learn from large model sets.
problem Learning with large sets of candidate models where uniform convergence is hard.
method Data-dependent learning that incorporates empirical data less reliant on prior assumptions.
result Demonstrates improved generalization in various learning assumptions.
The paper bounds and identifies joint probabilities in causal inference with monotonicity assumptions.
problem Bounding and identifying joint probabilities of potential outcomes and observed variables under monotonicity assumptions.
method Proposes new families of monotonicity assumptions, formulates bounding problem as linear programming, introduces new monotonicity assumption for identification.
result Validated methods through numerical experiments and applied to real-world datasets.
This paper introduces PM and PMLP to enhance SSL by considering probability density and cluster assumptions.
problem Insufficient utilization of unlabeled data in SSL.
method Introduces PM to discern similarity and PMLP to consider cluster assumption in label propagation.
result PMLP outperforms other methods in SSL tasks.
For binary classification we establish learning rates up to the order of n−1 for support vector machines (SVMs) with hinge loss and Gaussian RBF kernels. These rates are in terms of two assumptions on the considered distributions: Tsybakov's noise assumption to establish a small estimation error, and a new geometr…
Neurosymbolic predictors fail to model uncertainty under independence assumption.
problem Neurosymbolic predictors' reliance on independence assumption limits their ability to model uncertainty.
method Formal analysis of NeSy predictors under independence assumption.
result Assuming independence among symbolic concepts prevents NeSy predictors from representing uncertainty.
This paper tackles non-convex phase retrieval with structured assumptions.
problem Phase retrieval with limited measurements and structure assumptions.
method Non-convex approaches with sample complexity guarantees.
result Sample-efficient recovery with structured signals/images.
Derives formulas from Green function Hessian assumption.
problem Deriving formulas from Green function Hessian assumption.
method Assumption on Hessian of Green function leads to monotonicity formulas.
result Explicit examples of manifolds satisfying assumption.
Improved causal discovery methods for large graphs without strict assumptions.
problem Sub-optimal solutions due to faithfulness assumption violations.
method Super-structure estimation and local search strategies.
result The proposed method scales to hundreds of nodes with high accuracy.