New insights into privacy guarantees for subsampled mechanisms under composition.
problem Tight privacy guarantees for the composition of subsampled differentially private mechanisms.
method Addressed confusion points in privacy accounting for subsampled mechanisms, providing examples and counterexamples.
result Privacy guarantees for subsampled mechanisms differ significantly between Poisson subsampling and sampling without replacement.
Paper extends FFT-based differential privacy method to heterogeneous compositions.
problem Computing accurate differential privacy guarantees for mixed mechanisms.
method Uses Fast Fourier Transform (FFT) for error analysis and parameter selection.
result Provides tighter bounds for heterogeneous compositions compared to homogeneous cases.
This research proves guarantees on sequence models' generalization to longer and novel sequences.
problem Generalization to longer sequences and novel token combinations in sequence models.
method Provable guarantees on length and compositional generalization for various sequence models.
result Limited capacity models achieve both length and compositional generalization with diverse training distributions.
Edgeworth Accountant calculates privacy loss under differential privacy compositions efficiently.
problem Efficiently computing overall privacy loss under composition of private algorithms.
method Analytical approach using f f f -differential privacy framework and Edgeworth expansion. result Non-asymptotic ( ε , δ ) (ε, δ) ( ε , δ ) -differential privacy bounds with reduced computational cost. Paper develops momentum schemes with variance reduction for non-convex composition optimization.
problem Lack of convergence guarantee and efficient momentum design in existing algorithms.
method Develops various momentum schemes with SPIDER-based variance reduction.
result Achieves near-optimal sample complexity and linear convergence rate.
Improves privacy guarantees by analyzing randomness in privacy-preserving mechanisms.
problem Balancing user privacy and business constraints in privacy-preserving mechanisms.
method Analyzes explicit and implicit randomness in privacy mechanisms and proposes a probabilistic calibration method.
result Proposes privacy at risk, providing stronger privacy guarantees with quantifiable risks.
Sharp privacy bounds for sequential analysis of sensitive data.
problem Privacy degradation under sequential analysis of sensitive data.
method Edgeworth expansion in f-differential privacy framework.
result Improved privacy bounds under composition with refined approximation accuracy.
This paper advances FL algorithms for composite optimization and statistical recovery.
problem Federated learning optimization and statistical recovery in composite settings.
method Proposes Fast Federated Dual Averaging for strongly convex and smooth loss, and Multi-stage Federated Dual Averaging for restricted strongly convex and smooth loss.
result Establishes state-of-the-art iteration and communication complexity, and high probability complexity bound with linear speedup.
A folded type model is developed for analyzing compositional data. The proposed model involves an extension of the α α α -transformation for compositional data and provides a new and flexible class of distributions for modeling data defined on the simplex sample space. Despite its rather seemingly complex structure, emplo…
New filters match advanced composition for adaptive privacy, with practical constants.
problem Limitations of existing adaptive composition methods.
method Constructed new filters and odometers that match advanced composition rates, including constants.
result Achieved fully adaptive privacy with practical filters and odometers.
Deep networks learn sparse hierarchical features without CoD.
problem Overparameterized deep networks struggle with the curse of dimensionality.
method Norm-constrained neural networks for sparse compositional functions.
result Deep networks can learn sparse hierarchical features efficiently.
New method to measure compositional generalization on realistic data.
problem Limited compositional generalization in machine learning.
method Maximizing compound divergence while ensuring small atom divergence.
result Machine learning architectures fail to generalize compositionally.
CARE method estimates precision matrix for compositional data, achieving optimality in high dimensions.
problem Challenges in inferring conditional dependence relationships in high-dimensional compositional data.
method Composition adaptive regularized estimation (CARE) method for sparse basis precision matrix.
result CARE estimator achieves minimax optimality in high dimensions, performing as well as if the basis were observed.
Algorithm samples composite logconcave densities efficiently.
problem Sampling from composite logconcave densities efficiently.
method Uses a restricted Gaussian oracle and gradient queries.
result Achieves strong total variation distance guarantees.
Unified view of gradient-based algorithms for stochastic convex composite optimization.
problem Optimization of stochastic convex composite functions.
method Extend the concept of estimate sequence to cover various gradient-based methods.
result Generic convergence proof and new adaptive SVRG variant.
This paper presents foundational theoretical results on distributed parameter estimation for undirected probabilistic graphical models. It introduces a general condition on composite likelihood decompositions of these models which guarantees the global consistency of distributed estimators, provided the local estimator…
New algorithm samples efficiently from complex composite potentials.
problem Sampling from densities with smooth and non-smooth components.
method Metropolis-Hastings framework with proximal-based proposal.
result Mixes to target density in O ( d log ( d / ε ) ) O(d \log (d/\varepsilon)) O ( d log ( d / ε )) iterations. With the proliferation of mobile devices and the internet of things, developing principled solutions for privacy in time series applications has become increasingly important. While differential privacy is the gold standard for database privacy, many time series applications require a different kind of guarantee, and a…
New guarantees for black-box variational inference methods.
problem Insufficient theoretical guarantees for black-box variational inference.
method Novel convergence guarantees for stochastic optimization of variational inference.
result Provable convergence of proximal and projected stochastic gradient descent for variational inference.
Sublinearly structured DNNs achieve feature learning consistency for compositional functions.
problem Achieving feature-learning and prediction consistency in deep neural networks.
method Sublinearly structured DNNs
result Sublinearly structured DNNs match or surpass wide DNNs in prediction.
Adaptive MAB algorithms handle composite, anonymous feedback without reward interval knowledge.
problem Multi-armed bandit with composite and anonymous feedback, especially without reward interval size knowledge.
method Proposed adaptive algorithms for stochastic and adversarial cases, without reward interval knowledge.
result First algorithm for adversarial case handling non-oblivious adversary and unknown reward interval size.
Unified framework for aligning and composing diffusion models to satisfy multiple constraints.
problem Improving quality and compliance of generated samples from diffusion models.
method Constrained optimization framework that unifies alignment and composition of diffusion models.
result Proposed framework effectively satisfies multiple constraints in image generation.
Paper improves privacy bounds for shuffle model using novel numerical techniques.
problem Improving privacy guarantees in the shuffle model of differential privacy.
method Develops and evaluates numerical techniques for tighter ( ε , δ ) (\varepsilon,δ) ( ε , δ ) -differential privacy bounds. result Accurately evaluates privacy loss distribution for adaptive compositions of shufflers.
New DP-CD method outperforms DP-SGD in solving composite DP-ERM problems.
problem Privacy-preserving machine learning with differential privacy.
method Differentially Private proximal Coordinate Descent (DP-CD) for composite Empirical Risk Minimization (ERM).
result DP-CD outperforms DP-SGD due to larger step sizes and better gradient exploitation.
Investigates fairness in pipeline models where individuals may drop out.
problem Fairness in pipeline models where individuals may drop out and subsequent stages depend on remaining individuals.
method Rigorous framework for evaluating fairness guarantees, showing that naïve auditing is insufficient and dependence must exist between stages.
result Fairness in pipelines can be arbitrary, even with just two stages, and requires dependence between stages.
Annealed Langevin dynamics improves sampling from composite scores in SBI.
problem Irreducible bias in sampling from composite scores of SBI methods.
method Derive Wasserstein bounds and decision rules for hyperparameters.
result Explicit decision rules for hyperparameters guarantee prescribed sampling accuracy.
UCB-TQL learns from multiple tasks with shared dynamics and adapts to task-specific variations.
problem Transfer reinforcement learning with composite MDPs where tasks share core dynamics but have sparse differences.
method UCB-TQL, a novel transfer RL algorithm for composite MDPs.
result Achieved a regret bound of i l d e O ( e H 5 N ) ilde{O}(\sqrt{eH^5N}) i l d e O ( e H 5 N ) that scales independently of the ambient dimension. New algorithms improve tensor CP decomposition under mild conditions.
problem Improving tensor CP decomposition with theoretical guarantees under mild incoherence conditions.
method Composite PCA and Concurrent Orthogonalization algorithms.
result Theoretical guarantees and practical superiority over existing methods.
This work improves task specification learning from demonstrations using maximum causal entropy.
problem Lack of guarantees for safe task composition and historical dependencies in learning from demonstrations.
method Adapting maximum causal entropy inverse reinforcement learning to estimate task specifications using reduced ordered binary decision diagrams.
result Polynomial time algorithm for estimating task specifications from demonstrations.
Proposes efficient stochastic algorithms for optimizing NDCG with provable convergence guarantees.
problem Efficient and provable stochastic methods for maximizing NDCG in deep learning models.
method Formulates novel compositional optimization problems, develops efficient stochastic algorithms with provable convergence guarantees, and proposes practical strategies.
result Stochastic algorithms with provable convergence guarantees for optimizing NDCG and its top- K K K variant. Decentralized detection avoids sharing data, controls false discoveries.
problem Global false discovery rate control in decentralized novelty detection.
method Quantized surrogate models for low-precision sharing, preserving exchangeability.
result Quantized composite scores maintain competitive statistical power with reduced communication.
Enhances privacy in machine learning through Rényi Pufferfish mechanisms.
problem Designing general and efficient Pufferfish mechanisms that maintain privacy and utility.
method Introduces a Rényi divergence-based variant of Pufferfish, generalizes the Wasserstein mechanism, and proves privacy amplification results.
result Extends the applicability of Pufferfish framework and provides stronger privacy guarantees.
SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objec…
The adaptive gradient online learning method known as AdaGrad has seen widespread use in the machine learning community in stochastic and adversarial online learning problems and more recently in deep learning methods. The method's full-matrix incarnation offers much better theoretical guarantees and potentially better…
In this paper, we present a unified framework for decision making under uncertainty. Our framework is based on the composite of two risk measures, where the inner risk measure accounts for the risk of decision given the exact distribution of uncertain model parameters, and the outer risk measure quantifies the risk tha…
Unified analysis of KL divergence using shifted composition for sampling.
problem Sampling from target distributions with KL divergence guarantees.
method Shifted composition rule applied to KL divergence, combining local error analysis and Girsanov's theorem.
result Unified KL guarantees for strongly log-concave, weakly log-concave, and log-Sobolev distributions.
Unified framework controls false discovery rate in bandit multiple testing.
problem Designing adaptive algorithms to identify true discoveries in multiple hypothesis testing.
method Unified modular framework using e-processes for FDR control in arbitrary settings.
result Unified framework ensures FDR control for dependent and simultaneous arm queries.
BL learns interpretable optimization structures from data.
problem Learning interpretable optimization structures from data.
method BL parameterizes a compositional utility function from intrinsically interpretable modular blocks.
result BL supports architectures from single to hierarchical compositions, modeling hierarchical optimization structures.
The paper introduces a privacy-preserving method for estimating treatment effects that maintains accuracy.
problem Estimating heterogeneous treatment effects in sensitive data while protecting privacy.
method A general meta-algorithm for CATE estimation with differential privacy guarantees, using sample splitting and parallel composition.
result The meta-algorithm maintains accuracy even with differential privacy, showing that most accuracy loss is due to variance increase.
We propose an adaptive smoothing algorithm based on Nesterov's smoothing technique in \cite{Nesterov2005c} for solving "fully" nonsmooth composite convex optimization problems. Our method combines both Nesterov's accelerated proximal gradient scheme and a new homotopy strategy for smoothness parameter. By an appropriat…
New privacy framework improves data analysis security.
problem Weaknesses in existing privacy definitions, especially in composition and subsampling.
method Introduces f f f -differential privacy, a new relaxation that avoids composition and subsampling issues. result Privacy guarantees converge to Gaussian differential privacy (GDP) under composition.
New hybrid stochastic optimization framework tackles nonconvex problems efficiently.
problem Efficiently solving stochastic composite nonconvex optimization problems.
method Combining two stochastic estimators to create a hybrid one, developing several variants of stochastic gradient methods.
result Achieved best-known complexity bounds for various optimization problems.
Kandinsky conformal prediction expands conditional coverage guarantees.
problem Disparities in coverage guarantees across different subpopulations.
method Flexible handling of overlapping and fractional group memberships.
result Minimax-optimal high-probability conditional coverage bound.
Large language models can't efficiently reason conditionally in a distribution-free setting.
problem Impossibility of conditional PAC-efficient reasoning in large language models.
method Proof of impossibility in a distribution-free setting for non-atomic input spaces.
result Any algorithm achieving conditional PAC efficiency must defer to the expert model with high probability.
Deep learning models viewed through tame geometry for convergence guarantees.
problem Understanding convergence guarantees in deep learning models.
method Introducing tame geometry concepts and tools for nonsmooth nonconvex settings.
result Illustrates tame geometry as a natural framework for AI systems, especially deep learning.
Paper develops polynomial approximations for complex probability densities.
problem Approximating high-dimensional concentrated probability densities.
method Tensor-product spectral polynomials and KR rearrangements.
result Efficient approximation of complex densities using composite maps.
Thompson Sampling remains differentially private with minimal modifications.
problem Ensuring privacy in Thompson Sampling for multi-arm bandits.
method Demonstrated differential privacy of original Thompson Sampling, provided per-round guarantees, and introduced modifications for tighter privacy.
result Privacy guarantees can be tuned by modifying the algorithm, and these modifications impact expected regret.
A new GP model for non-Gaussian data with explicit inverse warping.
problem Limited expressiveness and computational complexity of Gaussian processes for non-Gaussian data.
method Compositionally-warped Gaussian processes (CWGP) with explicit inverse warping.
result CWGP provides more accurate predictions and shorter computation times than traditional warped GPs.