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 proves hyperbolicity of virtual knot compositions.
problem Proving hyperbolicity of virtual knot compositions.
method Exploring the composition of hyperbolic virtual knots.
result Strong lower bounds on the volume of compositions.
The paper studies tunnel and bridge numbers of composite genus 2 spatial graphs.
problem Understanding the tunnel and bridge numbers of composite genus 2 spatial graphs.
method Analyzes connected sum and trivalent vertex sum operations on genus 2 spatial graphs, proving bounds for tunnel and bridge numbers.
result Sharp bounds for the tunnel number of composite genus 2 spatial graphs, including lower bounds for bridge numbers.
The paper defines functions that induce bounded composition operators on RKHSs with analytic positive definite functions.
problem Characterizing functions that induce bounded composition operators on RKHSs.
method Intrinsic properties of RKHSs and asymptotic properties of orthogonal polynomials.
result Only affine transforms can induce bounded composition operators in a large class of RKHSs.
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.
Lower bounds set for infinite-precision transformers.
problem Understanding limitations of infinite-precision transformers.
method Used VC dimension technique to prove lower bounds.
result First lower bounds for two tasks: function composition and SUM 2 _2 2 . Paper analyzes stability and generalization of SCO algorithms.
problem Understanding how SCO algorithms perform on unseen data.
method Algorithmic stability analysis in statistical learning theory.
result Derives dimension-independent excess risk bounds for SCGD and SCSC.
Paper solves robust convex problems with heavy-tailed noise.
problem Solving convex compositional problems with heavy-tailed noise.
method Sub-Gaussian confidence bounds under weak heavy-tailed noise assumptions, using boosting strategy.
result Achieves nearly optimal high probability convergence result.
Gaussian processes struggle with compositional functions, but deep Gaussian processes can outperform.
problem Gaussian process regression struggles with compositional functions.
method We study information-theoretic lower bounds for posterior contraction rates in Gaussian process regression for a continuous regression model.
result Posterior based on any mean-zero Gaussian process can only recover the truth at a rate strictly slower than the minimax rate for generalized additive functions.
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.
New algorithm reduces complexity for optimizing complex machine learning tasks.
problem Optimizing complex machine learning objectives like reinforcement learning and portfolio management.
method Developed SARAH-Compositional algorithm using Stochastic Recursive Gradient Descent.
result Achieved optimal IFO complexity bounds for stochastic compositional optimization.
Validates composite systems using discrepancy propagation.
problem Validation of industrial systems with costly real-world tests.
method Propagates bounds on distributional discrepancy measures through a composite system.
result Derives upper bound on real system failure probability from simulations.
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. Unified algorithm for minimizing composite functions with flexible design.
problem Minimizing composite functions with specific structural properties.
method Unified accelerated algorithm for complementary composite minimization.
result Near-optimal algorithms for various optimization problems.
Paper shows a lower bound for composite knots crossing number.
problem Determining the crossing number for composite knots.
method Using the connected sum of knots, derived a new lower bound.
result Established that c ( K 1 # K 2 ) > ( c ( K 1 ) + c ( K 2 ) ) / 16 c(K_1\# K_2) > (c(K_1) + c(K_2))/16 c ( K 1 # K 2 ) > ( c ( K 1 ) + c ( K 2 )) /16 . The study reveals simplicity bias in neural networks leading to better compositional mappings.
problem Understanding when and how to encourage neural networks to learn compositional mappings.
method Examined compositional mappings through coding length and gradient descent dynamics.
result Neural networks tend to learn the simplest bijections, explaining their good generalization.
Discriminative classifier for compositional data using hierarchical mixture of Generalized Dirichlet models.
problem Classifying compositional data, especially in spam detection and color space identification.
method Hierarchical mixture of discriminative Generalized Dirichlet classifiers, using variational approximation for parameter learning.
result First time a variational upper-bound for Generalized Dirichlet mixture is proposed in literature.
New sparse GP model learns compositional kernels efficiently.
problem Learning accurate Gaussian Process models with complex kernel structures.
method MultiSVGP model with Horseshoe prior for kernel selection.
result Our model provides better fit and faster computation for large-scale data.
This work investigates the framework and performance issues of the composite neural network, which is composed of a collection of pre-trained and non-instantiated neural network models connected as a rooted directed acyclic graph for solving complicated applications. A pre-trained neural network model is generally well…
Paper simplifies DP composition for adaptive privacy budgets, enabling better privacy and accuracy in deep learning.
problem Tension between efficiency and flexibility in DP composition theorems.
method Rényi Differential Privacy (RDP) for adaptive privacy budgets, proving simpler composition theorem with smaller constants.
result Practical DP composition for adaptive privacy budgets, enabling better privacy and accuracy in deep learning.
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.
We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator introduced in (Nguyen et al, 2017) and consist of two steps: a proximal gradient and an averaging s…
The maximum number of maximum cliques in a graph is determined for graphs with at least 15 vertices.
problem Determining the maximum number of maximum cliques in a graph with n vertices.
method Defining prime and composite graphs, analyzing edge bounds, and using combinatorial arguments.
result For graphs with at least 15 vertices, the graph with the maximum number of maximum cliques is composite.
Study non-oblivious adversarial bandits with delayed feedback and propose algorithms with improved regret bounds.
problem Adversarial bandit problem with delayed, composite anonymous feedback.
method Propose wrapper algorithm for non-oblivious delay setting, achieving o ( T ) o(T) o ( T ) policy regret. result Achieve o ( T ) o(T) o ( T ) policy regret for many adversarial bandit problems with bounded memory loss sequences. Generative Flow Networks use submodular upper bounds to generate more data.
problem Generating data from unknown, complex reward functions efficiently.
method Introduce submodular upper bounds to estimate reward, use Optimism in the Face of Uncertainty principle to train GFNs.
result SUBo-GFN generates significantly more data than classical GFNs.
New method shows hidden state can significantly improve differential privacy in SGD.
problem Differential privacy in SGD with hidden state.
method Proves converging privacy bounds for hidden state SGD, using privacy amplification techniques.
result Privacy bound converges exponentially fast and is smaller than composition bounds.
We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the…
Improved bounds on neural network regions using activation histograms.
problem Bounding the number of affine regions in ReLU networks.
method Analysis of algebraic topology problem, extension of framework to subnetwork composition.
result Slightly tighter bounds and insights into parameter initialization.
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.
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.
Estimates input from output of nonlinear systems using ANN.
problem Estimating unknown compositional input from system output.
method Artificial Neural Networks (ANNs) for nonlinear system inversion.
result ANNs can compete with optimal bounds for linear systems and demonstrate promising results for nonlinear systems.
The ERI is a new index for measuring exam readiness.
problem Measuring exam readiness in a clear and actionable way.
method The ERI combines six signals derived from practice and mock tests, formalizing axioms for component maps and the composite.
result The ERI is a composite score interpretable and actionable for exam readiness.
New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
Adding noise controls capacity of function compositions.
problem Large capacity of function compositions with bounded capacity classes.
method Adding Gaussian noise to the output of F \mathcal{F} F before composing with H \mathcal{H} H . result Noise effectively controls the capacity of H ∘ F \mathcal{H} \circ \mathcal{F} H ∘ F , offering a general recipe for modular design. New algorithm solves complex optimization problems without needing projections.
problem Optimizing nested functions under convex constraints with noisy evaluations.
method Projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization.
result The algorithm achieves ε ε ε -stationary solutions with complexity bounds independent of ε ε ε and T T T . This paper shows that scientific discovery can be efficiently learned via compositional function trees, reducing the sample complexity.
problem Statistical and computational intractability of scientific discovery via symbolic regression.
method PAC learning approach focusing on compositional function trees built from a finite vocabulary of smooth operators.
result The Rademacher complexity and excess risk are controlled by depth and Lipschitz constants of the base operators, leading to finite-union bounds and high-probability risk bounds.
Curvature penalties improve interpretability of KANs without sacrificing accuracy.
problem Pathologically high-curvature oscillations in KANs activations make them hard to interpret.
method Derived a curvature penalty and proved an upper bound on model curvature.
result KANs with curvature penalties achieve substantially smoother activations while maintaining accuracy.
Recently, much work has been done on extending the scope of online learning and incremental stochastic optimization algorithms. In this paper we contribute to this effort in two ways: First, based on a new regret decomposition and a generalization of Bregman divergences, we provide a self-contained, modular analysis of…
Estimates returns for dollar cost averaging using geometric Brownian motion.
problem Estimating returns for dollar cost averaging investing strategy.
method Uses geometric Brownian motion and log-Normal distribution to construct a lower bound for returns. Computes parameters recursively and in closed form for dollar cost averaging. Compares to lump sum investing for matching wealth distributions.
result Probability of negative returns is less than 2.5% for 40 years of annual dollar cost averaging.
Optimizes convergence rate of stochastic proximal algorithms for composite convex problems.
problem Solving composite convex optimization problems with composite regularizers.
method Analyzed proximal stochastic gradient method and randomized incremental proximal method under relaxed variance assumptions.
result Proves O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate for last iterate of both algorithms under componentwise convexity and smoothness. 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.
The goal of online prediction with expert advice is to find a decision strategy which will perform almost as well as the best expert in a given pool of experts, on any sequence of outcomes. This problem has been widely studied and O ( T ) O(\sqrt{T}) O ( T ) and O ( log T ) O(\log{T}) O ( log T ) regret bounds can be achieved for convex losses (\cite{zin…
A new privacy accountant for Gaussian differential privacy measures individual privacy losses.
problem Bounding differential privacy loss for each participant in data analysis.
method Developed a privacy accountant for adaptive compositions of randomised mechanisms using Gaussian differential privacy.
result Provided optimal bounds for the Gaussian mechanism and constructed an approximative individual privacy accountant.
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.
The iterative nature of the expectation maximization (EM) algorithm presents a challenge for privacy-preserving estimation, as each iteration increases the amount of noise needed. We propose a practical private EM algorithm that overcomes this challenge using two innovations: (1) a novel moment perturbation formulation…
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 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.
Paper addresses uncertainty in model generalization under regime shifts.
problem Uncertainty in model generalization under regime changes.
method Proposes a framework to quantify and separate regime mismatch and sensitivity.
result Obtains exact decomposition and minimax lower bound for regime-aware models.