A measure of neural complexity quantifies how hard it is to access information across neurons.
problem Understanding how mutual information is distributed among neurons in neural networks.
method Partial Information Decomposition (PID) to disentangle contributions of single neurons, multiple neurons, and synergistic effects.
result Representational Complexity measures the difficulty of accessing information across multiple neurons.
Formalizes identifying information to answer key questions about machine learning from uncertain and novel observations.
problem Understanding and quantifying information from uncertain and novel observations in machine learning.
method Formalizes identifying information, defines hypothesis identification and sample complexity, and proves sample complexity properties for various data-generating processes.
result Proves the information theoretic characteristics of hypothesis identification and sample complexity, and shows how to compute identifying information and novel information.
How many bits of information are required to PAC learn a class of hypotheses of VC dimension d? The mathematical setting we follow is that of Bassily et al. (2018), where the value of interest is the mutual information I(S;A(S)) between the input sample S and the hypothesis outputted by the learning algo…
The paper proposes methods to extract and analyze individual variable information from complex dependencies.
problem Analyzing and understanding complex dependencies between multiple variables.
method Reversible normalization and iterative dependency reduction to extract individual information, and use it for direct mutual information and multi-feature Granger causality analysis.
result Decoupling of variables to analyze their individual information and direct mutual information transfers.
Study shows cognitive load impacts financial market efficiency, especially for less sophisticated investors.
problem Cognitive load's effect on financial market information processing.
method Developed a theoretical framework and tested it with exogenous disclosure complexity variation.
result Cognitive load significantly impairs price discovery, particularly for less sophisticated investors.
Introduces relative information gain for improving Gaussian process regression rates.
problem Improving the sample complexity of estimating or maximizing unknown functions.
method Introduces relative information gain, interpolates between effective dimension and information gain, and proves PAC-Bayesian bounds.
result Obtains minimax-optimal rates of convergence through the relative information gain.
Paper formalizes a reinforcement learning model for complex information structures.
problem Complex interdependence in sequential decision-making problems.
method Formalizes a novel reinforcement learning model with explicit information structure representation.
result Upper bound on sample complexity of learning general sequential decision-making problems.
This paper improves learning complex functions with CoT supervision, reducing sample complexity.
problem Learning complex functions with multi-step reasoning.
method Develops a statistical theory linking CoT risk and end-to-end risk, using CoT information measure.
result CoT supervision can achieve significantly faster learning rates compared to standard E2E supervision.
Active learning reduces spin network inference complexity by 10^6-fold.
problem Difficulty in inferring direct interactions in complex networks.
method Information geometry framework to quantify inference difficulty and information gain from perturbations.
result Designed perturbations reduce sampling complexity by 10^6-fold across various network architectures.
Quantum learning complexity reviewed using information theory.
problem Learning properties of quantum systems or processing data via quantum computing.
method Information-theoretic techniques focusing on data, copy, and model complexity.
result Copy complexity due to irreversible quantum measurements limits information extraction.
Method infers causal direction using data discretization and complexity calculation.
problem Determining causal direction between continuous variables.
method MDL Binning technique for data discretization and complexity calculation.
result Captures the shape of the data to determine causal direction.
We apply information-based complexity analysis to support vector machine (SVM) algorithms, with the goal of a comprehensive continuous algorithmic analysis of such algorithms. This involves complexity measures in which some higher order operations (e.g., certain optimizations) are considered primitive for the purposes …
Complex-valued neural networks improve seismic data analysis by preserving phase information.
problem Low-frequency aliasing in seismic data due to discarded phase information.
method Developed complex-valued deep convolutional networks to leverage phase information in deterministic physical data.
result Complex-valued networks outperform real-valued networks in training and inference from deterministic physical data.
In the information-based paradigm of inference, model selection is performed by selecting the candidate model with the best estimated predictive performance. The success of this approach depends on the accuracy of the estimate of the predictive complexity. In the large-sample-size limit of a regular model, the predicti…
There are (at least) three approaches to quantifying information. The first, algorithmic information or Kolmogorov complexity, takes events as strings and, given a universal Turing machine, quantifies the information content of a string as the length of the shortest program producing it. The second, Shannon information…
Examines predictability and complexity of economic time series using symbolic dynamics and entropy.
problem Understanding the predictability and complexity of economic time series.
method Symbolic dynamics and Information theory (entropy and uncertainty).
result Economic time series are complex and can be expressed in terms of information production.
Framework measures learning task complexity, distinguishing from memorization.
problem Measuring and distinguishing learning from memorization in learning tasks.
method Introduces an asymmetric distance and a non-asymptotic framework to compute complexity.
result Framework can measure complexity in large-scale models and real-world datasets.
Measures information in neural networks via weights and activations.
problem Understanding how information is encoded and used in deep neural networks.
method Measures information via the optimal trade-off between accuracy and complexity of weights, defined by coding length.
result Establishes a relation between information in weights and effective information in activations, showing low complexity models generalize better and learn invariant representations.
MIRO learns robust latent spaces by maximizing mutual information with future information.
problem Robust perception in complex, unstructured environments with low sample complexity.
method MIRO maximizes mutual information in a latent space for model-based reinforcement learning.
result MIRO outperforms reconstruction objectives in cluttered scenes.
A principle for specialized decision-making divides complex problems into manageable parts.
problem Complex decision-making problems beyond individual capabilities.
method An on-line learning rule that learns a partitioning of the problem space for specialized linear policies.
result The approach solves problems that exceed individual decision-makers' capabilities.
PINNs struggle with increasingly complex ODEs, especially when parameters control their complexity.
problem Evaluating physics-informed neural networks on complex coupled ODEs.
method Tuned benchmarks of partial differential equations and harmonic oscillators; varying network architecture and training method.
result PINNs fail to solve complex ODEs, revealing issues like insufficient capacity, poor conditioning, and high local curvature.
Neural network learns low-dimensional polynomials with SGD near information-theoretic limit.
problem Learning a single-index target function with gradient descent.
method Two-layer neural network optimized by SGD on squared loss.
result Sample and runtime complexity of n≃T=Θ(d⋅polylogd) for polynomial single-index models, matching information theoretic limit up to polylogarithmic factors. A new measure of model complexity based on Fisher Information.
problem Model complexity measurement in statistical models.
method Effective dimension defined by the number of cubes needed to cover the model space.
result The effective dimension is scale-dependent and measures model complexity.
This work defines a complexity measure for BAMDP planning and introduces state abstraction for more efficient approximate planning.
problem The computational intractability of exact BAMDP planning solutions.
method Define a complexity measure for BAMDP planning, introduce state abstraction, and develop an approximate planning algorithm.
result Introduces a computationally tractable approximate planning algorithm using state abstraction.
Accurately determining dependency structure is critical to discovering a system's causal organization. We recently showed that the transfer entropy fails in a key aspect of this---measuring information flow---due to its conflation of dyadic and polyadic relationships. We extend this observation to demonstrate that this…
This paper tackles online strategic decision making with asymmetry and knowledge transportability.
problem Strategic decision making with information asymmetry and knowledge transportability challenges.
method Developed a sample-efficient algorithm for online learning under these conditions.
result Proved sample complexity of O(1/ε2) for learning an ε-optimal policy. New bounds explain modern machine learning algorithms' generalization.
problem Explaining generalization behavior of modern machine learning algorithms.
method Proposes a new complexity measure based on empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class.
result Obtains novel bounds with finite fractal dimension, simplifies proofs, and recovers known results.
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
Proposes PEID for analyzing synergistic causation in complex systems.
problem Challenges in identifying and analyzing synergistic causation in complex systems.
method Partial Effective Information Decomposition (PEID) framework.
result Unified and computable characterization of synergistic causal relations.
This paper introduces Kernel-based Information Criterion (KIC) for model selection in regression analysis. The novel kernel-based complexity measure in KIC efficiently computes the interdependency between parameters of the model using a variable-wise variance and yields selection of better, more robust regressors. Expe…
Density destructors simplify complex PDFs to maximize entropy, linking to information theory.
problem Complex multivariate PDFs are hard to analyze.
method Invertible transforms that progressively remove structure from PDFs.
result Density destructors can improve estimates of information theoretic quantities.
We present arguments for the formulation of unified approach to different standard continuous inference methods from partial information. It is claimed that an explicit partition of information into a priori (prior knowledge) and a posteriori information (data) is an important way of standardizing inference approaches …
Study improves sampling from non-log-concave distributions using Fisher information.
problem Sampling from non-log-concave distributions with high Fisher information guarantees.
method Proximal sampler with RGO implementation, leveraging log-concave sampling results.
result Improved complexity guarantee in relative Fisher information for non-log-concave sampling.
Paper resolves open problems on sample complexity in binary hypothesis testing.
problem Open problems in distributed simple binary hypothesis testing under information constraints.
method One-shot lower bound on Bayes error, streamlined sample complexity formula, reverse data-processing inequality.
result Optimally tight sample complexity bounds for communication-constrained simple binary hypothesis testing.
Paper solves learning imperfect-information games with fewer episodes.
problem Learning imperfect-information extensive-form games from bandit feedback.
method Balanced Online Mirror Descent and Balanced Counterfactual Regret Minimization algorithms.
result Achieves near-optimal sample complexity for finding approximate Nash equilibria.
New model learns symmetry transformations from complex data.
problem Learning symmetry transformations in complex domains like chemical space.
method Two latent subspaces, deep information bottleneck, continuous mutual information regularizer.
result Model outperforms state-of-the-art methods on artificial and molecular datasets.
Measures neural network information transfer for generalization.
problem Estimating the generalizable information in neural networks.
method Proposes Information Transfer (LIT) based on prequential coding. result Consistently correlates with generalizable information in neural networks.
The paper extends physics-based information maximization to complex bandit problems.
problem Designing efficient decision-making policies for complex bandit problems.
method Information and free-energy maximization principles adapted to three distinct bandit types.
result Information maximization leads to strong performance in complex bandit problems.
Introduces a framework using information theory for understanding machine learning.
problem Understanding the effectiveness and design of modern machine learning architectures.
method An information-theoretic approach to learning, focusing on model complexity and architecture.
result Successful architectures have a broad complexity range, enabling learning in over-parameterized model classes.
Eluder dimension and information gain are equivalent for reproducing kernel Hilbert spaces.
problem Complexity measures in bandit and reinforcement learning.
method Equivalence of eluder dimension and information gain for reproducing kernel Hilbert spaces.
result Eluder dimension and information gain are equivalent for reproducing kernel Hilbert spaces.
Tutorial on information bottleneck problems with connections to coding and learning.
problem Information bottleneck problems and their connections to coding and learning.
method Information theoretic perspective, practical methods, connections to various problems.
result Optimal trade-offs between relevance and complexity in discrete and vector Gaussian frameworks.
New complexity measure MEHC refines MDP upper bounds and rewards informativeness.
problem Refining complexity measures for MDPs and understanding reward informativeness.
method Introducing MEHC, a new complexity measure that tightens MDP diameter by accounting for reward structure.
result MEHC replaces diameter in upper bounds on optimal value span and UCRL2-like algorithms' regret.
The Mutual Information (MI) is an often used measure of dependency between two random variables utilized in information theory, statistics and machine learning. Recently several MI estimators have been proposed that can achieve parametric MSE convergence rate. However, most of the previously proposed estimators have th…
The paper sets information-theoretic lower bounds for neural networks' parameter recovery and excess risk.
problem Establishing sample complexity lower bounds for neural network parameters and excess risk.
method Using information-theoretic tools, the paper proves lower bounds by constructing a generative network.
result Proves information-theoretic lower bounds for exact parameter recovery and positive excess risk.
The paper sets sample complexity bounds for identifying LTI systems from a finite set.
problem Identifying an LTI system from a finite set of possible systems using trajectory data.
method Maximum likelihood estimator and information theory tools.
result Upper and lower bounds for sample complexity are derived, independent of stability assumption.
Tag2Vec learns tag representations in hybrid networks with semantic and hierarchical information.
problem Lack of semantic and hierarchical information in tag networks.
method Tag2Vec model that combines nodes and tags into hybrid networks, using parameterized random walks and hyperbolic Skip-gram model.
result Tag2Vec outperforms other models in learning rich semantic tag representations.
RID framework quantifies and regularizes task-relevant knowledge in distillation.
problem Distilling irrelevant information can hinder student model performance.
method Partial Information Decomposition to quantify and regularize task-relevant knowledge.
result RID framework leads to more resilient distillation under nuisance teachers.
BNs extract sparse, non-redundant features from climate data networks.
problem Redundant information in correlation networks limits physical feature extraction.
method Construct data-driven complex networks using Bayesian Networks.
result Sparse, non-redundant features reveal generalizable physical features.