The classical multi-set split feasibility problem seeks a point in the intersection of finitely many closed convex domain constraints, whose image under a linear mapping also lies in the intersection of finitely many closed convex range constraints. Split feasibility generalizes important inverse problems including con…
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.
168,657 papers · 148 categories
Trend · papers per month
48 results for “feasibility problem”
New algorithm finds best feasible arm in grouped bandits.
problem Finding the best arm with all attributes above a threshold.
method Feasibility Constrained Successive Rejects (FCSR) algorithm.
result FCSR identifies the best feasible arm with optimal dependence on problem parameters.
Many engineering problems require identifying feasible domains under implicit constraints. One example is finding acceptable car body styling designs based on constraints like aesthetics and functionality. Current active-learning based methods learn feasible domains for bounded input spaces. However, we usually lack pr…
Bayesian search optimizes exploration of feasible solutions under expensive constraints.
problem Identifying feasible solutions in computationally expensive constraint spaces.
method Bayesian models with an acquisition function for efficient exploration and exploitation.
result The proposed acquisition function improves the prediction of feasibility.
To construct interpretable explanations that are consistent with the original ML model, counterfactual examples---showing how the model's output changes with small perturbations to the input---have been proposed. This paper extends the work in counterfactual explanations by addressing the challenge of feasibility of su…
Study tests feasibility of linear programs with bandit feedback.
problem Testing feasibility of unknown linear programs with bandit feedback.
method Developed a novel test based on low-regret algorithms and a nonasymptotic law of iterated logarithms.
result Proved that the test is reliable and adapts to the signal level, with mean sample costs scaling as \( \widetilde{O}(d^2/Γ^2) \).
Enhances OTA FL algorithms by defining inverse feasibility for linear models.
problem Improving security and privacy in over-the-air federated learning.
method Defines inverse feasibility as an upper bound on condition number, analyzes existing model, proposes new model.
result Proposes a new OTA FL model with enhanced characteristics.
Detecting correlated trees helps align sparse graphs.
problem Detecting correlation between trees for sparse random graphs.
method MPAlign message-passing algorithm for graph alignment.
result MPAlign succeeds in polynomial time for partial alignment.
We consider the problem of recovering a complex vector from quadratic measurements . This problem, known as quadratic feasibility, encompasses the well known phase retrieval problem and has applications in a wide range of important a…
DFFL tackles federated learning with heterogeneous objectives and constraints.
problem Federated learning with clients having different objectives and feasible regions.
method Derived heterogeneity bounds for cost-vector distances and support-function/shape-distance terms. Lifted pointwise bounds to local-versus-federated excess-risk comparison.
result Federation is beneficial when the statistical advantage of pooling exceeds a client-specific heterogeneity penalty.
In this paper we generalize the framework of the feasible descent method (FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent method (RC-FDM) framework. We show that the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, f…
SDP Feasibility Problems and sos Representation Ranks for OT-FKM Type Isoparametric Polynomialsmath.DG
The paper studies SDP feasibility and sos ranks for specific polynomials.
problem Characterizing sos representations of nonnegative polynomials.
method Explicit SDP formulation based on Clifford systems.
result Quantitative rank bounds for sos representations, with rigidity.
Paper defines conditions for feasible correlation matrices from factor structures.
problem Feasibility of option implied correlation matrices in non-FX markets.
method Quantitative and economic approaches to solve the nearest correlation matrix problem.
result Introduces methods to ensure feasible correlation matrices from factor structures.
Stochastic convex optimization problems with expectation constraints (SOECs) are encountered in statistics and machine learning, business, and engineering. In data-rich environments, the SOEC objective and constraints contain expectations defined with respect to large datasets. Therefore, efficient algorithms for solvi…
Bayesian framework proves thresholds for multi-graph alignment feasibility.
problem Determining when multi-graph alignment is statistically possible.
method Developed a Bayesian estimation framework over metric spaces.
result Identified thresholds for Gaussian and sparse Erdős-Rényi models.
Comonotonic allocations are restored under certain constraints, improving risk-sharing.
problem Feasibility constraints can distort optimal risk-sharing allocations.
method Identified componentwise convex-order solidity as a sufficient condition to restore comonotonic allocations.
result Componentwise convex-order solidity ensures comonotonic improvements under feasible constraints.
Unified framework for constrained online decision-making.
problem Sequential decisions under stage-wise feasibility constraints.
method Upper counterfactual confidence bounds and generalized eluder dimension.
result Principled foundation for constrained sequential decision-making.
Consider convex optimization problems subject to a large number of constraints. We focus on stochastic problems in which the objective takes the form of expected values and the feasible set is the intersection of a large number of convex sets. We propose a class of algorithms that perform both stochastic gradient desce…
Gradient descent is efficient for solving feasibility problems with minimal memory and queries.
problem Finding a point in a given set using a memory-constrained algorithm with a separation oracle.
method Oracle complexity lower bounds for gradient descent and other algorithms.
result Gradient descent is Pareto-optimal in the oracle complexity/memory tradeoff for feasibility problems.
We study system design problems stated as parameterized stochastic programs with a chance-constraint set. We adopt a Bayesian approach that requires the computation of a posterior predictive integral which is usually intractable. In addition, for the problem to be a well-defined convex program, we must retain the conve…
Mathematical framework for transfer learning feasibility and transfer risk.
problem Theoretical analysis of transfer learning.
method Reformulated transfer learning as an optimization problem, introduced transfer risk concept.
result Demonstrated the potential and benefits of incorporating transfer risk in transfer learning evaluation.
The study defines backdoor detection in ML and proves its infeasibility.
problem Backdoor detection in machine learning systems.
method Formal statistical definition and analysis of feasibility.
result Backdoor detection is impossible except for very small alphabet sizes.
We propose two new alternating direction methods to solve "fully" nonsmooth constrained convex problems. Our algorithms have the best known worst-case iteration-complexity guarantee under mild assumptions for both the objective residual and feasibility gap. Through theoretical analysis, we show how to update all the al…
Parking, matching, scheduling, and routing are common problems in train maintenance. In particular, train units are commonly maintained and cleaned at dedicated shunting yards. The planning problem that results from such situations is referred to as the Train Unit Shunting Problem (TUSP). This problem involves matching…
DC3 uses deep learning to solve hard-constrained optimization problems efficiently.
problem Hard constraints in optimization problems make classical solvers slow and infeasible.
method DC3 employs a differentiable procedure to enforce feasibility and unrolls corrections for inequality constraints.
result DC3 achieves near-optimal solutions while maintaining feasibility in both synthetic and real-world tasks.
Novel proof shows continuity of optimal transport feasible set mapping.
problem Continuity of feasible set mapping in optimal transport problems.
method Presented a novel and shorter proof of continuity.
result Established continuity of the feasible set mapping.
New method tackles constrained optimization in multi-fidelity Bayesian optimization.
problem Efficiently identifying feasible regions in constrained optimization problems.
method Proposes CMFBO method with novel acquisition functions.
result Demonstrates effectiveness on synthetic problems and real-world ICF and joint design problems.
Solves online 3D bin packing with deep reinforcement learning under constraints.
problem Challenges of packing items immediately without information and constraints.
method Constrained deep reinforcement learning (DRL) with feasibility predictor.
result Significantly outperforms state-of-the-art methods in online 3D bin packing.
New method improves feasibility of fitting Gaussian vectors to an ellipsoid.
problem Feasibility of fitting Gaussian vectors to an ellipsoid boundary.
method Improved concentration of Gram matrices using Bartl & Mendelson (2022) results.
result Feasibility of with high probability when .
COF algorithm minimizes cost in multi-armed bandits with known costs and reward constraints.
problem Minimizing cost while meeting a minimum reward requirement in uncertain environments.
method COF algorithm that intelligently combines samples from all arms to gauge feasibility and minimize cost.
result COF achieves instance-dependent upper bounds on cumulative cost and quality regret.
Proposes a recursive MPC scheme with probabilistic safety guarantees for uncertain dynamic systems.
problem Probabilistic safety guarantees for MPC in dynamic environments with unknown stochastic agents.
method Uses conformal prediction to derive high-confidence prediction regions and gradually relax safety constraints online.
result Ensures recursive feasibility of MPC schemes by relaxing safety constraints over time.
MI-GAN solves OPF with renewable uncertainty using model-informed layers.
problem Optimal Power Flow (OPF) under renewable uncertainty.
method Model-Informed Generative Adversarial Network (MI-GAN) framework with three layers.
result MI-GAN improves solution feasibility and optimality.
Develops a new framework for integrating satellite allocations in small portfolios.
problem Feasibility constraints in small portfolios, not return predictability, are the primary concerns.
method A four-layer feasibility framework: physical, economic, structural, and epistemic.
result Closed-form feasibility bounds on satellite size, turnover, and breadth without return forecasts.
Rank-one measurements limit feasible sets for low-rank PSD matrices.
problem Feasibility of PSD matrices under rank-one measurements.
method Characterization of feasible sets for PSD matrices given rank-one projections.
result Radius of feasible sets determines singleton solution sets for low-rank matrices.
Paper explores using hand gestures to type English letters.
problem Creating easy-to-remember, non-cumbersome gestures for typing.
method Statistical approach to handle randomness in hand movements.
result Achieved 97.33% accuracy with entire English alphabet.
A multilevel optimization method for constrained problems.
problem Regularized constrained linear inverse problems with box constraints.
method Geometric multilevel optimization with varying discretization levels.
result Preserves feasibility of updates while speeding up computations.
Quadratic memory is essential for optimal convex optimization queries.
problem Optimal query complexity for convex optimization and feasibility problems.
method Lower bounds on query complexity for convex optimization and feasibility problems.
result Center-of-mass algorithms are Pareto-optimal for both convex optimization and feasibility problems.
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexitycs.LG
Improved private learning of halfspaces with reduced sample complexity.
problem Private learning of halfspaces with reduced sample complexity.
method Iterative algorithm for solving linear feasibility problem, improving state-of-the-art results.
result Sample complexity reduced to , improving factor.
Bayesian optimization tackles constrained high-dimensional problems with penalties and trust regions.
problem Constrained optimization in high-dimensional black-box settings with expensive evaluations and complex feasibility regions.
method Penalty formulation, surrogate model, trust region strategy, Expected Improvement acquisition function.
result The proposed Trust Region method identifies high-quality feasible solutions with fewer evaluations and maintains stable performance.
There has been significant interest in the use of fully-connected graphical models and deep-structured graphical models for the purpose of structured inference. However, fully-connected and deep-structured graphical models have been largely explored independently, leaving the unification of these two concepts ripe for …
Work in Counterfactual Explanations tends to focus on the principle of "the closest possible world" that identifies small changes leading to the desired outcome. In this paper we argue that while this approach might initially seem intuitively appealing it exhibits shortcomings not addressed in the current literature. F…
Develops algorithms for multi-class Neyman-Pearson classification with cost sensitivity.
problem Asymmetric misclassification costs in multi-class classification problems.
method Establishes connection with cost-sensitive learning, proposes two algorithms, extends NP oracle properties.
result Proposes algorithms with theoretical guarantees for multi-class Neyman-Pearson classification.
New algorithm reduces sample complexity for safe reinforcement learning.
problem Safe reinforcement learning in constrained MDPs with performance and safety constraints.
method Model-based primal-dual algorithm balancing regret and bounded constraint violations.
result Proves near-optimal policies with bounded violations or zero violations in CMDPs.
A scalable method for deep metric learning using chance constraints.
problem Improving deep metric learning by addressing feasibility issues.
method Relating DML to chance constraints, reformulating as a feasibility problem, and iteratively training proxies.
result The method effectively improves deep metric learning performance across multiple benchmarks.
Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Setscs.LG
New algorithm exploits curvature of feasible sets for fast online convex optimization.
problem Online convex optimization with fast rates.
method Adapting FTL algorithm to curvature of feasible sets.
result Achieves logarithmic regret bound of in stochastic environments.
This work presents an explicit-implicit procedure to compute a model predictive control (MPC) law with guarantees on recursive feasibility and asymptotic stability. The approach combines an offline-trained fully-connected neural network with an online primal active set solver. The neural network provides a control inpu…
New algorithms optimize constrained problems faster, avoiding full set optimization.
problem Optimizing constrained problems efficiently and quickly.
method Designing accelerated first-order algorithms that avoid full set optimization.
result Proved convergence to stationary points in nonconvex settings and accelerated rates in convex settings.
New conditions ensure Dantzig-Wolfe relaxation matches rank-constrained optimization problems.
problem Rank-constrained optimization problems with linear matrix inequalities.
method Investigates Dantzig-Wolfe relaxation and develops conditions for exactness.
result Conditions for extreme point, convex hull, and objective exactness.