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 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.
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.
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.
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. 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).
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.
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.
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 ) . 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…
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.
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 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. 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…
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.
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.
The paper improves smoothed analysis for online problems with adaptive adversaries.
problem Online prediction, discrepancy minimization, and online optimization with adaptive adversaries.
method General technique to prove smoothed guarantees against adaptive adversaries, reducing to simpler oblivious adversaries.
result Strong smoothed guarantees for three online problems, matching or improving previous results.
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. 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.
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. 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.
New algorithm for countable bandits with optimal regret.
problem Stochastic bandit problem with countably many arms.
method Fully adaptive online learning algorithm with O(log n) expected cumulative regret.
result Achieves optimal regret of O(log n) after any number of plays n.
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 framework for understanding adversarial and stochastic learning.
problem Understanding the continuum from adversarial to stochastic settings in online learning.
method Distributionally constrained adversaries framework.
result Characterization of learnable distribution classes for various function classes.
Machine learning models (e.g., speech recognizers) are usually trained to minimize average loss, which results in representation disparity---minority groups (e.g., non-native speakers) contribute less to the training objective and thus tend to suffer higher loss. Worse, as model accuracy affects user retention, a minor…
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…
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.
Paper introduces a new IS scheme for estimating distribution tails of complex models.
problem Scalability and feasibility issues in traditional IS schemes for rich models.
method Develops a self-structuring IS approach guided by large deviations principles.
result First to achieve asymptotically optimal variance reduction across various multivariate distributions.
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.
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.
A new model shows fairness mechanisms can improve selection utility even without implicit bias.
problem Improving selection fairness without introducing a utility trade-off.
method A model with latent quality and group-dependent variance, comparing fairness mechanisms to group-oblivious selection.
result Demographic parity always increases selection utility, while γ γ γ -rules weakly increase it. Performance of distributed optimization and learning systems is bottlenecked by "straggler" nodes and slow communication links, which significantly delay computation. We propose a distributed optimization framework where the dataset is "encoded" to have an over-complete representation with built-in redundancy, and the …
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.
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.
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.
We study online linear regression problems in a distributed setting, where the data is spread over a network. In each round, each network node proposes a linear predictor, with the objective of fitting the \emph{network-wide} data. It then updates its predictor for the next round according to the received local feedbac…
Optimal sketching bounds for sparse linear regression under various loss functions are established.
problem Sparse linear regression under different loss functions.
method Distribution over oblivious sketches for sparse ℓ 2 \ell_2 ℓ 2 norm regression and hinge-like loss functions. result Optimal sketching bounds with O ( k log ( d / k ) / ε 2 ) O(k\log(d/k)/\varepsilon^2) O ( k log ( d / k ) / ε 2 ) rows for sparse ℓ 2 \ell_2 ℓ 2 norm regression and O ( μ 2 k log ( μ n d / ε ) / ε 2 ) O(μ^2 k\log(μn d/\varepsilon)/\varepsilon^2) O ( μ 2 k log ( μ n d / ε ) / ε 2 ) rows for hinge-like loss functions. 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.