Algorithm ensures privacy while strictly adhering to constraints.
problem Differential privacy with linear constraints that must be strictly followed.
method Developed an algorithm that releases a nearly-optimal solution satisfying constraints with probability 1.
result Achieved nearly optimal performance while preserving privacy and strictly adhering to constraints.
This paper considers online convex optimization over a complicated constraint set, which typically consists of multiple functional constraints and a set constraint. The conventional online projection algorithm (Zinkevich, 2003) can be difficult to implement due to the potentially high computation complexity of the proj…
New algorithms reduce orthogonality constraint enforcement time in machine learning.
problem Efficiently solving orthogonality constraints in machine learning.
method Extending the landing algorithm to Stiefel manifold, incorporating stochastic and variance reduction techniques.
result All proposed methods achieve the same convergence rate as Riemannian counterparts enforcing constraints.
Optimistic algorithm reduces regret and constraint violations in online convex optimization with adversarial constraints.
problem Online convex optimization with adversarial constraints.
method Improved algorithm using accurate predictions of loss and constraint functions.
result Improved bounds on regret and cumulative constraint violations.
Algorithm finds real line mapping from points under ordinal constraints.
problem Finding a mapping from points to real line under ordinal constraints.
method Approximation algorithm for dense case in O ( n 7 ) + ( 1 / ε ) O ( 1 / ε 1 / 8 ) n O(n^7) + (1/\varepsilon)^{O(1/\varepsilon^{1/8})} n O ( n 7 ) + ( 1/ ε ) O ( 1/ ε 1/8 ) n time. result Computes a solution satisfying ( 1 − O ( ε 1 / 8 ) ) (1-O(\varepsilon^{1/8})) ( 1 − O ( ε 1/8 )) -fraction of all constraints. New algorithm reduces regret and constraint violation in online convex optimization with complex constraints.
problem Online convex optimization with multiple functional constraints and a simple constraint set.
method Instance-dependent bound using online primal-dual mirror-prox algorithm in general normed spaces.
result Achieves an O(√V*(T)) regret and O(1) constraint violation, improving over previous works.
Hybrid quantum algorithm tackles binary optimization problems with multiple constraints.
problem Efficiently solving binary optimization problems with multiple constraints using quantum algorithms.
method Combines QAOA with penalty dephasing and Zeno effect for non-Ising constraints.
result Significant improvement in solving practical aircraft loading problems.
Efficient algorithms decide algebraic constraints of causal graphs.
problem Distinguish causal graphs with latent confounders.
method Study algebraic constraints and propose efficient algorithms.
result Decide equivalence or subset of algebraic constraints.
Algorithm minimizes regret while adhering to unknown safety constraints.
problem Online learning with unknown safety constraints.
method General meta-algorithm leveraging online regression and learning oracles.
result Concrete algorithm with T \sqrt{T} T regret for linear constraints. New algorithm tackles optimization with distributed constraints.
problem Optimization problems with generalized orthogonality constraints in a decentralized setting.
method Introduced a novel algorithm that tracks gradients and Jacobians simultaneously.
result Global convergence with an iteration complexity established.
VRSGT algorithm reduces orthogonality constraints in decentralized optimization.
problem Decentralized optimization with orthogonality constraints.
method VRSGT algorithm with variance reduction and orthogonal techniques.
result VRSGT achieves convergence rate of O(1 / k) for orthogonality constraints.
A new algorithm tackles submodular bandit problems with multiple constraints.
problem Addressing diversified retrieval and online learning with budget constraints.
method Non-greedy algorithm focusing on upper-confidence bounds.
result High-probability upper bound of an approximation regret matching fast offline algorithm's ratio.
Consistent algorithms for multiclass learning with complex metrics and constraints.
problem Learning with complex performance metrics and constraints.
method General framework for designing consistent algorithms by viewing the problem as an optimization over feasible confusion matrices.
result Rates of convergence to the optimal (feasible) classifier, showing asymptotic consistency.
New metrics improve landing algorithms for orthogonality constraints.
problem Optimizing landing algorithms with orthogonality constraints.
method Proposed a family of metrics over full-rank matrices to enhance landing algorithms.
result Natural extension of β-metric improves landing performance.
Paper solves optimization problems with convex expectation constraints using a new algorithm.
problem Minimizing convex expectation functions with inequality convex expectation constraints.
method Stochastic Augmented Lagrangian-Type Algorithm (Stochastic Linearized Proximal Method of Multipliers).
result Algorithm achieves O ( K − 1 / 2 ) O(K^{-1/2}) O ( K − 1/2 ) convergence rates for objective reduction and constraint violation. New algorithm optimizes online network resource allocation with long-term constraints.
problem Optimal resource reservation in communication networks with job transfers and budget limits.
method Randomized exponentially weighted method for long-term constraints.
result Upper bound for regret and cumulative constraint violations established.
New single-loop algorithm tackles weakly convex constraints in stochastic optimization.
problem Optimization with weakly convex constraints in machine learning.
method Single-loop penalty-based stochastic algorithm using hinge-based penalty.
result Achieves state-of-the-art complexity for finding approximate KKT solutions.
Two algorithms solve nonconvex minimax problems with linear constraints, achieving complexity guarantees.
problem Nonconvex minimax problems with coupled linear constraints.
method Zeroth-order primal-dual alternating projected gradient (ZO-PDAPG) and zeroth-order regularized momentum primal-dual projected gradient (ZO-RMPDPG) algorithms.
result Iteration complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints.
Algorithm samples constrained stochastic differential equations.
problem Sampling stochastic differential equations with complex constraints.
method Pathspace Metropolis-adjusted manifold sampling.
result Demonstrated effectiveness in various constrained conditions.
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.
New algorithms optimize actions under time-varying constraints without projecting.
problem Optimizing actions under time-varying constraints without projecting.
method Projection-free algorithms using linear optimization oracle.
result Guaranteed i l d e O ( T 3 / 4 ) ilde{O}(T^{3/4}) i l d e O ( T 3/4 ) regret and O ( T 7 / 8 ) O(T^{7/8}) O ( T 7/8 ) constraints violation. This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror des…
Paper proposes a model-free algorithm for CMDPs with long-term constraints, achieving optimal regret bounds.
problem Optimizing systems with long-term constraints where transition probabilities are unknown.
method Combines concepts from constrained optimization and Q-learning to propose an algorithm.
result Achieves optimal regret bounds for reward and constraint violation.
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. Recent advances in contextual bandit optimization and reinforcement learning have garnered interest in applying these methods to real-world sequential decision making problems. Real-world applications frequently have constraints with respect to a currently deployed policy. Many of the existing constraint-aware algorith…
Study contextual bandits with stage-wise constraints, proving regret bounds and extending results.
problem Contextual bandits with stage-wise constraints in high probability and expectation settings.
method Upper-confidence bound algorithms for linear and non-linear reward/cost functions, extending to multiple constraints.
result Regret bounds for various settings, including non-linear reward/cost functions.
Develops an algorithm for bilevel optimization with coupled constraints.
problem Challenges in bilevel optimization with coupled constraints.
method Primal-dual-assisted penalty approach and a fully first-order algorithm (BLOCC).
result Established rigorous convergence theory and demonstrated effectiveness on real-world applications.
Algorithm safely learns from sub-optimal baseline policies while satisfying constraints.
problem Safe reinforcement learning with constraints when baseline policy is sub-optimal.
method Iterative policy optimization alternating between return maximization, baseline distance minimization, and constraint projection.
result Consistently outperforms baselines, achieving 10x fewer constraint violations and 40% higher reward.
New algorithm reduces regret and constraint violation in online convex optimization with predictions.
problem Online convex optimization with time-varying constraints and predictions.
method Primal-dual algorithm combining Follow-The-Regularized-Leader with adaptive steps.
result Achieves O ( T 3 − β 4 ) \mathcal O(T^{\frac{3-β}{4}}) O ( T 4 3 − β ) regret and O ( T 1 + β 2 ) \mathcal O(T^{\frac{1+β}{2}}) O ( T 2 1 + β ) constraint violation bounds. New algorithm for contextual bandits with linear constraints using regression.
problem Contextual bandits with packing and covering constraints.
method Modular Lagrangian approach via regression.
result First vanishing-regret guarantees for CBwLC (or CBwK).
Submodular functions are a broad class of set functions, which naturally arise in diverse areas. Many algorithms have been suggested for the maximization of these functions. Unfortunately, once the function deviates from submodularity, the known algorithms may perform arbitrarily poorly. Amending this issue, by obtaini…
Algorithm improves movie recommendation efficiency with fairness constraints.
problem Improving movie recommendation efficiency with fairness constraints in combinatorial semi-bandits.
method Adopted Thompson Sampling with beta priors and Bernoulli likelihoods to handle fairness constraints.
result Time-averaged regret upper bounded by $\frac{N}{2η} + O\left(\frac{\sqrt{mNT\ln T}}{T}
ight)$ , with fairness constraints satisfied.
New algorithms control loss and constraints in uncertain, changing environments.
problem Adapting to adversarial constraints in uncertain, changing environments.
method Developed algorithms for constrained MAB problems with optimal rates of regret and positive constraint violation.
result Achieved optimal rates of regret and positive constraint violation under varying degrees of adversariality.
The Bayesian learning rule is a natural-gradient variational inference method, which not only contains many existing learning algorithms as special cases but also enables the design of new algorithms. Unfortunately, when variational parameters lie in an open constraint set, the rule may not satisfy the constraint and r…
New algorithm reduces regret in CMDPs without cancellation of errors.
problem Lagrangian approaches in CMDPs struggle with cancellation of errors.
method OptAug-CMDP, based on augmented Lagrangian method.
result Regret of i l d e O ( K ) ilde{O}(\sqrt{K}) i l d e O ( K ) for both objective and constraint violation. 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.
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…
Proposes a new algorithm for learning continuous-time Bayesian network structures.
problem Lack of constraint-based algorithms for continuous-time Bayesian networks.
method Develops a constraint-based algorithm using statistical tests for conditional independence.
result The proposed algorithm is more accurate with variables having more than two values.
The constraints arising from DAG models with latent variables can be naturally represented by means of acyclic directed mixed graphs (ADMGs). Such graphs contain directed and bidirected arrows, and contain no directed cycles. DAGs with latent variables imply independence constraints in the distribution resulting from a…
VRPG algorithm optimizes convex constraints with non-asymptotic guarantees.
problem Stochastic convex optimization under convex constraints.
method Natural variance reduced proximal gradient (VRPG) algorithm.
result VRPG achieves local minimax lower bound up to constants and log factor of N N N . Paper presents a framework to automatically discover constraints from data.
problem Discovering constraints from data for structured output prediction.
method Formulates structured output prediction as ILP, mines constraints by estimating polytopes of feasible set.
result Successfully identifies feasible sets and constraints for various tasks.
The paper tackles online resource allocation with uncertain coefficients and chance constraints.
problem Online stochastic resource allocation problem with chance constraints.
method Linearization and primal-dual algorithms with heuristic corrections.
result Optimality gap and constraint violation are on the order of √n.
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
Paper tackles online DR-submodular maximization with stochastic constraints.
problem Maximizing utility while adhering to a cumulative resource constraint in an online setting.
method Proposes OLFW algorithm to solve the problem of online continuous DR-submodular maximization with linear stochastic constraints.
result Obtains sub-linear regret and constraint violation bounds.
New algorithm tackles constrained Markov decision processes with peak constraints.
problem Optimizing dynamic systems with peak constraints.
method Model-free algorithm converting PCMDP to unconstrained problem, applying Q-learning.
result Algorithm achieves ( ε , p ) (ε,p) ( ε , p ) -PAC policy under certain conditions. Study discretizes Dirac and port-Hamiltonian systems using manifolds.
problem Discretization of Dirac and port-Hamiltonian systems.
method Retraction and discretization maps on manifolds for Dirac structures, applied to port-Hamiltonian systems.
result Numerical integrators for port-Hamiltonian systems derived from discretization techniques.
New approach tackles resource constraints in bandit problems with weakly adaptive algorithms.
problem Maximizing rewards while adhering to general long-term constraints.
method Weakly adaptive primal and dual regret minimizers.
result Achieves sublinear constraints violations and competitive ratios in both stochastic and adversarial settings.
When learning policies for real-world domains, two important questions arise: (i) how to efficiently use pre-collected off-policy, non-optimal behavior data; and (ii) how to mediate among different competing objectives and constraints. We thus study the problem of batch policy learning under multiple constraints, and o…