By reducing optimization to a sequence of smaller subproblems, working set algorithms achieve fast convergence times for many machine learning problems. Despite such performance, working set implementations often resort to heuristics to determine subproblem size, makeup, and stopping criteria. We propose BlitzWS, a wor…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Working Sets”
This work establishes properties on diffeological structures for set-valued maps and measures.
problem Establish rigorous properties on diffeological structures for set-valued maps and measures.
method Using diffeologies, the authors link various structures including set-valued maps, relations, gradients, measures, and shape analysis.
result Established rigorous properties on sample diffeologies.
Paper proposes a working set algorithm for non-convex sparse regression with provable convergence.
problem Estimating sparse linear models from high-dimensional data using non-convex regularizers.
method FireWorks algorithm based on non-convex reformulation and leveraging residual geometry.
result Convergence to a stationary point of the full problem with provable guarantees.
Convex sparsity-promoting regularizations are ubiquitous in modern statistical learning. By construction, they yield solutions with few non-zero coefficients, which correspond to saturated constraints in the dual optimization formulation. Working set (WS) strategies are generic optimization techniques that consist in s…
This work examines aggregation functions in Deep Set learning.
problem The sensitivity of Deep Set networks to aggregation function choices.
method Investigation of alternative aggregation functions, including learnable recurrent ones.
result Learnable aggregations improve performance, reduce hyper-parameter sensitivity, and generalize better.
We found a new simple family of Cantor sets whose projections are one-dimensional.
problem Finding simple Cantor sets with specific projection properties.
method Developed a new series of self-similar Cantor sets in .
result All projections of these new Cantor sets are connected and one-dimensional.
The C-bound, introduced in Lacasse et al., gives a tight upper bound on the risk of a binary majority vote classifier. In this work, we present a first step towards extending this work to more complex outputs, by providing generalizations of the C-bound to the multiclass and multi-label settings.
New condition for reconstructing Morse functions on 3D manifolds.
problem Reconstructing Morse functions with specific level sets.
method Studied a necessary and sufficient condition for reconstruction.
result New condition strengthens previous sufficient conditions.
Algorithm estimates Gaussian parameters under unknown truncation sets.
problem Estimating Gaussian parameters when samples are truncated to unknown sets.
method Efficient algorithm for arbitrary unknown truncation sets, using Gaussian surface area as complexity measure.
result Algorithm works for large families of sets including intersections of halfspaces and general convex sets.
The paper outlines future work in random sets theory.
problem Developing a theory of statistical reasoning with random sets.
method Generalizing logistic regression, probability laws, and geometric uncertainty.
result A new geometric approach to uncertainty with general random sets.
Algorithm tackles constrained reinforcement learning with concave-convex and knapsack constraints.
problem Constrained episodic reinforcement learning with concave rewards and convex constraints.
method Modular analysis with strong theoretical guarantees for concave-convex and knapsack settings.
result Significantly outperforms existing approaches in constrained episodic environments.
Improved RL algorithm with linear MDPs for offline learning with partial data coverage.
problem Efficient offline RL with linear MDPs under partial data coverage.
method Primal-dual algorithm with sample complexity.
result First computationally efficient algorithm with sample complexity for offline RL with linear MDPs under partial data coverage.
Fine properties of branch point singularities: Dirichlet energy minimizing multi-valued functionsmath.AP
In the early 1980's Almgren developed a theory of Dirichlet energy minimizing multi-valued functions, proving that the Hausdorff dimension of the singular set (including branch points) of such a function is at most where is the dimension of its domain. Almgren used this result in an essential way to show t…
Proposes a robust method for high-dimensional linear models.
problem Inference in high-dimensional settings with heavy-tailed errors and clustered data.
method Residual randomization procedure for Lasso-based inference.
result Outperforms state-of-the-art methods in challenging settings.
This work extends set-valued risk measures to discrete time, using difference inclusions and equations.
problem Defining set-valued dynamic risk measures in discrete time.
method Investigates discrete time setting with difference inclusions and difference equations.
result Provides insights for continuous time representations of set-valued dynamic risk measures.
New algorithms prove fast convergence in complex min-max problems.
problem Proving fast convergence in nonconvex min-max optimization.
method Hamiltonian Gradient Descent (HGD) and Consensus Optimization (CO) algorithms.
result HGD and CO achieve linear convergence in various settings.
New framework captures non-autonomous IFS limit set topology.
problem Understanding topological properties of non-autonomous IFS limit sets.
method Homological framework applied to fractal square.
result Provides insights into fractal topology, answering Mandelbrot's percolation problem.
This work extends learning theory to complexly dependent data under Dobrushin's condition.
problem Learning from weakly dependent data sampled on networks or spatial domains.
method Developed complexity measures and learning bounds for hypothesis classes under Dobrushin's condition.
result Generalization and learnability bounds degrade by constant and log factors compared to i.i.d. settings.
The paper tackles Kakeya and Nikodym sets on curved manifolds, reducing problems to Euclidean space.
problem Analyzing Kakeya and Nikodym sets on curved manifolds.
method Reduction of problems on curved manifolds to Euclidean space, using Bourgain's condition and recent breakthroughs.
result Establishes the Nikodym conjecture for three-dimensional manifolds with constant sectional curvature.
Given a simple algebraic group , a web is a directed trivalent graph with edges labelled by dominant minuscule weights. There is a natural surjection of webs onto the invariant space of tensor products of minuscule representations. Following the work of Westbury, we produce a set of webs for $\SL_n$ which form a bas…
This work introduces COLA, a strategy to aggregate conformal prediction sets efficiently.
problem Efficiently combining multiple conformity scores to reduce prediction set size.
method Introduces COnfidence-Level Allocation (COLA) to optimally allocate confidence levels across sets.
result COLA achieves smaller prediction sets than state-of-the-art methods while maintaining valid coverage.
For the supervised least squares classifier, when the number of training objects is smaller than the dimensionality of the data, adding more data to the training set may first increase the error rate before decreasing it. This, possibly counterintuitive, phenomenon is known as peaking. In this work, we observe that a s…
Study of mean curvature flow with obstacles using singular perturbation.
problem Obstacle problem associated to mean curvature flow.
method Geometric vanishing-viscosity approximation with singular perturbation.
result Generic level sets are distributional solutions of the obstacle problem.
ExNODE uses ODE to model sets with permutation equivariance.
problem Capturing intra-set dependencies in unordered sets.
method Exchangeable Neural ODE (ExNODE) using ODE.
result ExNODE achieves permutation equivariance for set modeling.
New algorithms learn sparse set functions in non-orthogonal Fourier bases.
problem Learning sparse set functions in non-orthogonal Fourier bases.
method Novel algorithms using non-orthogonal Fourier transforms.
result At most queries for non-zero Fourier coefficients.
This work introduces a noise-adaptive conformal inference method for better prediction sets in noisy data.
problem Real-world complications like random label noise limit the effectiveness of conformal inference.
method An adaptive conformal inference method capable of handling deviations from exchangeability.
result Informative prediction sets with tight marginal coverage guarantees in noisy data.
WHInter: A Working set algorithm for High-dimensional sparse second order Interaction modelsq-bio.QM
Learning sparse linear models with two-way interactions is desirable in many application domains such as genomics. l1-regularised linear models are popular to estimate sparse models, yet standard implementations fail to address specifically the quadratic explosion of candidate two-way interactions in high dimensions, a…
Improved regret bounds for structured linear contextual bandits with Gaussian noise.
problem Optimizing bandit learning algorithms for structured contexts with Gaussian perturbations.
method Proposed simple greedy algorithms for structured linear contextual bandits with Gaussian noise.
result Unified regret analysis for structured parameters with geometric quantities as bounds.
Optimal ANN pre-training with SDA reduces handwritten Bengali digit recognition error to 2.34%
problem Optimizing ANN architecture for Bengali handwritten digit recognition
method Pre-training ANN with stacked denoising autoencoder (SDA)
result Minimum validation error of 2.34% on handwritten Bengali dataset
We present the first adaptive strategy for active learning in the setting of classification with smooth decision boundary. The problem of adaptivity (to unknown distributional parameters) has remained opened since the seminal work of Castro and Nowak (2007), which first established (active learning) rates for this sett…
Study fixed points in digital images, introducing new invariants.
problem Understanding properties of digital images through fixed points.
method Introduce new invariants and freezing/cold sets to analyze fixed point sets.
result Existence of fixed point sets restricts maps on their complements.
New method for scalable set encoding with unbiased gradient approximation.
problem Limited expressive power and large set training issues in set functions.
method Universally MBC (UMBC) class of set functions and efficient MBC training algorithm.
result Unbiased approximation of full set gradient with constant memory overhead.
Online Meta-Learningcs.LG
This work introduces online meta-learning, merging paradigms to enhance continual learning.
problem Continuous learning of new tasks with fast adaptation.
method Follow the meta leader algorithm, extending MAML to online setting with theoretical guarantees.
result Significant performance improvement over traditional online learning approaches.
This work tackles robust Bayesian optimization under data shift using φ-divergences.
problem Bayesian optimization under uncertainty and data shift.
method Distributionally robust optimization with φ-divergences.
result A computationally tractable algorithm with provable sublinear regret bounds.
New gradient coding schemes reduce decoding error in both random and adversarial straggler settings.
problem Creating efficient approximate gradient coding schemes for distributed optimization.
method Introduced novel approximate gradient codes based on expander graphs, achieving optimal decoding coefficients.
result Achieved nearly optimal error in random setting and nearly half the error in adversarial setting compared to existing codes.
New results show contrastive learning can recover shared factors in multimodal data.
problem Understanding when contrastive learning can recover shared latent factors in multimodal data.
method New identifiability results for multimodal contrastive learning, distinguishing between multi-view and multimodal settings.
result Contrastive learning can block-identify shared latent factors in multimodal data, even with dependencies.
This work analyzes batch MARL with networked agents, providing finite-sample bounds.
problem Understanding the theoretical foundation of decentralized batch MARL with networked agents.
method Developed batch MARL algorithms for two settings: collaborative and competitive networks, without a central controller.
result Quantified finite-sample errors of estimated action-value functions for both settings.
Study real line subbundles on curves, extending classical work.
problem Understanding real line subbundles in real bundles on curves.
method Application of Atiyah's techniques and work of Lange-Narasimhan.
result Describes the Galois action on the set of lines through a real point in the moduli space of such bundles.
Finding simpler models is often hard, but this work introduces a new tool to check if they might exist.
problem Finding accurate yet simple models is NP-hard and often not known to exist.
method Introducing the Rashomon ratio to gauge simplicity and check for the existence of simple models.
result The Rashomon ratio can help determine if a simpler model might exist before searching for it.
In this paper we develop methods to extend the minimal hypersurface approach to positive scalar curvature problems to all dimensions. This includes a proof of the positive mass theorem in all dimensions without a spin assumption. It also includes statements about the structure of compact manifolds of positive scalar cu…
SCHA-VAE generates novel data from limited examples using hierarchical context aggregation.
problem Generating data from a novel distribution with limited examples.
method Hierarchical context aggregation with attention-based point to set-level aggregation.
result Hierarchical approach better captures intrinsic variability in small data.
New algorithm for ML models in gradually adapting data settings.
problem Training models when data distribution reacts to the model over time.
method Stateful Performative Gradient Descent (Stateful PerfGD)
result Stateful PerfGD minimizes performative loss in gradually adapting data settings.
Asymmetric expansion preserves convexity in hyperbolic geometry.
problem Maintaining convexity in hyperbolic geometry under asymmetric expansions.
method Generalizing earlier results on radial expansion to asymmetric expansion.
result Asymmetric expansion of hyperbolic convex sets remains convex.
Support vector machine (SVM) training is an active research area since the dawn of the method. In recent years there has been increasing interest in specialized solvers for the important case of linear models. The algorithm presented by Hsieh et al., probably best known under the name of the "liblinear" implementation,…
In an earlier work joint with X. X. Chen and G. Tian, we introduced the weak Kähler-Ricci flow for various geometric motivations. In the current work, we take further consideration on setting up the weak flow. Namely, the initial class is allowed to be no longer Kähler.
In the present work, we study the decompositions of codimension-one transitions that alter the singular set the of stable maps of into the topological behaviour of the singular set and the singularities in the branch set that involves cuspidal curves and swallowtails that alter the singular set. W…
Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspectivecs.LG
New algorithm achieves small-loss bounds in online learning with improved rates.
problem Achieving strong stability in online learning algorithms.
method Introduces -separation to enforce strong stability, unifying previous approaches.
result Oracle-efficient algorithm achieves small-loss bounds with improved rates.
Paper extends Brouwer Fixed Point Theorem with amiable and almost amiable fixed sets.
problem Extending the Brouwer Fixed Point Theorem to approximate fixed sets.
method Introducing shape boundary regions in CW spaces as amiable and almost amiable fixed subsets of dpc maps.
result Variation of Jordan Curve Theorem and Fixed Cell Complex Theorem.