19 problems

BDASG's linear-convergence conjecture under the Polyak–Łojasiewicz condition
arXiv@arxiv
Let the global objective function be the sum of the agents' local objective functions, and suppose that it satisfies the Polyak–Łojasiewicz (PL) inequality, without necessarily bei…
Conjectureopenbilevel-optimization distributed-optimization stochastic-optimization
1
Böhnlein–Schaudt–Schauer conjecture on the complexity of pricing problems
arXiv@arxiv
Let the knapsack pricing problem and the set packing pricing problem be the pricing problems associated with knapsack and set packing, respectively. The latter generalizes independ…
Conjectureopenbilevel-optimization computational-complexity pricing-games
0
The conjecture on objective alignment and the effectiveness of MILP cuts
arXiv@arxiv
Consider mixed-integer bilevel linear optimization instances classified by their objective alignment, and compare cut-generation performance with and without mixed-integer linear p…
Conjectureopenbilevel-optimization mixed-integer-programming valid-inequalities
0
The conjecture that cut-generation failure is low at objective alignment -1
arXiv@arxiv
Consider mixed-integer bilevel linear optimization instances with an objective-alignment parameter, and let the cut-generation failure rate denote the proportion of attempted inter…
Conjectureopenbilevel-optimization mixed-integer-programming valid-inequalities
0
The conjecture that MILP cuts reduce cut-generation failures
arXiv@arxiv
Mixed-integer bilevel linear optimization problems may use intersection cuts (ICs), including integer disjunctive intersection cuts and integer split intersection cuts, together wi…
Conjectureopenbilevel-optimization mixed-integer-programming valid-inequalities
0
Necessity of the second bilevel complexity term in differentially private ERM
arXiv@arxiv
The setting is differentially private bilevel empirical risk minimization, where the upper-bound rates contain a principal single-level term and additional terms reflecting the bil…
Conjectureopenbilevel-optimization differential-privacy optimization
0
Sufficiency of initial gradient descent steps in qNBO
arXiv@arxiv
qNBO initialization conjecture. In practice, a few initial gradient descent steps are sufficient, although they are necessary for the theoretical analysis.
Conjectureopenbilevel-optimization quasi-newton-methods
1
ScaleBiO's conjecture on dataset diversity and benchmark performance
arXiv@arxiv
The experiments compare data-selection methods on mathematical-reasoning benchmarks using a small, higher-quality dataset. ScaleBiO selects training samples for fine-tuning a DeepS…
Conjectureopenbilevel-optimization data-selection large-language-models
0
Primal-only gradient approximation for general convexly constrained bilevel optimization
arXiv@arxiv
The bilevel setting involves a hyperobjective $F$ and an inexact gradient oracle, while the current construction requires access to the exact dual multiplier. Primal-only gradient…
Conjectureopenbilevel-optimization convex-optimization first-order-methods
0
NP-hardness conjecture for zero-regret decision-focused prediction
arXiv@arxiv
Zero-regret NP-hardness conjecture. Without this unique-optimum assumption, determining whether there is a solution with zero regret becomes NP-hard.
Conjectureopenbilevel-optimization computational-complexity decision-focused-learning
0
Conjecture on unbounded root relaxation for RGUP KKT-based formulations
arXiv@arxiv
Let the RGUP constraints be the constraints presented in Appendix. Unbounded-relaxation conjecture. The result of Lemma holds for these RGUP constraints. The observed unbounded roo…
Conjectureopenbilevel-optimization mixed-integer-optimization robust-optimization
0
Conjecture on unbounded root relaxation for EFL KKT-based formulations
arXiv@arxiv
Let the EFL constraints be the constraints stated in Appendix. Unbounded-relaxation conjecture. The result of Lemma holds for these EFL constraints. This would explain the unbounde…
Conjectureopenbilevel-optimization mixed-integer-optimization spatial-price-equilibrium
0
Kwon et al.'s conjecture on a fundamental gap between gradient-based and HVP-based methods
arXiv@arxiv
Kwon et al.'s conjecture. A fundamental gap may exist between gradient-based methods and HVP-based methods for bilevel optimization.
Conjectureopenbilevel-optimization first-order-methods nonconvex-optimization
0
Smoothness conjecture for optimal persistent-monitoring controls
arXiv@arxiv
Let … denote the stated bound on the initial uncertainty. Smoothness conjecture. The smoothness observed in the proposed solutions is a fundamental behavior for solutions of … . Th…
Conjectureopenbilevel-optimization optimal-control persistent-monitoring
0
The fundamental lower-bound conjecture for fully first-order stochastic bilevel optimization
arXiv@arxiv
Fully first-order methods for stochastic bilevel optimization use only first-order gradient oracles, whereas existing methods using second-order information of the lower-level obje…
Conjectureopenbilevel-optimization complexity-theory stochastic-optimization
1
Moudafi's conjecture on removing the proximal-method control assumption
arXiv@arxiv
Moudafi's conjecture. The restrictive assumption $\|x_{n+1}-x_n\|=o(\beta_n)$ can be removed by introducing a conditioning notion for equilibrium bifunctions. The proposed conditio…
Conjectureopenbilevel-optimization equilibrium-problems proximal-methods
0
NP-hardness conjecture for the sum-objective bilevel minimum spanning tree problem
arXiv@arxiv
Shi et al.'s conjecture. The version of BMST in which both the leader and the follower have a sum objective is NP-hard.
Conjectureopenbilevel-optimization computational-complexity minimum-spanning-trees
0
The Pseudo-Newton reasonable-solutions conjecture for bilevel optimization problems
arXiv@arxiv
For a bilevel optimization problem among the 38 problems for which the Gauss–Newton method could not be implemented because the direction matrix was singular for one or more values…
Conjectureopenbilevel-optimization numerical-optimization
0
Conjecture that interval uncertainty cannot generally be reduced to the certain bilevel problem
arXiv@arxiv
Consider bilevel optimization problems with interval uncertainty in the follower's objective coefficients. Interval-reduction conjecture. In general, the interval case cannot be re…
Conjectureopenbilevel-optimization continuous-knapsack robust-optimization
0