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. Paper introduces zero-space memory protection for CNNs without ECC overhead.
problem Ensuring reliability of CNNs in safety-critical applications.
method In-place zero-space ECC with weight distribution-oriented training.
result First known zero-space cost memory protection for CNNs.
New families of translation surfaces with multiple oblivious points discovered.
problem Identifying points on translation surfaces without nearby closed geodesics.
method Constructing new families of translation surfaces and proving existence in higher genera.
result Translation surfaces in every genus ≥3 have at least one oblivious point.
Approaches for big data regression using sufficient statistics.
problem Challenges in computing closed-form solutions for large datasets.
method Multiple learning approaches using sufficient statistics arrays.
result Achieves closed-form solutions for multiple models at half the training time of traditional methods.
We derive upper and lower bounds for the policy regret of T T T -round online learning problems with graph-structured feedback, where the adversary is nonoblivious but assumed to have a bounded memory. We obtain upper bounds of O ~ ( T 2 / 3 ) \widetilde O(T^{2/3}) O ( T 2/3 ) and O ~ ( T 3 / 4 ) \widetilde O(T^{3/4}) O ( T 3/4 ) for strongly-observable and weakly-observab…
New algorithms optimize risk-aware selection in uncertain rewards.
problem Balancing expected reward and risk in uncertain, potentially heavy-tailed rewards.
method Distribution oblivious algorithms that consider CVaR, not bound on moments/tails.
result Provable upper bounds on incorrect identification probability.
New faster, space-saving methods for subspace embeddings in tensors.
problem Efficiently embedding large tensors with fewer random bits.
method Modewise Johnson-Lindenstrauss embeddings for rank- r r r tensors. result Improved space complexity for tensor subspaces with fewer random bits.
New study shows data-oblivious attacks can outperform data-aware ones.
problem Comparing effectiveness of data-oblivious and data-aware poisoning attacks.
method Theoretical study of feature selection with LASSO, focusing on separation between full-information and oblivious attackers.
result Data-oblivious attacks can achieve the same results as full-information attacks for feature selection with LASSO.
The paper tackles pure exploration in multi-armed bandits with low rank structure using oblivious sampling.
problem Pure exploration in multi-armed bandits with low rank reward sequences.
method The approach involves separating the exploration strategy from feedback, using oblivious sampling, and incorporating kernel information of reward vectors.
result Efficient algorithms with regret bound O ( d ( ln N ) / n ) O(d\sqrt{(\ln N)/n}) O ( d ( ln N ) / n ) for both time-varying and fixed cases, with a lower bound gap of O ( ln N ) O(\sqrt{\ln N}) O ( ln N ) . Optimal subspace embedding with near-optimal sparsity for high-dimensional data.
problem Efficiently preserving norms of vectors in high-dimensional subspaces.
method Near-optimal sparsity oblivious subspace embedding with decoupling argument and cumulant method.
result Achieved near-optimal sparsity of O ~ ( 1 / ε ) \tilde O(1/ε) O ~ ( 1/ ε ) non-zeros per column. DOFEN improves DNN performance on tabular data benchmarks.
problem DOFEN tackles the performance gap between DNNs and tree-based models on tabular data.
method DOFEN uses a two-level rODT forest ensembling process inspired by oblivious decision trees.
result DOFEN achieves state-of-the-art results on the Tabular Benchmark.
This work introduces oblivious fairness definitions for image generation.
problem Fairness in image generation with uncertain sensitive attributes.
method Introduces oblivious fairness definitions and uses Posterior Sampling.
result Conditional Proportional Representation can be achieved obliviously.
New features generated from kernel methods are minimally dependent on sensitive features.
problem Generating fair features in the presence of sensitive and non-sensitive features.
method Relaxed Maximum Mean Discrepancy criterion, Hilbert-space-valued conditional expectation, plug-in approach.
result Closed-form solution for minimizing dependencies between new and sensitive features.
New algorithms for GLMs with oblivious noise, identifying solutions even when half the data is corrupted.
problem Regression for GLMs with additive oblivious noise.
method Distribution-independent algorithms that return accurate estimates or candidate solutions.
result First algorithmic result for GLM regression with oblivious noise, handling more than half corrupted data.
New insights into variable selection with different model assumptions.
problem Sparse recovery with ℓ ∞ \ell_\infty ℓ ∞ error guarantees in variable selection. method Separation between oblivious and adaptive models of ℓ ∞ \ell_\infty ℓ ∞ sparse recovery. result Proves a surprising contrast between oblivious and adaptive models in ℓ ∞ \ell_\infty ℓ ∞ sparse recovery. A new data-oblivious sketch for logistic regression reduces data size while maintaining approximation accuracy.
problem Efficiently solving logistic regression in one pass over a data stream.
method Data-oblivious sketching approach that reduces data size to poly(μdlog n) weighted points.
result Sketching reduces data size significantly and provides approximation guarantees.
Paper improves performance guarantees for Rademacher projections.
problem Improving statistical guarantees for Rademacher random projections.
method Algebraic framework for proving Schur-concavity properties.
result Novel Schur-concavity property of Rademacher projections with improved performance.
Study improves privacy-preserving online prediction from experts with speed-ups.
problem Privacy-preserving online prediction from experts with speed-ups.
method Differentially private federated online prediction algorithms.
result Achieves m m m -fold regret speed-up with low-loss expert in federated setting. New algorithm achieves both static and dynamic regret optimally against an oblivious adversary for deterministic losses.
problem Achieving optimal static and dynamic regret simultaneously in adversarial bandits.
method Extends impossibility result to deterministic losses, uses negative static regret and Blackwell approachability.
result First algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary.
Study shows efficient algorithms for noiseless linear regression require quadratic sample complexity in contamination rate.
problem Efficient algorithms for noiseless linear regression under Gaussian covariates with oblivious contamination.
method Formal evidence using Statistical Query complexity.
result Any efficient Statistical Query algorithm requires VSTAT complexity at least Ω(d^(1/2)/α^2).
New algorithms optimize without knowing problem parameters.
problem Optimizing large-scale problems without knowing key parameters.
method Combining mirror descent with dual averaging techniques.
result Converges without prior knowledge of problem parameters.
NODE improves deep learning on tabular data, outperforming GBDT.
problem Limited performance of deep learning on tabular data compared to gradient boosting decision trees.
method Introducing Neural Oblivious Decision Ensembles (NODE), a deep learning architecture that generalizes ensembles of oblivious decision trees.
result NODE outperforms leading GBDT packages on most tabular tasks.
Sparse OSEs achieve optimal embedding dimension of O(d).
problem Achieving optimal embedding dimension for sparse OSEs.
method Random sparsified matrix with m ≥ ( 1 + θ ) d m \geq (1+θ)d m ≥ ( 1 + θ ) d non-zeros per column. result Sparse OSEs can achieve embedding dimension m = O ( d ) m=O(d) m = O ( d ) , improving on previous m = O ( d log ( d ) ) m=O(d\log(d)) m = O ( d log ( d )) . Study the tradeoffs of bandit feedback in multiclass classification.
problem The price of using bandit feedback in multiclass classification.
method Mistake bound model, analysis of variants, and comparison of learners and adversaries.
result The optimal mistake bound under bandit feedback is at most O ( k ) O(k) O ( k ) times higher than in full information, with a tight bound of O ( k ) O(k) O ( k ) . New method uses data characteristics for better random projections.
problem Improving random projections for better data reduction.
method Data-dependent random projections for superior performance.
result Proves superior performance in matrix multiplication, regression, and classification.
Slow running or straggler tasks can significantly reduce computation speed in distributed computation. Recently, coding-theory-inspired approaches have been applied to mitigate the effect of straggling, through embedding redundancy in certain linear computational steps of the optimization algorithm, thus completing the…
We study the problem of maximizing a monotone set function subject to a cardinality constraint k k k in the setting where some number of elements τ τ τ is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exist constant-factor guarantees when the function is submodu…
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
Linear regression models contaminated by Gaussian noise (inlier) and possibly unbounded sparse outliers are common in many signal processing applications. Sparse recovery inspired robust regression (SRIRR) techniques are shown to deliver high quality estimation performance in such regression models. Unfortunately, most…
This paper introduces TNTK to study infinite soft tree ensembles.
problem Understanding the behavior of infinite soft tree ensembles.
method Introduced Tree Neural Tangent Kernel (TNTK) to analyze infinite soft tree ensembles.
result Identified several non-trivial properties of infinite soft tree ensembles.
New algorithm speeds up polynomial kernel approximations.
problem Efficiently approximating polynomial kernels of high degree.
method Oblivious sketching combined with novel sampling.
result Polynomial factor slowdown removed in running time.
Improved upper bound for online calibrated forecasting of binary sequences.
problem Online calibrated forecasting of binary sequences.
method Introducing a variant of Qiao & Valiant's sign preservation game called sign preservation with reuse (SPR) and proving its equivalence to calibrated forecasting.
result Improved upper bound of O ( T 2 / 3 − ε ) O(T^{2/3 - \varepsilon}) O ( T 2/3 − ε ) for calibrated forecasting, improving the O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) bound of Foster & Vohra. Develops efficient estimators for PCA and sparse regression in the presence of oblivious outliers.
problem Estimation of PCA and sparse regression in the presence of a small fraction of corrupted data.
method Designs efficient estimators using Huber loss with non-smooth regularizers like the ℓ1 norm or nuclear norm.
result Achieves consistent estimation error approaching zero as the number of observations grows.
This paper finds an MFE in large stochastic games using reinforcement learning.
problem Finding an equilibrium in large stochastic games is difficult.
method Lower-myopic best response dynamics and posterior sampling for reinforcement learning.
result Policy and action distributions converge to optimal strategies in an MFE.
New algorithms improve online prediction from experts with privacy constraints.
problem Online prediction from experts under privacy constraints.
method Proposed and analyzed new algorithms for approximate and pure differential privacy.
result Achieved improved regret bounds for various adversaries.
We provide a fast L2-embedding for arbitrary accuracy with applications to regression and L1 tasks.
problem Efficiently embedding high-dimensional data while maintaining accuracy.
method Oblivious L2-embedding with dimension independent of accuracy.
result Achieves arbitrary accuracy with constant embedding dimension.
The paper describes an application of Aggregating Algorithm to the problem of regression. It generalizes earlier results concerned with plain linear regression to kernel techniques and presents an on-line algorithm which performs nearly as well as any oblivious kernel predictor. The paper contains the derivation of an …
This work improves tensor decomposition methods, especially for large datasets.
problem Lack of efficient methods for estimating Tucker decompositions.
method Applies Johnson-Lindenstrauss type guarantees to Tucker decompositions with random embeddings.
result Effective dimension reduction with minimal error for large tensors.
Paper details Hilbert-curve for high-performance data mining.
problem Efficiently mapping multi-dimensional data to one dimension.
method Defines Hilbert-curve using finite automaton and context-free grammar.
result Cache-oblivious algorithms for matrix operations and clustering.
Extended Q-learning stability and convergence analysis.
problem Stability and convergence of Q-learning with linear function approximation.
method Analysis of ( ε , κ ) (\varepsilon,κ) ( ε , κ ) -tamed Gibbs policy, and other Q-learning variants. result Far more structure is required for convergence of Q-learning.
We survey distributed deep learning models for training or inference without accessing raw data from clients. These methods aim to protect confidential patterns in data while still allowing servers to train models. The distributed deep learning methods of federated learning, split learning and large batch stochastic gr…
In this work we investigate the reasons why Batch Normalization (BN) improves the generalization performance of deep networks. We argue that one major reason, distinguishing it from data-independent normalization methods, is randomness of batch statistics. This randomness appears in the parameters rather than in activa…
Proposes a novel SAM operator for separate item and relational memories.
problem Limited memory interactions in neural networks.
method Introduces a Self-attentive Associative Memory (SAM) operator to separate item and relational memories.
result Achieves competitive results in various tasks, including geometry, graph, reinforcement learning, and question answering.
Dual memory improves reinforcement learning efficiency.
problem Training inefficiency in reinforcement learning.
method Introduces a dual memory structure with a main and cache memory.
result Dual memory structure leads to higher scores in reinforcement learning environments.
New robust regression method works with fewer data points than previous methods.
problem Adversary can corrupt most of the data, making traditional regression models unreliable.
method Developed a Huber loss estimator for robust linear regression with nearly linear sample size and inverse-polynomial inlier fraction.
result The Huber loss estimator is consistent for nearly linear sample size and inverse-polynomial inlier fraction.
Let X be a data matrix of rank ρ, whose rows represent n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique which is precomputed and can be applied to any input matrix X. We pr…
New algorithm recovers sparse signals robustly against Gaussian noise and adaptive adversaries.
problem Designing efficient estimators for sparse linear regression in the presence of two adversaries.
method Polynomial-time algorithms using sum-of-squares relaxations and weighted Huber loss minimization.
result Achieves error o ( ε ) o(\sqrt{\varepsilon}) o ( ε ) for various distributions and adversaries. Stable Hadamard Memory improves reinforcement learning by efficiently managing memory.
problem Memory models struggle in partially observable reinforcement learning environments.
method Introduces a novel memory model using the Hadamard product for efficient memory management and updates.
result Significantly outperforms state-of-the-art memory-based methods on challenging benchmarks.