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.
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…
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.
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.
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…
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.
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…
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 O(ρlogT) in stochastic environments. 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.
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.
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.
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…
SnareNet adds repair layers to neural networks to ensure outputs meet physical constraints.
problem Unconstrained neural network predictions violate physical or safety requirements.
method SnareNet appends a differentiable repair layer that navigates constraints to produce feasible outputs.
result SnareNet consistently improves objective quality while satisfying constraints more reliably.
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.
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.
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) \).
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.
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.
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.
The study examines higher-order modern portfolio theory with complex critical points and feasible portfolio variety.
problem Understanding the complex critical points and feasible portfolio variety in higher-order modern portfolio theory.
method Established genericity conditions for utility functions with higher-order cumulants, analyzed discriminant loci, and determined the dimension and degree of the feasible portfolio variety.
result The utility function has a constant number of complex critical points under genericity conditions, and the feasible portfolio variety has a determined dimension and degree.
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…
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…
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.
The paper introduces GAER to assess market feasibility under geopolitical and institutional constraints.
problem Feasibility of adaptive market efficiency under heterogeneous institutional and geopolitical conditions.
method Structural framework integrating adaptive market theory, institutional economics, and political economy.
result GAER as a diagnostic indicator for portfolio construction feasibility.
We consider the problem of recovering a complex vector x∈Cn from m quadratic measurements {⟨Aix,x⟩}i=1m. This problem, known as quadratic feasibility, encompasses the well known phase retrieval problem and has applications in a wide range of important a…
New algorithm reduces sample complexity for constrained MDPs.
problem Learning policies in constrained average-reward MDPs.
method Model-based algorithm for relaxed and strict feasibility settings.
result Achieves minimax-optimal bounds for constrained MDPs.
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.
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…
Paper introduces a method to generate physically feasible dynamics with physical priors.
problem Challenges in generating physically feasible dynamics under physical priors.
method Seamlessly incorporates physical priors into diffusion-based generative models.
result Efficient generation of physically realistic dynamics across various physical phenomena.
New method improves feasibility of fitting Gaussian vectors to an ellipsoid.
problem Feasibility of fitting n Gaussian vectors to an ellipsoid boundary. method Improved concentration of Gram matrices using Bartl & Mendelson (2022) results.
result Feasibility of (P) with high probability when n≤d2/C. 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.
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 d2.5⋅2log∗∣G∣, improving d2 factor. 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.
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.
In complex simulation environments, certain parameter space regions may result in non-convergent or unphysical outcomes. All parameters can therefore be labeled with a binary class describing whether or not they lead to valid results. In general, it can be very difficult to determine feasible parameter regions, especia…
New study shows limits to classifying brain activity from randomized EEG trials.
problem Classifying human brain activity from image stimuli using EEG is challenging.
method Used randomized trials on a larger dataset (20x) to avoid stimulus-time confound.
result Classification accuracy is marginally above chance and statistically significant.
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…
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.
A new model synthesizes population with fewer structural and sampling zeros.
problem Synthesizing a feasible and diverse synthetic population from limited data.
method A deep generative model with two regularizations to minimize structural zeros and preserve sampling zeros.
result The model significantly improves feasibility and diversity of synthetic populations.
Develops a framework to analyze financial structures.
problem Difficulty in systematic analysis, comparison, and verification of financial structures.
method Formalizes financial structures as structured allocation systems with explicit allocation operators.
result Specifies inputs, structural requirements, and feasibility restrictions for financial structures.
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…
Geometric theory explains substitutability in market outcomes based on production constraints.
problem Understanding substitutability in markets with structured feasible products.
method Modeling the set of feasible products as a compact Riemannian manifold to study intrinsic geometry and its effects on substitutability.
result Intrinsic geometry of the feasible set governs substitutability and market outcomes, with curvature controlling technological substitution elasticity.
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.
We investigate the feasibility of learning from a mix of both fully-labeled supervised data and contextual bandit data. We specifically consider settings in which the underlying learning signal may be different between these two data sources. Theoretically, we state and prove no-regret algorithms for learning that is r…
CEILS generates feasible counterfactual explanations by considering causal impacts.
problem Current counterfactual explanations lack feasibility and causal impact consideration.
method CEILS integrates causal reasoning into existing counterfactuals generation algorithms.
result CEILS provides feasible recommendations to achieve desired outcomes.
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…
Probabilistic vehicle trajectory prediction is essential for robust safety of autonomous driving. Current methods for long-term trajectory prediction cannot guarantee the physical feasibility of predicted distribution. Moreover, their models cannot adapt to the driving policy of the predicted target human driver. In th…
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.