Study finds a linear lower bound on conformal dimension for random hyperbolic groups.
problem Understanding conformal dimension in random hyperbolic groups.
method Building undistorted round trees from lower density groups.
result Achieves a linear lower bound in l l l at all densities 0 < d < 1 / 2 0 < d < 1/2 0 < d < 1/2 . Proposes rounding method for precise treatment effect estimation under budget constraints.
problem Resource-constrained experimental design for precise treatment effect estimation.
method Dependent randomized rounding procedure to convert assignment probabilities into binary treatment decisions.
result Improved estimator precision through variance reduction and efficient inference.
Simple algorithm approximates sparse PCA with guaranteed error.
problem Sparse Principal Component Analysis (PCA) optimization problem.
method Two-step approach: L1 penalized optimization followed by randomized rounding.
result Guaranteed additive error approximation with sparsity vs. accuracy tradeoff.
Most traditional online learning algorithms are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, tailored for transductive settings, which combines "random playout" and randomized rounding of loss subgradients. As an applic…
We prove a Chern-Lashof type formula computing the expected number of critical points of smooth function on a smooth manifold M M M randomly chosen from a finite dimensional subspace V ⊂ C ∞ ( M ) V\subset C^\infty(M) V ⊂ C ∞ ( M ) equipped with a Gaussian probability measure. We then use this formula this formula to find the asymptotics of the e…
New model tackles interference in online experiments.
problem Understanding cumulative performance in interference experiments.
method Introduces Multi-Armed Bandits with Interference (MABI) model.
result Cluster randomization policy achieves optimal expected regret and high probability bound.
Face recognition systems are vulnerable to composite face reconstruction attacks.
problem Vulnerability of face recognition systems to composite face reconstruction attacks.
method Assumed attacker uses composite face parts to reconstruct faces faster and more efficiently.
result Current face recognition systems are extremely vulnerable to random search attacks.
Improved cumulative regret for sequence prediction with limited expert advice.
problem Minimizing cumulative regret in sequence prediction with limited information.
method Convex combination of experts with limited observation, achieving constant regret.
result Strategies achieve constant regret independent of the horizon T, improving over standard bounds.
Improves sampling, rounding, and integration of logconcave functions.
problem Sampling, rounding, and integration of logconcave functions.
method Algorithmic diffusion approach.
result First complexity improvements in nearly two decades for general logconcave functions.
Unified framework for combinatorial and rounding algorithms in experimental design.
problem Designing and analyzing combinatorial and rounding algorithms for experimental design problems.
method Local search framework for combinatorial algorithms and regret minimization framework for rounding algorithms.
result Unified approach to match and improve all known results in D/A/E-design and obtain new results in unknown settings.
A new compression technique reduces communication costs in distributed deep learning.
problem Communication bottlenecks in distributed deep learning training.
method Natural Compression (NC) and Natural Dithering.
result Natural Compression increases communication savings by 3-4 times with negligible convergence speed impact.
A new reinforcement learning method improves Max-Cut solutions without needing training data.
problem Max-Cut problem is NP-hard, and existing methods struggle with generalizability and scalability.
method Training-data-free reinforcement learning approach to hyperplane rounding for Max-Cut optimization.
result Our method consistently achieves better Max-Cut solutions across various graph types.
A new mechanism reduces expert belief regret in online forecasting.
problem Minimizing expert belief regret in strategic forecasting.
method Developed a no-regret mechanism for non-myopic experts using online I-ELF.
result Achieved i l d e O ( T N ) ilde{O}(\sqrt{T N}) i l d e O ( T N ) regret for full-information setting. DUAL-LOCO uses random projections for efficient distributed statistical estimation.
problem Efficiently estimating statistical models in distributed systems.
method DUAL-LOCO employs low-dimensional random projections to approximate feature dependencies across workers.
result DUAL-LOCO achieves bounded approximation error with error bounds dependent weakly on the number of workers.
New research shows parallel optimization is ineffective for convex problems.
problem The inefficiency of parallel optimization methods for convex problems.
method Lower bounds analysis in the local oracle model of computation.
result Parallel and randomized algorithms cannot speed up convex optimization in various geometries and objective functions.
Two randomized algorithms improve regret bounds for generalized linear bandits.
problem Improving regret bounds for generalized linear bandits.
method Two randomized algorithms: GLM-TSL and GLM-FPL.
result Upper bounds of O ( d n log K ) O(d \sqrt{n \log K}) O ( d n log K ) on regret for both algorithms. A new algorithm for resource-aware multi-armed bandits minimizes regret.
problem Optimizing resource usage in a multi-armed bandit problem with censored observations.
method UCB-inspired online learning algorithm with theoretical regret analysis.
result The proposed algorithm outperforms standard multi-armed bandit algorithms in simulations.
New algorithm tackles CMAB with filtered feedback, achieving O ( ln ( n ) ) \mathcal{O}(\ln(n)) O ( ln ( n )) regret.
problem Sequential search and detection problems with hidden true rewards.
method Robust-F-CUCB algorithm, balancing exploration and exploitation.
result Upper confidence bound algorithm with O ( ln ( n ) ) \mathcal{O}(\ln(n)) O ( ln ( n )) regret bound. The paper improves bandit algorithms by incorporating random-effect models.
problem Improving statistical efficiency in multi-armed bandit problems with misspecified priors.
method Introduces a random-effect model to bandits, estimating arm means and designing a UCB algorithm ReUCB.
result Derives an upper bound on the Bayes regret of ReUCB, showing improved performance over Thompson sampling.
Novel unsupervised random forests improve density estimation and data synthesis.
problem Density estimation and data synthesis for complex tabular data.
method Recursive unsupervised random forests with alternating generation and discrimination rounds.
result Provable consistency and smooth densities with fast execution.
New method reduces distributed non-convex optimization rounds and bits.
problem Efficiently optimizing non-convex models in distributed systems.
method Introduces permutation compressors to reduce communication complexity.
result PermK compressors lead to significant communication complexity improvements.
The paper sets communication limits for distributed optimization with feature-based data partitions.
problem Understanding communication limits in distributed convex optimization with feature-based data partitions.
method Developed tight lower bounds on communication rounds for non-incremental and incremental algorithms.
result Established communication limits for a broad class of algorithms under feature-based data partitioning.
A new bandit algorithm observes arm rewards before playing, reducing regret.
problem Balancing exploration and exploitation with pre-observation costs.
method Design of OBP-UCB for single-player and C-MP-OBP for multi-player settings.
result Proved regret bounds for both single-player and multi-player settings.
Sparse random networks reduce communication in federated learning.
problem Large communication cost in federated learning.
method Freeze random weights, train stochastic binary mask to sparsify.
result Improves accuracy, reduces communication, speeds convergence.
PHE adds pseudo-rewards to history to minimize regret in stochastic bandits.
problem Minimizing cumulative regret in stochastic multi-armed bandits.
method PHE algorithm that adds O ( t ) O(t) O ( t ) i.i.d. pseudo-rewards to history and pulls the best arm based on the perturbed history. result Near-optimal regret bounds derived for PHE.
Algorithm allocates perishable resources online to minimize envy and inefficiency.
problem Online allocation of perishable resources to minimize envy and inefficiency.
method Algorithm uses predictions of perishing order and desired envy bound to adaptively allocate resources.
result Algorithm achieves optimal envy-efficiency trade-off as derived from strong lower bounds.
DSVGD improves federated learning with fewer communication rounds.
problem Federated learning scalability and trustworthiness.
method Distributed Stein Variational Gradient Descent (DSVGD) for non-parametric Bayesian inference.
result DSVGD achieves comparable accuracy and scalability to other methods, with well-calibrated predictions.
Gradient descent with biased rounding errors converges faster under certain conditions.
problem Stagnation or negative impact of rounding errors in neural network training with low precision.
method Analysis of gradient descent with stochastic fixed-point rounding errors under the Polyak-Lojasiewicz inequality.
result Biased rounding errors can improve convergence rates, especially when the Polyak-Lojasiewicz inequality holds.
Round spheres remain stable under slight entropy changes.
problem Maintaining the roundness of spheres under entropy changes.
method Analyzing the stability of hypersurfaces with respect to entropy changes.
result Hypersurfaces close to a round sphere remain close in Hausdorff distance.
FedShuffle improves local updates in FL, especially with data imbalance.
problem Data imbalance in FL leads to different clients performing different numbers of local updates.
method FedShuffle incorporates random reshuffling, data imbalance, and client sampling.
result FedShuffle improves upon FL methods that assume homogeneous updates in heterogeneous setups.
Round spheres are uniquely characterized by half-geodesics.
problem Characterizing round spheres in Riemannian geometry.
method Establishing that Riemannian spheres with specific geodesic properties are round.
result Riemannian spheres with all geodesics closed and many half-geodesics are round.
New algorithm reduces complexity for distributed and stochastic optimization.
problem Optimization of distributed and stochastic problems with multiple agents.
method Random Gradient Extrapolation Method (RGEM)
result Achieves optimal complexity bounds for both distributed and stochastic optimization.
The study extends Huisken's theorem to nonconvex surfaces that shrink to round points.
problem Extending Huisken's theorem to nonconvex surfaces.
method Constructing mean convex and non-mean convex hypersurfaces, using mean curvature flow.
result Found pathological examples of flows and sequences of flows that shrink to round points.
All radially symmetric connections on round spheres are parallel.
problem Classifying radially symmetric connections in vector bundles over spheres.
method Proving all such connections are parallel.
result Radially symmetric connections on round spheres are parallel.
New method certifies images against transformations like rotations and translations.
problem Certifying robustness of images against transformations like rotations and translations.
method Randomized smoothing with three different kinds of defenses.
result Individual certificates can be obtained via statistical error bounds or efficient online inverse computation.
Round surgery diagrams represent 3-manifolds in S 3 S^3 S 3 .
problem Representing and manipulating 3-manifolds in S 3 S^3 S 3 . method Introducing round surgery diagrams and defining moves to establish Kirby Calculus.
result Any 3-manifold can be obtained by a round surgery on a framed link in S 3 S^3 S 3 . A new algorithm finds minimizers in dueling optimization with a monotone adversary.
problem Finding minimizers in dueling optimization with a monotone adversary.
method Introduces and studies dueling optimization with a monotone adversary, designs an efficient randomized algorithm.
result Efficient algorithm incurs cost O ( d ) O(d) O ( d ) and iteration complexity O ( d log ( 1 / ε ) 2 ) O(d\log(1/\varepsilon)^2) O ( d log ( 1/ ε ) 2 ) , asymptotically optimal. Contact round surgeries on ( S 3 , ξ s t ) (\mathbb{S}^3,ξ_{st}) ( S 3 , ξ s t ) help in constructing and understanding contact 3-manifolds.
problem Constructing contact 3-manifolds using Legendrian surgeries.
method Introducing contact round surgeries of indices 1 and 2, and associating them with surgery diagrams.
result Every closed connected contact 3-manifold can be obtained by a sequence of contact round surgeries on Legendrian knots in ( S 3 , ξ s t ) (\mathbb{S}^3,ξ_{st}) ( S 3 , ξ s t ) . No complex structure exists on a round 6-sphere.
problem Existence of orthogonal complex structures on the round 6-sphere.
method Review of existing results.
result No orthogonal complex structure exists on the round 6-sphere.
MOL-TS uses Thompson Sampling for multi-objective linear bandits with Pareto guarantees.
problem Optimizing multiple conflicting objectives in linear contextual bandits.
method Proposes MOL-TS, a Thompson Sampling algorithm with Pareto regret guarantees.
result Achieves a worst-case Pareto regret bound of O ~ ( d 3 / 2 T ) \widetilde{O}(d^{3/2}\sqrt{T}) O ( d 3/2 T ) . 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.
Contact round surgery proves existence of contact structures on 3-manifolds.
problem Existence of contact structures on 3-manifolds.
method Contact round surgery and Lutz twist/Giroux torsion operations.
result Any contact structure on a closed orientable 3-manifold is constructed from the standard contact structure on the 3-sphere via contact round surgeries.
Consider an analytic map of a neighborhood of 0 in a vector space to a Euclidean space. Suppose that this map takes all germs of lines passing through 0 to germs of circles. Such a map is called rounding. We introduce a natural equivalence relation on roundings and prove that any rounding, whose differential at 0 has r…
Safe algorithm for linear bandits with safety constraints, matching previous results.
problem Designing safe bandit algorithms with linear safety constraints.
method Linear Thompson Sampling with frequentist regret analysis.
result Frequentist regret of order O ( d 3 / 2 log 1 / 2 d ⋅ T 1 / 2 log 3 / 2 T ) \mathcal{O} (d^{3/2}\log^{1/2}d \cdot T^{1/2}\log^{3/2}T) O ( d 3/2 log 1/2 d ⋅ T 1/2 log 3/2 T ) . New findings show infinitely many knots cannot be smoothly round handle slices.
problem Understanding the smoothability of knots in 4-dimensional space.
method Analyzing the properties of knots under surgery conjectures and cobordism conjectures.
result Infinitely many knots fail to be smoothly round handle slices.
This work investigates how multi-round reasoning improves LLM performance.
problem Improving problem-solving abilities in complex tasks with LLMs.
method Investigates approximation, learnability, and generalization properties of multi-round auto-regressive models.
result Transformers with finite context windows are universal approximators for Turing-computable functions and can approximate any Turing-computable sequence-to-sequence function through multi-round reasoning.
We discuss the integrability of orthogonal almost complex structures on Riemannian products of even-dimensional round spheres and give a partial answer to the question raised by E. Calabi concerning the existence of complex structures on a product manifold of a round 2-sphere and a round 4-sphere.
CORe uses randomization to explore bandit problems without external noise.
problem Exploration in stochastic bandit problems.
method Randomizes past observations to exploit variance in rewards.
result Achieves i l d e O ( d n log K ) ilde O(d\sqrt{n\log K}) i l d e O ( d n log K ) regret bound in stochastic linear bandits.