Study designs logging policies to minimize off-policy evaluation error.
problem Minimizing OPE error with logging policies for target policies.
method Characterizes reward-coverage tradeoff, proposes a unifying framework, derives optimal policies.
result Provides actionable guidance for firms choosing recommendation systems.
The main goal of this thesis is to point out that the bias-variance tradeoff is not always true (e.g. in neural networks). We advocate for this lack of universality to be acknowledged in textbooks and taught in introductory courses that cover the tradeoff. We first review the history of the bias-variance tradeoff, its …
A new tradeoff between regularization and sharpness improves model performance in overparameterized settings.
problem Improving model performance in overparameterized settings with minimum-norm interpolators.
method Proposes a regularization-sharpness tradeoff for overparameterized linear regression with an ℓ^p penalty.
result Empirical validation shows the tradeoff terms can distinguish performant linear interpolators.
Study the tradeoff between signal distortion and human perception over finite channels.
problem Characterize the distortion-perception tradeoff for finite channels with arbitrary metrics.
method Solve linear programming problems to compute the distortion-perception function and optimal reconstructions.
result DP function is piecewise linear in the perception index.
We perform the first study of the tradeoff space of access methods and replication to support statistical analytics using first-order methods executed in the main memory of a Non-Uniform Memory Access (NUMA) machine. Statistical analytics systems differ from conventional SQL-analytics in the amount and types of memory …
Paper explores tradeoff between standard and robust accuracy for latent models.
problem Tradeoff between standard accuracy and robust accuracy in adversarial training.
method Revisits adversarial training for latent models, considering Gaussian mixture and generalized linear models.
result Low-dimensional manifold structure mitigates the tradeoff between standard and robust accuracy.
Proposes a new adversarial model to avoid accuracy vs. adversarial accuracy tradeoff.
problem Inherent tradeoff between accuracy and adversarial accuracy in existing adversarial robustness definitions.
method Introduces Voronoi-epsilon adversary that balances perturbation constraints.
result Voronoi-epsilon adversary avoids accuracy vs. adversarial accuracy tradeoff even with large ε. We propose a data-driven framework for optimizing privacy-preserving data release mechanisms to attain the information-theoretically optimal tradeoff between minimizing distortion of useful data and concealing specific sensitive information. Our approach employs adversarially-trained neural networks to implement random…
Researchers study fairness-accuracy tradeoffs in predictive models for multiple groups.
problem Understanding the tradeoff between fairness and accuracy in models serving multiple demographic groups.
method Characterizing the fairness-accuracy (FA) Pareto frontier, approximating it from limited data, and bounding the worst-case gap.
result Derivation of worst-case-optimal estimators and uniform finite-sample bounds for the entire FA frontier.
Despite breakthrough performance, modern learning models are known to be highly vulnerable to small adversarial perturbations in their inputs. While a wide variety of recent \emph{adversarial training} methods have been effective at improving robustness to perturbed inputs (robust accuracy), often this benefit is accom…
The paper explores robustness in linear regression models under adversarial attacks.
problem The impact of test-time adversarial attacks on linear regression models.
method Quantitative estimates and phase transitions analysis.
result Precise characterization of tradeoffs between adversarial robustness and accuracy.
The paper analyzes the bias-variance tradeoff for Bregman divergences.
problem Understanding the bias-variance tradeoff for Bregman divergences.
method Analyzes the bias-variance tradeoff through operations in dual space.
result Derives several results including a generalized law of total variance and ensembling operations.
CDC-FM improves generative model quality-generalization tradeoff by regularizing with geometry-aware noise.
problem Tradeoff between high sample quality and memorization in deep generative models.
method Introduces Carré du champ flow matching (CDC-FM) that replaces homogeneous noise with anisotropic Gaussian noise capturing latent data manifold geometry.
result CDC-FM consistently offers better quality-generalization tradeoff across diverse datasets and architectures.
This paper explores tradeoffs between standard and adversarial risks in distributionally adversarial training.
problem Understanding the impact of adversarial training on standard risk and adversarial risk.
method Study of distributionally adversarial training with different learning settings and models.
result Derives Pareto-optimal tradeoff curves between standard and adversarial risks.
This paper considers portfolio construction in a dynamic setting. We specify a loss function comprised of utility and complexity components with an unknown tradeoff parameter. We develop a novel regret-based criterion for selecting the tradeoff parameter to construct optimal sparse portfolios over time.
In this paper, we exhibit the tradeoffs between the (training) sample, computation and storage complexity for the problem of supervised classification using signal subspace estimation. Our main tool is the use of tensor subspaces, i.e. subspaces with a Kronecker structure, for embedding the data into lower dimensions. …
New OLO algorithms use Stein's method for better performance tradeoffs.
problem Achieving optimal tradeoffs in adversarial online linear optimization.
method Operationalizing Stein's method for computationally efficient OLO algorithms.
result Additively sharp upper bounds on regret and total loss.
The paper explores the tradeoffs between fairness measures in machine learning.
problem The challenge of achieving all three fairness notions simultaneously in machine learning models.
method The approach uses partial information decomposition (PID) to analyze the relationships between fairness measures.
result Identifies the regions where fairness measures overlap and disagree, revealing potential tradeoffs.
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.
While adversarial training can improve robust accuracy (against an adversary), it sometimes hurts standard accuracy (when there is no adversary). Previous work has studied this tradeoff between standard and robust accuracy, but only in the setting where no predictor performs well on both objectives in the infinite data…
The paper analyzes the tradeoffs between accuracy and invariance in learning representations.
problem Achieving both accuracy and invariance in machine learning models.
method Information theoretic analysis of classification and regression settings.
result Characterization of the accuracy and invariance achievable by any representation of the data.
Paper improves privacy-accuracy balance in federated learning.
problem Privacy-accuracy tradeoffs in federated learning.
method Personalized federated learning with joint differential privacy.
result Coordination of local and centralized learning improves accuracy while maintaining privacy.
Improves early stopping in deep networks by adjusting stepsizes.
problem Epoch-wise double descent in deep networks.
method Analytical and empirical study of bias-variance tradeoffs in different network layers.
result Eliminating epoch-wise double descent through adjusting stepsizes of different layers improves early stopping performance.
Algorithm balances online and offline data for linear bandits.
problem Online learning with an offline dataset in linear bandits.
method Proposes a linear bandit algorithm that uses offline data early and increasingly favors exploration as the horizon grows.
result Establishes regret bounds showing competitive performance with both purely online and offline solutions.
This work explores feature learning tradeoffs in neural networks.
problem Resource tradeoffs in neural feature learning.
method Theoretical and experimental investigation of offline sparse parity learning.
result Width improves sample efficiency in sparse feature learning.
Faced with massive data, is it possible to trade off (statistical) risk, and (computational) space and time? This challenge lies at the heart of large-scale machine learning. Using k-means clustering as a prototypical unsupervised learning problem, we show how we can strategically summarize the data (control space) in …
Deep reinforcement learning (DRL) on Markov decision processes (MDPs) with continuous action spaces is often approached by directly training parametric policies along the direction of estimated policy gradients (PGs). Previous research revealed that the performance of these PG algorithms depends heavily on the bias-var…
New insights into bias-variance tradeoff for data-driven optimization under local misspecification.
problem Understanding the relative performance of SAA, IEO, and ETO under local misspecification.
method Developed a local misspecification perspective using contiguity theory in statistics.
result Explicit expressions for decision bias and geometric understanding of variance.
New method quantifies redundant information using information bottleneck.
problem Quantifying redundant information among multiple sources.
method Formulated as an information bottleneck problem, termed redundancy bottleneck.
result Extracts information that best predicts the target without revealing source identity.
The paper analyzes Adam and SGD in nonstationary optimization, revealing tradeoffs between noise and drift.
problem Analyzing Adam and SGD in nonstationary optimization problems.
method Theoretical analysis of Adam and SGD under non-stationary stochastic objectives, separating two regimes.
result Characterizes the tradeoff between noise and drift in Adam and SGD, revealing when adaptive step-sizing is beneficial or harmful.
New estimator reduces bias and variance in tensor and matrix denoising.
problem Optimal bias-variance tradeoff in matrix and tensor estimation.
method One-step variant of higher-order SVD (HOSVD) estimator.
result Achieves optimal bias-variance tradeoff in both matrix and tensor settings.
The bias-variance tradeoff tells us that as model complexity increases, bias falls and variances increases, leading to a U-shaped test error curve. However, recent empirical results with over-parameterized neural networks are marked by a striking absence of the classic U-shaped test error curve: test error keeps decrea…
This paper presents a bias-variance tradeoff of graph Laplacian regularizer, which is widely used in graph signal processing and semi-supervised learning tasks. The scaling law of the optimal regularization parameter is specified in terms of the spectral graph properties and a novel signal-to-noise ratio parameter, whi…
Paper characterizes fairness vs. accuracy tradeoff in classification.
problem Mitigating bias in machine learning models.
method Characterizes the tradeoff between fairness and accuracy, provides a post-processing algorithm.
result Post-processing algorithm yields optimal fair classifier when score is Bayes optimal.
We identify and optimize the fairness-accuracy tradeoff through TAF Curves and FAUC metrics.
problem Balancing fairness and accuracy in machine learning models for high-stakes decisions.
method Developed TAF Curves and FAUC metric to quantify the tradeoff, and introduced FairStacks framework to expand the Pareto frontier.
result FairStacks framework expands the empirical Pareto frontier and improves the FAUC for model ensembles.
Stochastic momentum methods trade compute efficiency for serial runtime.
problem Stochastic momentum methods trade compute efficiency for serial runtime.
method Stochastic HB and ASGD for consistent linear regression with Gaussian covariates.
result HB preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale.
DP-RandP improves privacy-utility tradeoff in DP-SGD by learning priors from random processes.
problem Improving the performance of differentially private stochastic gradient descent (DP-SGD) on private data.
method A three-phase approach that learns priors from images generated by random processes and transfers these priors to private data.
result New state-of-the-art accuracy on CIFAR10, CIFAR100, MedMNIST, and ImageNet for various privacy budgets.
Automated investment managers, or robo-advisors, have emerged as an alternative to traditional financial advisors. The viability of robo-advisors crucially depends on their ability to offer personalized financial advice. We introduce a novel framework, in which a robo-advisor interacts with a client to solve an adaptiv…
Paper solves NGCA for discrete distributions using LLL method.
problem Learning hidden non-Gaussian components in discrete distributions.
method Utilizes LLL lattice basis reduction method.
result Sample and computationally efficient algorithm for NGCA in discrete distributions.
Calibrated ensembles improve both ID and OOD accuracy in distribution shift.
problem Desired balance between in-distribution and out-of-distribution accuracy.
method Ensemble standard and robust models, calibrating on ID data only.
result ID-calibrated ensembles outperform state-of-the-art methods on multiple datasets.
Lossy compression algorithms are typically designed and analyzed through the lens of Shannon's rate-distortion theory, where the goal is to achieve the lowest possible distortion (e.g., low MSE or high SSIM) at any given bit rate. However, in recent years, it has become increasingly accepted that "low distortion" is no…
Optimizes sample and round complexity in adaptive sampling from multiple distributions.
problem Adaptive sampling from multiple distributions with limited rounds and samples.
method Introduces OODS framework and analyzes tradeoffs between sample and round complexity.
result Achieves near-optimal sample complexity and sub-polynomial round complexity.
Paper proposes SRA algorithm for online learning robustness and adaptivity.
problem Quantifying and evaluating tradeoff between robustness and adaptivity in online learning.
method SRA algorithm using biased stochastic approximation scheme with adaptive threshold.
result SRA algorithm provides superior performance in synthetic and real datasets.
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatori…
New method trains GFlowNets from partial episodes to improve convergence and stability.
problem Improving convergence and stability of GFlowNets training.
method Introducing SubTB(λ) for GFlowNet training from partial action subsequences. result SubTB(λ) accelerates GFlowNet convergence and enables training in longer action sequences. Survey of stablecoins to reduce cryptocurrency volatility.
problem Reduction of cryptocurrency volatility during financial crises.
method Classification of stablecoin approaches and assessment of tradeoffs.
result Different stablecoin types offer varying tradeoffs and challenges.
New estimator reduces bias-variance tradeoff in Markovian interference experiments.
problem Estimating impact of interventions in systems with limited resources.
method Differences-In-Q (DQ) estimator for on-policy policy evaluation.
result DQ estimator has exponentially smaller variance than off-policy methods.
Partial fusion combines neural networks to balance accuracy and efficiency.
problem Balancing accuracy and computational cost in neural networks.
method Extending weight aggregation methods based on neuron-level similarity, using partial optimal transport to match similar neurons.
result Achieves a flexible tradeoff between computational cost and performance.